THL 4

4
Analyse syntaxique.
1 – Généralités.
Soit G = (V, A, R) une grammaire et soit S ∈ V une variable choisie comme axiome.
Une analyse syntaxique par G d’une “phrase” u ∈ A∗ est un algorithme qui doit décider si
u ∈ L(G, S) et :
k
– dans le cas d’une réponse positive, décrire une dérivation S =⇒ u,
G
– dans le cas contraire, déterminer pourquoi une dérivation ne peut être construite, c’est–à–
dire, faire un diagnostic sur l’“erreur” qui est la cause de cet échec.
Les algorithmes d’analyse syntaxique qui nous intéressent ont quelques points communs :
– Ils lisent le mot à analyser de la gauche vers la droite (ceci justifie la première lettre, un L,
des sigles angloricains qui servent à les désigner).
– Ils choisissent, parmi les dérivations équivalentes possibles d’un même mot, une dérivation
particulière : soit à droite soit à gauche.
– dans le cas de dérivations à gauche (Leftmost), la construction s’effectue de l’axiome
vers le mot à analyser : on parle d’analyse “descendante” ou “prédictive”,
– dans le cas de dérivations à droite (Rightmost), la construction s’effectue du mot à
analyser vers l’axiome : on parle d’analyse “ascendante”.
– Ils sont basés sur l’utilisation d’“automates à pile” (dont la définition générale ne sera pas
donnée ici) : le résultat d’une analyse réussie est une suite de règles qui définit une dérivation
k
S =⇒ u.
G
– Ils sont déterministes.
Ils ne peuvent évidemment pas s’appliquer avec le même succès à toute grammaire, en particulier,
les grammaires “ambiguës” que nous allons maintenant définir, sont a priori hors du domaine
d’application de ces algorithmes.
k
Soient X ∈ V et α ∈ (A + V)∗ : lorsqu’il existe une dérivation X =⇒ α dans G, il en existe
G
généralement beaucoup d’autres ! Cependant, on sait que deux dérivations équivalentes font le
même calcul, c’est–à–dire, ont le même arbre.
On est conduit à dire qu’une grammaire n’est pas ambiguë ssi, pour toute X ∈ V et tout
k k
α ∈ (A + V)∗ , deux dérivations d : X =⇒ α et d : X =⇒ α sont équivalentes.
G G
Le déterminisme des algorithmes d’analyse syntaxique que nous allons étudier implique que les
grammaires auxquelles ils s’appliquent ne sont pas ambiguës. Dans la pratique, l’ambiguı̈té d’une
grammaire provient de conventions d’écriture bien répertoriées, par exemple
– Préséance : dans une grammaire dont certaines constantes représentent des opérateurs, par
exemple × pour un produit et ⊕ pour une somme, une expression de la forme α ⊕ β × γ
devra généralement être analysée comme α ⊕ (β × γ) et non pas comme (α ⊕ β) × γ : on
dira alors que × a un degré de préséance supérieur à celui de ⊕.
Théorie des langages. M.M Institut Galilée 2000

122 Chapitre 4
– Mode d’association : de même, une expression de la forme α ⊕ β ⊕ γ devra généralement

être analysée comme (α ⊕ β) ⊕ γ et non pas comme α ⊕ (β ⊕ γ) : on dira alors que ⊕ est
associative à (partir de la) gauche.
Ceci est évidemment l’objet d’une étude théorique (celle des grammaires d’opérateurs) mais nous
n’en parlerons pas. La méthode utilisée ici, pour tenir compte de telles conventions, est plus
pragmatique : elle consiste à sélectionner la dérivation voulue parmi toutes celles qui aboutissent
à un mot donné (cf. exercices 6 et 7).
Exemple 3.1 (suite).
Notre grammaire habituelle (exemple 1 du chapitre 3) est ambiguë : elle ne peut pas avoir toutes
1 1 1 1
les qualités ! En effet, les dérivations S =⇒ SbS =⇒ SbSbS et S =⇒ SbS =⇒ SbSbS ne sont pas
équivalentes.
Plus généralement, considérons une grammaire G disposant de règles (pas nécessairement dis-
tinctes) X −→ Xα et X −→ α X (on parle d’“appels récursifs” à gauche et à droite) alors G est
ambiguë, à cause des deux dérivations non équivalentes :
1 1 1 1
X =⇒ Xα =⇒ α Xα et X =⇒ α X =⇒ α Xα.
Cette cause d’ambiguı̈té n’est pas très grave car on peut effectivement éliminer tout appel récursif
à gauche sans pour cela changer les langages engendrés. Il y a des cas plus sérieux : il faut savoir
qu’il existe des langages algébriques qui ne peuvent pas être engendrés par une grammaire non
ambiguë ! (La vérification de cette affirmation dépasse nos compétences.)
ans toute la suite, nous supposerons que G est réduite pour son axiome S ; ceci signifie que
G ne comporte pas de variable inutile, plus précisément que toute X ∈ V est :
– productive : L(G, X) = ∅.
∗
– accessible à partir de S : il existe α et β ∈ (A + V)∗ tels que S =⇒ αXβ.
G
Les grammaires avec axiome et réduites pour leur axiome, peuvent se définir par leurs seules règles,
en appliquant les conventions suivantes :
– une variable est un symbole qui forme la partie gauche d’au moins une règle, l’axiome se
présente en premier,
– une constante est un symbole, distinct de toute variable, apparaissant dans la partie droite
d’au moins une règle (ε désigne le mot vide, comme d’habitude).
2 – Dérivations à droite et analyse ascendante.

Lorsque l’on séquentialise une arborescence, par exemple en utilisant une méthode descendante, on
peut choisir systématiquement d’élaguer la racine qui est le plus à droite : toute dérivation est donc
équivalente à une dérivation obtenue ainsi. Une telle dérivation applique une règle à l’occurrence de
la variable qui est située le plus à droite possible (ceci explique l’expression angloricaine rightmost
derivation).
Dérivations à droite
Une dérivation élémentaire est dite à droite lorsqu’elle se présente sous la forme
1
πXv =⇒ παv
G
pour v ∈ A∗ .
Une dérivation est dite à droite lorsqu’elle est définie comme un enchaı̂nement de dérivations
élémentaires à droite.
k k
Une dérivation à droite sera symbolisée avec β =⇒ γ et plus simplement par β =⇒ γ lorsque G
d,G d
est évidente.
Le cas des dérivations à gauche (leftmost derivations), facile à imaginer, sera envisagé dans l’annexe.
M.M Institut Galilée 2000 Analyse syntaxique.

Section 2 123
Observations.
• Dans une dérivation à droite, il n’est plus nécessaire de préciser l’occurrence de la variable à
laquelle on applique une règle, puisque l’on a convenu une fois pour toutes que c’était la plus à
droite !
• Soit u ∈ L(G, S), alors, si G n’est pas ambiguë, il existe exactement une dérivation à droite
k
S =⇒ u (et réciproquement, on peut définir l’ambiguı̈té d’une grammaire sur la base des seules
d
dérivations à droite).
Exemple 3.1 (suite).
11
Voici une dérivation à droite S =⇒ aabbabaabba dans notre grammaire habituelle :
d
1
S =⇒ SbS
d
1
=⇒ SbSbS
d
1
=⇒ SbSba
d
1
=⇒ Sbba
d
1
=⇒ SbSbba
d
1
=⇒ SbSbSbba
d
1
=⇒ SbSbaabba
d
1
=⇒ Sbabaabba
d
1
=⇒ SbSbabaabba
d
1
=⇒ Sbbabaabba
d
1
=⇒ aabbabaabba
d
dont l’arbre associé est encore la figure 3 du chapitre 3.
En énumérant les règles de la façon suivante :
1 : S −→ SbS 2 : S −→ ε 3 : S −→ a 4 : S −→ aa
on obtient la suite 1, 1, 3, 2, 1, 1, 4, 3, 1, 2, 4 avec laquelle on peut effectivement construire une
dérivation à droite.
2.1 – Analyse ascendante.

Ce type d’analyse est désigné par le sigle LR : on lit le mot à analyser de gauche à droite
(Left to right scanning) et on construit une dérivation à droite (Rightmost derivation). Il est
important d’observer que cette méthode construit les dérivations “à l’envers” ; c’est pourquoi on
parle d’analyse ascendante : on va du mot à analyser vers l’axiome !
Pour rendre ces méthodes efficaces, on se permet d’observer, dans la mesure du possible, les k
symboles qui sont au début de la partie du mot restant à analyser ; on obtient alors les algorithmes
de type LR(k) qui sont “d’autant plus déterministes” que k est grand (comme il se doit, une
grammaire peut fort bien résister à tous ces traitements !). Nous commencerons par LR(0), c’est–
à–dire par un algorithme aveugle puis, nous éprouverons le besoin d’étudier des algorithmes de
type LR(1), prévoyant 1 symbole ; contrairement aux précédents, ceux–ci sont très suffisants pour
les besoins courants actuels en compilation.
Analyse syntaxique. M.M Institut Galilée 2000

