Théorie des langages : Exercices compilation luc brun
Télécharger PDFCompilation
Luc Brun
1 / 134Plan Introduction
Bibliographie
Analyse lexicale
Analyse Syntaxique
Analyse descendante
Analyse ascendante
2 / 134
D ́efinitionI La compilation est l’analyse automatique d’un langage (avec un
vocabulaire et une syntaxe).I Action :I Interpr ́eteurs (javascripts, python,
shell,SQL,. . .),I editeurs structurels,I controleurs statiques.I Synth`eseI CompilateursI Filtres
La compilation va au del`a du domaine (d ́ej`a tr`es large) de la g ́en ́eration
de code ex ́ecutables `a partir de langages sources. Elle pose la question
des langages compr ́ehensibles sans ambiguit ́es.
3 / 134
Structure d’un compilateurI Analyse lexicale :
v ́erifie/reconnait le vocabulaire
(identificateurs, mots cl ́es,. . .)I Analyse syntaxique :
v ́erifie/reconnait la grammaireI Analyse s ́emantique : v ́erifie le
sens du programme (e.x. lestypes) I
RI : Langage interm ́ediare
permettant de factoriser des ́etapes pour plusieurs langages.
4 / 134
BibliographieI COMPILATEURS, Principes, techniques et outils. Alfred Aho, Ravi Sethi,
Jeffrey Ullman. InterEditions.I Les compilateurs, th ́eorie, construction, g ́en ́eration. R. Wilhelm, D.
Maurer. Masson Eds.I http ://uuu.enseirb-
matmeca.fr/∼dbarthou/compilation/courscompilation.pdf
5 / 134
Analyse lexicale
Objectifs :I Transformation d’un ensemble de caract`eres en concepts (nombres,
identificateurs, mots cl ́es,. . .)I On distingue les concepts suivants :
Unit ́e lexicale : correspond `a une entit ́e (un concept) renvoy ́e par
l’analyseur lexical. Par exemple<,>,<=,>= sont tous
des op ́erateurs relationels.
Un lex`eme est une instance d’unit ́e lexicale. Par exemple le lex`eme
6.28 une instance de l’unit ́e lexicale nombre.
Un mod`ele associe des lex`emes `a leur unit ́e lexicale.
6 / 134 ́
El ́ements de th ́eorie des langages
Alphabet :I Un alphabet Σ est un ensemble fini de symboles. L’alphabet binaire
{0,1}et les codes ASCII sont des exemples d’alphabets,{A,G,C,T}est
l’alphabet des bases ADN.I Une chaˆıne, est une s ́equence finie de symboles. Le terme mot est ́egalement utilis ́e.I Un pr ́efixe desest obtenu en supprimant un nombre quelconque de caract`eres
en fin des.I Un suffixe desest obtenu en supprimant un nombre quelconque de caract`eres
en d ́ebut des.I Une sous-chaˆıne desest obtenue en supprimant un pr ́efixe et/ou un suffixe desI Un pr ́efixe, suffixe, sous chaˆınepropre desest un suffixe, pr ́efixe ou une sous
chaˆıne desnon ́egal `as.I Sous suite des: toute chaˆıne obtenue en supprimant des caract`eres des.
7 / 134 ́
El ́ements de th ́eorie des langages
Langages :I Un langage est un ensemble a priori quelconques de chaˆınes construites
sur un alphabet. L’ensemble des codes source C, des nombres binaires ou
des codes ADN sont des langages.I ∅d ́esigne le langage vide. On d ́esigne ́egalement par{}le langage
compos ́e uniquement de la chaˆıne vide.I Sixetysont deux chaˆınes, la concat ́enation dexety,xyrepr ́esente la
chaˆıne form ́ee par la s ́equence des symboles dexsuivie de celle dey. Ex :
x=anti, y=constitutionnellement, xy=anticonstitutionnellement.I Un alphabet Σ munit de la concat ́enation et de son ́el ́ement neutrea
une structure de mono ̈ıde(intuitivement un groupe sans l’inverse).I Exponentiation :s0 =,s1 =s,sn =sn−1 s
8 / 134
Op ́erations sur les langages
D ́efinitions :I Union (L∪M) :
L∪M={s|s∈Lous∈M}I Concat ́enation (LM) :
LM={st|s∈Lets∈M}
Remarque :LLest d ́enot ́eL2 ,L0 ={},L1 =L.I Fermeture de Kleene (L∗ ) :L ∗= +∞⋃ i=0L iI Fermeture positive (L+ ) :L += +∞⋃ i=1L i
9 / 134
Op ́erations sur les langages
Exemples :I SiB={0,1},B +
est l’ensemble des nombres binaires d’au moins un chiffre.I SiC={0,1,2,3,4,5,6,7,8,9},C 4
est l’ensemle des nombres de 4 chiffres.I SiK={a,...,z,A,...,Z},K(K∪C) ∗
est l’ensemble des mots commen ̧cant par une lettre puis
compos ́es d’un nombre quelconque de lettres et chiffres.
10 / 134
Expressions r ́eguli`eresI Une expression r ́eguli`ererest construite r ́ecursivement `a partir d’union
(not ́ee|), de concat ́enation, et de fermeture. Elle d ́efinie un langageL(r).
1.est une expression r ́eguli`ere qui d ́enoteL() ={},
2.a∈Σ est une expression r ́eguli`ere qui d ́enote l’ensembleL(a) ={a},
2.1 (r) est une expression r ́eguli`ere d ́enotantL(r),
2.2 (r)|(s) est une expression r ́eguli`ere d ́enotantL(r)∪L(s),
2.3 (r)(s) est une expression r ́eguli`ere d ́enotantL(r)L(s),
2.4 (r)∗ est une expression r ́eguli`ere d ́enotantL(r)∗ ,I Toute expression construite a partir de la construction ci-dessus est
r ́eguli`ere.
11 / 134Exemple Soit Σ ={a,b}I L(a|b) ={a,b},I L((a|b)(a|b)) ={aa,ab,ba,bb},I L(a∗ ) ={,a,a2 ,...},I {a,a2 ,b,b2 ,ab,ab2 ,a2 b2 ,...}⊂L((a|b)∗ ),I On ́evite des paranth`ese inutiles en utilisant les conventions suivantes :I ∗a la plus haute priorit ́e,I la concat ́enation `a la deuxi`eme plus haute priorit ́e et est associative `a gauche,I |a la plus faible priorit ́e et est associatif `a gauche.a ∗(a|b|c) ∗
de= ((a)∗ (((a)|(b))|(c))∗ )((d)(e))
12 / 134
Propri ́et ́es alg ́ebriques
AxiomeDescriptif
r|s=s|r|est commutatif
r|(s|t) = (r|s)|t|est associatif
(rs)t=r(st)la concat ́enation est associa-tive r(s|t) =rs|rt
(s|t)r=sr|tr
la concat ́enation est distribu-
tive vis `a vis de|
r=r=rest un
́el ́emement neutre
pour la concat ́enationr ∗
= (r|)∗ r∗∗ =r∗ ∗est idempotent
13 / 134
D ́efinitions r ́eguli`eres
Il peut ˆetre commode de donner des noms `a des expressions r ́eguli`eres et
de s’en reservir dans des expressions plus complexes. On utilise pour cela
des d ́efinitions r ́eguli`eres.I Soit Σ un alphabet, et un ensemble de couplesd 1→r 1d 2→r 2. .. dn →rn o`uri est une expression r ́eguli`ere etdi son nom associ ́e.I Cette d ́efinition est appell ́ee r ́eguli`ere si chaqueri repr ́esente une
expression r ́eguli`ere construite sur Σ∪{d1 ,...,di−1 }.
14 / 134
Exemple de d ́efinition r ́eguli`ereI Identificateurs de variables
lettre→a|b|c...|z|A|B...|Z
chiffre→0|1|2|3|4|5|6|7|8|9
id→lettre(lettre|chiffre)∗ I
Nombres :
pm→(+|−)
chiffre→0|1|2|3|4|5|6|7|8|9
frac→.chiffre+ exp→E(pm|)chiffre+ nb→(pm|)( chiffre+ (frac|)|frac) (exp|)
NB : 14. ou -E5 ne sont pas reconnus par cette d ́efinition.
15 / 134
Notations abr ́eg ́ees et limites des expressions
r ́eguli`eres
Notations abr ́eg ́ees :I L’expression (r|) se note ́egalementr?. Ainsiexp→E(pm|)chiffre+ ,
se note ́egalementexp→Epm?chiffre+ ,I (a|b|c) se note ́egalement [abc]. De mˆeme (a|b|...,|z) se note [a−z] et
[a−zA−Z0−9] repr ́esente (a|...,|z|A|...|Z|0...|9). Ainsi l’ensemble
des identificateurs se note : [a−zA−Z][a−zA−Z0−9]∗ .
Limites des expressions r ́eguli`eres :
Ayez bien conscience que les expressions r ́eguli`eres ne permettent de
coder qu’un nombre limit ́e de languages. En particulier, les expressions
r ́eguli`eres ne permettent pas de compter. Ainsi le langage :
L={wcw|w∈L({a,b}∗ )}
n’est pas r ́egulier.
16 / 134
Unit ́es lexicales et diagrammes de transition
Un diagramme de transition est une repr ́esentation graphique du
processus de reconnaissance d’une unit ́e lexicale. Il repr ́esente les actions
r ́ealis ́ees par l’analyseur lexical sur le tampon d’entr ́e lorsqu’il est appel ́e
par l’analyseur syntaxique.I Un diagramme de transition est constitu ́e d’ ́états :I Internesy I
Finaux :y I
Finaux avec recul de tamponyj Ces ́états d’acceptation codent les cas o`u il est
n ́ecessaire de reculer le tampon d’entr ́e.I Les arcs codent les transitions entre ́etats. Ils ont des ́etiquettes indiquant
sur qu’elle entr ́ee s’effectue chaque changement d’ ́etat. L’ ́etiquette autre,
code tout caract`ere autre que ceux indiqu ́es par les changements d’ ́etats
sur l’ ́état courrant. On suppose les diagrammes d ́eterministes (i.e. une
mˆeme ́etiquette ne peut envoyer sur deux ́états diff ́erents)
17 / 134
Diagramme de transition : ExempleI oprel→(<|>|<=|>=|==|! =)I id→lettre(lettre|chiffre)∗ .
18 / 134
Automates fini non d ́eterministes (AFN)
Un AFNest un mod`ele math ́ematique d ́efini par :I Un ensemble d’ ́etatsE,I Un ensemble de symboles d’entr ́ees ΣI Une fonction de transition Transiter, qui fait correspondre des couples
( ́etat,symbole) `a des ensembles d’ ́etatsI Un ́etate0 correspondant `a l’ ́état de d ́epartI Un ensemble d’ ́etatsFrepr ́esentant les ́états d’acceptation (ou ́etats
finaux).
Le langage d ́efini par un AFN est l’ensemble des chaˆınes menant `a un ́état d’acceptation.
19 / 134
AFN : Un premier exempleI Soit l’unit ́e lexicale (a|b)∗ abb. Celle ci est reconnue par l’AFN suivant :I associ ́e `a la table de transition :
Transiter
EtatSymbole d’entr ́eeab 0{0,1}01−2 2−3
20 / 134
AFN : Un second exempleI Soit l’unit ́e lexicaleaa∗ |bb∗ I
Notez les transitionssur l’ ́état de d ́epart et les boucle sur les ́etats
d’acceptation.
21 / 134
Construction d’un AFN `a partir d’une expres-
sion r ́eguli`ere
Construction r ́ecursive :
1. Pourconstruire l’AFN :
2. Poura∈Σ construire l’AFN :
22 / 134
Construction d’un AFN `a partir d’une expres-
sion r ́eguli`ere
Construction r ́ecursive :
3. SoientN(s) etN(t) les AFN des expressionssett. L’AFNN(s|t) est
d ́efini par :
4. SoientN(s) etN(t) les AFN des expressionssett. L’AFNN(st) est
d ́efini par :
22 / 134
Construction d’un AFN `a partir d’une expres-
sion r ́eguli`ere
Construction r ́ecursive :
4. SoitN(s) l’AFN de l’expressions. L’AFNN(s∗ ) est d ́efini par :
5. L’AFN associ ́e `a (s) estN(s) lui mˆeme.
22 / 134
Propri ́et ́es de l’AFN construit
Les propri ́et ́es suivante se montrent facilement en suivant le processus de
construction.I N(r) a au plus deux fois plus d’ ́états qu’il n’y a de symboles dansr.I N(r) a exactement un ́état de d ́epart et un ́état d’acceptation. L’ ́etat
d’acceptation n’a pas de transition sortante.I Chaque ́état deN(r) a soit une transition sortante sur un symbole de Σ,
soit au plus deux transistions sortantes sur.
23 / 134Exemple I ́
Evaluation de (a|b)∗ abb. Son arbre syntaxique associ ́e est (cf ́evaluation
d’expressions cours 1A algo) :r 11 HH Hr 9 HH Hr 7 HH Hr 5 HH Hr 4 H HH H(r 3 H Hr 1a |r2 b) *r 6a r8 br 10b 24 / 134
Exemple de construction d’AFNI Construisons les AFN,N(r1 ) etN(r2 ) :
25 / 134
Exemple de construction d’AFNI Construisons l’AFN der3 =r1 |r2 .I N(r4 ) =N(r3 ), construisons l’AFN der5 = (r1 |r2 )∗ 25 / 134
Exemple de construction d’AFNI Construisons directementr11 par 3 applications successives de la r`egle 4.
Pour obtenir l’AFN final :
25 / 134
Reconnaissance d’une expression r ́eguli`ere
par un AFN
L’algorithme calcule it ́erativement un ensemble d’ ́etatsEen utilisant les
fonctions :I Transiter(E,a) : retourne l’ensemble des ́états accessibles via les ́etatsE
par une transition ’a’.I -fermeture(E) : renvoie l’ensemble des ́états accessibles depuisEpar une
transition.
fonctionrecAFN(e0 ,F) :Bool ́een
D ́eclarationE : Ensemble d’ ́etats,c : caract`ere
d ́ebut
E←-fermeture(e0 )
c←carSuivant()
tant quec6= fdffaire
E←-fermeture(Transiter(E,c))
c←carSuivant()
fintantque
retournerE∩F6=∅fin 26 / 134
D ́eroulement de la reconnaissance d’une ex-
pression r ́eguli`ere par un AFN
Consid ́erons le lex`emes=aabb.
1. E=-fermeture(0)={0,1,2,4,7}; c=’a’
2. Transiter(E,’a’)={3,8};
-fermeture(Transiter(E,’a’)={1,2,3,4,6,7,8};c=’a’
3. Transiter(E,’a’)={3,8};
-fermeture(Transiter(E,’a’)={1,2,3,4,6,7,8};c=’b’
4. Transiter(E,’b’)={5,9};
-fermeture(Transiter(E,’a’)={1,2,4,5,6,7,9};c=’b’
5. Transiter(E,’b’)={5,10};
-fermeture(Transiter(E,’a’)={1,2,4,5,6,7,10};c=’fdf’
27 / 134
Des AFN aux Automates finis d ́eterministes(AFD) L’utilisation d’un AFN pour reconnaˆıtre un lex`eme est parfaite. En
revanche si on doit traiter des milliers ou des millions de chaˆınes il est
certain que l’on effectuera de nombreuses fois les mˆemes-fermeture et
les mˆemes transitions. Un automate fini d ́eterministe (AFD) est un
automate o`u :I Aucun ́état n’a de-transitionI Pour chaque ́etateet chaque symbolea∈Σ il existe au plus une
transition ́etiquet ́ee ’a’ sortant dee.
La reconnaissance d’un lex`eme par un AFN consiste donc simplement a
tester si il existe un chemin de l’ ́état d’entr ́e `a un ́état d’acceptation.
28 / 134
Reconnaissance d’un lex`eme par un AFD
fonctionrecAFD(e0 ,F) :Bool ́een
D ́eclaratione : ́etat,c : caract`ere
d ́ebute←e 0
c←carSuivant()
tant quec6= fdffaire
e←Transiter(e,c)
c←carSuivant()
fintantque
retournere∈Ffin 29 / 134
Transformation d’un AFN en AFD
La reconnaissance d’un lex`eme par un AFD calcule une suite d’ensembles
d’ ́etats. L’id ́ee de base est de pr ́e calculer ces ensembles d’ ́états et de les
stocker dans l’AFD avec leurs transitions (table Dtran).
fonctionrecAFD(AFN(e0 ,F)) :AFD
D ́eclarationD ́état : ensemble d’ ́etats
d ́ebut
D- ́etat←-fermeture({e0 })
tant queil existeTnon marqu ́e dans D ́etatfaire
marquer T
Pour chaqueadansΣfaire
U←-fermeture(Transiter(T,a))
siU6∈D ́etatalors
D ́etat←D ́etat∪{U}finsi Dtran[T,a]←Ufinpour fintantque
retournerAFD(Dtran,D ́etat)fin 30 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=A
Transiter
EtatSymbole d’entr ́eeab A
A={0,1,2,4,7}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(A,a))=-fermeture({3,8})={1,2,3,4,6,7,8}=B
Transiter
EtatSymbole d’entr ́eeab ABB A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(A,b))=-fermeture({5})={1,2,4,5,6,7}=C
Transiter
EtatSymbole d’entr ́eeab ABCB C
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(B,a))=-fermeture({3,8})=B
Transiter
EtatSymbole d’entr ́eeab ABCBB C
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(B,b))=-fermeture({5,9})={1,2,4,5,6,7,9}=D
Transiter
EtatSymbole d’entr ́eeab ABCBBD CD A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(C,a))=-fermeture({3,8})=B
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBD A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(C,b))=-fermeture({5})=C
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCD A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(D,a))=-fermeture({3,8})=B
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCDB A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(D,b))=
-fermeture({5,10})={1,2,4,5,6,7,10}=E
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCDBE E
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
E={1,2,4,5,6,7,10}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(E,a))=-fermeture({3,8})=B
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCDBE EB
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
E={1,2,4,5,6,7,10}
31 / 134
Exemple de transformationI -fermeture({0})={0,1,2,4,7}=AI -fermeture(Transiter(E,b))=-fermeture({5})=C
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCDBE EBC
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
E={1,2,4,5,6,7,10}
31 / 134
Exemple de transformation
Transiter
EtatSymbole d’entr ́eeab ABCBBD CBCDBE EBC
32 / 134
DiscussionI La reconnaissance d’un lex`eme par un AFD est plus rapide (une seule
transition par ́etat),I En revanche le nombre d’ ́états d’un AFD peut ˆetre exponentiel par
rapport au nombres d’ ́états de l’AFN.
AutomatePlaceTemps
AFNO(|r|)O(|r|∗|x|)AFDO(2 |r|)O(|x|) I
Diff ́erents compromis ou heuristiques (tel que l’ ́evaluation paresseuse des
transitions) sont donc utilis ́es.
33 / 134
Un outil d’analyse lexicale : LexI L’analyseur lexical Lex se combine avec l’analyseur syntaxique Yacc pour
produire des compilateurs en C.I Les cousins de Lex/Yacc pour le C++ se nomment Flex et Bisons.I L’application de Lex sur un fichier produit un fichierlex.yy.cque l’on
compile en utilisant la librairie Lex : libl.I Ci joint un exemple de Makefile :CC=gcc LEX=lex
LEXFILE=monFichier.lex
OBJ=lex.yy.o
OUTPUT=nbIdLIB=-ll $(OUTPUT) :$(OBJ)
$(CC) $(OBJ) -o $@ $(LIB)
lex.yy.o :lex.yy.c
$(CC) -c lex.yy.c
lex.yy.c :$(LEXFILE)
$(LEX) $(LEXFILE)
34 / 134
Syntaxe des expressions r ́eguli`eres en Lex
xle caract`ere ”x”
.n’importe quel caract`ere sauf\n
[xyz]soit x, soit y, soit z
[ˆbz]tous les caract`eres, sauf b et z
[a-z]n’importe quel caract`ere entre a et z
[ˆa-z]tous les caract`eres, sauf ceux compris entre a et z
r*z ́ero r ou plus, o`u r est n’importe quelle expression r ́eguli`ere
r+au moins un r
r ?au plus un r (c’est-`a-dire un r optionnel)
r{2,5}entre 2 et 5 r
r{2,}2 r ou plus
r{2}exactement 2 r
rsr suivi de s
r|sr ou s
r/sr, seulement s’il est suivi par s
ˆrr, mais seulement en d ́ebut de ligne
r$r, mais seulement en fin de ligne
35 / 134
Syntaxe des expressions r ́eguli`eres en Lex
{r}l’expansion de r
”[xyz\”foo”la chaˆıne ”[xyz”foo”
\Xsi X est un ”a”, ”b”, ”f”, ”n”, ”r”, ”t”, ou ”v”, repr ́esente
l’interpr ́etation ANSI-C de\X.
\0le caract`ere ASCII 0
\123le caract`ere dont le code ASCII est 123, en octal
\x2Ale caract`ere dont le code ASCII est 2A, en hexad ́ecimal
<<EOF>>fin de fichier
35 / 134
Structure d’un fichier Lex%{ D ́eclaration des variables C%} D ́eclaration des Unit ́es lexicales%% D ́eclarations des actions associ ́ees `a la reconnaissance d’unit ́es lexicales%% Code C suppl ́ementaire (d ́eclarations de fonctions auxili`eres)
36 / 134
Exemple de fichier Lex%{ int nb_numbers=0,nb_id=0;%} pm [+-]
chiffre [0-9]
frac \.{chiffre}+
exp E{pm}?{chiffre}+
nb {pm}?(({chiffre}+{frac}?)|{frac}){exp}?
lettre [a-zA-z]
id {lettre}({lettre}|{chiffre})*%% {nb} { nb_numbers++;printf("Nombre %s reconnu : %f\n",yytext,atof(yytext));}
{id} { nb_id++;printf("Id %s reconnu\n",yytext);}
{nb}{id} {printf("Lexical error\n");}%% int main(){ yylex();
printf("Nb Numbers: %d, \nNb Id %d\n",nb_numbers,nb_id);
return 0;} 37 / 134
Analyse syntaxiqueI L’analyseur lexical a en charge la reconnaissance des unit ́es lexicales
(nombres, mots cl ́es, identifiants),I L’analyseur syntaxique prend en charge l’agencement des unit ́es lexicales
pour former un langage.I Les deux analyseurs collaborrent via la table des symboles.
Exemple :
Si (x<0) alorsx=-x Finsi−→ SiExpralorsInstr Finsi
38 / 134
Analyse Syntaxique et grammaires
Nous allons utiliser les grammaires car :I Les grammaires permettent une sp ́ecification facile et pr ́ecise d’un
langage,I Pour les classes de grammaires usuellement utilis ́ees, il existe des outils
efficaces (Yacc, Bisons,. . .) permettant d’analyser automatiquement un
fichier source `a partir d’une grammaire.I Les grammaires aident `a sp ́ecifier proprement les langages de
programmations ce qui est utile dans toutes les ́etapes ult ́erieures.I Une sp ́ecification d’un langage par une grammaire permet de le faire ́evoluer (ajouter des fonctionnalit ́es) simplement.
39 / 134
Grammaire non contextuelle
Une grammaire non contextuelle (/hors contexte/alg ́ebrique) est
compos ́ee de productions :X→w o`uXest appell ́e un non terminal (membre gauche de la r`egle) etwest
une chaˆıne compos ́ee de terminaux et/ou de non terminaux.
Le terme non contextuel vient du fait que l’on remplaceXparwsans
r ́ef ́erence au contexte o`u il apparaˆıt.
Exemple de grammaire :
expr→expropexpr
expr→(expr)
expr→ −exprexpr→Id op→+
op→ −
op→ ∗op→/ I
expretopsont des non terminauxI id, +,-,*,/ sont des terminauxI exprrepr ́esente l’axiome : tout le
langage est d ́eriv ́e de l’axiome.
40 / 134
Notations
1. Terminaux : Les lettres minuscules du d ́ebut de l’alphabet : a,b,c. . ., les
symboles d’op ́erateurs +,-,. . ., les symboles de ponctuation
’(’,’)’,’,’,’ ;’. . ., les chiffres 0 `a 9 les chaˆınes en grasid,Sirepr ́esentant
des unit ́es lexicales.
2. Non terminaux : Les lettres majuscules du d ́ebut de l’alphabet :
A,B,C. . ., la lettreSqui repr ́esente g ́en ́eralement l’axiome, les noms en
italiquesexpr,op
3. Les lettres majuscules de la fin de l’alphabetX,Y,Zrepr ́esentent des
symboles grammaticaux (i.e. des terminaux ou non terminaux)
4. les chaˆınes minuscules de la fin de l’alphabetu,v,w,...,zrepr ́esentent
des chaˆınes de terminaux (ou phrases).
5. Les lettres greques minusculesα,β,γrepr ́esentent des chaˆınes de
symboles grammaticaux ou proto phrases (compos ́ees de terminaux et
non terminaux). Ex :A→α
41 / 134
Notations
6. La suite de productionsA→α1 ,A→α2 ,...A→αn se r ́e ́ecrit enA→α 1|α 2|...|α n. 7. Sauf indication contraire la partie gauche de la premi`ere production
indique l’axiome.I La notationE⇒−EsignifieEse d ́erive en−E.
Exemple :
E⇒−E⇒−(E)⇒−(Id)
De fa ̧con plus g ́en ́eraleαAβ⇒αγβsiA→γ.I La notion se d ́erive en 0 `an ́etapes se note∗ ⇒. On a ainsiE∗ ⇒−(Id)
mais ́egalementE∗ ⇒−(E).I +
⇒signifie de d ́erive en 1 `an ́etapes.
42 / 134
V ́erification et expressions r ́eguli`eres
Le langage engendr ́e par une grammaire est l’ensemble des phrases
d ́eriv ́ees de son axiome. On dit dans ce cas que le langage est non
contextuel.
L(G) ={w∈Σ∗ |S∗ ⇒w}I La preuve qu’une grammaire engendre un langage particulier se fait
rarement sur des grammaires compl`etes mais peut se faire (et se fait) sur
des parties de celles-ci ou des grammaires simples. On montre que∀w∈Σ ∗
tel queS∗ ⇒won aw∈L(G) et inversement, pour tout
w∈L(G) il existe une s ́equence de r ́eduction telle queS∗ ⇒w.I Toute expression r ́eguli`ere peut ˆetre cod ́ee par une grammaire non
contextuelle. Le contraire n’est ́evidement pas vrai. On restreint l’analyse
lexicale `a la reconnaissance des unit ́es lexicales.
43 / 134
Suppression des ambigu ̈ıt ́es
La grammaire suivante :
inst→siexpralorsinst
|siexpralorsinstsinoninst|autre produit une ambigu ̈ıt ́e sur la proto-phrase :siE 1
alors siE2 alorsS1 sinonS2 inst H HH HH HH HH Hsiexpr E1 alorsinst PP PP PP P
siexpralorsinstsinoninst
44 / 134
Suppression des ambigu ̈ıt ́es
La grammaire suivante :
inst→siexpralorsinst
|siexpralorsinstsinoninst|autre produit une ambigu ̈ıt ́e sur la proto-phrase :siE 1
alors siE2 alorsS1 sinonS2 inst HH HH HH HX XX XX XX XX XX XX Xsiexpr E1 Alorsinst PP PP P
siexpralorsinst
SinoninstS 2
44 / 134
Suppression des ambigu ̈ıt ́es
Solution : Affecter chaque sinon au alors sans correspondant le plus
proche. R ́e ́ecrire la grammaire pour interdire les si alors sans
correspondant dans des si alors sinon.
inst→instFermee
instNonFerme
instFermee→siexpralorsinstFermeesinoninstFermeeautre instNonFermee→siexpralorsinst
|siexpralorsinstFermeesinoninstNonFermee
On interdit les constructions du type :siE 1
alors(siE2 alorsS1 )sinonS2 qui seront interpr ́et ́ees comme :siE 1
alors(siE2 alorsS1 sinonS2 )
45 / 134
Suppression de la r ́ecursivit ́e `a gauche
R ́ecusivit ́e directe
Une grammaire r