Cours sur l'analyse gramaticale

Sujets

• informatique

Informations

• Publié par: Thyas
• Nombre de lectures: 47
• Langue: Français

Extrait

Grammaires
Analyse grammaticale.
Didier Remy
Octobre 2000
http://cristal.inria.fr/~remy/poly/compil/8/
http://w3.edu.polytechnique.fr/profs/informatique/Didier.Remy/compil/8/
Grammaires algebriques (context-free)
Une grammaire permet une representation nie d’un langage
(eventuellement in ni). Noam Chomsky (c.f. author of
Manufacturing Conscent) a invente la notion de grammaire
formelle.
Une grammaire algebrique (ou context free) G est un quadruplet
( ;V;S;P ) o u :
Slide 1
{ est l’alphabet des terminaux (lexemes ou tokens),
{ V estet des non-terminaux (disjoint de ),
{ S2V est l’unique axiome.
{ P est un ensemble ni de regles de production,

de la forme ! avec 2V , et 2 ( [V )
Le langage L(G) associe a la grammaire G est la fermeture
transitive du singletonfSg par la regle d’induction :
u v 2L^!2P =)u v 2LDerivations
Pour montrer qu’un mot w est dans le langage L il faut donc
exhiber une suite nie d’applications de regles de production
partant de S et aboutissant a w, appelee une derivation.
On peut representer une derivation par
P P P1 2 n
S =w !w !:::!w =w0 1 n
Slide 2
uo w =u v =u v et P = ! .k k k k k+1 k+1 k+1 k k k
On laisse P implicite lorsqu’il n’y a pas d’ambiguite, ou on ecrit :i
S = u v ! u v =u v ! u v = :::1 1 1 1 1 1 2 2 2 2 2 2
u v ! u vn n n n n n
Exemples : expressions arithmetiques
Les terminaux (lexemes) sont NUM, ID, PLUS et MINUS .
S!E E! NUM E! ID E!E PLUS E E!E MINUS E
Pour reconna^ tre l’expression 1 - 1 + x, i.e. apres analyse
lexicale, NUM MINUS NUM PLUS ID, il existe de nombreuses
derivations possibles. L’ensemble de ces derivations peut ^etre
represente par un ensemble d’arbres syntaxiques (ici deux) :Slide 3
8 88> >> E! NUM E! NUM> ><> >> E! >MINUS MINUS< <> 8: >S!E! S!E!E! NUM E! NUM<> >> > E!> PLUS > PLUS >> > >> > :: :
E! ID E! ID
Chaque arbre syntaxique represente lui m^eme un ensemble de
derivations obtenues en xant un ordre d’application des regles.
2