124 Chapitre 4
2.2 – Configuration d’analyse partielle et préfixes viables.

L’analyse ascendante de u ∈ A∗ est la construction d’une dérivation S =⇒ u, qui détermine ses
règles dans l’ordre inverse de leur enchaı̂nement naturel : on remonte du mot u vers l’axiome S.
On peut appeler “analyse partielle de u” une dérivation π =⇒ w telle qu’il existe une dérivation
d
S =⇒ πv pour laquelle wv = u. La première question qui se pose est donc de trouver une condition
d
utilisable, que doit nécessairement satisfaire un “préfixe” π ∈ (A + V)∗ pour qu’il existe une
dérivation à droite S =⇒ πv : un tel préfixe sera dit “viable”.
d
Forme générale des dérivations à droite.

Une dérivation à droite X =⇒ γ de longueur > 0 (la longueur n’est notée explicitement que
d
lorsqu’elle est supposée être égale à 1) se décompose de la façon suivante :
1
X =⇒ α β =⇒ α v
d
où X −→ α β est sa première règle et où v ∈ A∗ (bien entendu, on a α v = γ).

Si le premier caractère de β est une variable, c’est–à–dire si β = Y α pour Y ∈ V, on peut préciser
l’analyse précédente en décomposant de la façon suivante :
1
X =⇒ α Y α =⇒ α Y v =⇒ α γv
d d
Nous dirons que cette dérivation est la composée de

1
X =⇒ α Y α =⇒ α Y v et de Y =⇒ γ
d d
Un raisonnement par induction sur la longueur montre alors que toute dérivation à droite, non
triviale, est une composée de dérivations des types précédents :
1
X0 =⇒ α1 X1 α1 =⇒ α1 X1 v1 pour v1 ∈ A∗
d
1
X1 =⇒ α2 X2 α2 =⇒ α2 X2 v2 pour v2 ∈ A∗
d
... ... ... ... ...
1
Xn−1 =⇒ αn Xn αn =⇒ αn Xn vn pour vn ∈ A∗
d
1
Xn =⇒ αn+1 αn+1 =⇒ αn+1 vn+1 pour vn+1 ∈ A∗
d
ce qui, dans le cas où n = 0 se présente sous la forme particulière suivante :
1
X0 =⇒ α1 α1 =⇒ α1 v1 pour v1 ∈ A∗
d
Commentaires.
• La composée de ces dérivations a la forme

1
X0 =⇒ πXn v =⇒ παn+1 αn+1 v =⇒ παn+1 vn+1 v
d d
où π = α1 . . . αn et v = vn . . . v1 .

• Les mots παn+1 obtenus ainsi sont les “préfixes” que nous cherchons à caractériser : la définition
exacte sera donnée plus bas.

• La dernière dérivation de la liste ci–dessus suppose seulement que αn+1 est un suffixe du
membre de gauche d’une règle pour Xn : une dérivation à droite admet donc généralement plusieurs
décompositions.

Section 2 125
1
• Un cas particulièrement intéressant est celui où αn+1 = ε : on a alors vn+1 = ε et Xn =⇒ αn+1
est la dernière dérivation élémentaire, ce qui veut dire que la règle Xn −→ αn+1 est la dernière de
la liste définissant la dérivation qui nous intéresse.
• Ce qui vient d’être dit est valable pour toute dérivation non triviale : la dérivation triviale
0
S =⇒ S, qui joue un rôle dans notre algorithme, ne rentre donc pas dans ce cadre. Ceci justifie la
notion d’“augmentation”, purement technique, dont il va être question maintenant.
Augmentation d’une grammaire.
La désignation effective de l’axiome S, se fait habituellement en “augmentant” la grammaire de
la façon suivante : on introduit une nouvelle variable S ∈ V et une seule nouvelle règle S −→ S.
Ainsi, S n’est–elle présente dans aucune autre règle que la sienne, contrairement à S qui peut très
bien être présente dans la partie droite de n’importe quelle règle, et S est l’axiome de la grammaire
ainsi construite. Nous préférons utiliser l’augmentation
∅ −→ S
produisant S à partir de l’ensemble vide lui–même (qui n’est pas un élément de V) : l’axiome se
trouve ainsi engendré à partir de “rien”, comme il se doit.
k k+1
Dans la grammaire ainsi augmentée, toute dérivation S =⇒ γ devient une dérivation ∅ =⇒ γ de
d d
1
longueur > 0 qui commence toujours par ∅ =⇒ S.
Nous sommes maintenant en mesure de caractériser les “préfixes” qui nous intéressent, en anticipant
sur une notation qui sera l’objet de la section suivante.
Préfixes viables
πα ∈ (A + V)∗ est appelé un préfixe viable ssi il existe une dérivation à droite
1
∅ =⇒ πXv =⇒ πα α v
d
(v est alors nécessairement un élément de A∗ ).
La règle X −→ α α définit alors un item valide pour ce préfixe viable, que l’on notera
. X −→ α . α , où . est un nouveau symbole (cf. ci–dessous).
Ce que nous avons observé au sujet des dérivations à droite peut s’exprimer en disant que toute
dérivation à droite détermine un enchaı̂nement d’item, c’est–à–dire, avec les notations ci–dessus :
ou bien :
∅ −→ . S
.S −→ α1 . X1 α1
. X1 −→ α2 . X2 α2
... ...
. Xn−1 −→ αn . Xn αn
. Xn −→ αn+1 . αn+1
ce qui, dans le cas où n = 0, se présente de la façon suivante :
∅ −→ .S
.S −→ α1 . α1
ou bien, le cas spécial
∅ −→ S .
qui provient de l’augmentation de la grammaire.
Réciproquement, tout enchaı̂nement d’item comme ci–dessus permet de construire des dérivations
à droite assurant la viabilité d’un préfixe donné.

126 Chapitre 4
Cette remarque est importante pour la compréhension et la justification de la suite. Par exemple,
la propriété importante
• Tout préfixe (facteur gauche) d’un préfixe viable est un préfixe viable.
s’observe très facilement en “raccourcissant” l’enchaı̂nement qui définit le préfixe viable en question.
2.3 – Item LR(0) d’une grammaire G.

Pour définir les item LR(0), on introduit un pointeur, c’est–à–dire un nouveau symbole . ∈ A + V.
Les item LR(0)
Pour toute X ∈ V + {∅}, et tout couple α ∈ (A + V)∗ et β ∈ (A + V)∗ :
. X −→ α . β est un item LR(0) de G ssi X −→ αβ est une règle de G.
Nous dirons simplement “item” pour “item LR(0)”.

Pour définir les item de façon plus active, considérons les mots sur l’alphabet . +A + V comportant
une et une seule occurrence de . (un tel mot peut s’écrire α . β pour α ∈ (A + V)∗ et β ∈ (A + V)∗ ).
On peut appliquer à ces mots l’opération de “décalage” qui est symbolisée par la règle
. ξ −→ ξ .
qui est sensible au contexte.
Alors, pour chaque règle X −→ α de G :
– . X −→ . α est un item (qui est l’application de X −→ α au mot . X) ;
– si . X −→ β . ξγ est un item où ξ ∈ A + V, alors . X −→ βξ . γ est un item qui est obtenu en
appliquant un décalage après . X −→ β . ξγ
Exemples.
Compte tenu du fait que . ∅ = ∅, la règle ∅ −→ S définit deux item :
– l’item initial : ∅ −→ . S

– l’item final : ∅ −→ S .
ne règle X −→ ε ne définit que le seul item : . X −→ . dont le second membre se réduit
effectivement à une occurrence de . !
La règle X −→ aXaY b définit les item suivants :
. X −→ . aXaY b . X −→ aX . aY b . X −→ aXaY . b
. X −→ a . XaY b . X −→ aXa . Y b . X −→ aXaY b .
2.3.1 – AFD des item LR(0).
Considérons l’ε–AF A, sur l’alphabet A + V, défini par les données suivantes :
– Les états sont les item ;
– l’entrée est ∅ −→ . S ;
– une transition(∗ ) par ξ ∈ A + V est définie sur les états de la forme . X −→ α . ξβ par un
décalage
ξ
. X −→ α . ξβ . X −→ αξ . β
– une ε–transition est définie sur les états de la forme . X −→ α . Y β, par
. X −→ α . Y β ε . Y −→ . γ
pour toute règle Y −→ γ
ξ
(∗ ) On représente la propriété r ∈ δ(q, ξ) par l’arête q r du graphe de transition.

