Chapitre3 Comp2018

Chapitre IV
Analyse Syntaxique
1 Présentation Générale
2 Analyse syntaxique descendante récursive
3 Analyse syntaxique Prédictive descendante récursive
4 Analyse syntaxique prédictive non récursive
5 Récupération sur erreur
6 Analyse syntaxique ascendante par décalage réduction
7 Analyseurs LR
5 / 141
Présentation Générale
Présentation générale
Analyse syntaxique
L’analyse syntaxique consiste à vérifier que la séquence d’unités
lexicales retournées par l’analyseur lexical est générée par la
grammaire du langage.
Ceci revient à construire un arbre syntaxique dont les feuilles
concordent avec la séquence d’unités lexicales en les parcourant
de gauche à droite.
Nous distinguons :
I Analyse syntaxique descendante
I Analyse syntaxique ascendante
Unité lexicale
PSOURCE
Analyseur Analyseur
Lexical Syntaxique
Obtenir prochaine
unité lexicale
Table des
Symboles
6 / 141
Analyse syntaxique descendante

Elle s’effectue par la construction descendante d’un arbre
syntaxique en partant de la racine étiquetée par l’axiome de la
grammaire et en réalisant de manière répétitive les étapes
suivantes :
1 Étape 1 : au nœud n étiqueté par le non terminal A, choisir une
production ayant A à gauche et construire les fils de n avec les
symboles en partie droite de la production.
2 Étape 2 : déterminer le prochain nœud où un sous arbre doit être
construit.
7 / 141
Analyse syntaxique ascendante

Une analyse syntaxique ascendant (bottom-up) crée une
dérivation à partir des symboles terminaux, en remontant vers le
symbole initial.
I Principe : construire un arbre de dérivation du bas (les feuilles, i.e.
les unités lexicales) vers le haut (la racine, i.e. l’axiome de départ).
8 / 141
Grammaire
Une grammaire est la donnée de G = (VT , VN , S, P) où
I VT est un ensemble non vide de symboles terminaux (alphabet
terminal)
I VN est un ensemble de symboles non terminaux, avec
VT ∩ VN = ∅
I S est un symbole initial ∈ VN appelée axiome
I P est un ensemble de règles de production (règles de réécriture)
9 / 141
Analyse syntaxique descendante récursive
Exemple
Le langage est formé par un ensemble de types générés par la
grammaire non contextuelle suivante :
I Type → array[Type simple]of Type
|Type simple
|ˆType
I Type simple → integer
|char
|nb 2points nb
Les étapes de construction descendante de l’arbre syntaxique
pour le mot : array[nb 2points nb] of integer sont les
suivantes :
10 / 141
Exemple (suite)
a. Type
11 / 141
Exemple (suite)
a. Type
b. Type
12 / 141
Exemple (suite)
a. Type
b. Type

9

array
13 / 141
Exemple (suite)
a. Type
b. Type

9
9

[ Typesimple ]

array
14 / 141
Exemple (suite)
a. Type
b. Type

?
9
9

[ Typesimple ]

array of
15 / 141
Exemple (suite)
a. Type
b. Type

?
HH
9
9
j
[ Typesimple ]

array of Type
16 / 141
Exemple (suite)
a. Type
b. Type

?
HH P
j PPP
9
9
q
[ Typesimple ]

array of Type
17 / 141
Exemple (suite)
a. Type
b. Type

?
HH P X X
j PPX
9
9
q XX
P z
[ Typesimple ]

array of Type
18 / 141
Exemple (suite)
a. Type
b. Type

H PPXXX

9
9
? H
j PP
q XX
z
[ Typesimple ]

array of Type
c. Type XXX
HPjPP
9
) ? H q XXX
P z
array [ Typesimple ] of Type
19 / 141
Exemple (suite)
a. Type
b. Type

?
HH P X X
j PPX
9
9
q XX
P z
[ Typesimple ]

array of Type
c. Type
HPPXXX
)
9 ? H
j PP
q XXX
z

9
nb
20 / 141
Exemple (suite)
a. Type
b. Type

H PPXXX

9
9
? H
j q XX
PP z
[ Typesimple ]

array of Type
c. Type

HPPXXX
)
9 ? H
j PP
q XXX
z

?

9
nb 2points
21 / 141
Exemple (suite)
a. Type
b. Type

H PPXXX

9
9
? H
j q XX
PP z
[ Typesimple ]

array of Type
c. Type

HPPXXX
)
9 ? H
j PP
q XXX
z
X
? XXXz

9 X
nb 2points nb
22 / 141
Exemple (suite)
d. Type

HP XXX
9
) ? jPP
H q XXX
P z
?XXXX

9 z
X
nb 2points nb
23 / 141
Exemple (suite)
d. Type

HP XXX
9
) ? jPP
H q XXX
P z
?XXXX

9 z
X ?
nb 2points nb Typesimple
24 / 141
Exemple (suite)
d. Type

HPPXXX
9
)
? H q XXX
j PP z
? XXXX
X
z ?
9
e.
Type
HPPXXX
9
) ? H
j PP
q XXX
z
?XXXXX

9 z ?
25 / 141
Exemple (suite)
d. Type

HPPXXX
9
)
? H q XXX
j PP z
?XXXXX

9 z ?
e. Type

HP XX
jPP X
)
9
? H q XX
P
[ Typesimple ]
z
X
array of Type
X
? XXXz

9 X ?
?
integer
26 / 141
Description
C’est une méthode d’analyse dans laquelle on exécute des
procédures récursives.
Une procédure est associée à chaque non terminal.
27 / 141
Exemple
Le langage est formé par un ensemble de types générés par la
grammaire non contextuelle suivante :
I Type → array[Type simple]of Type
|Type simple
|ˆType
I Type simple → integer
|char
|nb 2points nb
Les procédures associées à chaque non terminal sont les
suivantes :
1 Procédure Type
2 Procédure Type simple
28 / 141
Procédure accepter(symbole)
1 Procédure accepter( T )
2 Début
3 Si Symbole = T Alors
4 symbole←symbole suivant()
5 Sinon
6 erreur()
7 FinSi
8 Fin
29 / 141
2 Début
5
Symbole
Sinon suivant est une fonction qui retourne le nouveau
symbole trouvé par l’analyseur lexical et l’enregistre dans
6 erreur()
une variable globale symbole
7 FinSi
8 Fin
30 / 141
2 Début
5 Sinon
6 erreur()
7 FinSi
8 Fin
31 / 141

Procédure Type()
1 Procédure Type( )
2 Début
3 Si Symbole = array Alors
4 accepter(array); accepter([);
5 Type simple(); accepter(]);
6 accepter(of); Type();
7 Sinon
8 Si symbole ∈ {integer, char, nb} Alors
9 Type simple();
10 Sinon
32 / 141
Suite-Procédure Type()
11 Si symbole =ˆ Alors
12 accepter(ˆ ); Type();
13 Sinon
14 erreur()
15 FinSi
16 FinSi
17 FinSi
18 Fin
33 / 141
Procédure Type simple()
1 Procédure Type simple( )

2 Début
3 Si symbole = integer Alors
4 accepter(integer);
5 Sinon
6 Si symbole = char Alors
7 accepter(char);
8 Sinon
9 Si symbole = nb Alors
10 accepter(nb); accepter(2points);
11 accepter(nb);
34 / 141
Suite- Procédure Type simple()
12 Sinon
13 erreur()
14 FinSi
15 FinSi
16 FinSi
17 Fin
35 / 141
Analyse syntaxique Prédictive descendante récursive
Analyse syntaxique Prédictive descendante récursive
Description
C’est une méthode d’analyse syntaxique par descente récursive
où un symbole de prévision permet de décider d’une manière
unique quelle règle peut être appliquée.
La grammaire doit être non récursive à gauche et non ambiguë.
Pour se faire, il faut éliminer la récursivité à gauche puis enlever
l’ambigüité.
Ensuite, on associe une procédure à chaque non terminal.
Remarque
Le pseudo-code précédent est associé à un analyseur syntaxique
prédictif récursif car la grammaire qui génère les types est non
ambiguë et non récursive à gauche
36 / 141
Analyse syntaxique Prédictive descendante récursive Elimination de la récursivité à gauche
Elimination de la récursivité à gauche
Grammaire récursive à gauche

