Chapitre V.

Analyse syntaxique ascendante

a.hettab@centre-univ-mila.dz
 Introduction
 Les méthodes ascendantes cherchent a construire une
dérivation la plus à droite inverse à partir de la chaîne
de terminaux vers l‟axiome de la grammaire.
 De façon équivalente, les méthodes ascendantes
cherchent à construire un arbre syntaxique à partir des
feuilles en utilisant un parcours inverse en profondeur
d'abord de gauche a droite.

2 Chapitre 05 - Analyse syntaxique ascendante

 principe de l’analyse ascendante
 Le modèle par décalage-réduction (shift-reduce) est généralement
utilisé dans l‟analyse ascendante:
 décalage (shift) : décaler le pointeur de lecture d‟un symbole, sur
la chaîne d‟entrée.
 réduction (reduce) : réduire une chaîne de symbole (terminaux et
non terminaux) par un non terminal en utilisant une des règles de
production de la grammaire. La chaîne se trouve à gauche du pointeur
de lecture sur l‟entrée et finissant sur ce pointeur.

3 Chapitre 05 - Analyse syntaxique ascendante

 Exemple
 Soit la grammaire G avec les règles de production

suivantes :
S → aABe
A → Abc| b
B→d
 On veut analyser la chaîne abbcde de manière

ascendante.

4 Chapitre 05 - Analyse syntaxique ascendante

 Exemple (suite)
abbcde décalage
abbcde réduction par A → b
aAbcde décalage
aA b c d e décalage
aA b c d e réduction par A → Abc
aAde décalage
aA d e réduction par B → d
aA B e décalage
Arbre syntaxique obtenu
aA B e réduction par S → aABe
de manière ascendante
S “Chaîne accéptée”

5 Chapitre 05 - Analyse syntaxique ascendante

 Analyse par la méthode LR
 L’analyse LR(K) est une technique efficace d‟analyse
syntaxique ascendante qui peut être utilisée pour analyser une
large classe de grammaire non contextuelle :
 Signification de LR(k) :
 L : Left to right parsing, parcours de l‟entrée de la gauche
vers la droite
 R : Rightmost derivation in reverse, construire une
dérivation droite inverse
 k : k tokens to take an analysis decision. K indique le nombre
de symboles de prévision utilisés pour prendre une décision
d‟analyse.

6 Chapitre 05 - Analyse syntaxique ascendante

 Analyse par la méthode LR
 L’analyseur LR(K) est très intéressant pour les raisons suivantes:
 Les analyseurs LR peuvent être utilisé dans de nombreux
langages de programmation et dans la majorité des
constructeurs d’analyseur syntaxiques.
 La classe des grammaires qui peuvent être analysées par la
méthode LR est un sur-ensemble strict de la classe des
grammaires qui peuvent être analysées par les méthodes
prédictives (grammaires LL).
 Un analyseur LR peut détecter le plus tôt possible une erreur
de syntaxe.
 L’inconvénient major de la méthode LR est la difficulté de
produire à la main de tels analyseurs; pour cela ils sont généralement
construits par des générateurs d'analyse syntaxique comme Yacc par
exemple qui utilise une des méthode LR qui est LALR(1).

7 Chapitre 05 - Analyse syntaxique ascendante

 Analyse par la méthode LR
 L'analyse LR se fait en construisant un automate AFD
spécifiant les différents états d'avancement de l'analyse. Puis
cet automate est transcrit en table d'analyse.
 Les principales méthodes LR sont:
 SLR(1) : la plus simple à implémenter, mais la moins
puissante des autres
 LR(1) : très puissante mais nécessite une mémoire
importante
LALR(1) : version affaiblie de LR(1) puissante et
exécutable dans la majorité des grammaires des langage de
programmation.

8 Chapitre 05 - Analyse syntaxique ascendante

 Analyse par la méthode LR
 La classe des grammaires LR(1) est beaucoup plus grande que la
classe des grammaires SLR(1) et plus grande que la classe des
grammaires LALR(1).
 La classe des grammaires LALR(1) est plus grande que la classe des
grammaires SLR(1).
 Un analyseur LALR utilise des tables qui ont strictement le même
nombre d'états qu'un analyseur SLR.
LR(k)
LALR(k)

SLR(k)

9 Chapitre 05 - Analyse syntaxique ascendante

 programme d'analyse LR
 Le programme d'analyse LR est le même pour les différentes
méthodes LR.
 Il permet de faire une analyse syntaxique déterministe si la table
d'analyse, associée à une grammaire, est mono-définie.
 Chaque méthode LR possède a sa propre table d'analyse, et
chaque table d'analyse est organisée en deux parties : ACTION et
SUCCESSEUR.
 Le programme d'analyse LR analyse le flot d'entrée, produit
un flot de sortie en utilisant la table d'analyse et une pile.
 L’architecture de l'analyseur LR est décrit dans le schéma
suivant :

10 Chapitre 05 - Analyse syntaxique ascendante

 L’architecture d’un analyseur LR

…a+b# Tampon d’entrée

Pile Sn
Xn Programme
d’analyse LR Flot de sortie
Sn-1

S0
ACTION SUCCESSEUR

11 Chapitre 05 - Analyse syntaxique ascendante

 L’architecture d’un analyseur LR