Section 2 127
Si l’on fait une sortie de chacun de ses états, A reconnaı̂t le langage formé des préfixes viables.
Plus précisément
ε–AF des item
∗
Pour tout π ∈ (A + V) :
(∅ −→ . S, π) ∗ (. X −→ α . β, ε) ssi π est un préfixe viable et . X −→ α . β est valide pour π.
Un ε–AF A est peu maniable et il est préférable de considérer l’AFD D(A) équivalent obtenu en
appliquant l’algorithme de détermination (chapitre 2, section 5), et en négligeant l’état vide.
Ainsi, l’AFD équivalent à A est la partie accessible de l’AFD défini de la façon suivante :
– les états sont des ensembles clos non vides d’item,
– l’état initial : cl(∅ −→ . S),
– l’action de ξ sur q, q • ξ est la clôture de la réunion des images des éléments de q,
– les sorties ne jouent aucun rôle ici (on peut, par exemple, prendre tous les états comme
sorties).
Lorsque q • π = ∅, π définit un chemin partant de q ∈ Q : ch(q, π) ∈ Chem(q, q • π).
Plus précisément (cf. la section 7 du chapitre 1) :
– ch(q, ε) = q,
– si ch(q, π) = χr et si r • ξ = s, alors ch(q, πξ) = ch(q, π) ◦ rs = χrs.
Propriétés de l’AFD des item.

