CHAPITRE 5 : ANALYSE SYNTAXIQUE :

METHODES ASCENDANTES
5.1 Introduction lanalyse ascendante
Les mthodes ascendantes construisent larbre syntaxique de bas en haut, en partant de la chane analyse
(feuilles de larbre), puis, en assemblant, par des rductions, les sous-arbres sous les nouveaux nuds non
terminaux jusqu laxiome (racine de larbre).
Le modle gnral utilis en analyse ascendante est le modle par dcalage-rduction (shift-reduce) qui
autorise deux oprations :

dcaler (shift) : dcaler, dun symbole, le pointeur sur la chane dentre.

rduire (reduce) : rduire une chane par un non terminal en utilisant une des rgles de production,
sachant que la chane rduite est une suite de terminaux et non terminaux gauche du pointeur sur
lentre et finissant sur ce pointeur.

Exemple
Soit la grammaire G ayant les rgles de production suivantes :
S aABe
A Abc| b
B d
On se propose danalyser la chane abbcde de manire ascendante.
abbcde
abbcde
aAbcde
aAbcde
aAbcde
a A de
a A de
a A Be
a A Be
S

dcaler
rduire
dcaler
dcaler
rduire
dcaler
rduire
dcaler
rduire
Analyse russie

S
A
B
A

Figure 5.1. Arbre syntaxique obtenu de manire

ascendante pour la chane abbcde

En rsum, on a donc les rductions suivantes, partir desquelles on peut dduire, de manire ascendante,
larbre syntaxique correspondant la chane abbcde (voir figure 5.1) :
abbcde
aAbcde
a A de
a A Be
S
On constate que la squence de rductions prcdentes correspond, en sens inverse, aux drivations droites
suivantes : S aABe aAde aAbcde abbcde

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

48

Remarque : Il serait intressant de disposer dun moyen automatique pour choisir sil faut effectuer un
dcalage ou une rduction et quelle rduction choisir lorsque le pointeur dentre se trouve sur une position
donne.

5.2 Introduction aux analyseurs LR

Lanalyse LR (ou LR(k)) est une technique gnrale efficace danalyse syntaxique ascendante, base sur le
modle par dcalage-rduction et qui peut tre utilise pour analyser une large classe de grammaires non
contextuelles.
L : Left to right scanning (on parcourt ou on analyse la chane en entre de la gauche vers la droite)
R : constructing a Rightmost derivation in reverse (en construisant une drivation droite inverse)
k : on utilise k symboles dentre de prvision chaque tape ncessitant la prise dune dcision daction
danalyse. Quand k est omis , il est suppos gal 1.
Les analyseurs LR comportent :

Un algorithme danalyse commun aux diffrentes mthodes LR.

Une table danalyse dont le contenu diffre selon le type danalyseur LR.

On distingue trois techniques de construction de tables danalyse LR pour une grammaire donne :

Simple LR (SLR) : qui est la plus simple implmenter, mais la moins puissante des trois.

LR canonique : qui est la plus puissante, mais aussi la plus coteuse.

LookAhead LR (LALR) : qui a une puissance et un cot intermdiaires entre les deux autres et peut
tre applique la majorit des grammaires de langages de programmation.

5.2.1 Modle danalyseur LR

Un analyseur LR peut tre assimil un automate pile, il est modlis, comme le montre la figure 5.2, par un
tampon dentre, un flot de sortie, une pile, un programme danalyse (le mme pour tous les analyseurs LR) et
des tables danalyse divises en deux parties : Action et Successeur (Goto).

Action
Tampon dEntre
a1

..

..

an

Successeur

Programme
danalyse
LR

Flot de Sortie
Sm
Xm

Pile

S0

b
Figure 5.2. Modle dun analyseur LR
Le programme danalyse range dans la pile des chanes de la forme S 0X1S1X2S2XmSm. Chaque Xi est un
symbole de la grammaire (Xi (VTUVN)) et chaque Si est un tat (state) de lanalyseur qui rsume linformation
contenue dans la pile au dessous de lui, la combinaison du numro de ltat en sommet de pile et du symbole
dentre courant est utilis pour indicer les tables et dterminer laction effectuer (dcaler ou rduire).

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

49

Les tables danalyse contiennent deux parties : une fonction daction danalyse (action) et une fonction de
transfert (successeur). Linformation contenue dans ces champs reprsente la diffrence entre les analyseurs
LR.

5.2.2 Algorithme danalyse LR