Une grammaire est dite récursive à gauche si elle admet une
règle de la forme : A → Aα
Transformation de cette grammaire en une non récursive à

gauche
Une grammaire récursive à gauche avec les règles de production
I A → Aα1 |Aα2 | . . . |Aαn |β1 |β2 | . . . |βm
Est transformée en une grammaire non récursive à gauche ayant
les règles de production :
I A → β1 A0 |β2 A0 | . . . |βm A0
I A0 → α1 A0 |α2 A0 | . . . |αn A0 |ε
37 / 141
Analyse syntaxique Prédictive descendante récursive Elimination de la récursivité à gauche
Elimination de la récursivité à gauche
Exemple
La grammaire suivante est récursive à gauche
I Exp → Exp op Exp|(Exp)|id|nb
Elle est transformée en une grammaire non récursive à gauche
avec les règles suivantes :
I Exp → (Exp) E0 |id E0 |nb E0
I E0 → op Exp E0 |ε
38 / 141
Analyse syntaxique Prédictive descendante récursive Elimination de l’ambiguı̈té
Elimination de l’ambiguı̈té
Grammaire ambiguë
Admet des règles de la forme : A → αβ1 |αβ2
Transformation d’une grammaire ambiguë en une non ambiguë

Une grammaire ambiguë avec les règles de production :
I A → αβ1 |αβ2 | . . . |αβm |α1 |α2 | . . . |αn
Est transformée en une grammaire non ambiguë :
I A → αA0 |α1 |α2 | . . . |αn
I A0 → β1 |β2 | . . . |βm
39 / 141
Analyse syntaxique Prédictive descendante récursive Elimination de l’ambiguı̈té
Elimination de l’ambiguı̈té
Exemple
La grammaire suivante est ambiguë
I I → If (Expb) Then I|If (Expb) Then I else I
Elle est transformée en une grammaire non ambiguë :
I I → If (Expb) Then S
I S → ε|else I
40 / 141
Analyse syntaxique Prédictive descendante récursive Application
Application
Le langage, décrit par la grammaire suivante, est formé par une