Toutes ces propriétés viennent directement de la définition de l’AFD et des observations qui ont
été faites au sujet des dérivations à droite.
– q • ξ est défini ssi il existe (. X −→ α . ξβ) ∈ q.
– (. X −→ α . ξβ) ∈ q implique (. X −→ αξ . β) ∈ q • ξ.
En conséquence, toutes les transitions aboutissant à un état donné sont étiquetées par le
même symbole, c’est–à–dire que, si q ∈ δ(r, ξ) et q ∈ δ(s, η) alors ξ = η : un chemin détermine
donc au plus un mot. Il faudrait respecter cette propriété intéressante si l’on considérait un
AFDC : chacun des états improductifs qu’il faudrait introduire pour ce faire correspondrait
à une “erreur” particulière.
– on peut reformuler la remarque précédente en disant que, pour un q donné, la connaissance
de ch(q, π) et celle de π sont équivalentes. Dans la pratique, il est cependant intéressant de
les considérer tous les deux simultanément : dans les analyses que nous allons maintenant
définir, ils seront traités comme des piles avec sommet à droite ; respectivement “la pile
d’états” et “la pile” proprement dite.
– Soient q0 l’état initial, π un préfixe viable et q = q0 • π, alors :
– q est l’ensemble des item valides pour π,
– si (. X −→ α . ξβ) ∈ q alors πξ est viable,
– si (. X −→ α .) ∈ q alors π = π α pour un π ∈ (A + V)∗ et π X est un préfixe viable.
Un item de la forme . X −→ α . est dit complet.
Exemple 1.
Soit G1 la grammaire :
1 : S −→ (S ∧ S) 2 : S −→ ¬S 3 : S −→ id
AFD des item LR(0) de G1 .
(Chaque nouvel état Ii est accompagné de l’ensemble Σi des symboles ξ tels que Ii • ξ = ∅.)
I0 = {∅ −→ . S, Σ0 = S + (+¬ + id
. S −→ .(S ∧ S), . S −→ . ¬S, . S −→ . id}

128 Chapitre 4
I1 = I0 • S Σ1 = ∅
= {∅ −→ S .}
I2 = I0 •( Σ2 = S + (+¬ + id
= {. S −→ (. S ∧ S),
. S −→ .(S ∧ S), . S −→ . ¬S, . S −→ . id}
I3 = I0 • ¬ Σ3 = S + (+¬ + id
= {. S −→ ¬ . S,
. S −→ .(S ∧ S), . S −→ . ¬S, . S −→ . id}
I4 = I0 • id Σ4 = ∅
= {. S −→ id .}
I5 = I2 • S Σ5 = ∧
= {. S −→ (S . ∧S)}
I2 = I2 •(
I3 = I2 • ¬
I4 = I2 • id
I6 = I3 • S Σ6 = ∅
= {. S −→ ¬S .}
I2 = I3 •(
I3 = I3 • ¬
I4 = I3 • id
I7 = I5 • ∧ Σ7 = S + (+¬ + id
= {. S −→ (S ∧ . S),
. S −→ .(S ∧ S), . S −→ . ¬S, . S −→ . id}
I8 = I7 • S Σ8 =)
= {. S −→ (S ∧ S .)}
I2 = I7 •(
I3 = I7 • ¬
I4 = I7 • id
I9 = I8 •) Σ9 = ∅
= {. S −→ (S ∧ S) .}
Exemple 2.
Soit G2 la grammaire :
1 : E −→ E ⊕ T 3 : T −→ T ∗ F 5 : F −→ (E)
2 : E −→ T 4 : T −→ F 6 : F −→ id
I0 = {∅ −→ . E, Σ0 = E + T + F + (+id
. E −→ . E ⊕ T, . E −→ . T,
. T −→ . T ∗ F, . T −→ . F,
. F −→ .(E), . F −→ . id}
I0 • E = I1 Σ1 = ⊕
= {∅ −→ E .,

Section 2 129
. E −→ E . ⊕T }
I0 • T = I2 Σ2 = ∗
= {. E −→ T .,
. T −→ T . ∗F }
I0 • F = I3 Σ3 = ∅
= {. T −→ F .}
I0 •( = I4 Σ4 = E + T + F + (+id
= {. F −→ (. E),
. E −→ . E ⊕ T, . E −→ . T,
. T −→ . T ∗ F, . T −→ . F,
. F −→ .(E), . F −→ . id}
I0 • id = I5 Σ5 = ∅
= {. F −→ id .}
I1 • ⊕ = I6 Σ6 = T + F + (+id
= {. E −→ E ⊕ . T,
. T −→ . T ∗ F, . T −→ . F,
. F −→ .(E), . F −→ . id}
I2 • ∗ = I7 Σ7 = F + (+id
= {. T −→ T ∗ . F,
. F −→ .(E), . F −→ . id}
I4 • E = I8 Σ8 =) + ⊕
= {. F −→ (E .),
. E −→ E . ⊕T }
I4 • T = I2
I4 • F = I3
I4 •( = I4
I4 • id = I5
I6 • T = I9 Σ9 = ∗
= {. E −→ E ⊕ T .,
. T −→ T . ∗F }
I6 • F = I3
I6 •( = I4
I6 • id = I5
I7 • F = I10 Σ10 = ∅
= {. T −→ T ∗ F .}
I7 •( = I4
I7 • id = I5
I8 •) = I11 Σ11 = ∅
= {. F −→ (E) .}
I8 • ⊕ = I6
I9 • ∗ = I7

130 Chapitre 4
2.4 – L’automate à pile LR(0).

Une configuration d’analyse LR d’un mot u ∈ A∗ est un couple (π, v) où π est un préfixe viable
tel qu’il existe une dérivation π =⇒ w vérifiant wv = u. Pour avoir accès à l’état de l’AFD dans
d
lequel π est validé, il faut modifier un peu ce couple, en considérant la configuration (ch(q0 , π), v) :
comme il a déjà été signalé plus haut, il est intéressant de considérer aussi le mot π, bien que cette
information soit redondante.
L’automate à pile pour l’analyse LR(0) de G est défini de la façon suivante :
Une configuration est un couple (χ, v) où
– χ = ch(q0 , π) est traité comme une pile (la pile des états) dont le sommet est à droite ; le
mot π, lui aussi, est traité comme une pile (la pile proprement dite) dont le sommet est
encore à droite,
– v ∈ A∗ .
Les transitions sont définies par :
(D) (χq, xv) (χqr, v) si x ∈ A et q • x = r
(R) (χch(q, α), v) (χqr, v) si (. X −→ α .) ∈ q • α et q • X = r.
La configuration initiale pour l’analyse de u est (q0 , u).
La configuration d’acceptation est (q0 q1 , ε) pour q1 = q0 • S.
Les données nécessaires à la définition des transitions sont consignées dans une table Action(q, ξ)
définie pour les états q de l’AFD des item LR(0) et ξ ∈ ε + A + V, de la façon suivante :
Table LR(0)
Les Action( , ) sont les plus petits ensembles tels que
– r ∈ Action(q, ξ) si q • ξ = r pour ξ ∈ A + V
– (X −→ α) ∈ Action(q, ε) si (. X −→ α .) ∈ q pour X ∈ V
– Acc ∈ Action(q, ε) si (∅ −→ S .) ∈ q
C’est donc la table de transition de l’AFD des item LR(0) de G enrichi d’une colonne pour ε qui
comporte, pour chaque état, l’ensemble des “item complets” qu’il contient : on l’appelle la table
LR(0) de G.
Propriété.
Pour tout u ∈ A∗ :
∗
u ∈ L(G, S) ssi (q0 , u) (q0 q1 , ε)
∗
où signifie l’existence d’un enchaı̂nement de transitions.
La démonstration de cette propriété est basée sur des récurrences très évidentes.
2.5 – Grammaires LR(0).

Une grammaire est dite LR(0) ssi sa table LR(0) vérifie les propriétés suivantes :
pour tout état q de l’AFD
– Action(q, ε) comporte au plus un élément,
– si Action(q, ε) = ∅ alors Action(q, ξ) = ∅ pour tout ξ ∈ A.

Section 3 131
Remarques.
• Lorsque ces conditions sont vérifiées, chaque état q est d’une nature bien déterminée :
– si Action(q, ε) = ∅, alors Action(q, ε) contient un seul élément qui est :
– ou bien une réduction : q est un état de réduction,
– ou bien Acc : q = q1 = q0 • S est l’état d’acceptation,
– sinon, Action(q, x) contient au plus un décalage pour chaque x ∈ A : q est un état de
décalage.
• Les conditions signifient que l’automate à pile est déterministe : une analyse, lorsqu’elle est
faisable, l’est de façon unique. En particulier, une grammaire LR(0) n’est pas ambiguë.
2.5.1 – Algorithme d’analyse LR(0).
Soit G une grammaire LR(0) dont l’axiome est S.
L’analyse LR(0) de u ∈ A∗ s’effectue à partir de la configuration initiale (q0 , u) en tentant
d’exécuter une suite de transitions (D) ou (R). Chaque application de (R) ajoute une règle au
début de la liste d’analyse, initialement vide.
Soit (χ, v) la configuration courante. Lors de l’exécution de l’algorithme, on peut vérifier que χ
n’est jamais vide : notons χ = χ q pour mettre en valeur le sommet q de cette pile, qui est l’“état
courant” de l’automate. Alors :
• si q est un état de réduction :
si Action(q, ε) = (X −→ α), χ est alors nécessairement de la forme χ ch(r, α) (comme
on peut le vérifier par une induction) et si Action(r, X) = s : on passe à la configuration
(χ rs, v) par application d’une transition (R),
• si q est un état de décalage :
si v = xv avec x ∈ A et si Action(q, x) = r : on passe à la configuration (χ qr, v ) par
application d’une transition (D),
• si q = q1 = q0 • S est l’état d’acceptation :
si χ = q0 q1 et si v = ε : on est parvenu à la configuration d’acceptation et l’analyse est
terminée de façon satisfaisante.
• Dans les autres cas : l’analyse se termine sur un échec. Une bonne table d’analyse doit comporter
un diagnostic d’“erreur syntaxique” pour chacun de ces cas (qui correspondent aux cases vides de
la table).
Présentation pratique de la table LR(0).
Les états sont codés par des entiers (I0 , . . . , In ) et on note di (décaler en i) au lieu de Ii dans
la table de transition. De même, les règles sont codées par des entiers et on note rk (réduire par
la règle k), au lieu de la règle elle–même, dans la colonne ε (la réduction par ∅ −→ S, que l’on
n’effectue pas réellement, est codée par Acc). Ceci donne la description suivante de la table LR(0) :
– si Ii • ξ = Ij alors dj ∈ Action(i, ξ)
– si (. X −→ α .) ∈ Ii avec X ∈ V alors rk ∈ Action(i, ε) où k est le numéro de la règle
X −→ α
– si (∅ −→ S .) ∈ Ii alors Acc ∈ Action(i, ε).
Exemple.
Reprenons la grammaire G1 de l’exemple 1 ci–dessus, dont on connaı̂t déjà l’AFD des item LR(0).
3 – Analyse ascendante avec symboles de prévision.

Lorsque la première condition LR(0) n’est pas vérifiée, on parle d’un “conflit réduction–réduction”,
lorsque la deuxième ne l’est pas, d’un “conflit décalage–réduction”. Ces conflits sont fréquents dès
que G n’est plus extrêmement simpliste : ceci tient à ce que l’on n’est pas prévoyant !

132 Chapitre 4
ε ( ∧ ) ¬ id S
0 d2 d3 d4 d1
1 Acc
2 d2 d3 d4 d5
3 d2 d3 d4 d6
4 r3
5 d7
6 r2
7 d2 d3 d4 d8
8 d9
9 r1
Table LR(0) de G1 .
Pile Pile d’états Entrée Actions

ε 0 ¬(id ∧ ¬id) (d3 : lecture de ¬)
¬ 03 (id ∧ ¬id) (d2 : lecture de ()
¬( 032 id ∧ ¬id) (d4 : lecture de id)
¬(id 0324 ∧¬id) r3 : S −→ id
¬(S 0325 ∧¬id) (d7 : lecture de ∧)
¬(S∧ 03257 ¬id) (d3 : lecture de ¬)
¬(S ∧ ¬ 032573 id) (d4 : lecture de id)
¬(S ∧ ¬id 0325734 ) r3 : S −→ id
¬(S ∧ ¬S 0325736 ) r2 : S −→ ¬S
¬(S ∧ S 032578 ) (d9 : lecture de ))
¬(S ∧ S) 0325789 ε r1 : S −→ (S ∧ S)
¬S 036 ε r2 : S −→ ¬S
S 01 ε Acc
L’analyse LR(0) de ¬(id ∧ ¬id) dans G1 .
Exemple de conflit décalage–réduction.

L’état I9 = {. E −→ E ⊕ T ., . T −→ T . ∗F } de l’AFD de la grammaire G2 de l’exemple 2 , contient
un item complet, correspondant à une réduction par la règle E −→ E ⊕ T et un item non complet,
permettant un décalage sur ∗ : G2 n’est donc pas LR(0).
Dans ce qui suit, nous allons adjoindre des prévisions à 1 caractère pour résoudre ces conflits pour
des grammaires assez intéressantes : on est conduit à considérer comme item de type LR(1) les
couples (. X −→ α ., x) où x est un symbole de prévision.
La méthode utilisée pour LR(0) s’adapte facilement. Chacun des types d’analyse ainsi obtenu (il y

Section 3 133
en a trois) est caractérisé par une gestion particulière des symboles de prévision lors de la définition
de l’AF de ses item : nous la préciserons à la fin.
3.1 – Symboles de prévision.

Pour obtenir des algorithmes déterministes, nous allons les rendre “prévoyants”. Un choix (ou
l’absence de choix) est déterminé par la connaissance approximative de la partie du mot restant à
analyser, c’est–à–dire de quelques caractères du début de celle–ci. Voici ce que l’on entend par là :
Si k est le nombre de ces caractères et v ∈ A∗ , on définit un mot P remierk (v) ∈ (ε + A)k (donc,
de longueur ≤ k) de la façon suivante :
– si | v | ≤ k : P remierk (v) = v,
– sinon P remierk (v) est le facteur gauche de v dont la longueur est k.
Dans la pratique, il faut étendre cette notion à des S
mots sur A + V, en fonction de G et de S, de la façon
suivante :
k l
Soit S =⇒ uXw =⇒ uvw une dérivation du mot
uvw ∈ A∗ , dans laquelle on a mis en évidence une
l X
sous–dérivation X =⇒ v (voir la figure ci–contre).
Les approximations qui joueront un rôle sont :
– p = P remierk (v) u v w
– s = P remierk (w). p s
P remierk (X) est l’ensemble de tous les p que l’on peut obtenir ainsi et Suivantk (X) celui de tous
les s que l’on peut obtenir ainsi.
Le cas où k = 0 est toujours trivial puisque P remier0 (v) = ε pour tout v. Le cas où k = 1 est assez
simple mais déjà très signicatif ; de plus, il est suffisant pour analyser les langages que nous avons
en vue (des langages de programmation) : nous nous limiterons donc essentiellement à lui et nous
ne mentionnerons k que lorsqu’il ne sera pas supposé être égal à 1 : ainsi, P remier et Suivant
signifieront–ils respectivement P remier1 et Suivant1 .
3.1.1 – Calcul de P remier.

Pour toute X ∈ V, l’ensemble P remier(X) est formé de facteurs gauches des mots sur A que l’on
peut dériver à partir de X. Plus précisément, P remier(X) ⊆ ε + A est le plus petit ensemble tel
que :
∗
– si X =⇒ xα pour x ∈ A, alors x ∈ P remier(X) ;
∗
– si X =⇒ ε, alors ε ∈ P remier(X).
La deuxième clause signifie : ε ∈ P remier(X) ssi X ∈ Eps(G).
P remier(X) n’est pas vide puisque toute variable est productive.
Si, dans la définition de P remier(X), on remplace X par un élément quelconque de (A + V)∗ , on
obtient facilement les propriétés suivantes.
P remier
1) P remier(ε) = ε
2) pour tout x ∈ A et tout α ∈ (A + V)∗ : P remier(xα) = x
3) pour toute X ∈ V et tout α ∈ (A + V)∗ :

(P remier(X) − ε) + P remier(α) si X ∈ Eps(G),
P remier(Xα) =
P remier(X) sinon.
4) pour toute règle globale X −→ l : P remier(X) = P remier(l).

134 Chapitre 4
Dans la clause 4), on a étendu l’application P remier aux langages de la façon habituelle, elle doit
donc se comprendre comme étant :

P remier(X) = P remier(α).
α∈l
L’ensemble Eps(G) ⊆ V des variables de G qui produisent ε, défini par X ∈ Eps(G) ssi ε ∈ L(G, X)
a été étudié au chapitre 3 (section 4.2).
On a évidemment P remier0 (X) = ε. La définition de P remierk pour k > 1 est techniquement
plus compliquée, mais ne présente pas de réelle difficulté.
Exemple.
Appliquons cette construction à la grammaire G :
1 : E −→ E ⊕ T 3 : T −→ T ∗ F 5 : F −→ (E)
2 : E −→ T 4 : T −→ F 6 : F −→ id
• Il est clair que Eps(G) = ∅ ;
• En apliquant 4) et 3) on voit que :
P remier(E) = P remier(E ⊕ T ) + P remier(T ) = P remier(E) + P remier(T )

donc P remier(T ) ⊆ P remier(E).
P remier(T ) = P remier(T ∗ F ) + P remier(F ) = P remier(T ) + P remier(F )
donc P remier(F ) ⊆ P remier(T ).
• En faisant maintenant intervenir 2) :
P remier(F ) = P remier((E)) + P remier(id) = ( +id.
• On peut conclure en prenant les plus petits ensembles vérifiant ces propriétés :
P remier(E) = P remier(T ) = P remier(F ) = ( +id.
3.1.2 – Calcul de Suivant.

Pour tout X ∈ V, l’ensemble Suivant(X) est formé de facteurs de mots sur A qui peuvent
suivre immédiatement une occurrence de X dans un mot que l’on peut dériver à partir de S.
Plus précisément, Suivant(X) ⊆ ε + A est le plus petit ensemble tel que :
∗
si S =⇒ αXβ, alors P remier(β) ⊆ Suivant(X).
Suivant(X) n’est jamais vide puisque toute variable est accessible à partir de S.
Le calcul explicite de Suivant est basé sur la propriété suivante :
Suivant
Les Suivant( ) sont les plus petits ensembles tels que :
1) ε ∈ Suivant(S)
2) si Y −→ αXβ pour Y ∈ V :
P remier(β) − ε ⊆ Suivant(X)
3) si Y −→ αXβ pour Y ∈ V et si ε ∈ P remier(β) :
Suivant(Y ) ⊆ Suivant(X)
Remarques.
• Il ne faut pas oublier le cas où X se trouve en plusieurs occurrences dans la partie droite d’une
règle, lorsque l’on applique les clauses 2) et 3).
• De même, il ne faut pas oublier le cas β = ε dans la clause 3).
La vérification de la propriété est facile.