Le programme danalyse LR dtermine Sm (ltat en sommet de pile) et ai (le symbole terminal dentre
courant). Ceci correspond la configuration de lanalyseur (S0X1S1X2S2XmSm, aiai+1 an$) sachant que la
configuration initiale est (S0, a1a2 an$). Lanalyseur consulte Action [Sm, ai], dans la table des actions, qui
peut avoir une des quatre valeurs : dcaler, rduire, accepter ou erreur.
1er cas : Action [Sm, ai]=dcaler S (shift S) :
Lanalyseur empile ai et S, ai+1 devient le symbole dentre courant. La configuration de lanalyseur devient
donc : (S0X1S1X2S2XmSmaiS, ai+1 an$).
2me cas : Action [Sm, ai]=rduire par A:
Lanalyseur dpile 2r symboles, r symboles dtats et r symboles de grammaire, avec r=||=longueur de . Sm-r
devient le nouveau sommet de pile, ensuite lanalyseur empile A (partie gauche de la production A) et S
(entre pour Successeur[Sm-r, A]).
Remarques :
Le symbole dentre courant ne change pas avec une rduction.
La squence dpile Xm-r+1Xm correspond . La configuration de lanalyseur devient donc :
(S0X1S1X2S2Xm-rSm-rAS, aiai+1 an$).
3 me cas : Action [Sm, ai]=accepter:
Lanalyse est termine en acceptant la chane analyse.
4me cas : Action [Sm, ai]=erreur :
Lanalyse est termine en rejetant la chane analyse.

Rsum de lalgorithme danalyse LR

Entre : Chane w et table danalyse LR
Sortie : Rsultat de lanalyse ascendante de w si w L(G) (arbre syntaxique) ou chec si wL(G).
Mthode : on commence avec S0 dans la pile, w$ dans le tampon dentre, le pointeur source ps est initialis
au dbut de w. Lanalyseur excute la boucle Rpter jusqu ce quil rencontre une action Accepter ou Erreur.
Algorithme Analyse LR;
Rpter indfiniment
Dbut
Soit S ltat en sommet de pile et a le symbole point par ps
Si Action [S, a]= Dcaler S Alors
Dbut
Empiler a puis S ;
Avancer ps ;
Fin ;
Sinon Si Action [S, a]= Rduire par A Alors
Dbut
Dpiler 2|| symboles ;
Soit S le nouveau sommet de pile ;
Empiler A puis Successeur[S, A] ;
Emettre en sortie A ;
Fin
Sinon Si Action [S, a]= Accepter Alors Return Sinon Erreur() ;
Fin ;

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

50

5.2.3 Exemple dapplication de lalgorithme danalyse LR

Soit la grammaire G ayant les rgles de production suivantes :
E E+T
E T
T T*F

T F
F (E)
F id

Soit la table danalyse LR suppose dj construite :

Etat
+
0
1
2
3
4
5
6
7
8
9
10
11

d6
r2
r4

d7
r4

r6

r6

d6
r1
r3
r5

Action
(
)
d4

d4
d4
d4

d7
r3
r5

r2
r4
r6
d11
r1
r3
r5

id
d5

$
acc
r2
r4

d5

Successeur
E
T
F
1
2
3

r6

d5
d5

3
10

r1
r3
r5

Laction di signifie dcaler et empiler ltat i.

Laction rj signifie rduire par la production dont le numro est j.
Laction acc signifie accepter la chane analyse.
Une entre vide correspond une erreur.

On se propose maintenant danalyser la chane id *id+id.

Pile
S0
S0idS5
S0FS3
S0TS2
S0TS2*S7
S0TS2*S7 idS5
S0TS2*S7FS10
S0TS2
S0ES1
S0ES1+S6
S0ES1+S6idS5
S0ES1+S6FS3
S0ES1+S6TS9
S0ES1

Entre
id*id+id$
*id+id$
*id+id$
*id+id$
id+id$
+id$
+id$
+id$
+id$
id$
$
$
$
$

Sortie
Dcaler (d5)
Rduire Fid
Rduire TF
Dcaler (d7)
Dcaler(d5)
Rduire Fid
Rduire TT*F
Rduire ET
Dcaler (d6)
Dcaler (d5)
Rduire Fid
Rduire TF
Rduire EE+T
Accepter

5.3 Construction de table danalyse SLR

