Chapitre 3

Analyse syntaxique

3.1 Introduction

On associe, à tout langage de programmation, un ensemble de règles qui spécient la

structure syntaxique d'un programme correctement écrit dans ce langage. Les structures
syntaxiques des langages de programmation sont trop complexes pour être décrites par des
expressions régulières. À titre d'exemple, les expressions régulières ne permettent pas de
distinguer entre une expression arithmétique correctement parenthésée et une expression
arithmétique mal parenthésée. On fait alors recours à un outil théorique plus puissant, qui
sont les grammaires dites hors-contextes. Ces dernières permettent de décrire comment
les unités lexicales, identiées lors de l'analyse lexicale, peuvent être agencées entre elles
pour former des instructions syntaxiquement correctes.
3.2 Grammaire et arbre de dérivation

Commençons par dénir l'outil théorique sur lequel s'appuie l'analyse syntaxique.
Dénition 1 Une grammaire est dénie par un quadruplet G=(V , V , S, R), où :
T N

1. VT est un ensemble non vide de symboles terminaux,

2. VN est un ensemble de symbole non-terminaux,
3. S , qui est un élément de VN , est le symbole de départ,
4. R est un ensemble de règles de production. Chaque règle est un couple de
mots noté α → β , où α ∈ (VT ∪ VN )+ et β ∈ (VT ∪ VN )∗ .

Une grammaire permet de générer (de construire) les mots d'un langage donné en appli-
quant les règles de production à partir du symbole de départ. L'application d'une règle
α → β permet de remplacer le mot α par le mot β .

Remarque : si dans une grammaire G, la partie gauche de toute règle se réduit à un

simple symbole de V alors G est dite hors contexte.
N

Exemple d'une grammaire hors contexte :

1
  V = {a, b} ;
 V = {S} ;
T

 S est le symbole de départ.

N

 R = {S → aSb, S → ε} ;
On peut aisément vérier que cette grammaire est hors-contexte. Par ailleurs, le mot aabb
peut être généré par cette grammaire. En eet, aabb peut être obtenu, à partir du symbole
de départ S, par trois applications de règles :
étape mot règle appliquée
1 S S → aSb
2 aSb S → aSb
3 aaSbb S → 
4 aabb
Dénition 2 On appelle dérivation l'application d'une ou plusieurs règles de la
grammaire à partir d'un mot de (VT ∪ VN )+ .

Notations :
 La notation → désignera une dérivation obtenue par une seule application de règle.
 La notation → désignera une dérivation obtenue par n applications de règles, avec
∗

n ≥ 0.
 La notation → désignera une dérivation obtenue par, au moins, une application de
+

règle.
Exemple : soit la grammaire suivante, (la donnée des règles de la grammaire est souvent
susante pour dénir toute la grammaire) :


 E → EOE
E → T

 O → *|+|-|/
0-9

T →


Les deux suites de dérivations suivantes génèrent le mot 5 + 7 :

E → EOE → T OE → 5OE → 5+E → 5+T → 5+7

est une dérivation gauche car on applique les règles en priorité sur le non-terminal le plus
à gauche.
E → EOE → EOT → EO7 → E +7 → T +7 → 5+7

est une dérivation droite car on applique les règles en priorité sur le non-terminal le plus
à droite.
Dénition 3 Étant donné une grammaire G, on dénotera par L(G) le langage
généré par G : L(G) = {ω ∈ V | S → ω}.
T
∗ ∗

Exemple : le langage généré par la première grammaire de ce chapitre est a b . n n

2
 Dénition 4 On appelle arbre de dérivation ou arbre syntaxique tout arbre tel que
1. la racine de l'arbre est le symbole de départ ;
2. les feuilles sont les symboles terminaux ;
3. les n÷uds internes sont des symboles non terminaux ;
4. les ls d'un n÷ud X sont α0 , . . . , αn si est seulement si X → α0 . . . αn est
une règle de la grammaire avec αi ∈ (VT ∪ VN ).

Arbre de dérivation pour le mot 5 + 7 :

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

Exemple : considérons la grammaire suivante :

if (expr) instr else instr

 instr →
if (expr) instr

instr →

 instr → return(expr)
true | false

expr →


Cette grammaire est ambigüe. En eet, le mot if (true) if (false) return(true)