On a évidemment Suivant0 (X) = ε. La définition de Suivantk pour k > 1 est techniquement plus
compliquée, mais ne présente pas de réelle difficulté.

Section 3 135
Exemple.
Appliquons cette construction à la grammaire de l’exemple précédent.

• Suivant(E) :
Par 1), ε ∈ Suivant(E)
En appliquant 2) aux règles contenant E à droite, il vient ⊕ ∈ Suivant(E) par 1 : et ) ∈ Suivant(E)
par 5 : Comme on a épuisé toutes les possibilités, on peut en conclure que
Suivant(E) = ε + ⊕+)
• Suivant(T ) :
En appliquant 3) à 1 : ou 2 :, il vient Suivant(E) ⊆ Suivant(T )
En appliquant 2) à la règle 3 :, on a ∗ ⊆ Suivant(T ).
Finalement Suivant(T ) = ε + ⊕ + ∗+).
• Suivant(F ) :
L’application de 3) à 3 : ou 4 : implique que Suivant(T ) ⊆ Suivant(F ). Comme il n’y a pas d’autre
possibilité, on peut en conclure que
Suivant(F ) = Suivant(T ) = ε + ⊕ + ∗+)
3.2 – Automate à pile de type LR(1).

La définition de l’automate à pile s’effectue comme précédemment, à l’exception des transitions
qui tiennent compte des symboles de prévision :
(D) (χq, xv) (χqr, v) si x ∈ A et q.x = r

(R) (χch(q, α), v) (χqr, v) si (. X −→ α ., P remier(v)) ∈ q.α et q.X = r.
Il est commode de représenter les données nécessaires à la définition des transitions dans une
“table” Action(q, ξ) définie pour les états q de l’AFD des item de type LR(1) et ξ ∈ ε + A + V, de
la façon suivante :
Table de type LR(1)

Les Action( , ) sont les plus petits ensembles tels que
– r ∈ Action(q, ξ) si q • ξ = r pour ξ ∈ A + V
– (X −→ α) ∈ Action(q, x) si (. X −→ α ., x) ∈ q pour X ∈ V
– Acc ∈ Action(q, ε) si (∅ −→ S ., ε) ∈ q
C’est donc la réunion de la table de transition de l’AFD en question et d’une table caractérisant
la position des “item complets”.
Il faut remarquer que l’application d’une transition (R) est maintenant sujette à une condition sur
P remier(v) ∈ ε + A, contrairement au cas LR(0).

136 Chapitre 4
3.2.1 – Les trois types LR(1).

SLR(1) (Simple LR(1)) :
dans ce type, on forme un item pour . X −→ α . avec tout élément de Suivant(X).
LR(1) proprement dit :
l’action de l’AF est définie de la façon suivante :
– une transition(∗ ) par ξ ∈ A + V est définie sur les états de la forme (. X −→ α . ξβ, x)
par
ξ
. X −→ α . ξβ, x . X −→ αξ . β, x
– une ε–transition est définie sur les états de la forme (. X −→ α . Y β, x) par
. X −→ α . Y β, x ε . Y −→ . γ, y
pour chaque (Y −→ γ) ∈ R et chaque y ∈ P remier(βx).

LALR(1) (Look Ahead LR(1)) :
les états de l’AFD correspondant à ce type s’obtiennent en faisant la réunion des états de
l’AFD LR(1) qui ne diffèrent que par les symboles de prévision : ses états sont ceux de
l’AFD LR(0), aux éléments desquels on a adjoint des symboles de prévision. Il existe des
méthodes pour calculer ces symboles qui ne nécessitent pas le calcul de l’AFD LR(1) (Yacc
utilise une méthode de ce genre).
3.3 – Grammaires de type LR(1).

Une grammaire est dite LR(1) (resp. SLR(1), LALR(1)) ssi sa table LR(1) (resp. SLR(1),
LALR(1)) est déterministe,
c’est–à–dire, ssi chaque Action(q, ξ) comporte toujours au plus un élément.
Remarques.
• Cette condition signifie qu’il ne se produit pas de conflit et assure évidemment que l’automate
à pile correspondant est déterministe.
• Contrairement au cas LR(0), la nature de la transition à exécuter n’est pas déterminée par le
seul état courant (sommet de la pile d’états) mais aussi par le symbole de prévision.
• Comme dans le cas LR(0), on peut voir qu’une grammaire de type LR(1) n’est pas ambiguë.
3.3.1 – Algorithme d’analyse de type LR(1).

Soit G une grammaire de type LR(1) dont l’axiome est S.
L’analyse LR(1) de u ∈ A∗ s’effectue à partir de la configuration initiale (q0 , u) en tentant
d’exécuter une suite de transitions (D) ou (R). Chaque application de (R) ajoute une règle au
début de la liste d’analyse, initialament vide.
Soit (χ, v) la configuration courante. Lors de l’exécution de l’algorithme, on peut vérifier que χ
n’est jamais vide : notons χ = χ q pour mettre en valeur le sommet q de cette pile, qui est l’“état
courant” de l’automate. Alors :

• si Action(q, P remier(v)) = (X −→ α), χ est alors nécessairement de la forme χ ch(r, α)
(comme on peut le vérifier par une induction) et si Action(r, X) = s : on passe à la configuration
(χ rs, v) par application d’une transition (R),
ξ
(∗ ) On représente la propriété r ∈ δ(q, ξ) par l’arête q r du graphe de transition.