La construction dune table danalyse SLR (LR(0) ou SLR(1)) partir dune grammaire est la mthode la plus
simple implmenter (parmi les 3 mthodes SLR, LALR et LR canonique) mais cest la moins puissante du point
de vue du nombre de grammaire pour lesquelles elle russit. Elle constitue un bon point de dpart pour ltude
de lanalyse LR. Le principe de la mthode SLR est de construire, partir de la grammaire un automate fini
dterministe qui reconnat les prfixes viables de G (prfixes pouvant apparatre sur la pile) puis de transformer
cet automate en une table danalyse.

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

51

La construction
ditems LR(0).
Fermeture et
ncessaires la

des analyseurs SLR, pour une grammaire donne, est base sur la collection densembles
Pour construire cette collection, on dfinit une grammaire augmente, une fonction
une fonction Transition. Dans la section 5.3.1, on commence par dfinir les concepts
construction de collection densembles ditems LR(0) et de table danalyse SLR.

5.3.1 Concepts de base

5.3.1.1 Items LR(0)
Un item LR(0) dune grammaire G est une production de G avec un point (.) reprant une position de sa partie
droite.
Exemples
La production AXYZ fournit 4 items : A.XYZ, AX.YZ, AXY.Z et AXYZ.
La production A fournit un seul item A.
Remarque
Intuitivement, un item indique la quantit de partie droite qui a t reconnue un instant donn de lanalyse.
Par exemple, litem AX.YZ indique quon vient de voir en entre une chane drive de X et quon espre
maintenant voir une chane drive de YZ.

5.3.1.2 Grammaire augmente

Si G est une grammaire daxiome S, alors la grammaire augmente de G (note G) aura un nouvel axiome S et
une nouvelle rgle de production SS. Le but de lajout de cette production est dindiquer lanalyseur quand
il doit sarrter et annoncer lacceptation de la chane dentre (quand lanalyseur est sur le point de rduire S
par S).

5.3.1.3 Fonction Fermeture dun ensemble ditems LR(0)

Soit I un ensemble ditems pour une grammaire G. Fermeture (I) est lensemble ditems construit partir de I
par lapplication des 2 rgles suivantes :
Rgle 1 : initialement placer chaque item de I dans Ferm(I)
Rgle 2 : si A.B Ferm(I) et B est une production de G, alors ajouter B. Ferm(I), sil ny existe
pas dj. La rgle 2 doit tre applique jusqu ne plus pouvoir ajouter de nouveaux items Ferm(I).
Ainsi, la fonction Ferm(I) peut tre dfinie de la manire suivante :
Fonction Ferm(I);
Dbut
J :=I ;
Rpter
Pour chaque item A.B J et chaque production B telle que B. J
Faire Ajouter B . J
Jusqu ce quaucun item ne puisse tre ajout J ;
Ferm(I) :=J;
Fin ;
Exemple
Soit la grammaire G, ayant les rgles de production suivantes :
E E+T | T
T T*F | F
F (E) | id
Soit lensemble ditems I= {[E.E]}. On se propose de calculer Ferm(I). En appliquant les deux rgles
prcdentes, on trouve : Ferm(I) = { [E.E], [E.E+T], [E.T], [T.T*F], [T.F], [F.(E)], [F.id] }

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

52

5.3.1.4 Fonction Transition

Soit I un ensemble ditems et X un symbole de la grammaire (XVTUVN). Transition (I, X) est dfinie comme
tant la fermeture de tous les items [AX.] tels que [A.X] I.
Exemple
En utilisant la grammaire prcdente, on se propose de dterminer, pour I= {[EE.], [EE.+T]}, la fonction
Trans(I, +).
Trans(I, +)= Ferm ([EE+.T]) = {[EE+.T], [T.T*F], [T.F], [F.(E)], [F.id]}

5.3.2 Construction de la collection densembles ditems LR(0)

La collection canonique densembles ditems LR(0) correspond aux tats de lAFD permettant de reconnatre les
prfixes viables de la grammaire. La dtermination de cette collection constitue la base de la construction des
tables danalyses SLR. Lalgorithme suivant permet de dterminer C : la collection canonique densemble ditems
LR(0) pour une grammaire augmente G
Procdure CollectionEnsembleItems;
Dbut
C := {Ferm({[S.S]})} ;
Rpter
Pour chaque ensemble ditems I de C et pour chaque symbole
de la grammaire X tel que Trans(I, X) soit non vide et non encore dans C
Faire ajouter Trans(I, X) C
Jusqu ce quaucun ensemble ditems ne puisse tre ajout C;
Fin ;
Exemple
On se propose de dterminer la collection canonique densembles ditems de la grammaire augmente
suivante :
EE
E E+T | T
T T*F | F
F (E) | id
I0 =
=