Remarques :
 La partie ACTION de la table d'analyse correspond à la sous table où
les indices des colonnes sont des terminaux. La partie
SUCCESSEUR (fonction de transfert) de la table d'analyse
correspond à la sous table où les indices des colonnes sont les non-
terminaux.
 Les lignes de la table d‟analyse correspond aux états de l‟automate
AFD.
 La pile est utilisée pour ranger des chaines de la forme
S0X1S1X2…XnSn (sommet de pile à droite) où Xi est un
symbole de la grammaire et Si est un état.
 L'état en sommet de pile et le symbole d'entrée courant
suffisent pour décider de l'action d'analyse à entreprendre.

12 Chapitre 05 - Analyse syntaxique ascendante

 Algorithme d'analyse LR
 La pile contient au départ l'état initial de l'automate S0 ;
 Soit S l'état en sommet de pile; et Soit a le symbole pointé par Ps;
Répéter indéfiniment
Si ACTION[S,a]="Décaler T“ Alors
empiler(a); empiler(T); avancer Ps sur le prochain symbole;
Sinon
Si ACTION[S,a]="Réduire par A  “ Alors
dépiler 2*|| symboles;
Soit U le nouvel état en sommet de pile;
empiler(A); empiler(SUCCESSEUR[U,A]);
Sinon
Si ACTION[S,a]="Accepter“ Alors retourner(Réussite());
Sinon retourner(Echec());
FinSi;
FinSi;
FinSi;
Fin;

13 Chapitre 05 - Analyse syntaxique ascendante

 Principales méthodes LR
 Les principales méthodes LR sont:
 SLR(1) : la plus simple à implémenter, mais la moins
puissante des autres
 LR(1) : très puissante mais nécessite une mémoire
importante
LALR(1) : version affaiblie de LR(1) puissante et
exécutable dans la majorité des grammaires des langage de
programmation.

14 Chapitre 05 - Analyse syntaxique ascendante

 Analyse SLR(1)
 La construction d’une table d’analyse SLR (LR(0) ou
SLR(1)) à partir d‟une grammaire est la méthode la plus simple
à implémenter (parmi les 3 méthodes SLR (1), LALR (1) et
LR(1) ) mais c‟est la moins puissante du point de vue du
nombre de grammaire pour lesquelles elle réussit.
 L’analyse SLR(1) se fait comme suit:
 Construire l'automate d'états finis qui reconnait les préfixes
viables de G (préfixes pouvant apparaître sur la pile);
 Transcrire cet automate en table ;
 Si la table d‟analyse est mono-définie alors utiliser l‟algorithme
précédent pour effectuer l‟analyse SLR(1).
15 Chapitre 05 - Analyse syntaxique ascendante
 Analyse SLR(1) Concepts

 La construction des analyseurs SLR, pour une grammaire

