Analyse Syntaxique

Dr. Aida Lahouij

[email protected]

1
Plan
Introduction
Approche descendante (Top-down)
Approche ascendante (Bottom-up)

2
Introduction

 L'analyseur syntaxique (parser) reçoit une suite d'unités

lexicales (de symboles terminaux) de la part de l'analyseur
lexical.
 Il doit décider si un flux de tokens (un mot) est
syntaxiquement correct.
 Autrement dit, il doit décider si c'est un mot qui peut être
généré par la grammaire du langage qu'il possède.
 Pour ce faire, il doit construire l’arbre de dérivation de ce
mot.
 S’il y arrive alors le mot est syntaxiquement correct.

 Sinon, le mot est incorrect. 3

Introduction

4
Introduction

5
Introduction
 Structure générale d’un parser

 Parser = Algorithme qui reconnaît la structure du

programme et construit l’arbre syntaxique
correspondant
 Comme le langage à reconnaître est context-free,
un parser aura le fonctionnement d’un automate à
pile (PDA)
 Nous verrons 2 grandes classes de parsers :

 Les analyseurs descendants (top-down)

 Les analyseurs ascendants (bottom-up

6
Introduction

Approches de
construction d’un arbre
de dérivation

Approche descendante Approche ascendante

(Top-down) (bottom-up)

7
Approche descendante
(Top-down)

8
Approche descendante (Top-down)
Principe

 Construire l'arbre de dérivation du haut (la racine, c'est à

dire l'axiome de départ) vers le bas (les feuilles, c'est à dire
les unités lexicales).
 Le processus d'analyse commence par la racine de
l'arbre syntaxique et se déplace vers le bas en utilisant les
règles de la grammaire pour diviser la chaîne de
caractères en sous-éléments syntaxiques.
 Les règles de la grammaire sont appliquées de manière
récursive pour continuer à diviser la chaîne de caractères en
sous-éléments jusqu'à ce que les symboles terminaux
soient atteints.
9
Approche descendante (Top-down)
 Exemple 2
S->aTb
T->cd|c
Avec le mot w= acb

 Nous partons de S premier non terminal de la grammaire.

 S est la racine de l’arbre. Nous lisons ensuite la première
lettre (a) pour arriver à la construction :

w=acb

10
Approche descendante (Top-down)
 Exemple
S->aTb
T->cd|c
Avec le mot w= acb

 En lisant le caractère c, nous ne savons pas s’il faut

prendre la règle Tcd ou la règle T c : nous devons
essayer une règle et faire des retours en cas d’échec.

w=acb

11
Approche descendante (Top-down)
 Exemple
S->aTb
T->cd|c
Avec le mot w= acb

 Nous essayons la 1ère règle (T  cd) qui aboutit à un échec.

 Nous effectuons alors un retour en arrière (backtracking) pour
essayer la 2ème règle (T  c). Dans ce dernier cas le mot w = acb est
reconnu.

w=acb

12
Approche descendante (Top-down)

Conclusion
 Ce qui serait pratique, ça serait d'avoir une table qui
indique : quand on lit tel caractère et qu’on en est à
dériver tel symbole non-terminal, alors on applique telle
règle et on ne se pose pas de questions.
 Ça existe, et ça s'appelle une table d'analyse.

13
Approche descendante (Top-down)
Analyseur LL(1)

L'analyseur LL(1) est un type d'analyseur syntaxique qui est utilisé pour
analyser des langages de programmation ou des langues naturelles.

 "LL" signifie "analyseur en lecture anticipée de gauche à droite", et "1"

signifie qu'il ne regarde qu'un symbole d'entrée à la fois et prend des
décisions basées sur une lecture anticipée d'un seul symbole.

 Le terme LL(1) signifie que l'analyseur LL(1) utilise une méthode d'analyse
"left-to-right, leftmost-derivation" (de gauche à droite, dérivation la plus à
gauche) et qu'il utilise un seul symbole de lecture à chaque étape de
l'analyse.

 En outre, l'analyseur LL(1) peut prédire la production à utiliser en fonction du

symbole de lecture en cours et des symboles suivants, d'où le "1" qui
indique une seule avance de lecture.

14
Approche descendante (Top-down)
Analyseur LL(1)

 Un analyseur LL(1) utilise une table d'analyse syntaxique

appelée table d'analyse syntaxique LL(1), qui est un tableau de
correspondance entre les symboles de l'entrée et les
productions de la grammaire.

Cette table est construite à partir de la grammaire du langage

que l'on souhaite analyser.

 Elle contient des informations sur les symboles non

terminaux et terminaux, les productions de la grammaire, les
premiers et suivants des non terminaux, ainsi que les actions à
effectuer lorsque l'analyseur rencontre un symbole dans l'entrée.

15
Approche descendante (Top-down)
Analyseur LL(1)
L'analyseur LL(1) effectue une analyse syntaxique en suivant
une stratégie de lecture anticipée de gauche à droite.

 Il lit un symbole d'entrée et utilise la table d'analyse syntaxique

pour déterminer quelle production de la grammaire doit être
utilisée pour générer les symboles suivants.

 L'analyseur suit ensuite les symboles de la production et

continue de lire l'entrée jusqu'à ce qu'il ait généré une chaîne qui
correspond à la phrase donnée en entrée.

16
Approche descendante (Top-down)
Analyseur LL(1)
 L'analyseur LL(1) a l'avantage d'être facile à implémenter et de
générer des messages d'erreur clairs lorsqu'il rencontre des
erreurs de syntaxe.

 Cependant, il a également des limitations, car il ne peut pas

analyser toutes les grammaires, en particulier celles qui sont
ambiguës ou qui nécessitent des décisions de lecture anticipée
plus complexes.

17
Approche descendante (Top-down)
Analyseur LL(1)
Pour construire une table d'analyse, on a besoin de calculer
deux ensembles de terminaux :
 PREMIER “First()”
 SUIVANT “Follow()”

 First et Follow sont des ensembles utilisés dans l'analyse

syntaxique pour déterminer quelles productions appliquer
lorsqu'on analyse une chaîne de symboles.

 First(A) : l'ensemble First(A) contient les terminaux qui A->BC

peuvent commencer une chaîne de symboles dérivée de A.
B->a
Par exemple, si A peut produire le symbole B, et si B
commence par le terminal a alors First(A) contiendra a.

18
Approche descendante (Top-down)
Analyseur LL(1)
 Follow(A) : l'ensemble Follow(A) contient les terminaux qui
peuvent suivre A dans une chaîne de symboles. Par exemple, si
A est suivi par B dans une production, et si B peut être suivi par
le terminal c, alors Follow(A) contiendra c.

 Ces ensembles sont utilisés pour construire des tables

d'analyse syntaxique LL(1), qui permettent de décider quelle
production appliquer à chaque étape de l'analyse.

 En résumé, First et Follow sont des ensembles d'informations