séquence non vide d’instructions d’affectation :
I L I → I|I L I
I I → id := Exp;
I Exp → id|nb|(Exp)|Exp op Exp
1 En éliminant la récursivité à gauche, on obtient :
F L I → I|I L I
F I → id := Exp;
F Exp → id E 0 |nb E 0 |(Exp) E 0
F E 0 → op Exp E 0 |ε
2 En éliminant l’ambiguı̈té, on obtient :
F LI→IS
F S → ε|L I
F I → id := Exp;
F Exp → id E 0 |nb E 0 |(Exp) E 0
F E 0 → op Exp E 0 |ε
41 / 141
Un pseudo-code d’un AS prédictif et récursif associé
LI→IS
1 Procédure accepter( T ) S → ε|L I
2 Début I → id := Exp;
3 Si Symbole = T Alors Exp → id E0 |nb E0 |(Exp) E0
4 symbole←symbole suivant() E0 → op Exp E0 |ε
5 Sinon
6 erreur()
7 FinSi
8 Fin
1 Procédure L I( )
2 Début
3 I(); S();
4 Fin
42 / 141
1 Procédure S( )
2 Début
3 Si Symbole = id Alors
4 L I();
5 FinSi
6 Fin
43 / 141
1 Procédure I( )
2 Début
4 accepter(id); accepter(:=);
5 Exp(); accepter(;);
6 Sinon
7 erreur();
8 FinSi
9 Fin
44 / 141
1 Procédure Exp( )
2 Début
4 accepter(id); E’();
5 Sinon
6 Si Symbole = nb Alors
7 accepter(nb); E’();
8 Sinon
9 Si Symbole = ( Alors
10 accepter((); Exp();accepter()); E’();
11 Sinon
12 erreur();
13 FinSi
14 FinSi
15 FinSi
16 Fin
45 / 141
1 Procédure E’( )
2 Début
3 Si Symbole = op Alors
4 accepter(op); Exp();E’();
5 FinSi
6 Fin
46 / 141
Analyse syntaxique prédictive non récursive
Description
C’est une méthode d’analyse où on remplace l’appel de
procédures récursives par la manipulation d’une pile
La grammaire doit être non récursive à gauche et non ambiguë.
Initialement la pile contient le symbole fond de pile $ et au
sommet l’axiome de la grammaire, le tampon d’entrée contient le
mot à analyser suivi du symbole $, la tête de lecture/écriture
pointe sur le premier symbole
A la fin de l’analyse, la pile contient le symbole $ et la tête de L/E
pointe sur le symbole $ de fin de la chaı̂ne
L’évolution de l’analyse s’effectue en consultant une table
d’analyse
47 / 141
Exemple
Nous illustrons l’approche à travers l’exemple suivant de
grammaire :
I S → id := E;
I E → E + E|EE|E ∗ E|E/E|(E)|id|nb
Après l’élimination de la récursivité à gauche et de l’ambiguı̈té,
nous obtenons :
I S → id := E;
I E → (E) E0 |id E0 |nb E0
I E0 → + E E0 | E E0 | ∗ E E0 |/E E0 |ε
48 / 141
Exemple - Suite
Id := id op nb ; $ Tampon
Configuration
initiale S
$ Tête de L/E
Pile
Id := id op nb ; $ Tampon
Configuration
finale
$ Tête de L/E
Pile
49 / 141
Table d’analyse M
Elle spécifie
I pour chaque non terminal et
I pour chaque terminal ou $ (cas de la fin de la chaı̂ne)
F une règle de production pouvant éventuellement être appliquée
50 / 141
Exemple - Table d’analyse M
S → id:= E;
E → (E) E’ | id E’ | nb E’
E’ → + E E’ | – E E’ | * E E’ | /E E’ |ε
Non Symbole d’entrée

terminal
id nb + - * / ( ) := $
S S → id:=
E;
E E → id E→ E→
E’ nb E’ (E) E’
E’ E’ → E’ → E’ → E’ →
+E - E E’ * E E’ / E E’
E’
51 / 141
Algorithme d’analyse syntaxique prédictive non

récursive
1 Début
2 Positionner le pointeur (ps) sur le premier
3 symbole de ω$;
4 Répéter
5 Soit X le symbole en sommet de pile et a
6 le symbole en cours d’analyse (repéré par
7 ps) :
8 Si X est un terminal ou $ Alors
9 Si X = a Alors
10 enlever X de la pile et avancer ps
11 Sinon
12 erreur()
13 FinSi
52 / 141
Algorithme d’analyse syntaxique prédictive non

récursive
14 Sinon
15 consulter M [X,a]
16 Si M[X,a] = X → Y1 Y2 . . . Yk = α Alors
17 dépiler X et empiler l’image miroir de α
18 c-a- d empiler Yk Yk−1 . . . Y1 et émettre en
19 sortie la règle X → Y1 Y2 . . . Yk
20 Sinon
21 erreur ()
22 FinSi
23 FinSi
24 Jusqu’à X = $
25 Fin
53 / 141
Application - Algorithme
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E E → id E → nb E→
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
54 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
S
$
55 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
S
$
56 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
id
:=
E
S ;
$ $
57 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
id
:= :=
E E
S ; ;
$ $ $
58 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
id
:= :=
E E E
S ; ; ;
$ $ $ $
59 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id + nb ; $
id
:= := id
E E E E’
S ; ; ; ;
$ $ $ $ $
60 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id
:= := id
E E E E’ E’
S ; ; ; ; ;
$ $ $ $ $ $
61 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id +
:= := id E
E E E E’ E’ E’
S ; ; ; ; ; ;
$ $ $ $ $ $ $
62 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id +
:= := id E E
E E E E’ E’ E’ E’
S ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $
63 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id + nb
:= := id E E E’
E E E E’ E’ E’ E’ E’
S ; ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $ $
64 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id + nb
:= := id E E E’ E’
E E E E’ E’ E’ E’ E’ E’
S ; ; ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $ $ $
65 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id + nb
:= := id E E E’ E’
E E E E’ E’ E’ E’ E’ E’ E’
S ; ; ; ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $ $ $ $
66 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id + nb
:= := id E E E’ E’
E E E E’ E’ E’ E’ E’ E’ E’
S ; ; ; ; ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $ $ $ $ $
67 / 141
Symbole d’entrée
NT id nb + - * / ( ) := ; $
S S→
id:= E;
E’ E’ (E) E’
E’ E’ → E’ → - E’ → * E’ → / E’
+ E E’ E E’ E E’ E E’ →ε
id := id ++ nb ; $
id + nb
:= := id E E E’ E’
E E E E’ E’ E’ E’ E’ E’ E’
S ; ; ; ; ; ; ; ; ; ; ;
$ $ $ $ $ $ $ $ $ $ $ $ $
68 / 141
Pile Entrée Message
$S Id := id + nb ; $
$ ; E := id Id := id + nb ; $ S → id := E ; L’algorithme se
$ ; E := := id + nb ; $ contente d’informer
l’utilisateur par la
$;E id + nb ; $
règle appliquée
$ ; E’ id id + nb ; $ E → id E’ Ou bien par l’erreur
$ ; E’ + nb ; $ syntaxique détectée
Ces erreurs seront
$ ; E’ E + + nb ; $ E’ → + E E’ vues plutard
$ ; E’ E nb ; $
$ ; E’ E’ nb nb ; $ E → nb E’
$ ; E’ E’ ;$
$ ; E’ ;$ E’ → ε
$; ;$ E’ → ε
$ $
69 / 141
Calcul des premiers et suivants
La construction de la table d’analyse est facilitée par deux

fonctions associées à une grammaire G : Premier et Suivant
Premier
Pour toute chaı̂ne composée de symboles terminaux et
non-terminaux, on cherche PREMIER(α) : l’ensemble de tous les
terminaux qui peuvent commencer une chaı̂ne qui se dérive de α.
On cherche alors tous les terminaux a tel qu’il existe une
∗
dérivation α ⇒ aβ (β étant une chaı̂ne quelconque composée de
symboles terminaux et non-terminaux).
Suivant
Pour tout non-terminal A, on cherche SUIVANT(A) : l’ensemble de
tous les symboles terminaux a qui peuvent apparaı̂tre
immédiatement à droite de A dans une dérivation : S→ αAaβ
70 / 141
Calcul du PREMIER(X) pour tout symbole X de la grammaire

Appliquer les règles suivantes jusqu’à ce qu’aucun terminal ni ε ne
puisse être ajouté aux ensembles PREMIER :
1 Si X est un terminal, PREMIER(X) est {X}.
2 Si X → ε est une production, ajouter ε à PREMIER(X).
3 Si X est un non-terminal et X → Y1 Y2 . . . Yk une production, mettre a
dans PREMIER(X) s’il existe i tel que a est dans PREMIER(Yi ) et que ε
est dans tous les PREMIER(Y1 ), . . ., PREMIER(Yi−1 ) c.a.d
∗
Y1 ,. . .,Yi−1 ⇒ ε. Si Y1 ne dérive pas en ε, on n’ajoute rien de plus à
∗
PREMIER(X), mais si Y1 ⇒ ε, on ajoute PREMIER(Y2 ), etc.
71 / 141
Exemple : calcul des premiers

E →TE’ PREMIER(E) = PREMIER(T) =
PREMIER(F) = {(, id}
E’ → +TE’ |ε
PREMIER(E’) = {+, ε }
T → FT’
PREMIER(T’) = {*, ε }
T’ → *FT’ |ε
F → id | (E)
72 / 141
Calcul du SUIVANT(X) pour tout symbole X de la grammaire

Appliquer les règles suivantes jusqu’aucun terminal ne puisse être
ajouté aux ensembles SUIVANT
1 Mettre $ dans SUIVANT(S), où S est l’axiome et $ est le marqueur droit
indiquant la fin du texte source
2 S’il y a une production A→ αBβ, ajouter à SUIVANT(B) PREMIER(β)
sauf ε.
3 S’il existe une production A→ αB ou une production A→ αBβ telle que
∗
ε ∈PREMIER(β) (c.a.d β ⇒ ε), ajouter SUIVANT(A) à SUIVANT(B)
73 / 141
Exemple : calcul des suivants

E →TE’ SUIVANT(E) = SUIVANT(E’) = {), $ }
E’ → +TE’ |ε SUIVANT(T) = SUIVANT(T’) = { +, ), $ }
T → FT’ SUIVANT(F) = {+, *, ), $ }
T’ → *FT’ |ε
F → id | (E)
74 / 141
Algorithme de construction d’une table d’analyse

prédictive
Donnée. Une grammaire G

Résultat. Une table d’analyse M pour G
Méthode
1 Pour chaque production A→ α de G, procéder aux étapes 2 et 3.
2 Pour chaque terminal a∈PREMIER(α ), ajouter A→ α à M[A, a].
3 Si ε ∈ PREMIER(α ), ajouter A→ α à M[A, b] pour chaque b dans
SUIVANT(A). Si ε ∈PREMIER(α) et $ est dans SUIVANT(A),
ajouter A → α à M[A, $]
4 Faire de chaque entrée non définie de M une erreur.
75 / 141
Exemple d’une table d’analyse prédictive
Symbole d’entrée
Non id + * ( ) $
terminal
E E→TE’ E→TE’
E’ E’ →+TE’ E’→ε E’→ε
T T→FT’ T→FT’
T’ T’ →ε T’ →*FT’ T’ →ε T’ →ε
F F →id F → (E)
76 / 141
Exemple : Analyse du mot id+id*id

Symbole d’entrée
Non id + * ( ) $
terminal
E E→TE’ E→TE’
E’ E’ →+TE’ E’→ε E’→ε
T T→FT’ T→FT’
T’ T’ →ε T’ →*FT’ T’ →ε T’ →ε
F F →id F → (E)
PILE ENTREE SORTIE
$E Id+id*id$
$E’T Id+id*id$ E→TE’
$E’T’F Id+id*id$ T→FT’
$E’T’id Id+id*id$ F→id
$E’T’ +id*id$
$E’ +id*id$ T’ →ε
Cours Techniques de Compilation
$E’T+ +id*id$
2011-2012 E’ → +TE’
77 / 141
$E’T Id*id$
$E’T’F id*id$ T→FT’
$E’T’id id*id$ F→id
$E’T’ *id$
$E’T’F* *id$ T’→*FT’
$E’T’F id$
$E’T’id id$ F → id
$E’T’ $
$E’ $ T’ →ε
$ $ E’ → ε
78 / 141
L’analyse du mot id + id * id se termine avec succès
79 / 141
Grammaires LL(1)
Description
Une grammaire dont la table d’analyse n’a aucune entrée définie
de façon multiple est appelée LL(1).
Le premier L signifie
I parcours de l’entrée de gauche à droite (Left to right Scanning).
Le deuxième L signifie
I dérivation gauche (Left most derivation)
le 1 signifie qu’on utilise un seul symbole de prévision.
80 / 141
Grammaires LL(1)
Exemple
S→ iEtSS’ | a
S’ → eS |ε
E→b
Symbole d’entrée
Non T a b e i t $
S S→a S → iEtSS’
S’ S’ →ε S’ →ε
S’ →eS
E E→b
81 / 141
Récupération sur erreur
Quand on distingue une errer ?