Ferm {[E.E]}
E.E
E.E+T
E.T
T.T*F
T.F
F.(E)
F.id

I1= Trans(I0, E) = Ferm {[EE.], [EE.+T]}

= EE.
EE.+T
I2 = Trans(I0, T) = Ferm {[ET.], [TT.*F] }
= ET.
TT.*F
I3 = Trans(I0, F) = Ferm {[TF.]}
= TF.

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

53

I4 = Trans(I0, ( )= Ferm {[F(.E)]}

= F(.E)
E.E+T
E.T
T.T*F
T.F
F.(E)
F.id
I5 = Trans(I0,id) = Ferm {[Fid.]}
= Fid.
I6 = Trans(I1,+) = Ferm {[EE+.T]}
= EE+.T
T.T*F
T.F
F.(E)
F.id
I7 = Trans(I2,*) = Ferm {[TT*.F]}
= TT*.F
F.(E)
F.id
I8 = Trans(I4,E) = Ferm {[F(E.)], [EE.+T] }
= F(E.)
EE.+T
I2 = Trans(I4, T) = Ferm {[ET.], [TT.*F]}
I3 = Trans(I4, F) = Ferm {[TF.]}
I4 = Trans(I4, () = Ferm {[F(.E)]}
I5 = Trans(I4,id) = Ferm {[Fid.]}
I9 = Trans(I6, T) = Ferm {[EE+T.], [TT.*F]}
= EE+T.
TT.*F
I3 = Trans(I6, F) = Ferm {[TF.]}
I4 = Trans(I6, () = Ferm {[F(.E)]}
I5 = Trans(I6,id) = Ferm {[Fid.]}
I10 = Trans(I7,F)= Ferm {[TT*F.]}
= TT*F.
I4= Trans(I7, () = Ferm {[F(.E)]}
I5= Trans(I7.id) = Ferm {[Fid.]}
I11=Trans(I8, ) ) = Ferm {[F(E).]}
= F(E).
I6 = Trans(I8, +) = Ferm {[EE+.T]}
I7 = Trans(I9, *) = Ferm {[TT*.F]}
La fonction de transition pour la collection canonique densembles ditems de la grammaire augmente
considre dans cet exemple est donne sous forme dun AFD reprsent par la figure 5.3.

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

54

I0

I1

I6
F

vers I5
F

I7
(

I10
vers I4

id
F

vers I7

vers I4

id
I2

vers I3

I9

vers I5

I3
(

I4

id
T
F
id

I8

I11
vers I6

vers I2
vers I3

I5

Figure 5.3. Reprsentation de lAFD correspondant lexemple

5.3.3 Algorithme de construction de table danalyse SLR

La construction dune table danalyse SLR pour une grammaire G est effectue de la manire suivante :

Effectuer une augmentation de G pour obtenir la grammaire augmente G

Construire C la collection canonique densembles ditems LR(0) pour G, soit C={I0, I1, I2, .IN}

Construire les fonctions ACTION (actions danalyse) et SUCCESSEUR (transition) partir de C en

utilisant lalgorithme suivant :

Algorithme ConstructionTableSLR;
Dbut
1/ Ltat i est construit partir de Ii. La partie ACTION pour ltat i est dtermine comme suit:
a. Si [A.a] Ii et Trans (Ii, a)= Ij (avec a VT) Alors ACTION [i, a] dj (dcaler j)
b. Si [A.] Ii (avec AS) Alors ACTION [i, a] rnum pour tout a Suiv(A)
(rduire par la rgle A dont le numro est num )
c. Si [SS.] Ii Alors ACTION [i, $] accepter
2/ La partie SUCCESSEUR pour ltat i est dtermine comme suit :
Si Trans (Ii, A)= Ij Alors SUCCESSEUR [i, A] j
3/ Toutes les entre restantes dans la table sont mises ERREUR
4/ Ltat initial de lanalyseur est construit partir de lensemble ditems contenant [S.S]
Fin ;

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

55

Exemple
En appliquant lalgorithme ci-dessus, on se propose de construire la table SLR correspondant la grammaire G
de lexemple prcdent (dont on a dtermin la collection canonique densembles ditems). On obtient la table
SLR suivante :
Etat
0
1
2
3
4
5
6
7
8
9
10
11
Sachant que :
Suiv(E)= {+, ), $}
Suiv(T)= {, +, ), $}
Suiv(F)= {, +, ), $}

d6
r2
r4

Action
(
)
d4

d7
r4

r2
r4

r6

r6

d6
r1
r3
r5

d7
r3
r5

d4
d4
d4

r6
d11
r1
r3
r5

id
d5

d5
d5
d5

$
acc
r2
r4
r6

Successeur
E
T
F
1
2
3

3
10

r1
r3
r5

5.3.4 Grammaire SLR (1)

Les tables obtenues avec lalgorithme dfini dans la section prcdente (5.3.3) sont appeles les tables
SLR(1). Un analyseur utilisant ces tables est appel analyseur SLR(1). Une grammaire est dite SLR(1) ou
SLR si elle peut tre reprsente par une table SLR(1) dont chaque entre est dfinie de faon unique (d /r /acc
/erreur).
Exemple
Soit la grammaire G, ayant les rgles de production suivantes :
S G=D | D
G *D | id
DG
On se propose de montrer si cette grammaire est SLR(1).
On commence dabord par augmenter la grammaire :
SS
S G=D
SD
G *D
G id
D G

Dtermination de la collection canonique densembles ditems :

I0= Ferm {[S.S]}
= S.S
S.G=D
S.D
G.*D
G.id
D.G

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

56

I1= Trans (I0, S) =

=
I2= Trans (I0, G) =
=

Ferm{[SS.]}
SS.
Ferm {[SG.=D], [DG.]}
SG. =D
DG.
I3=Trans (I0, D) = Ferm {[SD.]}
= SD.
I4= Trans(I0, *) =Ferm{[G*.D]}
= G*.D
D.G
G.*D
G.id
I5= Trans(I0, id) = Ferm {[Gid.]}
= Gid.
I6= Trans (I2,=) = Ferm {[SG=.D]}
=SG=.D
D.G
G.*D
G.id
I7= Trans (I4, D) = Ferm {[G*D.]}
= G*D.
I8= Trans (I4,G) = Ferm {[DG.]}
= DG.
I4= Trans (I4,*) = Ferm {[G*.D]}
= G*.D
I5= Trans (I4,id) = Ferm {[Gid.]}
I9= Trans (I6,D) = Ferm {[SG=D.]}
= SG=D.
I8= Trans(I6,G) = Ferm {[DG.]}
= DG.
I4= Trans(I6, *) = Ferm {[G*.D]}
I5= Trans(I6, id) = Ferm {[Gid.]}
= Gid.
Construction de la table danalyse SLR :
Etat
0
1
2
3
4
5
6
7
8
9
Sachant que :
Suiv(D)= {=, $}
Suiv(G)= {=, $}
Suiv(S)= { $}

Action
*
id
d4
d5

d6/r5
r4
r3
r5

d4

d5

d4

d5

$
acc
r5
r2
r4

Successeur
S
G
D
1
2
3

r3
r5
r1

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

57

Remarque
On constate que Action[2,=] est une case dfinie de faon multiple. Ltat 2 prsente un conflit d/r
(dclarer/rduire) ou s/r (shift/reduce) sur le symbole dentre = donc la grammaire nest pas SLR (1).
Dans notre cas, la grammaire nest pas ambigu mais elle nest pas SLR(1). Dailleurs, beaucoup de grammaires
non ambigus ne sont pas SLR(1). Le conflit shift/rduce (dcaler/rduire) dans lexemple prcdent provient
du manque de puissance de la mthode SLR qui ne peut pas se rappeler assez de contexte gauche pour
dcider de laction de lanalyseur sur lentre = aprs avoir vu une chane pouvant tre rduite vers G.
Les mthodes LR canonique et LALR russissent pour un nombre plus important de grammaires
que la mthode SLR.

5.4 Construction de tables danalyse LR canonique ou LR(1)

La construction de tables danalyse LR canonique ou LR(1) est la technique la plus gnrale de construction de
tables danalyse LR pour une grammaire. Cette mthode permet dattacher plus dinformations un tat pour
viter un certain nombre dactions invalides et donc de conflits.

5.4.1 Items LR(1)

La forme gnrale dun item LR(1) est [A., a] sachant que :
A est une rgle de production de la grammaire et a VT U {$}.
Le 1 du LR(1) fait rfrence la longueur d second composant, appel symbole de pr-vision de litem. La
prvision na aucun effet dans un item de la forme [A., a] avec , mais un item de la forme [A., a]
implique rduire par A uniquement lorsque le prochain symbole entre est a . Ceci signifie que la
rduction par A ne se fait que sur les symboles dentre a pour lesquels [A., a] est un item LR(1) de
ltat en sommet de pile. Lensemble de tels a sera toujours un sous ensemble de Suiv(A).

5.4.2 Fermeture densemble ditems LR(1)

La fonction Ferm(I) peut tre dfinie de la manire suivante :
Fonction Ferm(I);
Dbut
Rpter
Pour chaque item [A.B, a] I, chaque production B G
et chaque terminal bPrem(a) tel que [B., b] I
Faire Ajouter [B ., b] I
Jusqu ce quaucun item ne puisse tre ajout I;
Ferm(I) := I;
Fin ;

5.4.3 Fonction Transition

Soit I un ensemble ditems LR(1) et X un symbole de la grammaire (XVTUVN). Transition (I, X) est dfinie de la
manire suivante :
Fonction Trans(I, X);
Dbut
Soit J lensemble des items [AX., a] tels que [A.X, a] I.
Trans(I, X) := Ferm(J);
Fin ;

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

58

5.4.4 Construction de la collection densembles ditems LR(1)

Lalgorithme suivant permet de dterminer la collection densemble ditems LR(1) pour une grammaire
augmente G
Procdure CollectionEnsembleItems;
Dbut
C := {Ferm({[S.S, $]})} ;
Rpter
Pour chaque ensemble ditems I de C et pour chaque symbole
de la grammaire X tel que Trans(I, X) soit non vide et non encore dans C
Faire ajouter Trans(I, X) C
Jusqu ce quaucun ensemble ditems ne puisse tre ajout C;
Fin ;

5.4.5 Algorithme de construction de tables danalyse LR(1)

La construction dune table danalyse LR(1) pour une grammaire G est effectue de la manire suivante :

Effectuer une augmentation de G pour obtenir la grammaire augmente G.

Construire C la collection densembles ditems LR(1) pour G.

Construire les fonctions ACTION (actions danalyse) et SUCCESSEUR (transition) partir de C en

utilisant lalgorithme suivant :

Algorithme ConstructionTableLR;
Dbut
1/ Ltat i est construit partir de Ii. La partie ACTION pour ltat i est dtermine comme suit:
a. Si [A.a, b] Ii et Trans (Ii, a)= Ij (avec a VT) Alors ACTION [i, a] dj (dcaler j)
b. Si [A., a] Ii (avec AS) Alors ACTION [i, a] rnum
(rduire par la rgle A dont le numro est num )
c. Si [SS., $] Ii Alors ACTION [i, $] accepter
2/ La partie SUCCESSEUR pour ltat i est dtermine comme suit :
Si Trans (Ii, A)= Ij Alors SUCCESSEUR [i, A] j
3/ Toutes les entre restantes dans la table sont mises ERREUR
4/ Ltat initial de lanalyseur est construit partir de lensemble ditems contenant [S.S, $]
Fin ;

5.4.6 Grammaire LR(1)

Les tables obtenues avec lalgorithme dfini dans la section prcdente (5.4.5) sont appeles les tables
canoniques danalyse LR(1). Un analyseur utilisant ces tables est appel analyseur LR(1) canonique.
Une grammaire est dite LR(1) ou LR si elle peut tre reprsente par une table LR(1) dont chaque entre est
dfinie de faon unique.
Toute grammaire SLR(1) est une grammaire LR(1), mais, pour une grammaire SLR(1), lanalyseur
LR canonique peut avoir un nombre dtats suprieur lanalyseur SLR pour la mme grammaire.

5.4.7 Exemple de construction de tables danalyse LR(1)

Soit la grammaire G, ayant les rgles de production suivantes :
S CC
C cC | d
On se propose de montrer si cette grammaire LR(1) (Question 1 de lexercice 6 de la srie de TD no : 4).

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

59

On commence dabord par augmenter la grammaire :

SS
S CC
C cC

Cd
Dtermination de la collection densembles ditems LR(1) :
I0= Ferm {[S.S, $]}
= S.S, $
Prem(a)= Prem($)= {$}
S.CC, $
Prem(a)= Prem(C$)= {c, d}
C.cC, c/d
C.d, c/d
I1= Trans (I0, S) = Ferm{[SS., $]}
= SS., $
I2= Trans (I0, C) = Ferm {[SC.C, $]}
= SC.C, $
C.cC, $
C.d, $
I3=Trans (I0, c) = Ferm {[Cc.C, c/d]}
= Cc.C, c/d
C.cC, c/d
C.d, c/d
I4= Trans(I0, d) =Ferm{ [Cd., c/d]}
= Cd., c/d
I5= Trans(I2, C) = Ferm {[ SCC., $]}
= SCC., $
I6= Trans (I2, c) = Ferm {[ Cc.C, $]}
= Cc.C, $
C.cC, $
C.d, $
I7= Trans (I2, d) = Ferm {[ Cd., $]}
= Cd., $
I8= Trans (I3, C) = Ferm {[ CcC., c/d]}
= CcC., c/d
I3= Trans (I3, c) = Ferm {[ Cc.C, c/d]}
I4= Trans (I3, d) = Ferm {[Cd., c/d]}
I9= Trans (I6,C) = Ferm {[ CcC., $]}
= CcC., $
I6= Trans(I6, c) = Ferm {[ Cc.C, $]}
I7= Trans(I6, d) = Ferm {[ Cd., $]}
Construction de la table danalyse LR :
Action
Successeur
Etat
c
d
$
S
C
0
d3
d4
1
2
1
acc
2
d6
d7
5
3
d3
d4
8
4
r3
r3
5
r1
6
d6
d7
9
7
r3
8
r2
r2
9
r2

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

60

5.5 Construction de tables danalyse LALR

La mthode LALR(1) (Look Ahead LR) est souvent utilise en pratique car cest une mthode ayant un cot et
une efficacit intermdiaire en comparaison avec SLR(1) et LR(1). Pour une grammaire donne, la table
danalyse LALR(1) occupe autant de place (mme nombre dtats) que la table SLR(1) (moins que la table
LR(1)) et satisfait une grande classe de grammaires. Ainsi, il est plus intressant, plus facile et plus conomique
de construire des tables SLR ou LALR que des tables LR canoniques. A titre dexemple, les mthodes SLR et
LALR donnent un nombre dtats de plusieurs centaines pour un langage tel que Pascal alors quon arrive
plusieurs milliers dtats avec la mthode LR canonique.

5.5.1 Algorithme de construction de tables LALR(1)

Cet algorithme se base sur la construction de la collection densembles ditems LR(1) ainsi que la table danalyse
LR(1). Il utilise la notion de cur ditem LR(1), sachant que : item LR(1)=[cur, symbole de pr-vision].
Lide gnrale de cet algorithme est de construire les ensembles ditems LR(1) et de fusionner les ensembles
ayant un cur commun. La table danalyse LALR(1) est construite partir de la collection des ensembles
ditems fusionns. Signalons que cet algorithme est le plus simple, mais il existe dautres algorithmes plus
efficaces pour la construction de tables LALR(1), qui ne se basent pas sur la mthode LR(1).
Algorithme ConstructionTableLALR;
Dbut
1/ Construire la collection densembles ditems LR(1) pour la grammaire augmente G.
2/ Pour chaque cur prsent parmi les ensembles ditems LR(1), trouver tous les tats ayant ce mme
cur et remplacer ces tats par leur union.
3/ La table LALR(1) est obtenue en condensant la table LR(1) par superposition des lignes correspondant
aux tats regroups.
Fin ;
Pendant la superposition des lignes, il y a un risque de conflit :
Cas 1 : Conflit dcaler/dcaler ou shift/shift (di/dj)
Ce cas de conflit ne peut pas se produire car le dcalage se base sur llment aprs le point.
Cas 2 : Conflit dcaler/rduire ou shift/reduce (d/r)
Ce cas de conflit ne peut se produire que sil existe dans la table LR(1) pour lun, au moins des tats dorigine.
Cas 3 : Conflit rduire/rduire ou reduce/reduce (ri/rj)
Cest le seul conflit possible. Il se produit quand deux items LR(1) ayant respectivement la [AC.,x] et
[BC.,x] appartiennent un ensemble obtenu aprs regroupement dtats.
Conclusion: Pendant la superposition des lignes, le seul cas de conflit qui peut se produire est rduire/rduire.
Remarque
Sil ny a pas de conflit dans la table LALR(1), la grammaire sera considre LALR(1) ou LALR.

5.5.2 Exemple de construction de tables danalyse LALR(1)

On se propose de construire la table danalyse LALR(1) pour la grammaire G, traite dans la section 5.4.7
(Question 2 de lexercice 6 de la srie de TD no :4):
S CC
C cC | d

Pour la dtermination de la collection densembles ditems LALR(1), on recherche les ensembles ditems LR(1)
pouvant tre fusionns, on en trouve trois paires : I3 avec I6, I4 avec I7 et I8 avec I9 qui seront remplacs par
leurs unions respectives :

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

61

I36=Cc.C, c/d/$
C.cC, c/d/$
C.d, c/d/$
I47= Cd., c/d/$
I89= CcC., c/d/$
Les autres ensembles ditems (non concerns par les fusions) restent inchangs.
La construction de la table danalyse LALR est obtenue par superposition des lignes correspondant aux tats
fusionns:
Action
Successeur
Etat
c
d
$
S
C
0
d36 d47
1
2
1
acc
2
d36 d47
5
36
d36 d47
89
47
r3
r3
r3
5
r1
89
r2
r2
r2

5.5.3 Analyse de chanes par la mthode LALR(1)

Si la chane analyse est correcte syntaxiquement (appartient au langage), lanalyse LALR(1) progressera de la
mme manire que LR(1). Les seules diffrences sont dans lappellation ou la numrotation des tats de
transition.
Si la chane analyse est errone syntaxiquement (nappartient pas au langage), lerreur sera dtecte plus
rapidement par lanalyseur LR(1) alors que lanalyseur LALR(1) peut effectuer plusieurs rductions avant de
signaler lerreur.

Ces deux cas sont illustrs travers la rponse aux questions 4 et 5 de lexercice 6.

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

62

SERIE DE TD N:4 COMPILATION, ANALYSE SYNTAXIQUE ASCENDANTE

Exercice 1
Soit la grammaire G ayant les rgles de production suivantes :
S AaAb | BbBa
A
B
1. Cette grammaire est-elle une grammaire SLR?
2. Analyser la chane ab en utilisant la table danalyse SLR et en rsolvant les conflits ventuels.

Exercice 2
Soit la grammaire augmente ayant les rgles de production suivantes :
SE
E E+E | E*E | nb
1. Construire la table d'analyse syntaxique SLR pour cette grammaire.
2. Utiliser cette table pour analyser les chanes 1+2+3 et 1+2*3 en rsolvant les conflits ventuels.

Exercice 3
Soit la grammaire ayant les rgles de production suivantes :
S if a then S | if a then S else S | i
1.
2.
3.
4.

Construire larbre de drivation de la chane if a then if a then i else i. Que peut-on conclure ?
Cette grammaire peut-elle tre une grammaire SLR ? Justifier votre rponse.
Construire la table danalyse SLR pour cette grammaire.
Utiliser cette table pour analyser la chane if a if then i else i en rsolvant les conflits ventuels.

Exercice 4 ( faire la maison, pas de correction en TD, quelques indications de rponses dans lnonc de
lexercice)
Soit la grammaire G = ({debut, fin, ., ;, si, alors, sinon, a, :=, et }, {A, L, I, E}, A, P) o P est dfini par les rgles de
production suivantes :
A debut L fin .
L L;I|I
I si E alors I | si E alors I sinon I | a := E
E E et E | a
1. Construire la collection densembles ditems LR(0) pour cette grammaire.
2.

3.

(Rponse partielle : on trouve 21 ensembles ditems de I0 jusqu I20)

Dresser la table d'analyse syntaxique SLR.
(Rponse partielle : on trouve 2 conflits d/r)
Utiliser cette table pour analyser la chane : debut si a et a alors a := a sinon a := a fin. puis dduire son arbre
de drivation. (Rponse partielle : la chane est accepte aprs 26 tapes danalyse)

Exercice 5
Soit la grammaire G ayant les rgles de production suivantes :
S G=D | D
G *D | id
DG
1. Cette grammaire est-elle une grammaire LR(1)?
2. Utiliser la table LR(1) pour analyser les chanes : id=id et id==id

puis dduire leurs arbres de drivation respectifs.

Exercice 6 (correction en cours)

Soit la grammaire G ayant les rgles de production suivantes :
S CC
C cC | d
1. Cette grammaire est-elle une grammaire LR(1)?
2. Cette grammaire est-elle une grammaire LALR(1)?
3. Peut-on dduire si cette grammaire est SLR ? Quelle est la taille de sa table SLR ?
4. Analyser la chane ccdccd et dduire son arbre de drivation en utilisant les mthodes LR et LALR. Conclusion ?
5. Analyser la chane ccd et dduire son arbre de drivation en utilisant les mthodes LR et LALR. Conclusion ?

Exercice 7
Soit la grammaire G ayant les rgles de production suivantes :
S aAd | bBd | aBe | bAe
A c
B c
1. Cette grammaire est-elle une grammaire LR(1)? Utiliser la table LR(1) pour analyser les chanes bcd et bcbd.
2. Peut-on dduire si cette grammaire est une grammaire LALR(1)?
3. Construire la table LALR(1).

Compilation, L3 Informatique , Pr Souici-Meslati L., Universit dAnnaba, 2012/2013

63