else return(false) a deux arbres de dérivation, qui sont les suivantes :

3
Comme de telles mots ont habituellement des signications diérentes, (selon la façon de
leur génération), on a besoin de travailler avec des grammaires non ambigües.
L'analyseur syntaxique obtient une séquence d'unités lexicales de l'analyseur lexical
et vérie si la séquence reçue peut être générée par la grammaire du langage source. Si
c'est le cas alors la séquence reçue est syntaxiquement correcte, sinon il y a une erreurs
syntaxique que l'analyseur syntaxique devra signaler au programmeur.
On distingue deux types d'analyseur syntaxique :
 ceux qui eectuent une analyse descendante et
 ceux qui eectuent une analyse ascendante.
3.3 Analyse descendante

Cette méthode d'analyse construit l'arbre syntaxique du haut (de la racine qui correspond
au symbole de départ de la grammaire) vers le bas (vers les feuilles qui correspondent au
4
unités lexicales).
Soit la grammaire suivante :
S → aS | bS | ε
Supposons que nous voulons générer le mot aba. Pour savoir quelle règle appliquer à
chaque étape du processus de génération, il sut de connaître le symbole à générer. En
eet, au départ on veut obtenir un `a', on doit donc appliquer la première règle.
S → aS
Ensuite, on veut obtenir un `b', on applique donc la deuxième règle :
aS → abS
puis de nouveau la première règle pour avoir le deuxième `a' :
abS → abaS
Enn, on applique la troisième règle pour se débarrasser du symbole non-terminal S :
abaS → aba
En général, la génération d'un mot par une grammaire n'est pas toujours aussi simple.
Reprenons la grammaire des expressions arithmétiques simples, a titre d'exemple. Si on se
limite à ne regarder qu'un seul symbole à la fois, celui qu'on veut générer, on ne saura pas
quelle règle appliquer, au départ, pour générer le mot 5 + 7. En eet, le premier symbole
du mot, qui est 5, ne permet pas de choisir entre les règles E → EOE et E → T . Pour
choisir la bonne règle, il faut lire le deuxième symbole du mot (+). Ceci permet d'éliminer
la règle E → T qui ne permet pas d'avoir le symbole +. Mais si l'on s'impose la contrainte
de ne regarder qu'un seul symbole à la fois, alors il faut remplacer la grammaire par une
autre grammaire équivalente, mais qui est conçue de telle sorte qu'à chaque étape, il n'y
a qu'une seule règle applicable. Cependant, la conception d'une telle grammaire n'est pas
toujours possible.
3.3.1 Table d'analyse LL(1)

La technique utilisée en compilation pour éviter d'essayer toutes les règles applicables,
à chaque pas de l'analyse syntaxique, consiste à construire une table qui, étant donné
le symbole à générer, détermine de manière unique la règle à appliquer. Une tel table
s'appelle table d'analyse.
La construction de la table d'analyse dite LL(1) nécessite le calcul de deux ensembles :
premier et suivant, pour des symboles de la grammaire ou des mots construit à partir de
ces symboles.
Les ensembles premier
Dénition 6 Soit α ∈ (VT ∪ VN )∗ , l'ensemble premier(α) est déni par
premier(α) = {α ∈ V
0
T
∗
∪ {} | α → α0 β, avec β ∈ (VT ∪ VN )∗ }

5
Ce sont donc les symboles terminaux qui peuvent commencer un mot se dérivant de α,
plus le mot vide si α → ε.
∗

Remarque : on a premier(a) = {a}, pour tout a ∈ V . T

Exemple : pour la grammaire de l'exemple des expressions arithmétiques, on a premier(E) =

premier(T ) = {0,1,...,9}.
Algorithme de calcul de l'ensemble premier pour tout X ∈ (V ∪ VN ) .
Donnée : une grammaire G = (VT , VN , S, R)
T

1: pour tout a ∈ VT faire premier[a] := {a}

2: pour tout X ∈ VN faire premier[X] := ∅
3: pour tout X → ε ∈ R faire premier[X] := {ε}
4: pour tout X → Y1 Y2 . . . Yn ∈ R faire
si (ε ∈ premier[Yi ], i : 1, . . . , n) alors premier[X] := {ε}
5: pour tout X → Y1 Y2 . . . Yn ∈ R faire
pour tout j, 1 ≤ j ≤ n tq ε ∈ premier[Yi ], i : 1, . . . , j − 1 faire
premier[X] := premier[X] ∪ (premier[Y ] \ {ε}) j

6 : Répéter l'étape 4 tant qu'il y a des changements

Exemple : soit la grammaire suivante


 E → T E0
+T E 0 | -T E 0 | ε

 E0 →


T → FT0
T0 → *F T 0 | /F T 0 | ε



(E ) | nb

F →


On a les ensembles premier suivants :

V premier
E ( nb
N

E' + - ε
T ( nb
T' * / ε
F ( nb
L'algorithme exposé ci-dessus calcule l'ensemble premier pour de simples symboles, alors
que l'on a besoin de connaître les ensembles premier associés à des mots. Pour ce faire, on
a la fonction récursive suivante, qui calcule l'ensemble Premier(α), pour α ∈ (V ∪ V ) . T N
∗

6
 Fonction Premier(α : mot, premiers : ensembles premier)
// avec α = α α . . . α et α ∈ (V ∪ V ).
// premier = les ensembles premier, pour tout symbole X ∈ (V .
1 2 n i T N
T ∪ VN )

si α = ε alors
retourner({ε})
sinon
si α1 ∈ VT alors
retourner({α1 })
sinon
si ε ∈ premier(α1 ) alors
retourner((premier[α1 ] \ {ε}) ∪ Premier(α2 . . . αn ))
sinon
retourner(premier[α1 ])

Exemple : avec la grammaire des expressions arithmétiques préxées, on a Premier(E 0 F ) =

{+,-,(,nb} .
Les ensembles suivant
Dénition 7 Pour tout symbole non-terminal A, on déni suivant(A) qui est l'en-
semble de tous les symboles terminaux a ∈ VT qui peuvent apparaître immédiatement
à droite de A dans une dérivation :

suivant(A) = {a ∈ V | S → αAaβ avec α, β ∈ (V ∪ V ) }

T
∗
T N
∗

Remarque : Avant de commencer l'analyse, on ajoute au mot qu'on veut analyser un

symbole particulier ($) indiquant la n du mot. Ce symbole $ est automatiquement ajouté
aux suivants du symbole de départ de la grammaire.
Algorithme de calcul de l'ensemble suivant pour A ∈ VN .
Données : une grammaire G = (VT , VN , S, R)
1: suivant[S] := {$}
2: pour chaque B ∈ V \ {S} faire suivant[B] := ∅
pour chaque règle A → αBβ faire
N
3:
suivant[B] := suivant[B] ∪ (Premier(β) \ {ε})
4 : Répéter
5: pour chaque règle A → αB faire
suivant[B] := suivant[B] ∪ suivant[A]
6: pour chaque règle A → αBβ , avec ε ∈ Premier(β) faire
suivant[B] := suivant[B] ∪ suivant[A]
7 : Jusqu'à(plus de changement)

Exemple : reprenons la grammaire des expressions arithmétiques préxées. On a :

7
 VN premier suivant
E ( nb $ )
E' + -ε $ )
T ( nb + - ) $
T' * /ε + - ) $
F ( nb * / ) + - $

Construction de la table d'analyse LL(1) Une table d'analyse LL(1) est un tableau
M a deux dimensions qui indique, pour chaque symbole terminal a de la grammaire (ou
$), la règle de production à appliquer pour générer ce symbole.

Algorithme de construction de la table LL(1)

Données : une grammaire G
1 : M := ∅
2 : pour toute regle
A→α de G faire
3: pour tout Premier
a∈ (α) et a 6= ε faire
4: M [A, a] := M [A, a] ∪ {A → α}
5: si ε ∈ Premier(α) alors
6: pour tout suivant
b∈ [A] faire
7: M [A, b] := M [A, b] ∪ {A → α}

Exemple : table d'analyse LL(1) de la grammaire de l'exemple précédent :

nb + - * / ( ) $
E E TE' → E TE'→
E' E'→+TE' E'→-TE' E'→ ε E'→ ε
T T→FT' T→FT'
T' T'→ ε T'→ ε T'→*FT' T'→/FT' T → ε T'→ ε
0

F F→nb F→(E)
Remarque : chaque case vide de la table LL(1) correspond à une erreur syntaxique.

3.3.2 Analyse syntaxique LL(1)

La table d'analyse LL(1) est utilisée par l'algorithme suivant pour déterminer si un mot
ω donné peut être généré par la grammaire correspondant à la table LL(1).

8
 Algorithme d'analyse LL(1)
Donnée : mot ω à la n duquel on ajoute le symbole $, table d'analyse M
1: Empiler (P, $, S)
2 : i := 0
3: erreur := faux
4: accepter := faux
5 : Répéter
6: X := Dépiler (P )
7: a := ω[i]
8: si X ∈ VN alors
9: si M [X, a] = X → Y1 . . . Yn alors
10 : Empiler (P, Yn , . . . , Y1 )
11 : sinon
12 : erreur := vrai
13 : sinon
14 : si X = $ alors
15 : si a = $ alors accepter := vrai sinon erreur := vrai
16 : sinon
17 : si X = a alors i := i + 1 sinon erreur := vrai
18 : Jusqu'a (erreur accepter)
ou

Exemple
Pour la grammaire précédente et le mot 3 + 4 * 5, qui est transformé en nb + nb * nb
lors de l'analyse lexicale, on obtient l'analyse suivantes :
Pile mot sortie
$E nb+nb*nb$ E→TE'
$E'T nb+nb*nb$ T→FT'
$E'T'F nb+nb*nb$ F→nb
$E'T'nb nb+nb*nb$
$E'T' +nb*nb$ T'→ ε
$E' +nb*nb$ E'→+TE'
$E'T+ +nb*nb$
$E'T nb*nb$ T→FT'
$E'T'F nb*nb$ F→nb
$E'T'nb nb*nb$
$E'T' *nb$ T'→*FT'
$E'T'F* *nb$
$E'T'F nb$ F→nb
$E'T'nb nb$
$E'T' $ T'→ ε
$E' $ E'→ ε
$ $ Accepté

9
Extraction de l'arbre syntaxique
Si l'application de l'algorithme d'analyse réussit à générer le mot en question, on peut
obtenir l'arbre syntaxique de ce dernier en eectuant une dérivation gauche à partir du
symbole de départ en appliquant les règles utilisées par l'algorithme d'analyse. Ainsi pour
le mot 3 + 4 * 5, on obtient l'arbre suivant :

3.3.3 Grammaire LL(1)

L'algorithme précédent ne peut fonctionner que si la grammaire possède certaines proprié-

tés qui garantissent que dans la table d'analyse LL(1), on ne peut avoir plus d'une règle
par case. Dans le cas contraire, on ne saura pas quelle règle appliquer à chaque itération
de l'algorithme d'analyse LL(1).
Dénition 8 On appelle grammaire LL(1) une grammaire pour laquelle chaque
case de la table d'analyse LL(1) contient, au plus, une règle de production.

L'une des causes qui font qu'une grammaire n'est pas LL(1) est qu'elle soit ambigüe. Mais
c'est pas l'unique cause.
3.3.4 Grammaire propre

Dénition 9 Une grammaire est dite propre si elle ne contient aucune règle de la
forme A → ε.

Une grammaire non propre peut être transformée en une grammaire propre équivalente
en appliquant l'algorithme suivant :

10
 Algorithme d'obtention d'une grammaire propre
Données : grammaire G
1: pour chaque règle A → ε de G faire
2: pour chaque règle B → αAβ de G faire
3: Ajouter la règle B → αβ
4: Supprimer A → ε
Exemple : pour la grammaire

S → Aa
A → Sb | ε

On obtient :

S → Aa | a
A → Sb

3.3.5 Récursivité à gauche

Une autre cause qui fait qu'une grammaire ne soit pas LL(1) est qu'elle soit récursive à
gauche. Il y a deux niveaux de récursive à gauche.
Dénition 10 Une grammaire est immédiatement récursive à gauche si elle
contient une règle de la forme A → Aα, où A ∈ VN et α ∈ (VT ∪ VN )∗ .

Exemple : la grammaire suivante est immédiatement récursive à gauche bien qu'elle soit
non ambigüe.

 A → A ou B | B
B → B et C | C

C → non C | (A) | vrai | faux

Algorithme d'élimination de la récursivité immédiate à gauche

Donnée : une grammaire G
1. Remplacer tout ensemble de règles de la forme A → Aα | β 1 | . . . | βn par
A → β1 A0 | . . . |βn A0


A0 → αA0 | ε

2. Répéter l'étape 1 autant que possible

Remarque : La grammaire ainsi obtenue n'est pas immédiatement récursive à gauche
est équivalente à la grammaire initiale.

11
 Dénition 11 Une grammaire est récursive à gauche si elle permet d'avoir une
dérivation A → Aα, où A ∈ VN et α ∈ (VT ∪ VN )∗ .
+

Exemple : Soit la grammaire G suivante


S → Aa
A → Sb | ε

On peut avoir la dérivation S → Aa → Sba, donc S → Sba. Par conséquent G est +

récursive à gauche.
Algorithme d'élimination de la récursivité à gauche
Donnée : une grammaire propre G
1 : Ordonnez les non-terminaux A , A , . . . , A
2 : pour i de 1 a n faire
1 2 n

3: pour j de 1 a i − 1 faire
4: Remplacer chaque groupe de règles de la forme A → A α | γ,
où A → β | . . . |β , par A → β α| . . . |β α | γ
i j
5:
Éliminer la récursivité immédiate a gauche des règles partant de A
j 1 p i 1 p
6: i

Remarque : si la grammaire de départ est propre (ne contient pas de règle A → ε)

alors la grammaire obtenue par ce dernier algorithme n'est pas récursive à gauche et est
équivalente à la grammaire initiale. Par contre, si la grammaire en entrée n'est pas propre,
l'algorithme ci-dessus peut donner un résultat faut, comme c'est le cas pour la grammaire
suite :

 A → Ba | a
B → CA
C → ε


Exemple : dérécursication de la grammaire suivante :


A → Aa | B | a
B → A|b
Ordre : A, B
Remplacer A → Aa|B|a par A → BA | aA et A → aA |ε
0 0 0 0

Remplacer B → A|b par B → BA | aA | b qui a leur tour sont remplacées par B →

0 0

aA B |bB et B → A B |ε. On obtient :

0 0 0 0 0 0



 A → aA0 | BA0
 0
A → aA0 | ε

 B → aA0 B 0 | bB 0
 0
B → A0 B 0 | ε

12
3.3.6 Factorisation à gauche

Cette action vise à supprimer les choix multiples de règle. Le principe est de regrouper les
règles qui partent d'un même symbole non-terminal et qui ont un préxe commun dans
leur partie droite : A → αβ | αβ . Dans ce cas, le préxe commun est α et les règles sont
0

remplacées par A → αA et A → β|β , où A est un nouveau symbole.

0 0 0 0

Algorithme factorisation à gauche

Donnée : une grammaire G
1: Répéter
2: pour chaque A ∈ VN faire
3: trouver le plus long préxe α commun à des règles partant de A
4: si α 6=  alors
5: Remplacer A → αβ | . . . |αβ |γ | . . . |γ
par A → αA |γ | . . . |γ et A → β | . . . |β
1 n 1 p
0 0

6 : Jusqu'à (pas de changement)

1 p 1 n

Exemple : Soit la grammaire suivante


A → Bca|Bcb|Bd|d
B → b|ε

En appliquant l'algorithme de factorisation à gauche on obtient :


 A → BcA0 |Bd|d
A0 → a|b
B → b|ε


Puis


 A → BB 0 |d
 0
B → cA0 |d

 A0 → a|b
B → b|


3.3.7 Démarche pour une analyse descendante

Si une grammaire est LL(1) alors l'analyse syntaxique peut se faire de manière descen-
dante. Il reste donc à savoir si la grammaire en question est LL(1).
Theorem 1 Une grammaire ambigüe, récursive à gauche ou non factorisé à gauche
n'est pas LL(1).

Étant donné une grammaire, on peut procéder comme suit :

13
 1. rendre la grammaire non ambigüe (pas d'algorithme)
2. rendre la grammaire propre
3. éliminer la récursivité à gauche
4. factoriser à gauche
5. construire la table d'analyse et vérier qu'elle est LL(1)
6. si c'est le cas, eectuer l'analyse
7. sinon il faut penser à une autre méthode d'analyse : l'analyse ascendante

3.4 Analyse ascendante

Contrairement à l'analyse descendante, une analyse ascendante procède en construisant

un arbre syntaxique du bas (les feuilles qui sont les unités lexicales) vers le haut (la racine
qui est le symbole de départ de la grammaire). Pour ce faire, une analyse ascendante
eectue, à chaque pas de l'analyse, un décalage ou une réduction.
 Un décalage consiste à avancer un pointeur qui pointe vers les symboles du mot
d'entré d'une position vers la droite.
 Une réduction consiste à remplacer une suite de symboles se trouvant à gauche du
pointeur et correspondant à la partie droite d'une règle de production de la gram-
maire par le symbole non-terminal constituant la partie gauche de cette même règle.
Exemple : on veut générer le mot nb*(nb+nb) par la grammaire suivante
 E → E+T |T


T → T *F |F
F → (E ) | nb


On peut eectuer l'analyse suivante : 1

1. La position du pointer est indiquée par des symboles en caractère gras.

14
 mot action
nb*(nb+nb) on réduit en utilisant la règle F → nb
F*(nb+nb) on réduit en utilisant la règle T → F
T*(nb+nb) on décale
T*(nb+nb) on décale
T*(nb+nb) on décale
T*(nb+nb) on réduit en utilisant la règle F → nb
T*(F+nb) on réduit en utilisant la règle T → F
T*(T+nb) on réduit en utilisant la règle E → T
T*(E+nb) on décale
T*(E+nb) on décale
T*(E+nb) on réduit en utilisant la règle F → nb
T*(E+F) on réduit en utilisant la règle T → F
T*(E+T) on réduit en utilisant la règle E → E+T
T*(E) on décale
T*(E) on réduit en utilisant la règle F → (E)
T*F on réduit en utilisant la règle T → T *F
T on réduit en utilisant la règle E → T
E accepter
Le choix entre eectuer une réduction ou un décalage n'est pas toujours unique. En eet,
dans à l'étape 1 par exemple, on a réduit alors que l'on aurai pu décaler. A l'inverse, à
l'étape 3, on a décalé alors qu'il était possible de réduire en utilisant la règle E → T . Il est
donc indispensable d'avoir une table d'analyse qui indique si l'on doit décaler ou réduire,
et dans le cas où il faut déduire, par quelle règle?
3.4.1 Table SLR

Les analyseurs ascendants les plus connus sont dans la classe paramétrée dite LR(k). Ce
sont des analyseurs qui lisent le ot en entrée de gauche a droite (d'où le L dans LR)
pour reconstruire une dérivation droite (d'où le R dans LR). La classe des grammaires
LR(k) est plus grande que la classe LL(1). Heureusement, la classe LR(1) est largement
susante pour les langages de programmation modernes. Cependant, an de simplier
l'analyse ascendante, on distingue les grammaires SLR (simple LR), qui constituent une
classe de grammaires comprise entre la classe LR(0) et la classe LR(1).
Une analyse impliquant une grammaire SLR s'appuie également sur une table d'ana-
lyse. Une table SLR nous indique à chaque étape quelle action eectuer, un décalage
ou une réduction. Si c'est une réduction, la table nous indique la règle à appliquer. Sa
construction nécessite le calcul des ensemble premier et suivant. On a également besoin
de calculer ce que l'on appelle des fermetures d'ensemble d'item.
Un item est une règle de la grammaire à laquelle on ajoute un point quelque part dans
la partie droite. Donc si A → αβ est une règle d'une grammaire alors A → α.β est un
item de la même grammaire.
En partant d'un ensemble d'items, on peut calculer ce que l'on appelle la fermeture
de cette ensemble, par l'algorithme suivant :

15
 Algorithme du calcul de la fermeture d'un ensemble d'items
Donnée : un ensemble d'items I .
1 : F := I
2 : Répéter
3: pour chaque item i ∈ F de la forme A → α.Bβ faire
4: pour chaque regle B → γ faire
5: F := F ∪ {B → .γ}
6 : Jusqu'à (pas de changement)
Exemple : Pour la grammaire précédente et l'ensemble d'item I = {E → E .+T, T →
T *.F }, on obtient : Fermeture(I) = {E → E .+T, T → T *.F, F → .(E ), F → .nb}

Transition par un symbole d'un ensemble d'items

Étant donné un ensemble d'items I et un symbole X ∈ (V ∪ V ), on déni la fonction
suivante :
T N

∆(I, X) = Fermeture({A → αX .β | A → α.Xβ ∈ I})

Exemple : pour la grammaire précédente et pour l'ensemble d'item I = {T → T *.F, E →

E .+T }, on a :
∆(I, F ) = {T → T *F .}
∆(I, +) = {E → E +.T, T → .T *F, T → .F, F → .(E ), F → .nb}

Algorithme de calcul de la collection des ensembles d'items

Donnée : une grammaire G
1: Ajouter un nouveau symbole de départ et la regle S → S
S0 0

Fermeture
2 : I0 := ({S → .S})
0

3 : C := {I0 }
4 : Répéter
5: pourchaque I ∈ C faire
6: pour chaque X ∈ (VN ∪ VT ) tq ∆(I, X) 6= ∅ faire
7: C := C ∪ {∆(I, X)}
8 :Jusqu'à (pas de changement)
Exemple : Considérons toujours la même grammaire. On obtient la collection d'items
suivants :

16
 I0 = Fermeture(E → .E)
0
...
∆(I0 , E) = Fermeture({E → E., E → E.+T }) ={E → E., E → E.+T } = I
0 0

= Fermeture({E → T ., T → T .*F }) = {E → T ., T → T .*F } = I

1
∆(I0 , T )
= Fermeture({T → F .})
2
∆(I0 , F ) = {T → F .} = I
= Fermeture(∅)
3
∆(I0 , +) =∅
∆(I0 , *) = Fermeture(∅) =∅
∆(I0 , () = Fermeture({F → (.E)}) ...
∆(I0 , )) = Fermeture(∅) =∅
∆(I0 , nb) = Fermeture({F → nb.}) = {F → nb.}
Construction de la table SLR
La table SLR est un tableau à deux entrées. Chaque ligne correspond à un item de la
collection d'items de la grammaire. Chaque colonne correspond un un symbole terminal
ou non-terminal de la grammaire plus le symbole $.
Algorithme de construction de la table SLR
Donnée : une grammaire G
1 : Calculer la collection d'item I , . . . , I de G
2 : pour chaque I faire
0 n

pour chaque ∆(I , a) = I faire

i
3:
Mettre `décaler et aller à j' dans la case M [i, a]
i j
4:
5: pour chaque ∆(I , A) = I faire
Mettre `aller à j' dans la case M [i, a]
i j
6:
7: pour chaque A → α. ∈ I tq A 6= S faire 0

Mettre `réduire par A → α' dans toute case M [i, a], où a ∈ suivant[A]
i
8:
9: si S → S . ∈ I alors mettre `accepter ' dans la case M [i, $]
0
i

Exemple : toujours pour la même grammaire, on calcul les ensembles premier et suivant
V premier suivant
E ( nb $ + )
N

T ( nb + * ) $
F ( nb + * ) $
Puis, on numérote les règles
 (1) E → E +T (2) E → T


(3) T → T *F (4) T → F
(5) F → (E ) (6) F → nb


Enn, on construit la table SLR

17
 état nb + * ( ) $ E T F
0 d5 d4 1 2 3
1 d6 acc
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 8 2 3
5 r6 r6 r6 r6
6 d5 d4 9 3
7 d5 d4 10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
3.4.2 Algorithme d'analyse ascendante

Comme nous l'avons signaler précédemment, les grammaires SLR (simple LR) sont des
grammaires plus puissantes que les grammaires LR(0) mais moins puissantes que les gram-
maires LR(1). Toutefois, ces grammaires susent pour analyser la plupart des langages
de programmation.
Dénition 12 On appelle grammaire SLR une grammaire pour laquelle chaque
case de la table d'analyse SLR contient, au plus, une action.

L'analyse ascendante SLR d'un mot utilise une pile et un pointeur qui marque le
symbole courant du mot à analyser. La pile sert a stocker non seulement les symboles
mais aussi les états. L'algorithme de cette analyse est le suivant :

18
 Algorithme Analyse Ascendante SLR
données : un mot ω, table d'analyse SLR, M
1: Empiler (P, 0)
2 : k := 0
3: erreur := faux
4: accepter := faux
5 : Répéter
6: X := Dépiler (P )
7: a := ω[k]
8: si X ∈ VN alors
9: Dépiler
i := (P )
10 : `aller a '
si M [i, X] = j alors
11 : Empiler (P, i, X, j)
12 : sinon
13 : erreur := vrai
14 : sinon // X est un état
15 : `décaler et aller a '
si M [X, a] = j alors
16 : Empiler (P, X, a, j)
16 : k := k + 1
17 : sinon
18 : `réduire par
si M [X, a] = 'A → α alors
19 : Dépiler tout les symboles de et les états qui les séparent
α
20 : Empiler (P, A)
21 : sinon
22 : `accepter'
si M [X, a] = alors
23 : accepter := vrai
24 : sinon
25 : erreur := vrai
26 : Jusqu'à (erreur accepter)
ou

Exemple : Analyse SLR du mot nb+nb*nb.

19
 pile mot action
0 nb+nb*nb$ d5
0nb5 +nb*nb$ r6
0F +nb*nb$ 3
0F3 +nb*nb$ r4
0T +nb*nb$ 2
0T2 +nb*nb$ r2
0E +nb*nb$ 1
0E1 +nb*nb$ d6
0E1+6 nb*nb$ d5
0E1+6nb5 *nb$ r6
0E1+6F *nb$ 3
0E1+6F3 *nb$ r4
0E1+6T *nb$ 9
0E1+6T9 *nb$ d7
0E1+6T9*7 nb$ d5
0E1+6T9*7nb5 $ r6
0E1+6T9*7F $ 10
0E1+6T9*7F10 $ r3
0E1+6T $ 9
0E1+6T9 $ r1
0E $ 1
0E1 $ accepté

3.4.3 Démarche pour une analyse ascendante

Les étapes à suivre pour eectuer une analyse ascendante sont les suivantes :
1. Trouver une grammaire non-ambiguë équivalente.
2. Calculer la collection des ensembles d'item de la grammaire.
3. Calculer les ensemble premier et suivant.
4. Construire la table SLR.
5. s'il y a, au plus, une action par case alors eectuer l'analyse,
6. sinon on peut, parfois, dénir des priorités entre les actions se trouvant dans une
même case de la table SLR et eectuer, comme même, une analyse SLR.
3.5 Erreurs syntaxiques

Que ce soit lors d'une analyse descendante ou lors d'une analyse ascendante, si l'algo-
rithme d'analyse accède à une case vide de la table d'analyse alors le programme analysé
contient une erreur syntaxique. Le compilateur doit signaler de telles erreurs de la manière
la plus claire possible. Ainsi, les cases vides de la table d'analyse sont remplies par des
pointeurs vers des routines de gestion d'erreurs. Chaque fois que l'algorithme d'analyse
accède à une case vide, la routine correspondant à cette case est exécutée. Ce sont ces
routines qui achent les messages d'erreurs que le programmeur utilise pour corriger son
programme.
20
Exemple : reprenons la grammaire des expressions arithmétique. La table SLR avec rou-
tine d'erreurs de cette grammaire est :
état nb + * ( ) $ E T F
0 d5 e1 e1 d4 e2 e1 1 2 3
1 e3 d6 e3 e3 acc
2 e3 r2 d7 e3 r2 r2
3 e3 r4 r4 e3 r4 r4
4 d5 e1 e1 d4 e2 e1 8 2 3
5 e3 r6 r6 e3 r6 r6
6 d5 e1 e1 d4 e2 e1 9 3
7 d5 e1 e1 d4 e2 e1 10
8 e3 d6 e3 d11 e4
9 e3 r1 d7 e3 r1 r1
10 e3 r3 r3 e3 r3 r3
11 e3 r5 r5 e3 r5 r5
L'interprétation des diérentes erreurs est la suivante :
1. e1 : opérande manquant. Cette erreur se produit quand on trouve un opérateur ou
l'on détecte la n de chaîne alors que l'on attend un opérande.
2. e2 : parenthèse fermante mal placée. Cette erreur se produit quand on détecte une
parenthèse fermante alors que l'on cherche un opérande.
3. e3 : opérateur manquant. Cette erreur se produit quand on détecte un opérande
ou une parenthèse ouvrante alors que l'on cherche un opérateur.
4. e4 : parenthèse fermante manquante.

21