Une erreur provient dans une analyse syntaxique prédictive non
récursive lorsque :
1 nous avons un symbole non terminal A en sommet de pile et un
symbole a en entrée et M[A, a] = ∅
2 le symbole terminal sommet est différent du symbole en entrée

Une erreur peut être récupérée :
1 en mode panique : l’analyseur saute les symboles en entrée
jusqu’à ce qu’apparaisse une unité lexicale appartenant à un
ensemble sélectionné d’unités lexicales de synchronisation
2 au niveau du syntagme : l’analyseur exécute des routines
d’erreurs qui remplacent, insèrent ou suppriment des symboles
d’entrée et émettre des messages d’erreur.
82 / 141
1 Nous avons un symbole non terminal A en sommet de pile et un

symbole a en entrée et M[A, a] = ∅ :
1 On est au début de l’analyse alors sauter jusqu’à premier(A) dans
l’espoir de continuer avec A
2 On n’est pas au début de l’analyse alors sauter jusqu’à suivant(A)
et dépiler A dans l’espoir de continuer avec les suivants de A
) * id + id $ ) * id + id $ ) * id + id $
Sauter jusqu’à
Premier(E)
Sauter jusqu’à
suivant(A) et
dépiler A
T M[A, a] = φ ⇒
E E E’ Sauter jusqu’à
premier(A)
$ $ $
83 / 141
1 Nous avons un symbole non terminal A en sommet de pile et un

symbole a en entrée et M[A, a] = ∅ :
1 On est au début de l’analyse alors sauter jusqu’à premier(A) dans
l’espoir de continuer avec A
2 On n’est pas au début de l’analyse alors sauter jusqu’à suivant(A)
et dépiler A dans l’espoir Symbole
de continuer
d’entrée avec les suivants de A
Non id + * ( ) $
terminal
E E→TE’ E→TE’ Sync Sync
E’ E’ →+TE’ E’→ε E’→ε
T T→FT’ Sync T→FT’ Sync Sync
T’ T’ →ε T’ →*FT’ T’ →ε T’ →ε
F F →id Sync Sync F → (E) Sync Sync
) id * + id $ ) id * + id $ ) id * + id $
Sauter jusqu’à
F suivant(F) et
+ dépiler F +
T T T
E’ E’ E’
… … …
$ $ $
84 / 141
2 Nous avons un symbole terminal a en sommet de pile et un

symbole b en entrée et a 6= b
I On dépile le sommet a et on informe l’utilisateur par a manquant
id id + nb $ id id + nb $ id id + nb $
Dépiler ‘:=‘
:=
id id …
… … $
$ $
85 / 141
Analyse du mot )id*+id

PILE ENTREE SORTIE
$E )Id *+ id$ Erreur, sauter ‘)’ --- ‘)’mal inséré
$E Id *+id $ Sauter jusqu’à id qui est dans premier(E)
$E’T Id *+id $ T→TE’
$E’T’F Id *+id $ F→FT’
$E’T’id Id *+id $ F→id
$E’T’ *+id $
$E’T’F* *+id $ T’ → *FT’
$E’T’F +id $ Erreur, M[F,+]=sync
$E’T’ +id $ Dépiler F ----- ‘ F’ mal formé
$E’ +id$ T’ → ε
$E’T+ + id$ E’ → +TE’
$E’T id$
$E’T’F id$ T → FT’
$E’T’id id$ F → id
$E’T’ $
$E’ $ T’ → ε
$ $ E’ → ε
86 / 141

Analyse du mot )id*+id
Symbole d’entrée
Non id + * ( ) $
terminal
E E→TE’ E→TE’ Sync Sync
E’ E’ →+TE’ E’→ε E’→ε
T T→FT’ Sync T→FT’ Sync Sync
T’ T’ →ε T’ →*FT’ T’ →ε T’ →ε
F F →id Sync Sync F → (E) Sync Sync
Cas général de traitement des erreurs On se synchronise avec les

suivants des non terminaux en
M[A, a] = φ ⇒ Sauter a
replissant les cases [A, suivant(A)]
par Sync si la case est vide
M[A, a] = Sync ⇒ Dépiler A si au milieu d’analyse
Sauter si début d’analyse
87 / 141
Analyse syntaxique ascendante par décalage réduction
AS ascendante par décalage réduction
Description
L’analyse par décalage-réduction a pour but de construire un
arbre d’analyse pour une chaı̂ne source en commençant par les
feuilles et en remontant vers la racine.
C’est un processus de réduction d’une chaı̂ne ω vers l’axiome de
la grammaire.
À chaque étape de réduction, une sous-chaı̂ne particulière
correspondant à la partie droite d’une production est remplacée
par le symbole de la partie gauche de cette production.
Si la sous-chaı̂ne est choisie correctement à chaque étape, alors
une dérivation droite est ainsi élaborée en sens inverse.
88 / 141
Analyse syntaxique ascendante par décalage

réduction
Exemple
Considérons la grammaire avec les règles de production suivantes :
S → aABe
A → Abc | b
B→d
La phrase abbcde peut être réduite vers S par les étapes suivantes :
1 abbcde abbcde
2 aAbcde aAbcde
3 aAde aAde
4 aABe aABe
5 S S
89 / 141

réduction
Exemple-Suite
1 abbcde abbcde
2 aAbcde aAbcde
3 aAde aAde
4 aABe aABe
5 S S
Ces réductions élaborent en sens inverse la dérivation droite suivante :
S⇒ aABe ⇒ aAde ⇒ aAbcde ⇒ abbcde

d d d d
90 / 141

réduction
Manche
Informellement, un manche d’une chaı̂ne est une sous-chaı̂ne qui
correspond à la partie droite d’une production et dont la réduction
vers le non terminal de la partie gauche de cette production
représente une étape le long de la dérivation droite inverse.
Formellement, un manche d’une proto-phrase droite γ est une
production A → β et une position dans γ où la chaı̂ne β peut être
trouvée et remplacée par A pour produire la proto-phrase droite
précédente dans une dérivation droite de γ. Autrement :
∗
I Si S ⇒ α A ω ⇒ αβω
d d
I Alors, A → β dans la position qui suit α est un manche de αβω
I On dit aussi que β est un manche pour αβω
91 / 141

réduction
Exemple-Manche
Considérons la grammaire suivante :
I E → E + E| E * E|(E)
I E → id
Une dérivation droite est :
I E⇒E +E
d
I ⇒E+E ∗E
d
I ⇒ E + E * id3
d
I ⇒ E + id2 * id3
d
I ⇒ id1 + id2 * id3
d
Id1 est un manche de la proto-phrase droite id1+id2*id3 car id est
la partie droite de la production E→ id et le remplacement de id1
par E produit la proto-phrase droite précédente E + id2 * id3. 92 / 141

réduction
Exemple-Suite
La séquence de réductions réduit id1 + id2 * id3 vers l’axiome E :
Proto-phrase droite Manche Production de réduction
id1 + id2 * id3 Id1 E→id
E + id2 * id3 id2 E→id
E + E * id3 id3 E→id
E+E*E E*E E→E*E
E+E E+E E→ E+ E
93 / 141

réduction
Implantation à l’aide d’une pile de l’analyse par