qui aident à déterminer les productions à appliquer lors de
l'analyse syntaxique d'une chaîne de symboles selon une
grammaire donnée.

19
Approche descendante (Top-down)
Analyseur LL(1)
En résumé

20
Approche descendante
(Top-down)
Calcul des premiers

21
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

22
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers
Algorithme de calcul des ensembles PREMIER(X)
X est composé de terminaux et de non-terminaux :
1. Si X est un non-terminal et X  Y1Y2..Yn est une production de la grammaire
(avec Yi symbole terminal ou non-terminal) alors

a. Ajouter les éléments de PREMIER(Y1) sauf ε dans PREMIER(X)

b. Si ε ∈ PREMIER(Yi) pour i ∈ [1..j] alors PREMIER(Yi+1) ⊂ PREMIER(X) sauf ε

c. Si ε ∈ PREMIER(Yi) pour i ∈ [1..n] alors ε ∈ PREMIER(X)

2. Si X est un non-terminal et X  ε est une production, alors ε ∈ PREMIER(X)

3. Si X est un terminal, PREMIER(X)={X} .

4. Recommencer jusqu'à ce qu'on n'ajoute rien de nouveau dans les ensembles

PREMIER.

23
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

24
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

25
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

premier(S)= premier(A)-ε +premier(s si A=ε)- ε +premier(s si A=ε et B=ε)- ε

premiers (B)- ε premiers (C)- ε

premier(A)= {a, ε}
premiers (B)={b, c, ε}
premiers (C)={d}

premier(S)= {a,b,c,d}
26
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

27
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers
Si on rajoute ε à la règle de production de C

premier(A)= {a, ε}
premiers (B)={b, c, ε}
premiers (C)={d, ε}

premier(S)= premier(A)- ε +premier(S si A=ε) - ε +premier(S si A=ε et B=ε)- ε

+premier(S si A=ε et B=ε et C=ε)
= premier(A)- ε + premiers (B)- ε + premier(C)- ε + ε

premier(S)= {a,b,c,d,ε}

28
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

Calcul des ensembles PREMIER(X) : Exemple

29
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

Calcul des ensembles PREMIER(X) : Exemple

30
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

Calcul des ensembles PREMIER(X) : Exemple

31
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

Calcul des ensembles PREMIER(X) : Exemple

32
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

33
Approche descendante (Top-down)
Analyseur LL(1): Calcul des premiers

34
Approche descendante
(Top-down)
Calcul des suivants

35
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants
• Pour tout non-terminal A, on cherche SUIVANT(A) :
SUIVANT(A) = l'ensemble de tous les symboles terminaux a qui peuvent
apparaître immédiatement à droite de A dans une dérivation S  αAaβ

36
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants
Algorithme de calcul des ensembles SUIVANT(X)
1. Ajouter un marqueur de fin de chaîne (symbole $ par exemple) à
SUIVANT(S) (où S est l'axiome de départ de la grammaire)

2. S'il y a une production A -> αBC où B est un non-terminal, alors

ajouter le contenu de PREMIER(C) à SUIVANT(B), sauf ε

3. S'il y a une production A -> αB, alors ajouter SUIVANT(A) à

SUIVANT(B)

4. S'il y a une production A -> αBC avec ε ∈ PREMIER(C), alors ajouter

SUIVANT(A) à SUIVANT(B)

5. Recommencer à partir de l’étape 3 jusqu'à ce qu'on n'ajoute rien de

nouveau dans les ensembles SUIVANT.
37
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(C)=Suivant(A)+Suivant(C)=Suivant(A)={σ, $}

38
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(A)={σ, $}

39
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(B)=premier(C)-ε +Suivant(A si C=ε)+Suivant(C si C=ε)

40
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(C)=Suivant(A)+Suivant(C)={σ, $}

41
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(B)=premier(C)-ε +Suivant(A si C=ε)+Suivant(C si C=ε)

={α , σ, $}

42
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(E)=Suivant(B)+Suivant(E)
=Suivant(B)
={α , σ, $}

43
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(D)= premier(E)-ε+ Suivant(B si E=ε)+Suivant(E si E=ε)

={β, α , σ, $}

44
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

 Suivant(A)={σ, $}
 Suivant(B)= {α , σ, $}
 Suivant(C)={σ, $}
 Suivant(D)={β, α , σ, $}
 Suivant(E)= {α , σ, $}

45
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

Suivant(S)={$}
Suivant(A)=Premier(B)-ε+ Premier(C si B=ε)-ε +Suivant(A) +Suivant(C)={b,c,d,$}
Suivant(C)=Suivant(S)+Suivant(C)={$}
Suivant(B)= Premier(C)-ε+Suivant(B)={d}

46
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

47
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants
Exemple
S  iEtSS’|a
S’  eS|ε
E  bb

PREMIER SUIVANT
S
S’
E

48
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants
Exemple
S  iEtSS’|a
S’  eS|ε
E  bb

PREMIER SUIVANT
S ia $e
S’ eε $e
E b t

49
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

50
Approche descendante (Top-down)
Analyseur LL(1): Calcul des suivants

51
Approche descendante
(Top-down)
Construction de la table
d’analyse

52
Approche descendante (Top-down)
Analyseur LL(1): Construction de la table d’analyse

• Une table d'analyse est une matrice M où :

• Dans la première colonne, on représente les non-
terminaux.
• Dans la première ligne on place les terminaux et le

symbole $ (sauf le mot vide).

• Chaque case M[X,x] comporte la règle de production à

appliquer.

53
 Approche descendante (Top-down)
Analyseur LL(1): Construction de la table d’analyse

 Algorithme de construction de la table d’analyse

1. Pour chaque production A  α faire

a. pour tout a ∈ PREMIER(α) (et a ≠ε), rajouter la production
A  α dans la case M[A,a].
b. si ε ∈ PREMIER(α), alors pour chaque b ∈ SUIVANT(A)
ajouter A  α dans M[A,b].
2. Chaque case M[A,a] vide est une erreur de syntaxe.

54
Approche descendante (Top-down)
Analyseur LL(1): Construction de la table d’analyse

55
Approche descendante (Top-down)
Analyseur LL(1)

56
Approche descendante (Top-down)
Analyseur LL(1)

57
Approche descendante (Top-down)
Analyseur LL(1)

58
Approche descendante (Top-down)
Analyseur LL(1)

59
Approche descendante (Top-down)
Analyseur LL(1)

60
Approche descendante (Top-down)
Analyseur LL(1)

Grammaire non LL(1) 61

Approche descendante (Top-down)
Analyseur LL(1)
Construction
 de la table d’analyse : Exemple

PREMIER(E)=PREMIER(T)={(,nb} SUIVANT(E)={$,)}
PREMIER(E’)={+,-,ε} SUIVANT(E’)={$,)}
PREMIER(T)=PREMIER(F)={(,nb} SUIVANT(T)={+,-,),$}
PREMIER(T’)={*,/,ε} SUIVANT(T’)={+,-,),$}
PREMIER(F)={(,nb} SUIVANT(F)={*,/,),+,-,$}
62
Approche descendante (Top-down)
Analyseur LL(1)
Construction
 de la table d’analyse : Exemple

