cours-2-4
8
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
8
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Grammaires 1Utiliser la machine tortue– En Caml ?Possible, mais :Oblige à savoir « trop » de chosesOblige à s'occuper de détails indépendants du vrai problèmeOblige à connaître Caml !– En un autre langage ?Oui, mais :Lequel ?DEF carre(l) PARREPETE 4 FOIS SEQ A l; T 90 QESFED DEUG 2 2000Grammaires 2Trouver Saussure à son pied• Problème :Si nous souhaitons définir un nouveau langage pour les graphiques tortue, nous devons répondre à quelques questions :A quelles phrases pouvons-nous associer un sens ?• REPETE 2 FOIS carre(10)• RECULE 37Quels sont les mots qui ont un sens ?• DEF• carreComment doit-on arranger les mots ?• on mots arranger doit comment les ?Qu’est-ce qu’un mot ?• euhhhhhhDEUG 2 2000Page 1Grammaires 3Langage : définition• Langage =Système de signes servant à transmettre des significationsLorsqu’il y a transmission de sentiments ou de significations à plusieurs niveaux, il est préférable de parler de langue• Langage formel =Système dans lequel il existe des règles rigides qui permettent dedonner un sens univoque aux phrasesdéfinir des procédures de transformation et de manipulation de phrasesDEUG 2 2000Grammaires 4Phrase : définition• Mot =Unité élémentaire (c’est-à-dire non décomposable) composée de caractères• Phrase =Concaténation (c’est-à-dire, mise bout à bout) de motsLa théorie ne différencie pas entre mots (au sens usuel), symboles, ponctuation, etc.Les mots peuvent eux-mêmes avoir une structure, ...
Voir
Publié par
Langue
Français
Page 1
DEUG 2
2000
1
Grammaires
Utiliser la machine tortue
– En Caml ?
Possible, mais :
Oblige à savoir « trop » de choses
Oblige à s'occuper de détails indépendants du vrai problème
Oblige à connaître Caml !
– En un autre langage ?
Oui, mais :
Lequel ?
DEF carre(l) PAR
REPETE 4 FOIS
SEQ A l; T 90 QES
FED
DEUG 2
2000
2
Grammaires
Trouver Saussure à son pied
• Problème :
Si nous souhaitons définir un nouveau langage pour les
graphiques tortue, nous devons répondre à quelques
questions :
A quelles phrases pouvons-nous associer un sens ?
• REPETE 2 FOIS carre(10)
• RECULE 37
Quels sont les mots qui ont un sens ?
• DEF
• carre
Comment doit-on arranger les mots ?
• on mots arranger doit comment les ?
Qu’est-ce qu’un mot ?
• euhhhhhh
Page 2
DEUG 2
2000
3
Grammaires
Langage : définition
• Langage =
Système de signes servant à transmettre des significations
Lorsqu’il y a transmission de sentiments ou de significations à
plusieurs niveaux, il est préférable de parler de
langue
• Langage formel =
Système dans lequel il existe des règles rigides qui
permettent de
donner un sens univoque aux phrases
définir des procédures de transformation et de
manipulation de phrases
DEUG 2
2000
4
Grammaires
Phrase : définition
• Mot =
Unité élémentaire (c’est-à-dire non décomposable)
composée de caractères
• Phrase =
Concaténation (c’est-à-dire, mise bout à bout) de mots
La théorie ne différencie pas entre mots (au sens usuel),
symboles, ponctuation, etc.
Les mots peuvent eux-mêmes avoir une structure, mais celle-ci
correspond à un autre langage (ex. écriture des nombres)
Mathématiquement, les phrases sont des structures
appartenant aux monoïdes
Page 3
DEUG 2
2000
5
Grammaires
Rôle des langages
• En mathématiques
– parler de propriétés
• toute fonction dérivable est-elle continue ?
• (
2200
f, dérivable(f)
⇒
continue(f) )
– exprimer des relations
• (U + V) ‘ = U’ + V’
• En informatique
– donner des ordres à une machine
• let q = 123;;
• SEQ A 100; T 90; C bleu QES
– exprimer des algorithmes
• function x -> x+1;;
DEUG 2
2000
6
Grammaires
Cas de
-Logo
– Doit être capable de décrire un graphique
• des figures simples
• des figures construites par assemblage
• des figures calculées (Von Koch)
– Agit sur une machine tortue
• la signification sera le tracé de graphique
– Doit être traitable par une machine
• Un utilisateur doit pouvoir écrireen
μ
-Logo (c’est-à-dire, écrire des
textes)
• Un programme doit pouvoir déterminer si un texte est en
μ
-Logo ou
non
• Un programme doit pouvoir transformer le texte en la suite d’appel
des fonctions de la machine tortue
Page 4
DEUG 2
2000
7
Grammaires
Définir un langage
• Un langage : trois constituants
–
vocabulaire =
ensemble des mots qui peuvent apparaître dans les
phrases
–
syntaxe =
ensemble des règles permettant d’assembler les mots
pour former des phrases
–
sémantique =
ensemble des règles permettant de déterminer le sens
d’une phrase
Pour les langages formels, les 3 constituants sont définis de
façon arbitraire
DEUG 2
2000
8
Grammaires
Grammaire : définition
• Grammaire =
1) mécanisme de réécriture (ou de production) qui permet
d’engendrer systématiquement les phrases d’un langage
2) ensemble des règles de réécriture qui définissent un
langage particulier
– définition due à N. Chomsky
– définition constructive :
» un langage est défini comme les objets (phrases) que
l’on peut construire
– les grammaires des langues sont plutôt descriptives : elles
recensent les règles de cohérence interne des phrases et
définissent une langue comme l’ensemble des phrases
cohérentes
Page 5
DEUG 2
2000
9
Grammaires
Exemple des propositions
AX ::= PROP
PROP ::=
APROP ou APROP |
APROP et APROP |
non APROP |
APROP
APROP ::=
p |
q |
r |
( PROP )
» les phrases suivantes sont-elles des propositions ?
• p
ou q et r
• (non (((p)))) ou r
DEUG 2
2000
10
Grammaires
Mécanisme de génération
• Terminal =
élément du vocabulaire du langage, n'apparaît qu’à droite
du symbole ::=
• Non Terminal =
élément du méta-vocabulaire qui sera réécrit, apparaît à
gauche du symbole ::=
• Productions =
ensemble des façons de réécrire un non terminal,
exprimées comme une liste d’alternatives (symbole |)
• Axiome =
non terminal qui n'apparaît jamais à droite du symbole ::=
Page 6
DEUG 2
2000
11
Grammaires
Algorithme de génération
– On représente une phrase par une liste de mots
– la liste initiale contient uniquement l’axiome
– tant que la liste contient des non terminaux
» sélectionner un non terminal
» le remplacer par une de ses productions
– le procès s’arrête lorsque la liste ne contient plus que des
terminaux, l’écriture de cette liste produit une phrase
Le procès s’arrête-t-il toujours ? Non, certains langages ont des
phrases infinies !
L’ordre de choix des non terminaux est-il important ? Non, pour
les langages que nous considérons
DEUG 2
2000
12
Grammaires
Camlisons
– Soit le module “grammaire” qui propose les définitions suivantes
type grammaire
type production = string list
est_terminal: grammaire -> string -> bool
productions: grammaire -> string -> production list
une_production: grammaire -> string -> production
– fonction de création d’une phrase à partir d’une production
let phrase = function prod ->
list_it (function g -> function d -> g^” “^d) prod “ “ ;;
– fonction technique de réécriture
let reecrit = function gram ->
function mot ->
if
est_terminal gram mot
then [mot]
else une_production gram mot;;
Page 7
DEUG 2
2000
13
Grammaires
Génération
let Chomsky =
function gram ->
function axiome ->
let rec Noam =
function prod ->
if (for_all (est_terminal gram) prod)
then prod
else Noam (List.flatten
(List.map (reecrit gram) prod))
in Noam [axiome];;
List.flatten: 'a list list -> 'a list = <fun>
List.flatten [a; b; ... ; k] == a @ b @...@ k
DEUG 2
2000
14
Grammaires
Intérêt des grammaires
• Objets mathématiques
– Propriétés démontrables
» classes de langages
• régulier, non contextuel, contextuel, etc.
» techniques de traitement
• automates, générateurs de reconnaisseurs, etc.
– Classes d’équivalences de langages
• langages égaux = langages engendrables par la même grammaire
• grammaires équivalentes = qui engendrent les mêmes langages
– Transformations
• pour adapter la définition d’un langage à des outils
Page 8
DEUG 2
2000
15
Grammaires
Intérêt des grammaires
• Moyen de description
– Manuel de référence des langages de programmation
– Description des langages de données de certaines
applications
• Précision
• Concision
• Non ambiguïté
• Outil de modélisation
– Objets complexes
– Représentation textuelle de valeurs complexes