donnée, est basée sur la collection canonique d’items
LR(0) (qui construisent les états de l'AFD).
 Pour construire cette collection, on définit:
 une grammaire augmentée,
 une fonction Fermeture,
 une fonction Transition GOTO.

16 Chapitre 05 - Analyse syntaxique ascendante

 Analyse SLR(1) Item
Items LR(0)
 Un item LR(0) d'une grammaire G est une production avec un point
(.) repérant une position de sa partie droite .
Exemples :
 La production A  XYZ fournit quatre items qui sont :
[A  .XYZ] , [A  X.YZ] , [A  XY.Z], [A  XYZ.]
 La production A   fournit l'item : [A  . ]
Remarque
 Un item indique la «quantité» de partie droite qui a été reconnue
à un instant donné de l‟analyse.
 Par exemple, l‟item [A  X.YZ] indique qu‟on vient de reconnaitre
une chaine dérivée de X et on attend de reconnaître une chaine
dérivée de YZ.

17 Chapitre 05 - Analyse syntaxique ascendante

 Fermeture d'un ensemble d'items
LR(0)
Grammaire augmentée :
 La grammaire initiale sera augmentée de la règle S'  S (où S est
l'axiome de la grammaire) pour obtenir l'état initial de l'AFD
Fermeture(I)
 Soit I un ensemble d'items ;
 Placer chaque item de I dans Fermeture(I);
 Si [A.B] est dans Fermeture(I) et B est une
production: Alors ajouter l'item [B.] à Fermeture(I) s'il
n'y est pas ;
 Appliquer cette règle jusqu'à ce qu'aucun item ne puisse être
ajouté à Fermeture(I).
18 Chapitre 05 - Analyse syntaxique ascendante
 Fermeture d'un ensemble d'items
LR(0)
Exemple:
 Considérer la grammaire G dont les productions sont
données ci-après:
E  E +T |T
T T * F | F
F(E)|i
 La grammaire est augmentée de la règle E'  E ;
Fermeture([E'  .E]) = {[E'  .E], [E .E+T], [E 
.T], [T  .T*F], [T .F], [F  .(E)], [F  .i]}

19 Chapitre 05 - Analyse syntaxique ascendante

 Fonction de transition GoTo pour
les items LR(0)
 Soit I un ensemble d‟items et X un symbole de la grammaire.
 La fonction de transition GoTo (I, X) est définie comme
suit:
GoTo (I, X) = fermeture [A→αX.β] tels que [A →α.X β] є I.
Exemple:
 En utilisant la grammaire de l‟exemple précédent, Si I=
{[E’→E.], [E → E.+T]}, alors la fonction GoTo est défini
comme suit:
GoTo(I, +)= Fermeture ([E → E+.T]) = {[E → E+.T], [T
→.T*F], [T →.F], [F →.(E)], [F →.i]}
20 Chapitre 05 - Analyse syntaxique ascendante
 Construction de l’ensemble canonique
d'items LR(0)
Algorithme:

 Construction des ensembles d'items LR(0)

 Donnee : une grammaire augmentée G0

 Résultat : une collection canonique d'ensembles d'items

LR(0) C pour la grammaire augmentée G0

 Méthode : on exécute la procédure suivante pour ajouter les

transitions sur tous les symboles a partir de l'axiome:

21 Chapitre 05 - Analyse syntaxique ascendante
 Construction de l’ensemble canonique
d'items LR(0)
Procédure Items(G0);
Début
C = {Fermeture([S'  .S])};
Répéter
Pour chaque ensemble d'items I de C Faire
Pour chaque symbole X de la grammaire tel que GOTO(I,X)
soit non vide et non encore dans C Faire
ajouter GOTO(I,X) à C;
Fin pour;
Fin pour;
Jusqu'à ce qu'aucun nouvel ensemble ne puisse être ajouté à C;
Fin.

22 Chapitre 05 - Analyse syntaxique ascendante

 Construction de l’ensemble canonique
d'items LR(0)
Exemple:
 Considérer la grammaire augmentée G0 pour la grammaire
de l‟exemple précédent :
E'  E
E  E +T |T
T T * F | F
F(E)|i
 La collection canonique d‟items LR(0) est la suivante:

23 Chapitre 05 - Analyse syntaxique ascendante

 Construction de l’ensemble canonique
d'items LR(0)
Exemple (suite 1):
I0 = {[E'  .E], [E  .E+T], [E  .T], [T.T*F],[T  .F], [F
 .(E)], [F  .i]}
I1 = GOTO(I0, E) = {[E'  E.], [E  E.+T]}
I2 = GOTO(I0, T) = {[E  T.], [T  T.*F]}
I3 = GOTO(I0, F) = {[T  F.]}
I4 = GOTO(I0, ( ) = {[F  (.E)], [E  .E+T], [E .T], [T 
.T*F],[T  .F], [F.(E)], [F.i]}
 I5 = GOTO(I0, i ) = {[F  i.]}
I6 = GOTO(I1, +) = {[E  E+.T], [T.T*F], [T.F], [F 
.(E)], [F.i]}
24 Chapitre 05 - Analyse syntaxique ascendante
 Construction de l’ensemble canonique
d'items LR(0)
Exemple (suite 2):
I7 = GOTO(I2, *) = {[T  T*.F], [F.(E)], [F .i]}
I8 = GOTO(I4, E) = {[F  (E.)], [EE.+T]}
GOTO(I4, T) = I2
GOTO(I4, F) = I3
GOTO(I4, ( ) = I4
GOTO(I4, i) = I5
I9 = GOTO(I6, T) = {[E  E+T.], [TT.*F]}
 GOTO(I6, F) = I3
 GOTO(I6, () = I4

25 Chapitre 05 - Analyse syntaxique ascendante

 Construction de l’ensemble canonique
d'items LR(0)
Exemple (suite 3):
 GOTO(I6, i) = I5
 I10 = GOTO(I7, F) = {[T  T*F.]}
 GOTO(I7, () = I4
 GOTO(I7, i) = I5
 I11 = GOTO(I8, ) ) = {[F  (E).]}
 GOTO(I8, +) = I6
 GOTO(I9, *) = I7

26 Chapitre 05 - Analyse syntaxique ascendante

 Construction de l’ensemble canonique
d'items LR(0)
Exemple (suite 4):
• Voici l'AFD construit
pour la fonction
de transition GoTo.
Avec I0 est l‟état initial et
tous les autres états
sont des états finaux.

27 Chapitre 05 - Analyse syntaxique ascendante

Construction de la table d’analyse SLR (1)
Algorithme
Début
L‟état i est construit à partir de Ii.
- La partie ACTION pour l‟état i est déterminée comme suit:
Si [A→α.aβ] є Ii et GoTo (Ii, a)= Ij (avec a є T) Alors
Ajouter dj (décaler j) à ACTION [i, a]
Fin si
Si [A→α.] є Ii (avec A≠S’) Alors
pour tout a є Suiv(A)
Ajouter r(k) à ACTION [i, a] (k est le numéro de la
règle A→α )
Fin pour
Fin si
Si [S’→S.] є Ii Alors maître « accepter » à ACTION [i, #]
28 Fin Chapitre
si 05 - Analyse syntaxique ascendante
 Construction de la table d’analyse SLR (1)
Algorithme (suite)
-La partie SUCCESSEUR pour l‟état i est déterminée comme suit :
Si Goto (Ii, A)= Ij Alors
Ajouter j à SUCCESSEUR [i, A]
Fin si
- Toutes les entrée restantes dans la table sont mises à « ERREUR »
-L’état initial de l‟analyseur est construit à partir de l‟ensemble
d‟items contenant [S’→.S]
Fin ;

29 Chapitre 05 - Analyse syntaxique ascendante

 Construction de la table d’analyse SLR (1)
Exemple
 Considérer la grammaire augmentée G0 pour la grammaire de
l‟exemple précédent dont les productions numérotées sont
données ci-après :
0) E'  E
1) E  E + T
SUIVANT
2) E  T
E # ) +
3) T  T * F T # ) + *
4) T  F F # ) + *

5) F  ( E )
6) F  i
30 Chapitre 05 - Analyse syntaxique ascendante
 Construction de la table d’analyse SLR (1)
Exemple (suite)
+ * ( ) i # E T F
0 D4 D5 1 2 3
1 D6 Accepter
2 R (2) D 7 R (2) R (2)
3 R (4) R (4) R (4) R (4)
4 D4 D5 8 2 3
5 R (6) R (6) R (6) R (6)
6 D4 D5 9 3
7 D4 D5 10
8 D6 D 11
9 R (1) D 7 R (1) R (1)
10 R (3) R (3) R (3) R (3)
11 R (5) R (5) R (5) R (5)
La table est mono-définie donc la grammaire précédente est SLR(1);
31 Chapitre 05 - Analyse syntaxique ascendante
Exemple d’analyse Pile Restant à Action
SLR(1) analyser
 Analyse de la chaine 0 i+i*i# D5
"i+i*i": 0i5 +i*i# R (6)
0F3 +i*i# R (4)
0) E'  E 0T2 +i*i# R (2)
1) E  E + T 0E1 +i*i# D6
2) E  T 0E1+6 i*i# D5
3) T  T * F 0E1+6i5 *i# R (6)
4) T  F 0E1+6F3 *i# R (4)
5) F  ( E ) 0E1+6T9 *i# D7
0E1+6T9*7 i# D5
6) F  i 0E1+6T9*7i5 # R (6)
0 E 1 + 6 T 9 * 7 F 10 # R (3)
0E1+6T9 # R (1)
32 Chapitre 05 - Analyse syntaxique ascendante 0E1 # "Accepter"
 Conflits dans l’analyse SLR(1)
 Deux types de conflits existent dans l‟analyse SLR(1):
 Conflit Décaler - Réduire