décalage-réduction
Nous utilisons une pile pour conserver les symboles
grammaticaux et un tampon d’entrée qui contient la chaı̂ne β à
analyser.
Le symbole $ est utilisé pour marquer le fond de la pile et
l’extrémité droite du tampon d’entrée.
Tampon
Id + id * id $
Configuration
initiale
Tête de L/E
$
Pile
Tampon
Id + id * id $
Configuration
finale
S
Tête de L/E 94 / 141
$

réduction
Les opérations de base de l’analyseur

(1) décaler, (2) réduire, (3) accepter et (4) erreur.
1 Dans une action décaler, le prochain symbole du tampon d’entrée
est enlevé du tampon et placé en sommet de la pile.
2 Dans une action réduire, l’analyseur sait que l’extrémité de la
partie droite du manche est dans la pile et décide par quel
non-terminal remplacer le manche
3 Dans une action accepter, l’analyseur s’arrête et annonce la
réussite finale de l’analyse.
4 Dans une action erreur, l’analyseur découvre qu’une erreur de
syntaxe s’est produite et appelle une routine de récupération sur
erreur.
95 / 141

réduction
Algorithme par Décalage/Réduction (Shift/Reduce)

1 Initialement, la pile contient $ et l’entrée contient ω$
2 A chaque étape, l’analyseur décale un ou plusieurs symboles
(action décaler) jusqu’à ce qu’un manche apparaı̂t au sommet de
la pile.
3 Une action réduire est alors réalisée en remplaçant le manche par
la partie gauche de la règle de production associée.
96 / 141

réduction-Exemple
PILE ENTREE SORTIE
$ Id1 + id2 * id3 $ Décaler
$id1 + id2 * id3 $ Réduire par E→id
$E + id2 * id3 $ Décaler
$E+ id2 * id3 $ Décaler
$E+ id2 * id3 $ Réduire par E → id
$E + E * Id3 $ Décaler
$E + E * id3 $ Décaler
$E + E * id3 $ Réduire par E → id
$E + E * E $ Réduire par E → E*E
$E + E $ Réduire par E → E+E
$E $ Accepter
97 / 141
Analyseurs LR
Méthode d’analyse LR
Description
C’est une méthode d’analyse syntaxique ascendante qui peut être
utilisée pour analyser une large classe de grammaires non
contextuelles.
Cette technique est appelée analyse LR(k) :
I L signifie le parcours de l’entrée de gauche vers la droite (Left to
right scanning of the input)
I R signifie en construisant une dérivation droite inverse
(constructing a Rightmost derivation in reverse)
I k indique le nombre de symboles de prévision utilisés pour prendre
une décision d’analyse. Quand k est omis, k est supposé être égal
à 1.
98 / 141
Analyseurs LR
Méthode d’analyse LR
Avantages
Les analyseurs LR reconnaissent virtuellement toutes les
constructions des langages de programmation qui peuvent être
décrits par des un grammaire non contextuelle
La méthode d’analyse LR peut être implantée aussi efficacement
que les autres méthodes par décalage-réduction
Un analyseur LR peut détecter une erreur de syntaxe aussitôt que
possible au cours d’un parcours de gauche à droite de l’entrée.
Inconvénient
La méthode d’analyse LR exige de fournir un outil spécialiser pour
construire les analyseurs (Yacc)
I Une quantité de travail trop importante pour construire à la main un
analyseur
99 / 141
Analyseurs LR
Modèle d’un analyseur LR
a1 … ai … an $
Sm Programme Flot de Sortie

Xm d’analyse
LR
Sm-1
Xm-1
Action Successeur
…
S0
100 / 141
Analyseurs LR
Tables d’analyse
Les tables d’analyse contiennent deux parties

I une fonction d’actions d’analyse Action
I une fonction de transfert Successeur.
F prend comme arguments un état et un symbole non-terminal et
retourne un état
Le programme dirigeant l’analyseur LR se comporte de la façon
suivante.
I Il détermine sm , l’état en sommet de pile, et ai , le symbole terminal
d’entrée courant.
I Il consulte alors Action[sm , ai ], l’entrée de la table des actions pour
l’état sm et le terminal ai qui peut avoir l’une des quatre valeurs :
1 Décaler s où s est un état
2 Réduire par une production de la grammaire A→ β
3 Accepter
4 Erreur
101 / 141
Analyseurs LR
Configuration d’un analyseur LR
Une configuration d’un analyseur LR est un couple dont le premier

composant est le contenu de la pile et dont le second composant
est la chaı̂ne d’entrée restant à analyser :
I (s0 X1 s1 X2 . . . Xm sm , ai ai+1 . . . an $)
Cette configuration représente la proto-phrase droite :
I X1 X2 . . . Xm ai ai+1 . . . am $
analogue à l’analyse par décalage/ Réduction ; seule la présence
d’états en pile est nouvelle
L’action suivante de l’analyseur est déterminée par la lecture de
ai , le symbole d’entrée courant, sm , l’état en sommet de pile, et la
consultation de l’entrée Action [sm , ai ] de la table des actions
d’analyse.
102 / 141
Analyseurs LR
Configuration d’un analyseur LR-Suite
Les configurations résultantes après chacun des quatre types

d’action, sont les suivantes :
1 Si Action[sm , ai ] = décaler s, l’analyseur exécute une action décaler
atteignant la configuration :
F (s0 X1 s1 X2 . . . Xm sm ai s, ai+1 . . . an $)
F Ici, l’analyseur a à la fois empilé le symbole d’entrée courant ai et le
prochain état s, qui est donné par Action[sm , ai ] ; ai+1 devient le
symbole d’entrée courant.
2 Si Action[sm , ai ] = réduire par A→ β alors l’analyseur exécute une
action réduire, atteignant la configuration :
F (s0 X1 s1 X2 . . . Xm−r sm−r , A s ai ai+1 . . . an $)
Où s = Successeur[sm−r , A] et r est la longueur de β, partie droite
de la production.
F Ici l’analyseur commence par dépiler 2r symboles (r symboles d’états
et r symboles grammaticaux), exposant ainsi l’état sm−r au sommet.
103 / 141
Analyseurs LR
Configuration d’un analyseur LR-Suite
I L’analyseur empile alors à la fois A, partie gauche de la production

et s, l’entrée pour Successeur[sm−r , A]. Le symbole d’entrée n’a
pas changé.
I La séquence de symboles dépilés Xm−r +1 . . .Xm correspond
toujours à β
3 Si Action[sm , ai ] = accepter, l’analyse est terminée
4 Si Action[sm , ai ] = erreur, l’analyseur a découvert une erreur et
appelle une routine de récupération sur erreur.
104 / 141
Analyseurs LR
Algorithme de l’analyse LR
Algorithme
Entrée : Table d’analyseur et le mot ω
Initialiser le pointeur source ps sur le premier symbole de ω$ ; La
pile contient s0
1 Début
2 TantQue vrai Faire
3 Soit s l’état en sommet de pile et
4 a le symbole pointé par ps;
5 Si Action[s, a] = décaler s’ Alors
6 empiler a puis s’;
7 avancer ps sur le prochain symbole
8 en entrée;
9 Sinon
105 / 141
Analyseurs LR
Algorithme-Suite
10 Si Action[s, a] = réduire par A→ β Alors

11 dépiler 2 x |β| symboles;
12 soit s’ le nouvel état sommet de pile;
13 empiler A puis Successeur [s’, A];
14 émettre en sortie une identification
15 de la production A → β;
16 Sinon
17 Si Action[s, a] = accepter Alors
18 Retourner
19 Sinon
20 erreur()
21 FinSi
106 / 141
Analyseurs LR
Algorithme-Suite
22 FinSi
23 FinSi
24 FinTantQue
25 Fin
107 / 141
Analyseurs LR
Exemple
Soit la grammaire des Le codage des actions est :
expressions suivantes : 1 di signifie décaler et
1 E→E+T empiler l’état i,
2 E →T 2 rj signifie réduire par la
3 T→T*F production (j),
4 T→F 3 Acc signifie accepter,
5 F → (E) 4 Une entrée vide signifie
erreur
6 F →id
108 / 141
Analyseurs LR
Algorithme de l’analyse LR - Exemple