PREMIER(E)=PREMIER(T)={(,nb} SUIVANT(E)={$,)}
PREMIER(E’)={+,-,ε} SUIVANT(E’)={$,)}
PREMIER(T)=PREMIER(F)={(,nb} SUIVANT(T)={+,-,),$}
PREMIER(T’)={*,/,ε} SUIVANT(T’)={+,-,),$}
PREMIER(F)={(,nb} SUIVANT(F)={*,/,),+,-,$}
63
Approche descendante (Top-down)
Analyseur LL(1)

64
Approche descendante (Top-down)
Analyseur LL(1)

65
Approche descendante
(Top-down)
En pratique

66
Approche descendante (Top-down)
Analyseur LL(1)

67
Approche descendante (Top-down)
Analyseur LL(1)

68
Approche descendante (Top-down)
Analyseur LL(1)

69
Approche descendante (Top-down)
Analyseur LL(1)

70
Approche descendante (Top-down)
Analyseur LL(1)

71
Approche descendante (Top-down)
Analyseur LL(1) E→TE’

T
E’

72
Approche descendante (Top-down)
Analyseur LL(1) E→TE’

T
E’

73
Approche descendante (Top-down)
Analyseur LL(1)
E→TE’
T→FT’

F
T’
E’

74
Approche descendante (Top-down)
Analyseur LL(1) Depiler
E→TE’
T→FT’
F→id
dépiler

id
T’
E’

75
Approche descendante (Top-down)
Analyseur LL(1)
E→TE’
T→FT’
F→id
dépiler

T’
E’

76
Approche descendante (Top-down)
Analyseur LL(1)
E→TE’
T→FT’
F→id
dépiler
T’→ε
E’→+TE’

E’

77
Approche descendante (Top-down)
Analyseur LL(1) Depiler
E→TE’
T→FT’
F→id
dépiler
T’→ε
+
E’→+TE’
+
T dépiler
E’

78
Approche descendante (Top-down)
Analyseur LL(1)
E→TE’
T→FT’
F→id
dépiler
T’→ε
E’→+TE’

* dépiler
id T→FT’
F→id
dépiler
T’→*FT’
dépiler
F→id
dépiler
T’→ε
E’→ε

79
Approche descendante (Top-down)
Analyseur LL(1)
Algorithme
Répéter
Soit X le symbole en sommet de pile
Soit a la lettre pointée par ps
Si X est un non terminal alors
Si M[X,a]= X  Y1..Yn alors
enlever X de la pile
mettre Yn puis Yn-1 puis ...puis Y1 dans la pile
émettre en sortie la production X  Y1..Yn
Sinon
ERREUR
Finsi
Sinon
Si X=$ alors
Si a=$ alors ACCEPTER
Sinon ERREUR
Finsi
Sinon
Si X=a alors
enlever X de la pile
avancer ps
Sinon
ERREUR
Finsi
Finsi
Finsi
jusqu'à ERREUR ou ACCEPTER 80
Approche descendante (Top-down)
Analyseur LL(1)

Données en entrée : le mot m avec $ à la fin et la table d’analyse M

Initialisation de la pile : $S où S est l’axiome de départ et un pointeur ps

sur la première lettre du mot

Exemple: Pile Entrée Sortie
$S 2+6*9$

81
Approche descendante (Top-down)
Analyseur LL(1) Pile Entrée Sortie
Accepter/Rejeter un mot $E 3+4*5$ ETE’
$ E'T 3+4*5$ TFT’
m=3+4*5 $ E'T'F 3+4*5$ Fnb
$ E'T'3 3+4*5$
$ E'T' +4*5$ T’ ε
$ E' +4*5$ E’ +TE’
$ E'T+ +4*5$
$ E'T 4*5$ TFT’
$ E'T'F 4*5$ Fnb
$ E'T'4 4*5$
$ E'T' *5$ T’ *FT’
$ E'T'F* *5$
$ E'T'F 5$ Fnb
$ E'T'5 5$
$ E'T' $ T’ ε
$ E' $ E’ ε
analyse
$ $ syntaxique
réussie
82
Approche descendante (Top-down)
Analyseur LL(1) Pile Entrée Sortie
Accepter/Rejeter un mot $E 3+4*5$ ETE’
$ E'T 3+4*5$ TFT’
m=3+4*5 $ E'T'F 3+4*5$ Fnb
$ E'T'3 3+4*5$
Analyse syntaxique réussie : on $ E'T' +4*5$ T’ ε
obtient l’arbre syntaxique suivant
$ E' +4*5$ E’ +TE’
$ E'T+ +4*5$
$ E'T 4*5$ TFT’
$ E'T'F 4*5$ Fnb
$ E'T'4 4*5$
$ E'T' *5$ T’ *FT’
$ E'T'F* *5$
$ E'T'F 5$ Fnb
$ E'T'5 5$
$ E'T' $ T’ ε
$ E' $ E’ ε
analyse
$ $ syntaxique
réussie
83
Approche descendante (Top-down)
Analyseur LL(1)

84
Approche descendante (Top-down)
Analyseur LL(1)

85
Approche descendante (Top-down)
Analyseur LL(1)

86
Approche descendante (Top-down)
Exercice 1
Considérons la grammaire suivante:
S -> aX
X -> B | CD | E
B -> bB | ε
C -> cC | ε
D -> dDd | ε
E -> FG
F-> aF|cF|ε
G -> g | h
 Calculer les ensembles premier et suivant.

 Construire la table d'analyse LL de cette grammaire.

 Vérifier si les mots acdd et acaah et aghac sont reconnus.

 Construire les arbres de dérivation correspondants.

87
Approche descendante (Top-down)
Exercice 1 Ensembles premiers :
Premier(S) = {a}
S -> aX Premier(X) = {b, c, d, g, h, ε}
X -> B | CD | E Premier(B) = {b, ε}
B -> bB | ε Premier(C) = {c, ε}
C -> cC | ε Premier(D) = {d, ε}
D -> dDd | ε Premier(E) = {a, c, g, h}
E -> FG Premier(F) = {a, c, ε}
F-> aF|cF|ε Premier(G) = {g, h}
G -> g | h