Section 3 137
• si Action(q, P remier(v)) = r où r est un état (alors on a nécessairement P remier(v) = x ∈ A

et) v s’écrit sous la forme v = xv , et si Action(q, x) = r : on passe à la configuration (χ qr, v ) par
application d’une transition (D),
• si χ = q0 q1 et si v = ε : on est parvenu à la configuration d’acceptation et l’analyse est terminée
de façon satisfaisante.
• Dans les autres cas : l’analyse se termine sur un échec. Une bonne table d’analyse doit comporter
la table).
Le codage introduit pour la table LR(0) est encore appliqué ici ; ceci donne la description suivante :
– si Ii • ξ = Ij alors dj ∈ Action(i, ξ)
– si (. X −→ α ., x) ∈ Ii avec X ∈ V alors rk ∈ Action(i, x) où k est le numéro de la règle
X −→ α
– si (∅ −→ S ., ε) ∈ Ii alors Acc ∈ Action(i, ε).
Exemple 2 : analyse SLR(1).
Reprenons la grammaire G2 de l’exemple 2 ci–dessus, dont on connaı̂t déjà l’AFD des item LR(0).
Symboles de prévision.
Eps(G) = ∅
P remier(E) = P remier(T ) = P remier(F ) = (+id
Suivant(E) = ε + ⊕+)
Suivant(T ) = Suivant(F ) = ε + ⊕ + ∗+)
La table SLR(1) de G2 et un exemple d’analyse sont présentés dans les tableaux ci–dessous.
ε ⊕ ∗ ( ) id E T F
0 d4 d5 d1 d2 d3
1 Acc d6
2 r2 r2 d7 r2
3 r4 r4 r4 r4
4 d4 d5 d8 d2 d3
5 r6 r6 r6 r6
6 d4 d5 d9 d3
7 d4 d5 d10
8 d6 d11
9 r1 r1 d7 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Table SLR(1) de G2 .

138 Chapitre 4
Pile Pile d’états Entrée Actions

ε 0 id ⊕ id ∗ id (d5 : lecture de id)
id 05 ⊕ id ∗ id r6 : F −→ id
F 03 ⊕ id ∗ id r4 : T −→ F
T 02 ⊕ id ∗ id r2 : E −→ T
E 01 ⊕ id ∗ id (d6 : lecture de ⊕)
E⊕ 016 id ∗ id (d5 : lecture de id)
E ⊕ id 0165 ∗ id r6 : F −→ id
E⊕F 0163 ∗ id r4 : T −→ F
E⊕T 0169 ∗ id (d7 : lecture de ∗)
E ⊕ T∗ 01697 id (d5 : lecture de id)
E ⊕ T ∗ id 016975 ε r6 : F −→ id
E⊕T ∗F 0 1 6 9 7 10 ε r3 : T −→ T ∗ F
E⊕T 0169 ε r1 : E −→ E ⊕ T
E 01 ε Acc
L’analyse SLR(1) de id ⊕ id ∗ id dans G2 .
Exemple 3 : analyses LR(1) et LALR(1).

Considérons la grammaire G3 :
1 : S −→ G=D 3 : G −→ ∗D 5 : D −→ G
2 : S −→ D 4 : G −→ id
Le début du calcul de l’AFD des item LR(0) montre que G3 n’est pas SLR(1), en effet, on a
I0 = {∅ −→ . S,
. S −→ . G=D, . S −→ . D,
. G −→ . ∗D, . G −→ . id,
. D −→ . G}
et donc I2 = I0 • G = {. S −→ G . =D, . D −→ G .} ; or, il est facile de voir que = ∈ Suivant(D) et
donc que la méthode SLR(1) ne résoud pas le conflit décalage–réduction qui se présente dans cet
état : nous allons voir que les item LR(1) sont capables de le faire.
L’état initial est :
I0 = {(∅ −→ . S, ε),
(. S −→ . G=D, ε), (. S −→ . D, ε),
(. G −→ . ∗D, =), (. G −→ . id, =),
(. D −→ . G, ε),
(. G −→ . ∗D, ε), (. G −→ . id, ε)}
Il est commode de regrouper les item d’un même état qui ne diffèrent que par leur symbole de
prévision, en notant ( , P ) un ensemble d’item de ce type ( , x), où P ⊆ ε + A (une notation
x∈P
plus standard serait simplement × P , qui désigne bien l’ensemble des couples que l’on veut
représenter).

Section 3 139
Reprenons notre calcul en utilisant cette notation.

I0 = {(∅ −→ . S, ε), Σ0 = S + G + D + ∗ + id
(. S −→ . G=D, ε), (. S −→ . D, ε),
(. G −→ . ∗D, ε + =), (. G −→ . id, ε + =),
(. D −→ . G, ε)}
I0 • S = I1 Σ1 = ∅
= {(∅ −→ S ., ε)}
I0 • G = I2 Σ2 = =
= {(. S −→ G . =D, ε), (. D −→ G ., ε)}
I0 • D = I3 Σ3 = ∅
= {(. S −→ D ., ε)}
I0 • ∗ = I4 Σ4 = D + G + ∗ + id
= {(. G −→ ∗ . D, ε + =),
(. D −→ . G, ε + =),
(. G −→ . ∗D, ε + =), (. G −→ . id, ε + =)}
I0 • id = I5 Σ5 = ∅
= {(. G −→ id ., ε + =)}
I2 • = = I6 Σ6 = D + G + ∗ + id
= {(. S −→ G= . D, ε),
(. D −→ . G, ε),
(. G −→ . ∗D, ε), (. G −→ . id, ε)}
I4 • D = I7 Σ7 = ∅
= {(. G −→ ∗D ., ε + =)}
I4 • G = I8 Σ8 = ∅
= {(. D −→ G ., ε + =)}
I4 • ∗ = I4
I4 • id = I5
I6 • D = I9 Σ9 = ∅
= {(. S −→ G=D ., ε)}
I6 • G = I10 Σ10 = ∅
= {(. D −→ G ., ε)}
I6 • ∗ = I11 Σ11 = D + G + ∗ + id
= {(. G −→ ∗ . D, ε),
(. D −→ . G, ε),
(. G −→ . ∗D, ε), (. G −→ . id, ε)}
I6 • id = I12 Σ12 = ∅
= {(. G −→ id ., ε)}
I11 • D = I13 Σ13 = ∅
= {(. G −→ ∗D ., ε)}
I11 • G = I10
I11 • ∗ = I11
I11 • id = I12

140 Chapitre 4
Grâce à la gestion plus parcimonieuse des symboles de prévision, les item LR(1) définissent un
AFD dont aucun état ne connaı̂t de conflit ; dans l’état I2 qui était conflictuel dans la version
SLR(1), le symbole = n’est plus utilisé pour déclencher une réduction par la règle D −→ G, ainsi
la table LR(1) est–elle déterministe.
ε = ∗ id S G D
0 d4 d5 d1 d2 d3
1 Acc
2 r5 d6
3 r2
4 d4 d5 d8 d7
5 r4 r4
6 d11 d12 d10 d9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 d11 d12 d10 d13
12 r4
13 r3
Table LR(1) de G3 .
Lorsque l’on fait la réunion des états de l’AFD LR(1) qui ne diffèrent que par les symboles de
prévision, on ne réintroduit pas de conflit : la table LALR(1) a été construite en numérotant les
nouveaux états de la façon suivante :
I4 = I4 + I11 I5 = I5 + I12 I7 = I7 + I13 I8 = I8 + I10
La grammaire G3 est donc LALR(1).
4 – Annexe : analyse descendante.

Une analyse de ce type se fait en descendant de l’axiome vers le mot à analyser. L’analyse détermine
donc les règles convenables dans le même ordre que celui dans lequel elles seraient appliquées lors
d’une dérivation. De même, l’analyse se fait de gauche à droite : puisque l’on “descend”, ceci
correspond à une dérivation à gauche (d’où le deuxième L, pour “Leftmost derivation”, du sigle
LL).

Section 4 141
ε = ∗ id S G D
0 d4 d5 d1 d2 d3
1 Acc
2 r5 d6
3 r2
4 d4 d5 d8 d7
5 r4 r4
6 d4 d5 d8 d9
7 r3 r3
8 r5 r5
9 r1
Table LALR(1) de G3 .
4.1 – Configurations d’analyse partielle.