PILE ENTREE ACTION
(1) 0 Id*id+id$ Décaler
(2) 0 id 5 *id+id$ Réduire par F→id
Et Action Successeur (3) 0 F 3 *id+id$ Réduire par T→F

at (4) 0 T 2 *id+id$ Décaler
Id + * ( ) $ E T F (5) 0 T 2 * 7 id+id$ Décaler
0 d5 d4 1 2 3 (6) 0 T 2 *7 id 5 +id$ Réduire par F→id
1 d6 acc (7) 0 T 2 * 7 F 10 +id$ Réduire par
2 r2 d7 r2 r2 T→T*F
3 r4 r4 r4 r4 (8) 0 T 2 +id$ Réduire par E→T
4 d5 d4 8 2 3 (9) 0 E 1 +id$ Décaler
5 r6 r6 r6 r6 (10) 0 E 1 + 6 id$ Décaler
6 d5 d4 9 3 (11) 0 E 1 + 6 id 5 $ Réduire par F→id
7 d5 d4 10 (12) 0 E 1 + 6 F 3 $ Réduire par T→F
8 d6 d11 (13) 0 E 1 + 6 T 9 $ Réduire par E
→E+T
9 r1 d7 r1 r1
(14) 0 E 1 $ Accepter
10 r3 r3 r3 r3
11 r5 r5
Leila Jemni Ben Ayed
r5 r5
109 / 141
Analyseurs LR
Construction de la table d’analyse LR
Pour la construction des Tables d’analyse LR à partir d’une grammaire,

nous distinguons trois méthodes qui diffèrent par leur puissance et leur
facilité d’implantation :
1 La première est appelée Simple LR ou SLR. Elle est la plus
simple à implanter mais la moins puissante en terme de nombre
de grammaires pour lesquelles elle réussit.
2 la seconde méthode, appelée LR canonique est la plus puissante
mais la plus coûteuse
3 La troisième méthode, appelée LookAhead LR (LALR) a une
puissance et un coût intermédiaire entre les deux. elle est
applicable à la plupart des grammaires de langages de
programmation.
I Les deux dernières méthodes augmentent la méthode SLR avec
une information de prévision.
110 / 141
Analyseurs LR
Construction de la table d’analyse SLR
Basée sur :
Préfixe viable est tout préfixe d’une forme grammaticale pouvant
apparaı̂tre sur la pile d’un analyseur décalage/réduction. Un
préfixe viable ne dépasse jamais un manche.
Item est une règle de production avec un point repérant une
position de la partie droite.
I A→ x . Yz
111 / 141
Analyseurs LR
Basée sur :
I A→ x . Yz
Ce qu’on a déjà Ce qu’on espère voir
Rencontré
112 / 141
Analyseurs LR
Basée sur :
I A→ x . Yz
La production A → XYZ où X, Y, Z ∈ (VN ∪VT ) fournit les 4 items :

I A → . XYZ
I A → X . YZ
I A → XY . Z
I A → XYZ .
La production A → ε fournit uniquement l’item A → .
113 / 141
Analyseurs LR
Item
Un item peut être codé par un couple d’entiers, le premier donnant
le numéro de la production et le second, la position du point.
Un item indique la quantité de partie droite qui a été reconnue, à
un moment donné au cours du processus d’analyse.
L’item A →. XYZ indique qu’on espère voir en entrée une chaı̂ne
dérivable depuis XYZ.
L’item suivant A → X . YZ indique que nous venons de voir en
entrée une chaı̂ne dérivée de X et que nous espérons maintenant
voir une chaı̂ne dérivée de YZ.
114 / 141
Analyseurs LR
Technique SLR
La SLR se base sur la construction d’un automate permettant la
reconnaissance des préfixes viables.
Les items sont regroupés en des ensembles qui constituent les
états de l’analyseur SLR.
Une collection d’ensembles d’items LR(0), que nous appelons
collection LR(0) canonique, fournit la base de la construction des
analyseurs SLR.
Pour construire la collection LR(0), nous définissons une
grammaire augmentée et deux fonctions, Fermeture et Transition.
115 / 141
Analyseurs LR
Grammaire augmentée
Si G est une grammaire d’axiome S, alors G0 , la grammaire
augmentée de G, est G avec un nouvel axiome S 0 et une nouvelle
production S 0 → S .
On espère atteindre un mot du langage c-a-d on espère
reconnaı̂tre un mot dérivé à partir de S
I S’ → S
I S’ → .S
I S’ → S.
La chaı̂ne d’entrée est acceptée quand et seulement quand
l’analyseur est le point de réduire S 0 → S
116 / 141
Analyseurs LR
L’opération Fermeture
Si I est un ensemble d’items pour une grammaire G, Fermeture (I)
est l’ensemble d’items construit à partir de I par les deux règles :
1 Initialement, placer chaque item de I dans Fermeture(I)
2 Si A →α.Bβ est dans Fermeture(I) et B → γ est une production,
ajouter l’item B → .γ à Fermeture(I), s’il ne s’y trouve pas déjà.
Nous appliquons cette règle jusqu’à ce qu’aucun nouvel item ne
puisse plus être ajouté à Fermeture(I).
E’ → E ; E → E + T | T ; T → T * F | F ; F → (E) | id
Si I est l’ensemble formé par l’unique item {[E 0 → .E]},alors
Fermeture(I) contient les items :
I E’ → .E (par r1) ici α = ε et β = ε, B = E, γ = E+T
I E → .E+T E → .T (par r2)
I T → .T*F T → .F (par r2)
I F → .(E) F → .id (par r2)
117 / 141
Analyseurs LR
Algorithme de l’opération Fermeture
1 Fonction Fermeture( I ):
2 Début
3 J← I;
4 Répéter
5 Pour chaque item A → α.Bβ ∈ J et
chaque production B → γ de G tel que
B →.γ ∈/ J Faire
6 ajouter B →.γ à J
7 FinPour
8 Jusqu’à aucun autre item ne puisse être ajouté à
J
9 Fin
118 / 141
Analyseurs LR
L’opération Transition
Transition(I, X) où I est un ensemble d’items et X est un symbole
de la grammaire. Transition(I, X) est définie comme la fermeture
de l’ensemble de tous les items [A → αX.β] tels que [A → α.Xβ]
appartienne à I.
Intuitivement, si I est l’ensemble des items qui sont valides par un
préfixe viable donné γ, alors Transition(I, X) est l’ensemble des
items qui sont valides pour le préfixe viable γX.
119 / 141
Analyseurs LR
Exemple-Transition
E’ → E ; E → E + T | T ; T → T * F | F ; F → (E) | id
Si I est l’ensemble formé des deux items
{[E 0 → E.], [E → E. + T ]}, alors Transition(I, +) consiste en :
I Nous calculons Transition(I, +) en cherchant dans I les items
immédiatement à droite du point.
I E’ →E. ne convient pas, mais E →E+.T répond au critère.
I Nous franchissons au point le + afin d’obtenir {[E → E + .T ]}.
I Puis nous calculons fermeture de cet ensemble.
120 / 141
Analyseurs LR