88
Approche descendante (Top-down)
Exercice 1 Suivants(S) = {$}
Suivants(X) = {$}
S -> aX Suivants(B) = {$}
X -> B | CD | E Suivants(C) = {d, $}
B -> bB | ε Suivants(D) = {d, $}
C -> cC | ε Suivants(E) = {$}
D -> dDd | ε Suivants(F) = {g, h}
E -> FG Suivants(G) = {$}
F-> aF|cF|ε
G -> g | h

89
Approche descendante (Top-down)
Exercice 1 Premier(S) = {a} Suivants(S) = {$}
Premier(X) = {b, c, d, g, h, ε} Suivants(X) = {$}
S -> aX Premier(B) = {b, ε} Suivants(B) = {$}
X -> B | CD | E Premier(C) = {c, ε} Suivants(C) = {d, $}
B -> bB | ε Premier(D) = {d, ε} Suivants(D) = {d, $}
C -> cC | ε Premier(E) = {a, c, g, h} Suivants(E) = {$}
D -> dDd | ε Premier(F) = {a, c, ε} Suivants(F) = {g, h}
E -> FG Premier(G) = {g, h} Suivants(G) = {$}
F-> aF|cF|ε
G -> g | h

90
Approche descendante (Top-down)
Exercice 1 S -> aX
Premier(S) = {a} Suivants(S) = {$}
X -> B | CD | E Premier(X) = {b, c, d, g, h, ε} Suivants(X) = {$}
B -> bB | ε Premier(B) = {b, ε} Suivants(B) = {$}
C -> cC | ε Premier(C) = {c, ε} Suivants(C) = {d, $}
D -> dDd | ε Premier(D) = {d, ε} Suivants(D) = {d, $}
E -> FG Premier(E) = {a, c, g, h} Suivants(E) = {$}
Premier(F) = {a, c, ε} Suivants(F) = {g, h}
F-> aF|cF|ε
Premier(G) = {g, h} Suivants(G) = {$}
G -> g | h
a b c d g h $
S S -> aX
X X -> B X -> CD X -> CD X -> E X -> E X -> ε
B B -> bB B -> ε
C C -> cC C -> ε
D D -> dDd D -> ε
E E -> FG E -> FG E -> FG E -> FG
F F -> aF F -> cF F -> ε F -> ε
G G -> g G -> h

91
Approche descendante (Top-down)
Exercice 1

acdd
Etape Pile Entrée Action
1 $S acdd$ S->aX

2 $Xa acdd$ depiler

3 $X cdd$ X -> E
4 $E cdd$ E -> FG
5 $GF cdd$ F -> cF
6 $GFc cdd$ depiler
Erreur
7 $GF dd$
syntaxique

92
Approche descendante (Top-down)
Exercice 1

acaah
Etape Pile Entrée Action
1 $S acaah$ S->aX

2 $Xa acaah$ depiler

3 $X caah$ X -> E
4 $E caah$ E -> FG
5 $GF caah$ F -> cF
6 $GFc caah$ depiler
7 $GF aah$ F -> aF
8 $GFa aah$ depiler
9 $GF ah$ F -> aF
10 $GFa ah$ depiler
11 $GF h$ F -> ε
12 $G h$ G -> h
13 $h h$ depiler
14 $ $ succès

93
Approche descendante (Top-down)
Exercice 1

aghac
Etape Pile Entrée Action
1 $S aghac$ S->aX

2 $Xa aghac$ depiler

3 $X ghac$ X -> E

4 $E ghac$ E -> FG

5 $GF ghac$ F -> ε

6 $G ghac$ G -> g

7 $g ghac$ depiler

ERREUR
8 $ hac$
syntaxique

94
Approche descendante (Top-down)
Analyseur LL(1)

Remarque

 L'algorithme précédent ne peut pas être appliqué à toutes les

grammaires. En effet, si la table d'analyse comporte des entrées
multiples (plusieurs productions pour une même case M[A,a]),
on ne pourra pas faire une telle analyse descendante car on ne
pourra pas savoir quelle production appliquer.

95
Approche descendante (Top-down)
Une grammaire ambigüe
Définition
On appelle grammaire LL(1) une grammaire pour laquelle la table d'analyse
(décrite précédemment) n'a aucune case définie de façon multiple.

Théorème
Une grammaire ambigüe ou récursive à gauche ou non factorisée à gauche
n'est pas LL(1).

Définition

Une grammaire est dite ambigüe s'il existe un mot de L(G) ayant
plusieurs arbres syntaxiques.

96
Approche descendante (Top-down)
Grammaire LL(1)

Grammaire ambigüe

Exemple

Soit G donnée par :

instr  if (expr) instr else instr
instr  if (expr) instr
instr  …
expr  …

Cette grammaire est ambiguë car le mot m= if (x>10 ) if (y<0) a=1 else a=0
possède deux arbres syntaxiques différents :

97
Approche descendante (Top-down)
Grammaire LL(1)

Grammaire ambigüe

Exemple

98
Approche descendante (Top-down)
Grammaire LL(1)

Grammaire ambigüe

Exemple
car il y a deux interprétations syntaxiques possibles :

if (x>10) if (x>10)
if (y<0) if (y<0)
a=1 a=1
else ; ; //
finsi
a=0 else
// finsi ; a=0
// finsi // finsi
;

99
Approche descendante (Top-down)
Une grammaire ambigüe

Théorème
Une grammaire ambigüe ou récursive à gauche ou non factorisée à gauche
n'est pas LL(1).

Eliminer la récursive à gauche

Factoriser à gauche

100
Approche descendante (Top-down)
Elimination de la récursive à gauche
 Une grammaire est immédiatement récursive à
gauche si elle contient un non-terminal A tel qu'il existe
une production A-> Aα où α est une chaîne quelconque.

101
Approche descendante (Top-down)
Elimination de la récursive à gauche
 Une grammaire est récursive à gauche si elle
contient un non-terminal A tel qu'il existe une dérivation
+ Aα où α est une chaîne quelconque.
A->

S->Aa|b
A->Ac|Sd|ε

102
Approche descendante (Top-down)
Elimination de la récursive à gauche

103
Approche descendante (Top-down)
Elimination de la récursive à gauche

104
Approche descendante (Top-down)
Elimination de la récursive à gauche

105
Approche descendante (Top-down)
Elimination de la récursive à gauche

106
Approche descendante (Top-down)
Elimination de la récursive à gauche

107
Approche descendante (Top-down)
Elimination de la récursive à gauche

108
Approche descendante (Top-down)
Elimination de la récursive à gauche

109
Approche descendante (Top-down)
Factorisation à gauche

110
Approche descendante (Top-down)
Factorisation à gauche

111
Approche descendante (Top-down)
Factorisation à gauche

112
Approche descendante (Top-down)
Factorisation à gauche

113
Approche descendante (Top-down)
Factorisation à gauche

114
Approche descendante (Top-down)
Factorisation à gauche

115
Approche descendante (Top-down)

Exercice