Une dérivation à gauche est un enchaı̂nement de dérivations élémentaires à gauche, c’est–à–dire,
de la forme
1
wXπ =⇒ wαπ
où w ∈ A∗ : ceci signifie que l’on applique toujours une règle sur la variable qui est le plus à gauche
du mot courant.
L’analyse descendante de u ∈ A∗ est la construction d’une dérivation S =⇒ u dont on connaı̂t
l’aboutissement.
On peut appeler “analyse partielle de u” une dérivation S =⇒ wπ telle qu’il existe une dérivation
g
π =⇒ v pour laquelle wv = u. Avec ces notations, une configuration d’analyse partielle de u peut
g
s’écrire (w; π, v)
la configuration initiale est (ε; S, u)
la configuration d’acceptation est (u; ε, ε)
les modifications permises sont de deux types :
1
L : (w; xπ , xv ) =⇒ (wx; π , v ) pour x ∈ A
1
D : (w; Xπ , v) =⇒ (w; απ , v) pour X −→ α.
G
• Une “lecture”, c’est–à–dire une modification L, ne s’applique que lorsque π = xπ et v = xv
pour le même x ∈ A.
• Chaque modification D ajoute une règle à la liste qui constituera l’analyse de u. Or, S =⇒
g
1
wXπ =⇒ wαπ n’est une analyse partiele de u que s’il existe une dérivation απ =⇒ v.
g g
Une condition nécessaire à l’existence d’une telle dérivation est, si l’on prévoit 1 caractère
x = P remier(v), que :
– ou bien x ∈ P remier(α),
– ou bien ε ∈ P remier(α) et x ∈ Suivant(X).

142 Chapitre 4
4.2 – Automate à pile LL(1).

Ce qui précède est adapté à l’analyse d’un u ∈ A∗ particulier : si on veut traiter le problème plus
globalement, on est conduit à considérer les couples (π, v) au lieu des triplets (w; π, v) et à poser
la définition suivante.
L’automate à pile pour l’analyse LL(1) de G est défini de la façon suivante :
Une configuration est un couple (π, v) où v ∈ A∗ et où π ∈ (A + V)∗ est traité comme une pile
dont le sommet est à gauche.
Les transitions sont de deux types :
(L) (xπ, xv) (π, v) pour tout x ∈ A,
(D) (Xπ, v) (απ, v) pour (X −→ α) ∈ M (X, P remier(v))
où, pour X ∈ V et x ∈ ε + A.
La configuration initiale pour l’analyse de u est (ε, u).
La configuration finale est (ε, ε).
M (X, x) est un ensemble de règles de G défini de la façon suivante :
Table LL(1)
Les M ( , ) sont les plus petits ensembles de règles tels que :
pour toute X ∈ V, toute règle X −→ α et tout x ∈ P remier(α) :
– si x ∈ A alors (X −→ α) ∈ M (X, x)
– si x = ε alors (X −→ α) ∈ M (X, y) pour tout y ∈ Suivant(X).
L’application à un u ∈ A∗ particulier permet effectivement de faire le lien avec les observations de

la section précédente :
Propriété.
Pour tout u ∈ A∗ :
∗
u ∈ L(G, S) ssi (S, u) (ε, ε)
∗
où signifie l’existence d’un enchaı̂nement de transitions.
La démonstration de cette propriété est basée sur des récurrences très évidentes.
4.3 – Grammaires LL(1).

Une grammaire est LL(1) ssi sa table LL(1) est déterministe, c’est–à–dire ssi chaque M (X, x)
contient au plus un élément.
Lorsque c’est le cas, u ∈ L(G, S) équivaut donc à l’existence d’exactement une dérivation
l k
(S, u) (ε, ε), c’est–à–dire à celle d’exactement une dérivation à gauche S =⇒ u.
g
Remarques.
• Ce qui vient d’être dit implique en particulier qu’une grammaire LL(1) n’est pas ambiguë.
• En regardant la définition en détails, on peut vérifier qu’une grammaire qui comporte une règle
“récursive à gauche” X −→ Xα n’est pas LL(1), mais les méthodes de dérécursion (voir chapitre
3) peuvent alors s’appliquer.
• De même, qu’une grammaire n’est pas LL(1) lorsqu’elle admet une factorisation, c’est–à–dire,
deux règles distinctes X −→ ξα et X −→ ξβ pour ξ ∈ A + V.
En fait, ces deux derniers points peuvent se résoudre en modifiant la grammaire de façon adéquate.

Section 4 143
4.3.1 – Algorithme d’analyse LL(1).

Soit G une grammaire avec S comme axiome et dont la table LL(1) est déterministe.
L’analyse LL(1) de u ∈ A∗ par G s’effectue à partir de la “configuration initiale” (S, u) en tentant
d’exécuter une suite d’opérations (L) et (D). Chaque application de (D) ajoute une règle à la “liste
d’analyse”, initialement vide.
Notons (π, v) la configuration à laquelle on est parvenu (π est la “pile” dont le sommet est à gauche
et v l’“entrée” c’est–à–dire le facteur droit du mot restant à analyser) :
• si π = xπ avec x ∈ A :
– si v = xv : on fait la lecture de x, c’est–à–dire que l’on passe à la configuration (π , v ) par
application de (L),
• si π = Xπ avec X ∈ V :
– si X −→ α ∈ M (X, P remier(v)) : on passe à la configuration (απ , v), par application de
(D),
• si π = ε et v = ε, on est parvenu à la “configuration d’acceptation” : l’analyse est achevée, de
façon positive,
• Dans les autres cas : l’analyse se termine sur un échec. Un bonne table d’analyse doit comporter
la table).
Exemple.
Considérons la grammaire G4 :
1 : E −→ T E 4 : T −→ F T 7 : F −→ (E)

2 : E −→ ⊕T E 5 : T −→ ∗F T 8 : F −→ id
3 : E −→ ε 6 : T −→ ε
La construction de la table LL(1) de G4 est basée sur les données ci–dessous, dont le calcul est
facile.
Eps(G) = E + T
P remier(E) = P remier(T ) = P remier(F ) = (+id
P remier(E ) = ⊕ + ε, P remier(T ) = ∗ + ε
Suivant(E) = Suivant(E ) =) + ε
Suivant(T ) = Suivant(T ) = ⊕+) + ε
Suivant(F ) = ⊕ + ∗+) + ε
ε ⊕ ∗ ( ) id
E 1 1
E 3 2 3
T 4 4
T 6 6 5 6
F 7 8
La table LL(1) de G4 .

144 Chapitre 4
Pile Entrée Actions

E id ⊕ id ∗ id 1 : E −→ T E
T E id ⊕ id ∗ id 4 : T −→ F T
F T E id ⊕ id ∗ id 8 : F −→ id
idT E id ⊕ id ∗ id (Lecture de id)

T E ⊕id ∗ id 6 : T −→ ε
E ⊕id ∗ id 2 : E −→ ⊕T E
⊕T E ⊕id ∗ id (Lecture de ⊕)

TE id ∗ id 4 : T −→ F T
F T E id ∗ id 8 : F −→ id
idT E id ∗ id (Lecture de id)

T E ∗id 5 : T −→ ∗F T
∗F T E ∗id Lecture de ∗
F T E id 8 : F −→ id

idT E id (Lecture de id)

T E ε 6 : T −→ ε
E ε 3 : E −→ ε
ε ε OK
L’analyse LL(1) de id ⊕ id ∗ id dans G4 .

Exercices 145
EXERCICES.
Analyse LR.
Exercice 1.
Montrer que la grammaire suivante est LR(0) :
1 : S −→ CC 2 : C −→ c C 3 : C −→ d
Exercice 2.
Montrer que la grammaire suivante est LR(0) :
1 : S −→ f SS 2 : S −→ g S 3 : S −→ a
Faire l’analyse de g f f a g a g a et construire l’arbre de dérivation correspondant.
Exercice 3.
La grammaire suivante est–elle LR(0) ? SLR(1) ?
1 : S −→ SS f 2 : S −→ S g 3 : S −→ a
Faire l’analyse de a g a g a f f g et construire l’arbre de dérivation correspondant.
Exercice 4.
Construire la table SLR(1) de la grammaire suivante :
1 : E −→ T F 2 : F −→ ε 4 : T −→ (E)
3 : F −→ ⊕T F 5 : T −→ id
La grammaire en question est–elle SLR(1) ? Si oui, utiliser la table pour faire l’analyse de id ⊕( id )
et construire l’arbre de dérivation correspondant.
Exercice 5.
Voici quelques grammaires sur la nature desquelles vous pourrez vous interroger. Au passage,
vérifiez que, pour toute grammaire G :
– si G est LR(0) alors G est SLR(1),
– si G est SLR(1) alors G est LALR(1),
– si G est LALR(1) alors G est LR(1).
G5 : 1 : S −→ a A c 2 : A −→ A b b 3 : A −→ b
G6 : 1 : A −→ a S 2 : S −→ b S 3 : S −→ a a b
G7 : 1 : A −→ BA 2 : A −→ a 3 : B −→ AB 4 : B −→ b
G8 : 1 : S −→ S a S b 2 : S −→ ε
G9 : 1 : S −→ AB 2 : A −→ a A b 4 : B −→ b B
3 : A −→ ε 5 : B −→ b
G10 : 1 : S −→ AB 3 : B −→ CD 5 : C −→ a b 7 : E −→ b b a
2 : A −→ a 4 : B −→ a E 6 : D −→ b b
G11 : 1 : S −→ S ⊕ A 3 : A −→ (S) 5 : A −→ a
2 : S −→ A 4 : A −→ a (S)
G12 : 1 : S −→ a D ; I b 2 : D −→ D ; d 4 : I −→ i ; I
3 : D −→ d 5 : I −→ i