Construction des ensembles d’items
La collection canonique d’ensembles d’items LR(0) pour une
grammaire augmentée G’ est calculée par la procédure suivante :
Procédure Items( G’ )
Début
C← {Fermeture({[S’ →.S]})};
Répéter
Pour pour chaque ensemble d’items I de C
et pour chaque symbole X de la
grammaire tel que Transition(I, X)
soit non vide et non encore dans
C Faire
ajouter Transition (I, X) à C
FinPour
Jusqu’à ce qu’aucun nouvel ensemble d’items
ne puisse plus être ajouté à C
Fin 121 / 141
Analyseurs LR
Exemple (1) E→E+T

E’ → E (2) E→T
E→E+T|T (3) T→T*F
T→T*F|F (4) T→F
F → (E) | id (5) F → (E)
(6) F → id
La collection canonique d’ensembles d’items LR(0) pour cette grammaire est:
I0: E’ →.E I3: T →F. I6: E →E+.T I9: E →E+T.
E → .E + T T →.T*F T →T.*F
E → .T I4: F →(.E) T →.F I10: T →T*F.
T → .T * F E →.E+T F →.(E) I11: F →(E).
T → .F E →.T F →.id
F → .(E) T →.T*F I7: T → T*.F
F → .id T →.F F →.(E)
I1: E’ →E. F →.(E) F →.id
E → E. + T F →.id I8: F →(E.)
I2: E → T. E →E.+T
→ T.*F
LeilaTJemni Ben Ayed I5: F →id.
Cours Techniques de Compilation
1
2011-2012
122 / 141
Analyseurs LR
E * Vers I7
I0 I1 I6 I9
F
( Vers I3
id Vers I4
Vers I5
T * F
I2 I7 I10
(
F Vers I4
I3 id
Vers I5
(
( E )
I4 I8 I11
id +
T Vers I6
F Vers I2
id
I5 Vers I3
123 / 141
Analyseurs LR
Algorithme
Entrée : Une grammaire augmentée G’
Sortie : Les tables d’analyse SLR des fonctions Action et Successeur
pour G’.
Méthode :
1 Construire C = {I0 , I1 , , In }, la collection des ensembles d’items
LR(0) pour G’.
2 L’état i est construit à partir de Ii . Les actions d’analyse pour l’état i
sont déterminées comme suit :
1 Si [A → α.aβ] est dans Ii et Transition(Ii , a) = Ij , remplir Action[i, a]
avec décaler j . Ici a doit être un terminal
2 Si [A → α.] est dans Ii , remplir Action[i, a] avec réduire par A → α
pour tous les a dans SUIVANT(A) ; ici A ne doit pas être S’.
3 Si [S’ → S.] est dans Ii , remplir Action[i, $] avec accepter.
Si les règles précédentes engendrent des actions conflictuelles, nous
disons que la grammaire n’est pas SLR(1).
Dans ce cas, l’algorithme ne produit pas d’analyseur.
124 / 141
Analyseurs LR
Algorithme - Suite
3 On construit les transitions Successeur pour l’état i pour tout non
terminal A en utilisant la règle :
1 Si Transition(Ii , A) = Ij , alors Successeur[i, A] = j
4 Toutes les entrées non définies par les règles (2) et (3) sont
positionnées à erreur
5 L’état initial de l’analyseur est celui qui a été construit à partir de
l’ensemble contenant l’item [S’ → .S].
125 / 141
Analyseurs LR
Construction de la table d’analyse SLR-Exemple
Exemple:
Construisons les tables SLR pour la grammaire des expressions.
Considérons tout d’abord l’ensemble d’items I0 de la collection canonique de
l’ensemble des items LR(0):
E’ →.E
E → .E + T E → .T
T → .T * F T → .F
F → .(E) F → .id
L’item F → .(E) produit l’entrée Action[0, (]= décaler 4 et l’item F → .id l’entrée
Action[0, id] = décaler 5. Les autres items de I0 ne produisent aucune action.
Considérons maintenant I1
E’ → E.
E → E.+T
Le premier item produit Action[1, $] = accepter, le second item produit
Action[1, +] = décaler 6.
126 / 141
Analyseurs LR
Construction de la table d’analyse SLR-Exemple
Exemple-Suite:
Considérons ensuite I2
E → T.
T → T.*F
Comme SUIVANT(E) = {$, +, )},
le premier item produit Action[2, $] = Action[2, +]= Action[2, )]= réduire par E→T
Le second item produit Action[2, *] = décaler 7. En continuant ainsi, nous
obtenons les tables Action et Successeur présentées précédemment. L’ordre
des numéros de production dans les actions réduire est le même que l’ordre
d’apparition de ces productions dans la grammaire initiale. C-a-d E → E+T est
numéroté 1, E → T est numéroté 2 et ainsi de suite.
127 / 141
Analyseurs LR
Exercice d’application
Énoncé
Construire la table d’analyse SLR(1) pour la grammaire avec les règles de production
suivantes :
(1) S → L = R (2) S → R (3) L → ∗R (4)L → id (5)R → L
Solution : Calcul des items et des SUIVANTs

I0 = f (S 0 → .S) = {S → .S, S → .L = R, S → .R, L → . ∗ R, L → .id, R → .L}
I1 = tr (I0 , S) = {S 0 → S.} I2 = tr (I0 , L) = {S → L. = R, R → L.}
I3 = tr (I0 , R) = {S → R.} I4 = tr (I0 , id) = {L → id.}
I5 = tr (I0 , ∗) = {L → ∗.R, R → .L, L → . ∗ R, L → .id}
tr (I0 , =) = ∅ tr (I1 , X ) = tr (I3 , X ) = tr (I4 , X ) = ∅
I6 = tr (I2 , =) = f (S → L = .R) = {S → L = .R, R → .L, L → . ∗ R, L → .id}
I7 = tr (I5 , R) = {L → ∗R.} I8 = tr (I5 , L) = {R → L.}
tr (I5 , id) = {L → id.} = I4 tr (I5 , ∗) = {L → ∗.R, R → .L, L → . ∗ R, L → .id} = I5
tr (I5 , S) = tr (I5 , =) = ∅ I9 = tr (I6 , R) = {S → L = R.}
tr (I6 , L) = {R → L.} = I8 tr (I6 , ∗) = f (L → ∗.R) = I5 Tr (I6 , id) = I4
tr (I6 , =) = tr (I6 , S) = ∅ tr (I7 , X ) = tr (I9 , X ) = ∅
SUIVANT (S) = {$} SUIVANT (R) = SUIVANT (L) = {=, $}
128 / 141
Analyseurs LR
Solution : Construction de l’automate

S
I0 I1
L = R
I2 I6 I9
id
R
I3 L
*
id
I4
I9
id
* I8
R
* L
I5
129 / 141
Analyseurs LR
Solution : Construction de la table SLR(1)
Etat Action Successeur

G n’est pas
SLR(1) car la = * id $ S L R
table n’est 0 d5 d4 1 2 3
pas 1 acc
déterministe.
2 d6 R→L
→L
R→
3 S→R
4 L→id L→id
5 d5 d4 8 7
6 d5 d4 8 9
7 L→*R L→*R
8 R→L R→L
9 S→L=R
130 / 141
Analyseurs LR
Construction des tables canoniques d’analyse LR
Motivation
L’analyse LR canonique est plus performante que la technique
SLR car elle permet d’analyser avec succès un nombre plus
important de grammaires.
I Dans la méthode SLR, l’état i indique une action réduire par A → α
à la vue d’un terminal a appartenant à SUIVANT(A).
I Cependant, dans certains cas, quand l’état i apparaı̂t en sommet
de pile, le préfixe viable βα de la pile est tel que βA ne peut être
suivi par a dans aucune proto-phrase. Par conséquent, réduire par
A → α est invalide à la vue de a.
Il faut attacher plus d’information à un état : information qui
permet d’éviter les réductions invalides comme A → α
I Information supplémentaire dans l’état : ajouter un symbole
terminal comme second composant d’un item ([A → α . β, a])
I L’item est appelé alors item LR(1)
131 / 141
Analyseurs LR
Algorithme
Entrée : Une grammaire augmentée G’
Sortie : Les fonctions Action et Successeur des tables
canoniques d’analyse LR associées à G’.
Méthode :
1 Construire C = {I0 , I1 ,. . . , In }, la collection des ensembles d’items
LR(1) pour G’.
2 L’état i est construit à partir de Ii . Les actions d’analyse pour l’état i
sont déterminées comme suit :
1 Si [A → α.aβ,b] est dans Ii et Transition(Ii , a) = Ij , remplir Action[i, a]
avec décaler j . Ici a doit être un terminal
2 Si [A → α.,a] est dans Ii , A 6= S 0 , remplir Action[i, a] avec réduire par
A → α.
3 Si [S’ → S.,$] est dans Ii , remplir Action[i, $] avec accepter. Si un
conflit résulte de l’application des règles précédentes, la grammaire
n’est pas LR(1) et l’algorithme échoue.
132 / 141
Analyseurs LR
Algorithme - Suite
3 Les transitions Successeur pour l’état i sont déterminées comme
suit :
1 Si Transition(Ii , A) = Ij , alors Successeur[i, A] = j
4 Toutes les entrées non définies par les règles (2) et (3) sont
remplies avec erreur.
5 L’état initial de l’analyseur est celui qui a été construit à partir de
l’ensemble contenant l’item [S’ → .S,$].
133 / 141
Analyseurs LR
Construction des ensembles d’items LR(1)

Donnée : une grammaire augmentée G’
Résultat : les ensembles d’items LR(1) qui sont les ensembles
d’items valides pour un ou plusieurs préfixes viables de G’.
Méthode : Les procédures Fermeture et Transition et la procédure
principale Items sont les suivantes :
134 / 141
Analyseurs LR

1 Fonction Fermeture( I ):
2 Début
3 Répéter
4 Pour chaque item [A → α · Bβ,a] ∈ I
et chaque production B → γ de G’,
et chaque terminal b de premier (βa)
tel que [B →.γ,b] ∈/ I Faire
5 ajouter [B →.γ,b] à I
6 FinPour
7 Jusqu’à aucun autre item ne puisse être ajouté à
I
8 Retourner I
9 Fin
135 / 141
Analyseurs LR
1 Fonction Transition( I,X ):

2 Début
3 soit J l’ensembles des items [A → αX · β,a]
4 tel que [A → α · X β,a] ∈I;
5 Retourner Fermeture(J)
6 Fin
136 / 141
Analyseurs LR
Procédure Items( G’ )
Début
C← {Fermeture({[S’ → ·S, $]})};
Répéter
Pour pour chaque ensemble d’items I de C
et pour chaque symbole de la grammaire X
tel que Transition(I, X) soit non vide et
non encore dans C Faire
ajouter Transition (I, X) à C
FinPour
Jusqu’à ce qu’aucun nouvel ensemble d’items ne
puisse plus être ajouté à C
Fin
137 / 141
Analyseurs LR
Construction des tables canoniques d’analyse

LR-Exemple
PILE ENTREE ACTION

(1) 0 ccdd$ Décaler
(2) 0c3 cdd$ Décaler
(3) 0 c3c3 dd$ Décaler
(4) 0c3c3d4 d$ Réduire C→ D
(5) 0 c3c3C8 d$ Réduire C→ cC
(6) 0c3C8 d$ Réduire C→cC
(7) 0 C2 d$ Décaler
(8) 0C2d7 $ Réduire C→ d
(9) 0C2C5 $ Réduire S→ CC
(10) 0 E 1 + 6 $ Décaler
(11) 0S1 $ Acc
138 / 141
Analyseurs LR
Résumé sur l’analyse Lexicale/Syntaxique
L’analyse lexicale transforme un flot de caractères en un flot

d’unités lexicales. L’analyse syntaxique transforme un flot d’unités
lexicales en arbre syntaxique.
Une unité lexicale est généralement une classe et une chaı̂ne de
caractères (son nom)
Les analyseurs lexicaux peuvent être générés à partir des
automates d’états finis, eux-mêmes générés à partir des
expressions régulières décrivant des langages.
L’analyseur lexical fait un traitement lorsqu’il rencontre un
identificateur (en général il le référence dans une table des
symboles).
L’analyse syntaxique peut se faire de manière descendante ou
ascendante (se référant à la manière avec laquelle on construit
l’arbre syntaxique).
139 / 141
Analyseurs LR
Les analyseurs syntaxiques descendants écrits à la main

consistent en un ensemble de procédures mutuellement
récursives structurées comme la grammaire.
Pour écrire ces analyseurs, il faut avoir calculé les ensembles
Premier et Suivant. Les grammaires acceptées par ces
analyseurs sont dites LL(1).
Les grammaires récursives à gauche ne sont pas LL(1), on peut
”dérécursiver” une grammaire récursive à gauche.
Les analyseurs ascendants manipulent des items : à la base c’est
une règle avec un point symbolisant l’endroit jusqu’auquel on a
reconnu (éventuellement associé à un ou plusieurs symboles
représentant ce que l’on rencontrera après avoir fini de
reconnaı̂tre la règle en question).
140 / 141
Analyseurs LR
Les analyseurs ascendants essayent d’identifier successivement

les réductions candidates.
Il y de nombreuses techniques pour trouver les réductions
candidates. Les analyseurs LR(1) utilisent des ensembles d’items
LR(1).
En parsing LR(0) tout item de la forme [N → α·] génère une
réduction. En parsing SLR(1) un item [N → α·] génère une
réduction si et seulement si le prochain symbole à lire appartient à
Suivant(N). En parsing LR(1) un item [N → α·, A] génère une
réduction si le prochain symbole à lire est dans l’ensemble A, un
petit ensemble de terminaux. En LR(1) A est limité à un symbole.
En LALR(1) c’est un ensemble de symbole (dans Suivant(N)). En
pratique une grammaire LR(1) a de très fortes chances d’être
LALR(1)
141 / 141

Chapitre3 Comp2018

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre3 Comp2018

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre3 Comp2018

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre IV

2 Analyse syntaxique descendante récursive

3 Analyse syntaxique Prédictive descendante récursive

4 Analyse syntaxique prédictive non récursive

5 Récupération sur erreur

6 Analyse syntaxique ascendante par décalage réduction

Analyse syntaxique descendante

Analyse syntaxique ascendante

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Analyse syntaxique descendante récursive

Procédure Type simple()

1 Procédure Type simple( )

Analyse syntaxique descendante récursive

Suite- Procédure Type simple()

Analyse syntaxique Prédictive descendante récursive

Elimination de la récursivité à gauche

Grammaire récursive à gauche

Transformation de cette grammaire en une non récursive à

Elimination de la récursivité à gauche

Transformation d’une grammaire ambiguë en une non ambiguë

Le langage, décrit par la grammaire suivante, est formé par une

Un pseudo-code d’un AS prédictif et récursif associé

Un pseudo-code d’un AS prédictif et récursif associé

Un pseudo-code d’un AS prédictif et récursif associé

Un pseudo-code d’un AS prédictif et récursif associé

Un pseudo-code d’un AS prédictif et récursif associé

Analyse syntaxique prédictive non récursive

Analyse syntaxique prédictive non récursive

Analyse syntaxique prédictive non récursive

Exemple - Table d’analyse M

Non Symbole d’entrée

Algorithme d’analyse syntaxique prédictive non

Algorithme d’analyse syntaxique prédictive non

Calcul des premiers et suivants

La construction de la table d’analyse est facilitée par deux

Calcul des premiers et suivants

E+EE EE E→E*E