S  ScA|B
A  Aa|ε
B  Bb|d|e

116
Approche descendante (Top-down)

Exercice

S  ScA|B
A  Aa|ε
B  Bb|d|e

117
Approche descendante (Top-down)

Exercice
S -> aEbS|aEbSeB|a
E -> bcB|bca
B -> ba

Devient S -> aEbSS’|a

S’ -> eB|ε
E -> bcE’
E’-> B|a
B ->ba 118
Approche descendante (Top-down)

Exercice
S -> aEbS|aEbSeB|a
E -> bcB|bca
B -> ba

Devient S -> aEbSS’|a

S’ -> eB|ε
E -> bcE’
E’-> B|a
B ->ba 119
Approche descendante (Top-down)

Conclusion
Exemple : grammaire des expressions arithmétiques avec les opérateurs + et *
E->E+E|E*E|(E)|nb
Mais elle est ambiguë. Pour lever l'ambiguïté, on considère les priorités
classiques des opérateurs et on obtient la grammaire non ambiguë :

E->E+T|T
T->T*F|F
F->(E)|nb

120
Approche descendante (Top-down)

Conclusion
Exemple : grammaire des expressions arithmétiques avec les opérateurs + et *
E->E+E|E*E|(E)|nb
Mais elle est ambiguë. Pour lever l'ambiguïté, on considère les priorités
classiques des opérateurs et on obtient la grammaire non ambiguë :

E->E+T|T
T->T*F|F
F->(E)|nb

121
Approche descendante (Top-down)
Grammaire LL(1)
Conclusion
Exemple : grammaire des expressions arithmétiques avec les opérateurs + et *
E->E+T|T
T->T*F|F
F->(E)|nb
Après suppression de la récursivité à gauche, on obtient

122
Approche ascendante
(Bottom-up)

123
Approche ascendante (Bottom-up)

124
Approche ascendante (Bottom-up)
Analyse SLR

125
Approche ascendante (Bottom-up)
Analyse SLR

126
Approche ascendante (Bottom-up)
Analyse SLR

127
Approche ascendante (Bottom-up)
Analyse SLR

128
Approche ascendante (Bottom-up)
Analyse SLR

129
Approche ascendante (Bottom-up)
Analyse SLR

130
Approche ascendante (Bottom-up)
Analyse SLR

131
Approche ascendante (Bottom-up)
Analyse SLR

132
Approche ascendante (Bottom-up)
Analyse SLR

133
Approche ascendante (Bottom-up)
Analyse SLR

134
Approche ascendante (Bottom-up)
Analyse SLR

135
Approche ascendante (Bottom-up)
Analyse SLR

136
Approche ascendante (Bottom-up)
Analyse SLR

137
Approche ascendante (Bottom-up)
Analyse SLR

138
Approche ascendante (Bottom-up)
Analyse SLR

139
Approche ascendante (Bottom-up)
Analyse SLR

140
Approche ascendante (Bottom-up)
Analyse SLR

141
Approche ascendante (Bottom-up)
Analyse SLR

142
Approche ascendante (Bottom-up)
Analyse SLR

143
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

144
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

145
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

146
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

147
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

148
Approche ascendante (Bottom-up)
Analyse SLR: Construction de la table d’analyse SLR

149
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

150
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

151
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

152
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

153
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

154
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

155
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

156
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

157
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

158
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

159
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

160
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

161
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

162
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

163
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

164
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

165
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

166
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

167
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

168
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

169
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

170
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

171
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

172
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

173
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

174
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

175
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

176
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

177
Approche ascendante (Bottom-up)
Analyse SLR: Analyse d’un mot

178
Approche ascendante (Bottom-up)
Exercice:
S -> E
E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | id | num

1. Cette grammaire est-elle ambiguë?

2. Calculer l'ensemble des premiers de cette grammaire
3. Calculer l'ensemble des suivants de cette grammaire
4. Établir la table d'analyse SLR
5. Donner l’analyse ascendante des expressions
3 + 4 * (5 - 2)
179
x * (y+ 3) - z/ 2
Approche ascendante (Bottom-up)
Exercice:
S -> E
E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | id | num
ε
1. Cette grammaire est-elle ambiguë?
Oui.
Elimination de la récursivité gauche
E -> E + T | E - T | T T -> T * F | T / F | F
E-> TE’ T->FT’
E’->+TE’|-TE’|ε T’->*FT’ | /FT’|ε

180
Approche ascendante (Bottom-up)
Exercice: S -> E
E -> T E'
S -> E E' -> + T E' | - T E' | ε
E -> E + T | E - T | T T -> F T'
T -> T * F | T / F | F T' -> * F T' | / F T' | ε
F -> ( E ) | id | num F -> ( E ) | id | num

Calculer l'ensemble des premiers de cette grammaire

Premiers(S)= Premiers(E)-ε= Premiers(T )-ε = Premiers(F )-ε ={ (,id, num}

Premiers(E)= Premiers(T )-ε = Premiers(F )-ε ={ (,id, num}
Premiers(E’)={ +, -, ε }
Premiers(T‘)= { *, /, ε }
Premiers(F)={ (, id, num }

181
Approche ascendante (Bottom-up)
Exercice: S -> E
E -> T E'
S -> E E' -> + T E' | - T E' | ε
E -> E + T | E - T | T T -> F T'
T -> T * F | T / F | F T' -> * F T' | / F T' | ε
F -> ( E ) | id | num F -> ( E ) | id | num

Calculer l'ensemble des suivants de cette grammaire

Suivants (S) = { $ }
Suivants (E)= Suivants (S) + { ) }={ ),$ }
Suivants (E’)= Suivants (E)=}={ ),$}
Suivants (T)= Premiers(E’)-ε+ Suivants(E) + Suivants(E’)= { +, -, ), $ }
Suivants (T’)=Suivants (T)={ +, -, ), $ }
Suivants (F)= Premiers(T’)- ε +Suivants(T) +Suivants(T’)= { +, -, *, /, ), $ }

182
Approche ascendante (Bottom-up)
S -> E
Exercice: E -> T E'
E' -> + T E' | - T E' | ε
T -> F T'
T' -> * F T' | / F T' | ε
F -> ( E ) | id | num

Établir la table d'analyse SLR

1.Augmentation
S’->S
S -> E
E -> T E'
E' -> + T E' | - T E' | ε
T -> F T'
T' -> * F T' | / F T' | ε
183
F -> ( E ) | id | num
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice:
5.E' -> - T E'

6.E' -> ε

7.T -> F T'

Établir la table d'analyse SLR 8.T' -> * F T'

9.T' -> / F T'

2. I={S’->S} 10.T' -> ε