146 Chapitre 4
Utilisation de grammaires ambiguës.

Les langages de programmation permettent l’usage de quelques ambiguı̈tés. Les programmes
y gagnent en simplicité mais ne seraient pas analysables par une méthode déterministe si
certaines conventions n’étaient pas posées, par exemple : il est en général convenu que l’expression
id + id + id sera calculée comme ( id + id ) + id .
Il existe deux méthodes pour faire l’analyse syntaxique de telles expressions :
1) On utilise une grammaire ambiguë, qui suit exactement la syntaxe des espressions en
question : les conflits, qui se présentent inévitablement dans la table d’analyse, sont résolus
en choisissant (une fois pour toute !) dans chaque état de l’AFD, l’action qui correspond à
la façon dont on prétend faire l’analyse. Yacc est capable de faire ce choix, dans des cas
simples, lorsqu’on lui donne des informations sur l’associativité (ou la non associativité) des
opérations et sur leur préséance relative.
Cette opération consiste en fait à sélectionner certaines dérivations, parmi toutes celles qui
sont possibles : on court ainsi le risque de ne plus pouvoir analyser des phrases qui sont
pourtant dans le langage engendré par la grammaire !
2) On utilise une grammaire non ambiguë qui est capable de faire l’analyse correctement.
Cette méthode paraı̂t plus saine que la précédente mais, sa mise en œuvre nécessite une
grammaire plus complexe, en particulier comportant plus de variables ; les analyses dans
une telle grammaire sont souvent beaucoup plus longues que dans la méthode 1).
Les deux exercices qui suivent ont pour but de montrer comment on pratique la première méthode.
La seconde méthode est seulement illustrée par la donnée d’une grammaire permettant sa mise en
œuvre : les vérifications utiles sont laissées à votre initiative personnelle !
Exercice 6. Ambiguı̈té des expressions arithmétiques.
Calculer la table SLR(1) de la grammaire
1:E →E⊕E 2:E →E∗E 3 : E → (E) 4 : E → id
puis résoudre les conflits que l’on peut y observer de telle façon que ⊕ et ∗ soient associatives à
gauche et que ∗ ait une préséance supérieure à ⊕.
(La grammaire
E →E⊕T T →T ∗F F → (E)
E→T T →F F → id
équivalente à la précédente, est SLR(1) et prend en compte les conventions précédentes.)
Exercice 7. Ambiguı̈té du “sinon en suspens”.
La grammaire suivante décrit les instruction conditionnelles :
I → si E alors I sinon I I → si E alors I I → autre
Pour l’étudier, nous en considérons la forme abrégée suivante :
1:I → iI eI 2:I → iI 3:I→ a
Calculer la table SLR(1) de cette grammaire puis, résoudre le conflit que l’on peut y observer
de telle façon que la règle habituelle soit respectée : “un sinon est associé au dernier alors en
suspens”, c’est–à–dire, par exemple, que la phrase i i a e a soit analysée comme i [ i a e a ].
Serait–il possible de faire un choix autre que celui qui vient d’être fait ?
(La grammaire
I→J J→ iJ eJ K→ iI
I→K J→ a K→ iJeK
équivalente à la précédente, est SLR(1) et prend en compte la convention précédente.)

Exercices 147
Exercice 8. Récursion et pile d’analyse.

On considère les grammaires sur l’alphabet de terminaux composé des digits binaires 0 et 1 et
du point “binaire” . pour représenter les rationnels en notation binaire et l’alphabet de variables
V = S + E + D + B où S est choisie comme axiome :
G dont les règles sont
1 : S −→ E . D 3 : E −→ EB 5 : D −→ BD 7 : B −→ 0
2 : S −→ E 4 : E −→ B 6 : D −→ B 8 : B −→ 1

et G dont les règles sont celles de G à l’exception de 5 : qui est remplacée par 5’ : D −→ DB.
Les grammaires sont assez simples et admettent une analyse ascendante : il est facile de simuler
un analyseur de type LR pour traiter la question qui suit.
Faire une analyse LR de 1 . 0 0 1 1 1 dans les deux grammaires et comparer l’évolution des
piles respectives.
(Il manque la définition intrinsèque des grammaires LR(k))
Analyse LL.
(Il faudrait ajouter des exercices sur l’analyse descendante.)

148 Chapitre 4

THL 4

Transféré par

Droits d'auteur :

Formats disponibles

THL 4

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

THL 4

Transféré par

Droits d'auteur :

Formats disponibles

4

Théorie des langages. M.M Institut Galilée 2000

– Mode d’association : de même, une expression de la forme α ⊕ β ⊕ γ devra généralement

2 – Dérivations à droite et analyse ascendante.

M.M Institut Galilée 2000 Analyse syntaxique.

2.1 – Analyse ascendante.

Analyse syntaxique. M.M Institut Galilée 2000

2.2 – Configuration d’analyse partielle et préfixes viables.

Forme générale des dérivations à droite.

où X −→ α β est sa première règle et où v ∈ A∗ (bien entendu, on a α v = γ).

Nous dirons que cette dérivation est la composée de

ce qui, dans le cas où n = 0 se présente sous la forme particulière suivante :

• La composée de ces dérivations a la forme

où π = α1 . . . αn et v = vn . . . v1 .

M.M Institut Galilée 2000 Analyse syntaxique.

Analyse syntaxique. M.M Institut Galilée 2000

2.3 – Item LR(0) d’une grammaire G.

Nous dirons simplement “item” pour “item LR(0)”.

– une ε–transition est déﬁnie sur les états de la forme . X −→ α . Y β, par

pour toute règle Y −→ γ

M.M Institut Galilée 2000 Analyse syntaxique.

Propriétés de l’AFD des item.

Analyse syntaxique. M.M Institut Galilée 2000

M.M Institut Galilée 2000 Analyse syntaxique.

Analyse syntaxique. M.M Institut Galilée 2000

2.4 – L’automate à pile LR(0).

2.5 – Grammaires LR(0).

M.M Institut Galilée 2000 Analyse syntaxique.

3 – Analyse ascendante avec symboles de prévision.

Analyse syntaxique. M.M Institut Galilée 2000

Pile Pile d’états Entrée Actions

L’analyse LR(0) de ¬(id ∧ ¬id) dans G1 .

Exemple de conflit décalage–réduction.

M.M Institut Galilée 2000 Analyse syntaxique.

3.1 – Symboles de prévision.

3.1.1 – Calcul de P remier.

Analyse syntaxique. M.M Institut Galilée 2000

• En apliquant 4) et 3) on voit que :

P remier(E) = P remier(E ⊕ T ) + P remier(T ) = P remier(E) + P remier(T )

P remier(E) = P remier(T ) = P remier(F ) = ( +id.

3.1.2 – Calcul de Suivant.

La vériﬁcation de la propriété est facile.

M.M Institut Galilée 2000 Analyse syntaxique.

Appliquons cette construction à la grammaire de l’exemple précédent.

Suivant(F ) = Suivant(T ) = ε + ⊕ + ∗+)

3.2 – Automate à pile de type LR(1).

(D) (χq, xv) (χqr, v) si x ∈ A et q.x = r

Table de type LR(1)

Analyse syntaxique. M.M Institut Galilée 2000

3.2.1 – Les trois types LR(1).

– une ε–transition est déﬁnie sur les états de la forme (. X −→ α . Y β, x) par

pour chaque (Y −→ γ) ∈ R et chaque y ∈ P remier(βx).

3.3 – Grammaires de type LR(1).

3.3.1 – Algorithme d’analyse de type LR(1).

M.M Institut Galilée 2000 Analyse syntaxique.

• si Action(q, P remier(v)) = r où r est un état (alors on a nécessairement P remier(v) = x ∈ A

Exemple 2 : analyse SLR(1).

Analyse syntaxique. M.M Institut Galilée 2000

Pile Pile d’états Entrée Actions