Certains états peuvent contenir un item de la forme
[A →α.aβ] et un item de la forme [A →α.].
 Conflit Réduire - Réduire
Certains états peuvent contenir un item de la forme
[A →α.] et un item de la forme [B→β.]. Avec
suivant (A) ∩ suivant (B) ≠Ф .
Ils représentent deux situations de réduction par deux
productions différentes.

33 Chapitre 05 - Analyse syntaxique ascendante

 Conflits dans l’analyse SLR(1)
Exemple
I0 = {[E'  .E], [E  .E+T], [E  .T], [T.i], [T  .(E)],
[T  .ii[E]]}
---------------------------------------------------------------------
I1 = GOTO(I0, E) = {[E'  E.], [E  E.+T]}
I2 = GOTO(I0, T) = {[E  T.]}
I3 = GOTO(I0, i) = {[Ti.],[T  i.i[E]]}
Conflit Décaler - Réduire en items LR(0)
I4 = GOTO(I0, ( ) = {[F  (.E)], [E  .E+T], [E  .T],
[T.i], [T  .(E)], [T  .i[E]]}

34 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LR(1)
 La méthode d’analyse LR(1) ou LR canonique est la
technique la plus générale de construction de tables
d‟analyse LR pour une grammaire .
 La classe des grammaires LR(1) est plus grande que celle
des grammaires SLR(1).
 La méthode LR(1) permet éviter un certain nombre
d‟actions invalides et de conflits en attachant plus
d‟informations à un état.

35 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LR(1)
Concepts
 La construction des analyseurs LR (1), pour une
grammaire donnée, est basée sur la collection
canonique d’items LR(1).
 Pour construire cette collection, on définit:
 une grammaire augmentée,
 une fonction Fermeture,
 une fonction Transition GOTO.

36 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LR(1)
Item LR (1)
 La forme générale d‟un item LR(1) est [A→α.β, a] tel que
: A→αβ est une règle de production de la grammaire et a
est le symbole de prévision avec a є T  {#}.
 Le symbole de prévision a n‟a aucun effet dans un item de la
forme [A →α.β, a] avec β ≠ ε,
 Le symbole de prévision a implique « réduire par A →α
uniquement lorsque le prochain symbole entrée est a » dans
un item de la forme [A →α., a].
 L‟ensemble des symboles de prévision est un sous ensemble
de Suivant(A).
37 Chapitre 05 - Analyse syntaxique ascendante
 Fermeture d'un ensemble d'items
LR(1)
Grammaire augmentée :
 La grammaire initiale sera augmentée de la règle S'  S (où S est
l'axiome de la grammaire) pour obtenir l'état initial de l'AFD
Fermeture(I)
 Soit I un ensemble d'items ;
 Placer chaque item de I dans Fermeture(I);
 Si [A.B,a] est dans Fermeture(I) et B est une
production: Alors ajouter l'item [B.,b] avec b 
PREMIER(a) à Fermeture(I) s'il n'y est pas ;
 Appliquer cette règle jusqu'à ce qu'aucun item ne puisse être
ajouté à Fermeture(I).
38 Chapitre 05 - Analyse syntaxique ascendante
 Fermeture d'un ensemble d'items
LR(1)
Exemple:
 Considérer la grammaire G dont les productions sont données ci-
après:
S  AA
A  aA
Ab
La grammaire est augmentée de la règle S'  S ;
Fermeture([S'  .S,#]) = {[S'  .S,#], [S .AA,#], [A 
.aA, a/b], [A .b, a/b]}

39 Chapitre 05 - Analyse syntaxique ascendante

 Fonction de transition GoTo pour
les items LR(1)
 Soit I un ensemble d‟items et X un symbole de la grammaire.
 La fonction de transition GoTo (I, X) est définie comme
suit: GoTo (I, X) = fermeture [A→αX.β,a] tels que [A
→α.X β,a] є I.
Exemple:
 En utilisant la grammaire de l‟exemple précédent, Si I= {[S' 
.S , #], [S  .AA , #], [A.aA , a/b], [A .b , a/b]}, alors la
fonction GoTo est défini comme suit:
GoTo(I, A)= Fermeture ([S → A.A , #]) = {[S → A.A , #],
[A → .aA , #], [A→ .b , #]}
40 Chapitre 05 - Analyse syntaxique ascendante
 Construction de l’ensemble canonique
d'items LR(1)
Algorithme:

 Construction des ensembles d'items LR(1)

 Donnee : une grammaire augmentée G’

 Résultat : une collection canonique d'ensembles d'items

LR(1) C pour la grammaire augmentée G’

 Méthode : on exécute la procédure suivante pour ajouter les

transitions sur tous les symboles a partir de l'axiome:

41 Chapitre 05 - Analyse syntaxique ascendante
 Construction de l’ensemble canonique
d'items LR(1)
Procédure Items(G‟);
Début
C = {Fermeture([S'  .S,#])};
Répéter
Pour chaque ensemble d'items I de C Faire
Pour chaque symbole X de la grammaire tel que GOTO(I,X)
soit non vide et non encore dans C Faire
ajouter GOTO(I,X) à C;
Fin pour;
Fin pour;
Jusqu'à ce qu'aucun nouvel ensemble ne puisse être ajouté à C;
Fin.

42 Chapitre 05 - Analyse syntaxique ascendante

 Construction de tous les ensembles
d'items LR(1)
Exemple:
 Considérer la grammaire augmentée G‟ pour la grammaire de
l‟exemple précédent :
S'  S
S  AA
A  aA
Ab
 La collection canonique d‟items LR(1) est la suivante:

43 Chapitre 05 - Analyse syntaxique ascendante

 Construction de tous les ensembles
d'items LR(1)
Exemple (suite):
 I0 = {[S'  .S , #], [S  .AA , #], [A.aA , a/b], [A .b ,
a/b]}
 I1 = GOTO(I0, S) = {[S'  S. , #]}
 I2 = GOTO(I0, A) = {[S  A.A , #], [A  .aA , #], [A
.b , #]}
 I3 = GOTO(I0, a) = {[A  a.A , a/b], [A  .aA , a/b], [A
 .b , a/b]}
 I4 = GOTO(I0, b) = {[A  b. , a/b]}

44 Chapitre 05 - Analyse syntaxique ascendante

 Construction de tous les ensembles
d'items LR(1)
Exemple (suite):
 I5 = GOTO(I2, A) = {[S  AA. , #]}
 I6 = GOTO(I2, a) = {[A  a.A , #], [A  .aA , #], [A .b ,
#]}
 I7 = GOTO(I2, b) = {[A  b. , #]}
 I8 = GOTO(I3, A) = {[A  aA. , a/b]}
 GOTO(I3, a) = I3
 GOTO(I3, b ) = I4
 I9 = GOTO(I6, A) = {[A  aA. , #]}
 GOTO(I6, a) = I6
 GOTO(I6, b) = I7

45 Chapitre 05 - Analyse syntaxique ascendante

 Construction de la table d’analyse LR (1)
Algorithme
Début
L‟état i est construit à partir de Ii.
- La partie ACTION pour l‟état i est déterminée comme suit:
Si [A→α.aβ,b] є Ii et GoTo (Ii, a)= Ij (avec a,b є T) Alors
Ajouter dj (décaler j) à ACTION [i, a]
Fin si
Si [A→α.,a] є Ii (avec A≠S’) Alors
Ajouter r(k) à ACTION [i, a] (k est le numéro de la
règle A→α )
Fin si
Si [S’→S.,#] є Ii Alors maître « accepter » à ACTION [i, #]
Fin si

46 Chapitre 05 - Analyse syntaxique ascendante

 Construction de la table d’analyse LR (1)
Algorithme (suite)
-La partie SUCCESSEUR pour l‟état i est déterminée comme suit :
Si Goto (Ii, A)= Ij Alors
Ajouter j à SUCCESSEUR [i, A]
Fin si
- Toutes les entrée restantes dans la table sont mises à « ERREUR »
-L’état initial de l‟analyseur est construit à partir de l‟ensemble
d‟items contenant [S’→.S,#]
Fin ;

47 Chapitre 05 - Analyse syntaxique ascendante

 Construction de la table d’analyse LR (1)
Exemple (suite)
a b # S A
0 D3 D4 1 2
1 Accepter
2 D6 D7 5
3 D3 D4 8
4 R (3) R (3)
5 R (1)
6 D6 D7 9
7 R(3)
8 R (2) R (2)
9 R(2)

La table est mono-définie donc la grammaire précédente est LR(1);

48 Chapitre 05 - Analyse syntaxique ascendante

 Exemple d’analyse LR(1)
0) S'  S  Analyse de la chaine « aabb »
1) S  AA
2) A  aA Pile Restant à Action
analyser
3) A  b
0 aabb# D3
 Analyse de la chaine « aaab » 0a3 abb# D3
0a3a3 bb# D4
Pile Restant à Action
0a3a3b4 b# R(3)
analyser
0a3a3A8 b# R(2)
0 aaab# D 3 0a3A8 b# R(2)
0a3 aab# D 3 0A2 b# D7
0a3a3 ab# D3 0A2b7 # R(3)
0a3a3a3 b# D4 0A2A5 # R(1)
0a3a3a3b4 # “Erreur” 0S1 # “chaîne
acceptée”
49 Chapitre 05 - Analyse syntaxique ascendante
 Conflits dans l’analyse LR(1)
 Deux types de conflits existent dans l‟analyse LR(1):
 Conflit Décaler - Réduire
Certains états peuvent contenir un item de la forme
[A → β.aγ,b] et un item de la forme [A →α.,a].
 Conflit Réduire - Réduire
Certains états peuvent contenir un item de la forme
[A →α.,a] et un item de la forme [B→β.,a].
Ils représentent deux situations de réduction par le
caractère a commun aux suivants de A et de B.

50 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
 La méthode d’analyse LALR(1) (Look Ahead LR) est
un très bon compromis entre les analyses SLR(1) et
LR(1).
 Un analyseur LALR(1) utilise des tables qui ont
strictement le même nombre d'états qu'un analyseur
SLR(1), mais la classe des grammaire LALR(1) est plus
grande que la classe des grammaires SLR(1).
 La méthode d‟analyse LALR(1) est largement utilisée dans
la pratique, par exemple le générateur de compilateur
YACC utilise la méthode LALR(1) pour la partie
syntaxique du compilateur.

51 Chapitre 05 - Analyse syntaxique ascendante

 Construction de la table d’analyse LALR (1)

•La construction de la table d‟analyse LALR(1) est basé sur la

collection d‟ensembles d‟items LR(1) en regroupant les items
LR(1) ayant le même cœur . Sachant que : item
LR(1)=[cœur, symbole de prévision].
• La table d’analyse LALR(1) est construite à partir de la
collection des ensembles d‟items fusionnés.
• Remarque: Il existe une autre méthode plus efficace pour
construire des tables LALR (1), basée sur les items LR (0) de la
méthode SLR (1). Mais dans ce cours nous utiliserons la
méthode qui est basée sur les items LR (1) car elle est plus
simple.
52 Chapitre 05 - Analyse syntaxique ascendante
 Construction de la table d’analyse LALR (1)
Algorithme
Début
I. Construire la collection d‟ensembles d‟items LR(1) C =
{I0,I1,…,In} .
II. Pour chaque cœur présent parmi les ensembles d‟items LR(1),
trouver tous les états ayant ce même cœur et remplacer ces
états par leur union.
III. Soit C' = {J0,J1,…,Jm} la nouvelle collection d'items;
L'opération GOTO est obtenue de la façon suivante :
Si J=I0I1…Is Alors
K =  GOTO(Ii,X) , i=1…s;
GOTO(J,X) = K;
53
FinSi;
Chapitre 05 - Analyse syntaxique ascendante

I. .
 Analyse LALR(1)
Exemple
Exemple:
 Considérer la grammaire augmentée G‟ pour la grammaire de
l‟exemple précédent :
S'  S
S  AA
A  aA
Ab
 La collection canonique d‟items LR(1) est la suivante:

54 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
Exemple (suite)
 I0 = {[S'  .S , #], [S  .AA , #], [A.aA , a/b], [A .b ,
a/b]}
 I1 = GOTO(I0, S) = {[S'  S. , #]}
 I2 = GOTO(I0, A) = {[S  A.A , #], [A  .aA , #], [A
.b , #]}
 I3 = GOTO(I0, a) = {[A  a.A , a/b], [A  .aA , a/b], [A
 .b , a/b]}
 I4 = GOTO(I0, b) = {[A  b. , a/b]}

55 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
Exemple (suite)
 I5 = GOTO(I2, A) = {[S  AA. , #]}
 I6 = GOTO(I2, a) = {[A  a.A , #], [A  .aA , #], [A .b
, #]}
 I7 = GOTO(I2, b) = {[A  b. , #]}
 I8 = GOTO(I3, A) = {[A  aA. , a/b]}
 GOTO(I3, a) = I3
 GOTO(I3, b ) = I4
 I9 = GOTO(I6, A) = {[A  aA. , #]}
 GOTO(I6, a) = I6
 GOTO(I6, b) = I7

56 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
Exemple (suite)
Construction de l’ensemble canonique d’items LR(1)
en regroupant les items qui ont le même cœur:
Les états I3 et I6 ayant le même cœur:
 I3 = {[A  a.A , a/b], [A  .aA , a/b], [A  .b , a/b]}
 I6 = {[A  a.A , #], [A  .aA , #], [A .b , #]}
 Ils seront regroupés en:
 I36 = {[A  a.A , a/b/#], [A  .aA , a/b/#], [A  .b ,
a/b/#]}

57 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
Exemple (suite)
Les états I4 et I7 ayant le même cœur:
 I4 = {[A  b. , a/b]}
 I7 = {[A  b. , #]}
 Ils seront regroupés en:
 I47 = {[A  b. , a/b/#]}
Les états I8 et I9 ayant le même cœur:
 I8 = {[A  aA. , a/b]}
 I9 = {[A  aA. , #]}
 Ils seront regroupés en:
 I89 = {[A  aA. , a/b/#]}

58 Chapitre 05 - Analyse syntaxique ascendante

 Analyse LALR(1)
Exemple (suite)
La nouvelle ensemble canonique d’items C’ est:
 I0 = {[S'  .S , #], [S  .AA , #], [A.aA , a/b], [A .b ,
a/b]}
 I1 = GOTO(I0, S) = {[S'  S. , #]}
 I2 = GOTO(I0, A) = {[S  A.A , #], [A  .aA , #], [A
.b , #]}
 I36 = GOTO(I0, a) = {[A  a.A , a/b/#], [A  .aA ,
a/b/#], [A  .b , a/b/#]}
 I47 = GOTO(I0, b) = {[A  b. , a/b/#]}

59 Chapitre 05 - Analyse syntaxique ascendante

  I5 = GOTO(I2, A) = {[S  AA. , #]}
 GOTO(I2, a) = I36
 GOTO(I2, b) = I47
 I89 = GOTO(I36, A) = {[A  aA. , a/b/#]}
 GOTO(I36, a) = I36
 GOTO(I36, b ) = I47

60 Chapitre 05 - Analyse syntaxique ascendante

Construction de la table d’analyse LALR (1)
Exemple (suite)

a b # S A
0 D 36 D 47 1 2
1 Accepter
2 D 36 D 47 5
36 D 36 D 47 89
47 R(3) R(3) R(3)
5 R(1)
89 R(2) R(2) R(2)

La table est mono-définie donc la grammaire précédente est LALR(1);

61 Chapitre 05 - Analyse syntaxique ascendante

 Exemple d’analyse LALR(1)
0) S'  S
1) S  AA  Analyse de la chaine « aabb »
 Analyse de la chaine 2) A  aA
3) A  b
« aaab » Pile Restant à Action
Pile Restant à Action analyser
analyser 0 aabb# D 36
0 aaab# D 36 0a36 abb# D36

0a36 aab# D36 0a36a36 bb# D47

0a36a36 ab# D36 0a36a36b47 b# R(3)

0a36a36a36 b# D47 0a36a36A89 b# R(2)

0a36a36a36b47 # R(3) 0a36A89 b# R(2)

0a36a36a36A89 # R(2) 0A2 b# D47

0a36a36A89 # R(2) 0A2b47 # R(3)

0a36A89 # R(2) 0A2A5 # R(1)
0S1 # “chaîne
0A2 # “Erreur”
acceptée”
62 Chapitre 05 - Analyse syntaxique ascendante
 Conflits dans l’analyse LALR(1)
 Pendant la construction des tables LALR(1) à partir des tables
LR(1) il y a un risque de conflit :
 Conflit Décaler - Réduire
La fusion de deux états ne peut entraîner de nouveaux
conflits Décaler - Réduire absents des états LR(1).
car les états fusionnés ont le même cœur.
 Conflit Réduire - Réduire
Le seul cas de conflit qui peut se produire durant la
fusion des états LR(1). C‟est pour cette raison qu‟il
existe des grammaires LR(1) qui ne sont pas LALR(1).

63 Chapitre 05 - Analyse syntaxique ascendante

 Yacc, un générateur d'analyseurs
syntaxiques
 Le programme Yacc (Yet Another Compiler Compiler) est
un générateur d'analyseurs syntaxiques.
 Il prend en entrée un fichier source constitué
essentiellement des productions d'une grammaire non
contextuelle G, et il donne comme sortie: un programme C
qui, une fois compilé, il donne un analyseur syntaxique
pour le langage L(G).
 Yacc s'appuie sur la méthode d‟analyse syntaxique
ascendante LALR.

64 Chapitre 03. Principes de l'analyse syntaxique

 Yacc, un générateur d'analyseurs
syntaxiques
 Dans la description de la grammaire donnée à yacc on peut

associer des actions sémantiques aux productions ; ce

sont des instructions de code source C que yacc place aux
bons endroits de l'analyseur construit. Ce dernier peut
ainsi exécuter des actions ou produire des informations
déduites du texte source.

65 Chapitre 03. Principes de l'analyse syntaxique

 Yacc et lex

 Un analyseur syntaxique requiert pour travailler un

analyseur lexical qui lui délivre le flot d'entrée sous forme

d'unités lexicales successives. Par défaut, yacc suppose que
l'analyseur lexical disponible a été fabriqué par lex.

 Pour cela, le programme produit par yacc comporte des appels de

la fonction yylex (de lex) aux endroits où l'acquisition d'une

unité lexicale est nécessaire.

66 Chapitre 03. Principes de l'analyse syntaxique

 Yacc et lex
 Le schéma en dessous illustre les étapes de construction d‟un

analyseur syntaxique complet en utilisant yacc et lex.

67 Chapitre 03. Principes de l'analyse syntaxique

 Yacc et lex
 Les commandes pour créer le fichier exécutable, bas.exe

(l‟analyseur syntaxique), sont :

 yacc -d bas.y # créer les fichiers y.tab.h, y.tab.c

 lex bas.l # créer le fichier lex.yy.c

 gcc lex.yy.c y.tab.c -o bas.exe -lfl # créer le

fichier exécutable bas.exe

68 Chapitre 05 - Analyse syntaxique ascendante

Structure d'un fichier source pour yacc

 Un fichier source pour yacc doit avoir un nom terminé par

« .y ». Il se compose de trois sections, délimitées par le
symbole « %% » :
%{
déclarations pour le compilateur C
%}
déclarations pour yacc
%%
règles (productions + actions sémantiques)
%%
fonctions C supplémentaires

69 Chapitre 03. Principes de l'analyse syntaxique

 Structure d'un fichier source pour yacc

 La partie « déclarations pour le compilateur C » est

simplement recopiée dans le fichier à produire.
 La partie « déclarations pour yacc » sert pour spécifier les
déclarations des unités lexicales.
 Exemple:
%{
char nom[256];
int b = 50;
%}
%token nombre identificateur

70 Chapitre 03. Principes de l'analyse syntaxique

Structure d'un fichier source pour yacc
 La partie « règles (productions + actions sémantiques) » , sert
pour définir les productions de la grammaire du langage choisi.
 Chaque production s'écrit sous la forme suivante:
non_terminal:
corps_1 {action_sémantique_1}
|…
| corps_n {action_sémantique_n}
;
Exemple: terme :
terme '*' facteur { printf(" *"); }
| facteur
;
71 Chapitre 06 -Yet Another Compiler Compiler
Structure d'un fichier source pour yacc
 La partie « fonctions C supplémentaires» contient
obligatoirement la fonction main() qui contient généralement
la fonction yyparse( ) qui est utilisée pour exécuter l‟analyseur.
 Exemple:
int main(void)
{
if (yyparse() == 0)
printf("Texte correct\n");
}

72 Chapitre 05 - Analyse syntaxique ascendante

Structure d'un fichier source pour yacc
 Remarque:
 Dans un programme yacc, il faut écrire une fonction qui est
appelée en cas d'erreur avec la spécification suivante :
void yyerror(char *message).
Exemple:
void yyerror(char *message)
{
printf(" <<< %s\n", message);
}

73 Chapitre 05 - Analyse syntaxique ascendante

Lex et Yacc: Exemple
%{
#include "syntaxe.tab.h"
extern char nom[]; /* chaîne de caractères partagée avec l'analyseur syntaxique */
%}
chiffre [0-9]
lettre [A-Za-z]
%%
[" "\t\n] {}
{chiffre}+ { yylval = atoi(yytext); return nombre; }
{lettre}({lettre}|{chiffre})* { strcpy(nom, yytext); return identificateur; }
. { return yytext[0]; }
%%
int yywrap(void)
{ return 1; } Fichier de spécification lex

74 Chapitre 06 -Yet Another Compiler Compiler

 Lex et Yacc: Exemple
%{ %%
char nom[256]; /* chaîne de caractères partagée avec le fichier lex */ void yyerror(char *s)
%} {
%token nombre identificateur printf("<<< \n%s", s);
%% }
expression : expression '+' terme { printf(" +"); } main()
| terme ; {
terme : terme '*' facteur { printf(" *"); } if (yyparse() == 0)
| facteur ; printf(" Expression
facteur : nombre { printf(" %d", yylval); } correcte\n");
| identificateur { printf(" %s", nom); } }
| '(' expression ')„ ;

Fichier de spécification yacc

75 Chapitre 05 - Analyse syntaxique ascendante

 Variables de YACC
 YACC utilise des variables pour désigner les non terminaux
et les terminaux dans une grammaire.
 $$ désigne l'attribut associé à la partie gauche d'une règle de
production ).
 $i désigne l'attribut associé au ième symbole d la partie
droite d‟une règle de production.
 La règle sémantique par défaut est {$$=$1}.
 La production vide est représentée par une alternative vide.

76 Chapitre 06 -Yet Another Compiler Compiler

 Les conflits dans YACC
Yacc effectue une action par défaut en cas de conflit.
I) Conflits Décaler/Réduire:
 Yacc choisi un décalage.
II) Conflits de Réduire/Réduire:
 Yacc utilise la première règle de la liste. Il affiche également
un message d'avertissement chaque fois qu'un conflit existe.

77 Chapitre 06 -Yet Another Compiler Compiler

 Résolution des conflits en YACC
 On peut spécifier dans un fichier YACC une grammaire
ambiguë. Mais il faut spécifier les associativités et priorités
des opérateurs dans la partie déclaration, pour lever
l‟ambiguïtés.
 Les associativités sont spécifiées par les mots clés Left (pour
associativité gauche) ou Right (pour une associativité droite).
 Les opérateurs ainsi spécifiés auront des priorités croissantes
selon l'ordre d'écriture.
 Exemple:
 %left '+','-'
 %left '*','/'

78 Chapitre 06 -Yet Another Compiler Compiler