11.F -> ( E )
3. I0=fermeture(I)=fermeture{S’->S}
12.F -> id
I0={S’->.S, S ->.E, E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}
13.F -> num
4. Δ (I0, X) X={S,E,T,F,(,id,num}
Δ (I0, S)={S’ ->S.}=I1
Δ (I0, E)={S ->E.}=I2
Δ (I0, T)={E ->T.E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.}=I3
Δ (I0, F)={T -> F.T‘, T' -> .* F T‘, T’->./ F T‘, T' -> .}=I4
Δ (I0, ()={F -> (.E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5
Δ (I0, id)={F->id.}=I6
Δ (I0, num)={F->num.}=I7
184
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice:
5.E' -> - T E'

I1={S’ ->S.} 6.E' -> ε

7.T -> F T'

Δ (I1, X) X={}
8.T' -> * F T'
---------------------------- 9.T' -> / F T'

I2={S ->E.} 10.T' -> ε

Δ (I2, X) X={} 11.F -> ( E )

12.F -> id
-----------------------
13.F -> num
I3={E ->T.E‘, E' -> .+ T E‘, E' -> .- T E‘, E' -> .}
Δ (I3, X) X={E’,+,-}
Δ (I3, E’)={E ->TE‘.}=I8
Δ (I3, +)={E' -> + .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I9
Δ (I3, -)={E' -> - .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I10

185
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice:
5.E' -> - T E'

6.E' -> ε

7.T -> F T'

I4={T -> F.T‘, T' -> .* F T‘, T’->./ F T‘, T' -> .} 8.T' -> * F T'

Δ (I4, X) X={T’,*,/} 9.T' -> / F T'

10.T' -> ε
Δ (I4, T’}={T -> FT‘.}=I12
11.F -> ( E )
Δ (I4, *}={T' -> * .F T‘, F -> .( E ), F->.id, F->. Num}=I13 12.F -> id

Δ (I4, /}={T’->/. F T‘, F -> .( E ), F->.id, F->. Num}=I14 13.F -> num

186
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I5={F -> (.E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num} 6.E' -> ε
Δ (I5, X) x={E,T,F,(,id,num} 7.T -> F T'

Δ (I5, E)={F -> (E. )}=I14 8.T' -> * F T'

Δ (I5, T)={E ->T .E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.}=I3 9.T' -> / F T'

10.T' -> ε
Δ (I5, F)={T -> F. T‘, T' -> .* F T‘, T’->./ F T‘, T’->.}=I4
11.F -> ( E )
Δ (I5, ()={F -> (. E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5
12.F -> id
Δ (I5, id)={F->id.}=I6
13.F -> num
Δ (I5, num)={F->num.}=I7
--------------------------------------------------------
I6={F->id.} x={}
----------------------------------
I7={F->num.} X={}
-----------------------------
I8={E ->TE‘.} X={}

187
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I9={E' -> + .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num} 6.E' -> ε
Δ (I9, X) x={T,F,(,id,num} 7.T -> F T'

Δ (I9, T)={E' -> + T. E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.}=I15 8.T' -> * F T'

Δ (I9, F)={T -> F. T‘, T' -> .* F T‘, T’->./ F T‘, T’->.}=I4 9.T' -> / F T'

10.T' -> ε
Δ (I9, ()={F -> (. E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5
11.F -> ( E )
Δ (I9, id)={F->id.}=I6
12.F -> id
Δ (I9, num)={F->num.}=I7 13.F -> num
-------------------------------------
I10={E' -> - .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}
Δ (I10, X) x={T,F,(,id,num}
Δ (I10, T)={E' -> -T. E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.}=I16
Δ (I10, F)={T -> F. T‘, T' -> .* F T‘, T’->./ F T‘, T’->.}=I4
Δ (I10, ()={F -> (. E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5
Δ (I10, id)={F->id.}=I6
Δ (I10, num)={F->num.}=I7 188
 1.S'-> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
----------------
6.E' -> ε
I11={T -> FT‘.}
7.T -> F T'
Δ (I11, X) x={}
8.T' -> * F T'
----------------
9.T' -> / F T'
I12 ={T' -> * .F T‘, F -> .( E ), F->.id, F->. Num}
10.T' -> ε
Δ (I12, X) x={F,(,id,num}
11.F -> ( E )
Δ (I12, F) ={T' -> * F .T‘,T' -> .* F T‘, T’->./ F T‘, T’->.}=I17 12.F -> id
Δ (I12, () ={F -> (. E ),E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5 13.F -> num
Δ (I12, id) ={F->id.}=I6
Δ (I12, num) ={F->Num.}=I7

189
 1.S'-> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I13={T’->/. F T‘, F -> .( E ), F->.id, F->. Num} 6.E' -> ε

Δ (I13, X) x={F,(,id,num} 7.T -> F T'

Δ (I13, F) ={T' -> / F .T‘,T' -> .* F T‘, T’->./ F T‘, T’->.}=I18 8.T' -> * F T'

Δ (I13, () ={F -> (. E ),E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I5 9.T' -> / F T'
10.T' -> ε
Δ (I13, id) ={F->id.}=I6
11.F -> ( E )
Δ (I13,num) ={F->Num.}=I7 12.F -> id
_____________________________________ 13.F -> num

I14={F -> (E. )}

Δ (I14, X) x={)}
Δ (I14, )) ={ F -> (E).}=I19

190
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I15={E' -> + T. E‘, E' -> .+ T E‘, E' -> .- T E‘} 6.E' -> ε

Δ (I15, X) x={E',+,-} 7.T -> F T'

Δ (I15, E') ={E' -> + TE‘.}=I20 8.T' -> * F T'

9.T' -> / F T'

Δ (I15, +) ={E' -> + .TE‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I9
10.T' -> ε
Δ (I15, -) ={E' -> -.TE‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I10
11.F -> ( E )
___________________ 12.F -> id
I16=E' -> -T. E‘, E' -> .+ T E‘, E' -> .- T E‘} 13.F -> num

Δ (I16, X) x={E',+,-}
Δ (I16, E') ={E' -> - TE‘.}=I21
Δ (I16, +) ={E' -> + .TE‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I9
Δ (I16, -) ={E' -> -.TE‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}=I10

191
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I17={T' -> * F .T‘,T' -> .* F T‘, T’->./ F T‘} 6.E' -> ε

Δ (I17, X) x={T',*,/} 7.T -> F T'

Δ (I17, T') ={T' -> * F T‘.}=I22 8.T' -> * F T'

9.T' -> / F T'

Δ (I17, *) ={T' -> *. F T‘, F -> .( E ), F->.id, F->. Num}=I12
10.T' -> ε
Δ (I17 ,/) ={T’->/ .F T‘, F -> .( E ), F->.id, F->. Num}=I13
11.F -> ( E )
___________________ 12.F -> id
I18={T' -> / F .T‘,T' -> .* F T‘, T’->./ F T‘} 13.F -> num

Δ (I18, X) x={T',*,/}
Δ (I18, T') ={T' -> / F T‘.}=I23
Δ (I18, *) ={T' -> *. F T‘,F -> .( E ), F->.id, F->. Num}=I12
Δ (I18, /) ={T’->/. F T‘, F -> .( E ), F->.id, F->. Num}=I13
___________________
I19={F -> (E).}
Δ (I19, X) x={}
192
 1.S' -> S
Approche ascendante (Bottom-up) 2.S->E

3.E -> T E'

4.E' -> + T E'

Exercice
5.E' -> - T E'
I20={E' -> + TE‘.} 6.E' -> ε

Δ (I20, X) x={} 7.T -> F T'

_________________ 8.T' -> * F T'

9.T' -> / F T'

I21={E' -> - TE‘.}
10.T' -> ε
Δ (I21, X) x={}
11.F -> ( E )
_________________ 12.F -> id
I22={T' -> * F T‘.} 13.F -> num

Δ (I22, X) x={}
_________________
I23={T' -> / F T‘.}
Δ (I23, X) x={}

193
 1.S' -> S
Δ (I0, S)=I1={S’ ->S.}
2.S->E
Δ (I0, E)=I2={S ->E.} 3.E -> T E'
Δ (I0, T)=I3={E ->T.E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.} 4.E' -> + T E'
Δ (I0, F)=I4={T -> F.T‘, T' -> .* F T‘, T’->./ F T‘, T’->.} 5.E' -> - T E'

Δ (I0, ()=I5={F -> (.E ), E ->.T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num} 6.E' -> ε
Δ (I0, id)=I6={F->id.} 7.T -> F T'

8.T' -> * F T'

Δ (I0, num)=I7={F->num.}
9.T' -> / F T'
Δ (I3, E')=I8={E ->TE‘.}
10.T' -> ε
Δ (I3, +)=I9={E' -> + .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num}
11.F -> ( E )
Δ (I3, -)=I10={E' -> - .T E‘, T -> .F T‘, F -> .( E ), F->.id, F->. Num} 12.F -> id
Δ (I4, T')=I11={T -> FT‘.} 13.F -> num
Δ (I4, *)=I12={T' -> * .F T‘, F -> .( E ), F->.id, F->. Num}
Δ (I4, /)=I13={T’->/. F T‘, F -> .( E ), F->.id, F->. Num} Δ (I14, ))=I19={ F -> (E).}
Δ (I5, E)=I14={F -> (E. )} Δ (I15, E')=I20={E' -> + TE‘.}
Δ (I9, T)=I15={E' -> + T. E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.} Δ (I16, E')=I21={E' -> - TE‘.}
Δ (I10, T)=I16={E' -> -T. E‘, E' -> .+ T E‘, E' -> .- T E‘, E’->.} Δ (I17, T')=I22={T' -> *F T‘.}
Δ (I12, F)=I17={T' -> * F .T‘,T' -> .* F T‘, T’->./ F T‘, T’->.} Δ (I18, T')=I23={T' -> / F T‘.}
Δ (I13, F)=I18={T' -> / F .T‘,T' -> .* F T‘, T’->./ F T‘, T’->.}
194
ite Action Succ
m + - * / ( ) $ id num S E E' T T' F
I0 d5 d6 d7 1 2 3 4
I1 acc
I2 r2
I3 d9 d10 r6 r6 8
I4 r10 r10 d12 d13 r10 r10 11
I5 d5 d6 d7 14 3 4
I6 r12 r12 r12 r12 r12 r12
I7 r13 r13 r13 r13 r13 r13
I8 r3 r3
I9 d5 d6 d7 15 4
I10 d5 d6 d7 16 4
I11 r7 r7 r7 r7
I12 d5 d6 d7 17

I13 d5 d6 d7 18

I14
d19
195
I15
d9 d10 r6 r6 20
ite Action Succ
m + - * / ( ) $ id num S E E' T T' F
I16 d9 d10 r6 r6 21
I17 r10 r10 d12 d13 r10 r10 22
I18 r10 r10 d12 d13 r10 r10 23
I19 r11 r11 r11 r11 r11 r11
I20 r4 r4
I21 r5 r5
I22 r8 r8 r8 r8
I23 r9 r9 r9 r9

196
l’analyse ascendante de 3 + 4 * (5 - 2)
Pile Entrée Sortie
$I0 3 + 4 * (5 - 2) $ d7
$I03I7 +4*(5-2)$ r13:F->num
$I0F +4*(5-2)$
$I0FI4 +4*(5-2)$ r10:T’->ε
$I0FI4T’ +4*(5-2)$
$I0FI4T’I11 +4*(5-2)$ r7:T->FT’
$I0T +4*(5-2)$
$I0TI3 +4*(5-2)$ d9
$I0TI3+I9 4*(5-2)$ d7
$I0TI3+I9 4 I7 *(5-2)$ r13:F->num
$I0TI3+I9 F *(5-2)$
$I0TI3+I9 FI4 *(5-2)$ d12
$I0TI3+I9 FI4*I12 (5-2)$ d5
$I0TI3+I9 FI4*I12(I5 5-2)$ d7
197
$I0TI3+I9 FI4*I12(I5 5 I7 -2)$ r13:F->num
l’analyse ascendante de 3 + 4 * (5 - 2)
Pile Entrée Sortie
$I0TI3+I9 FI4*I12(I5 5 I7 -2)$ r13:F->num
$I0TI3+I9 FI4*I12(I5 F -2)$
$I0TI3+I9 FI4*I12(I5 F I4 -2)$ r10:T’->ε
$I0TI3+I9 FI4*I12(I5 F I4 T’ -2)$
$I0TI3+I9 FI4*I12(I5 F I4 T’ I11 -2)$ r7:T->FT’
$I0TI3+I9 FI4*I12(I5 T -2)$
$I0TI3+I9 FI4*I12(I5 T -2)$
$I0TI3+I9 FI4*I12(I5 T I3 -2)$ d10
$I0TI3+I9 FI4*I12(I5 T I3 – I10 2)$ d7
$I0TI3+I9 FI4*I12(I5 T I3 – I10 2 I7 )$ R13: F->num
$I0TI3+I9 FI4*I12(I5 T I3 – I10 F )$
$I0TI3+I9 FI4*I12(I5 T I3 – I10 F I4 )$ r10: T’->ε
$I0TI3+I9 FI4*I12(I5 T I3 – I10 F I4 T’ )$
$I0TI3+I9 FI4*I12(I5 T I3 – I10 F I4 T’ I11 )$ r7:T->FT’
198
l’analyse ascendante de 3 + 4 * (5 - 2)
Pile Entrée Sortie
$I0TI3+I9 FI4*I12(I5 T I3 – I10 F I4 T’ I11 )$ r7:T->FT’
$I0TI3+I9 FI4*I12(I5 T I3 – I10 T )$
$I0TI3+I9 FI4*I12(I5 T I3 – I10 T I16 )$ r6:E’->ε
$I0TI3+I9 FI4*I12(I5 T I3 – I10 T I16 E’ )$
$I0TI3+I9 FI4*I12(I5 T I3 – I10 T I16 E’ I21 )$ r5:E’->-TE’
$I0TI3+I9 FI4*I12(I5 T I3 E’ )$
$I0TI3+I9 FI4*I12(I5 T I3 E’ I8 )$ r3:E->TE’
$I0TI3+I9 FI4*I12(I5 E )$
$I0TI3+I9 FI4*I12(I5 E I14 )$ d19
$I0TI3+I9 FI4*I12(I5 E I14 ) I19 $ r11: F->(E)
$I0TI3+I9 FI4*I12 F $
$I0TI3+I9 FI4*I12 F I17 $ r10:T’->ε
$I0TI3+I9 FI4*I12 F I17 T’ $
$I0TI3+I9 FI4*I12 F I17 T’ I22 $ r8: T’->*FT’
199
$I0TI3+I9 FI4 T’ $
l’analyse ascendante de 3 + 4 * (5 - 2)
Pile Entrée Sortie
$I0TI3+I9 FI4 T’ $
$I0TI3+I9 FI4 T’ I11 $ r7: T->FT’
$I0TI3+I9 T I15 $ r6:E’->ε
$I0TI3+I9 T I15 E’ $
$I0TI3+I9 T I15 E’ I20 $ r4: E’->+TE’
$I0TI3E’ $
$I0TI3E’ I8 $ r3: E->TE’
$I0 E $
$I0 E I2 $ r2: S->E
$I0 S $
$I0 S I1 $ Accept

200
l’analyse ascendante de
3 + 4 * (5 - 2)
x * (y+ 3) - z/ 2

201
l’analyse ascendante de x * (y+ 3) - z/ 2
Pile Entrée Sortie
$I0 x * (y+ 3) - z/ 2 $ d6
$I0 x I6 * (y+ 3) - z/ 2 $ r12:F->id
$I0 F * (y+ 3) - z/ 2 $
$I0 F I4 * (y+ 3) - z/ 2 $ d12
$I0 F I4 * I12 (y+ 3) - z/ 2 $ d5
$I0 F I4 * I12 ( I5 y+ 3) - z/ 2 $ d6
$I0 F I4 * I12 ( I5 y I6 + 3) - z/ 2 $ r12:F->id
$I0 F I4 * I12 ( I5 F + 3) - z/ 2 $
$I0 F I4 * I12 ( I5 F I4 + 3) - z/ 2 $ r10: T’->ε
$I0 F I4 * I12 ( I5 F I4 T’ + 3) - z/ 2 $
$I0 F I4 * I12 ( I5 F I4 T’ I11 + 3) - z/ 2 $ r7: T->FT’
$I0 F I4 * I12 ( I5 T + 3) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 + 3) - z/ 2 $ d9
$I0 F I4 * I12 ( I5 T I3 + I9 3) - z/ 2 $ d7
202
$I0 F I4 * I12 ( I5 T I3 + I9 3 I7 ) - z/ 2 $ r13:F->num
l’analyse ascendante de x * (y+ 3) - z/ 2
Pile Entrée Sortie
$I0 F I4 * I12 ( I5 T I3 + I9 3 I7 ) - z/ 2 $ r13:F->num
$I0 F I4 * I12 ( I5 T I3 + I9 F ) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 + I9 F I4 ) - z/ 2 $ r10:T’->ε
$I0 F I4 * I12 ( I5 T I3 + I9 F I4 T’ ) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 + I9 F I4 T’ I11 ) - z/ 2 $ r7:T->FT’
$I0 F I4 * I12 ( I5 T I3 + I9 T ) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 + I9 T I15 ) - z/ 2 $ r6: E’->ε
$I0 F I4 * I12 ( I5 T I3 + I9 T I15 E’ ) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 + I9 T I15 E’ I20 ) - z/ 2 $ r4:E’->+TE’
$I0 F I4 * I12 ( I5 T I3 E’ ) - z/ 2 $
$I0 F I4 * I12 ( I5 T I3 E’ I8 ) - z/ 2 $ r3:E->TE’
$I0 F I4 * I12 ( I5 E ) - z/ 2 $
$I0 F I4 * I12 ( I5 E I14 - z/ 2 $ d19
$I0 F I4 * I12 ( I5 E I14 ) I19 - z/ 2 $ r11:F->(E)
203
l’analyse ascendante de x * (y+ 3) - z/ 2
Pile Entrée Sortie
$I0 F I4 * I12 ( I5 E I14 ) I19 - z/ 2 $ r11:F->(E)
$I0 F I4 * I12 F - z/ 2 $
$I0 F I4 * I12 F I17 - z/ 2 $ r10:T’->ε
$I0 F I4 * I12 F I17 T’ - z/ 2 $
$I0 F I4 * I12 F I17 T’ I22 - z/ 2 $ r8:T’->*FT’
$I0 F I4 T’ I11 - z/ 2 $ r7:T->FT’
$I0 T - z/ 2 $
$I0 T I3 - z/ 2 $ d10
$I0 T I3 – I10 z/ 2 $ d6
$I0 T I3 – I10 z I6 /2$ r12:F->id
$I0 T I3 – I10 F /2$
$I0 T I3 – I10 F I4 /2$ d13
$I0 T I3 – I10 F I4 / I13 2$ d7
$I0 T I3 – I10 F I4 / I13 2 I7 $ r13: F->num
204
l’analyse ascendante de x * (y+ 3) - z/ 2
Pile Entrée Sortie
$I0 T I3 – I10 F I4 / I13 2 I7 $ r13: F->num
$I0 T I3 – I10 F I4 / I13 F $
$I0 T I3 – I10 F I4 / I13 F I18 $ r10:T’->ε
$I0 T I3 – I10 F I4 / I13 F I18 T’ $
$I0 T I3 – I10 F I4 / I13 F I18 T’ I23 $ r9: T’->/FT’
$I0 T I3 – I10 F I4 T’ $
$I0 T I3 – I10 F I4 T’ I11 $ r7:T->FT’
$I0 T I3 – I10 T $
$I0 T I3 – I10 T I16 $ r6: E’->ε
$I0 T I3 – I10 T I16 E’ $
$I0 T I3 – I10 T I16 E’ I21 $ r5:E’->-TE’
$I0 T I3 E’ $
$I0 T I3 E’ I8 $ r3:E->TE’
$I0 E $ 205
l’analyse ascendante de x * (y+ 3) - z/ 2
Pile Entrée Sortie
$I0 E I2 $ r2:S->E
$I0 S $
$I0 S I1 $ accept

206