Université de BOUIRA

Département d’informatique
Support pour L3

Compilation
CHAPITRE II : ANALYSE
SYNTAXIQYE
2: ANALYSE ASCENDANTE

HAMID Rabah
r_hamid@[Link]

2018/2019 3° eme ANNEE SYSTÈME

INFORMATIQUE
ANALYSE ASCENDANTE
Principe:

Construire un arbre de dérivation du bas (les feuilles, les

unités lexicales) vers le haut (la racine l’axiome de
départ) Le modèle général utilisé est le modèle par
décalages réductions

• décalage (shift) : décaler d’une lettre le pointeur sur

le mot en entrée.
• réduction (reduce) : réduire une chaine par un non
terminal en utilisant une des règles de production.

Nous présentons quatre techniques pour construire la

table d’analyse LR pour une grammaire. Ces méthodes
utilisent un programme identique appelé conducteur,
cependant le contenu de la table d’analyse est différent
ANALYSE ASCENDANTE
Principe:
1 2
Exemple : E  E+T /T
T id 3 /(E)4
La chaine id + (id) peut être réduite à
l’axiome E
Id+(id) Π =323241 est l’inverse de la dérivation droite de id+(id)
3 T+(id) La dérivation droite de cette même chaine est
2 E+( id) Π ‘ = 142323
4 E+(T) 1 4 2 3 2 3
5 E+(E) E  E+T  E+(E )  E+(T)  E+(id)  T+(id) 
4 E+T id+(id)
1 E
Définition d’un manche ou Handle
Un manche d’une protophrase est partie de cette
protophrase égale à un membre droit d’une production et
dont la réduction au nom terminal de gauche représente
ANALYSE ASCENDANTE :
Le programme
conducteur :
Chaine à Table
Le programme
analyser d’analy
conducteur :
se

Il utilise une pile dont le contenu spécifie l’état de

l’analyse et un vecteur contenant le reste de la chaine à
analyser. Au départ la configuration de l’analyse est la
suivante : S0 a1,a2 …….an # Etat initial chaine à analyser
Au cours de l’analyse, la configuration varie et devient :
(S0 X1S1X2S2……….. X mSm ai,ai+1,…..an # ) où Sm est au
sommet .
Chaque Xi est un symbole de la grammaire et chaque Si
est un symbole appelé état , pour passer à la
configuration suivante, l’analyseur consulte la table
ANALYSE ASCENDANTE :

Les types d’action que le simulateur peut rencontrer

dans la table sont :
• - Décaler (shift ) ou empiler j ( noté Sj )
• - Réduire j (reduce ) ( noté rj)
• - Accepter ( noté acc)
• - Erreur : (err) une erreur est indiquée par une case
vide.

Les lignes de la table sont des états de l’automate

Les colonnes sont les symboles de la grammaire avec le
#
ANALYSE ASCENDANTE :

Les types d’action que le simulateur peut rencontrer

dans la table sont :
• - Décaler (shift ) ou empiler j ( noté Sj )
• - Réduire j (reduce ) ( noté rj)
• - Accepter ( noté acc)
• - Erreur : (err) une erreur est indiquée par une case
vide.

Les lignes de la table sont des états de l’automate

Les colonnes sont les symboles de la grammaire avec le
#
ANALYSE ASCENDANTE :

La case ( sp , ai) indique l’action à entreprendre , si

l’action est :
1- Sj : l’analyseur doit empiler l’élément ai ensuite j qui
est le numéro de l’état suivant par la transition j= goto
( sp , ai).
2- Rj : j indique un numéro de règle de la grammaire , à
ce moment la partie droite de cette production apparait
au sommet de la pile, il faut substituer la partie droite ,
par la partie gauche de la règle, à la suite de cette
opération, l’analyseur empile le numéro de l’état de
transition trouvé dans la deuxième partie de la table c.à.d
k= goto( spr , A) , où A est le non terminal apparaissant
au sommet de la pile et spr se trouve juste avant A dans
ANALYSE ASCENDANTE :
gorithme d’analyse LR :

Donnée : une chaine d’entrée w et des tables d’analyse

LR .

Résultat : si w est dans L(G), une analyse ascendante de

w, sinon, une indication d’erreur

Méthode : Initialement, l’analyseur a S0 en pile, où S0 est

l’état initial et w# dans son tampon , l’analyseur doit
exécuter le programme ci-dessous jusqu’à ce qu’il
rencontre soit, ne action accepter soit erreur
ANALYSE ASCENDANTE :
gorithme d’analyse LR :
Initialiser le pointeur source ps sur le premier symbole de
w# ;
Répéter indéfiniment début
Soit S l’état en sommet de pile et a le symbole pointé
par ps ;
Si action [ S ,a]= décaler S’ alors
début Empiler a puis S’
Avancer ps sur le prochain symbole en entrée
Fin
Sinon si action [s,a]= réduire par Aβ alors début
Dépiler 2 X |β| symboles ;
Soit S’ le nouvel état sommet de la pile ;
Empiler A puis Goto[ S’ , A] ;
Emettre en sortie une identification de la
production Aβ ;
Fin Sinon
 ANALYSE ASCENDANTE :
Analyseur 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 :

L : signifie « parcours de l’entrée de la gauche vers la

droite » (left to right scanning of the input »,

R : signifie « en construisant une dérivation droite inverse

» (constructing a Right most derivation in
reverse)et

K indique le nombre de symboles de prévision utilisés

 ANALYSE ASCENDANTE :
Analyseur LR :
Un certain nombre de raisons rendent l’analyse LR
intéressante :
- Les analyseurs LR peuvent reconnaitre toutes les
constructions des langages de programmation décrites
par une grammaire non contextuelle.
- La classe des grammaires analysées par les méthodes
LR est un sur ensemble strict de la classe des grammaires
LL (1).
- Un analyseur LR peut détecter une erreur de syntaxe
aussitôt que possible au cours d’un parcours de gauche à
droite de l’entrée.

La principal inconvénient de la méthode est qu’elle exige

de fournir une quantité trop importante de travail pour
 ANALYSE ASCENDANTE :
Analyseur LR :

Dans cette analyse nous construisons un automate AFD

spécifiant les différents états d’avancement d’analyse.
Un état de l’automate contient un ensemble d’éléments
décrivant ce que l’analyse anticipe de rencontrer à partir
de l’instant où l’analyse transite vers cet état Un
élément de cet ensemble est appelé Item LR(0), une
fois l’automate élaboré, nous procédons à la
construction de la table d’analyse.
Item LR( 0) : Un Item LR(0) d’une grammaire G est une
production de G avec un point repérant une position de sa
partie droite par conséquent, la production A XYZ fournit
les quatre Items :
A .XYZ A  [Link] A  XY.Z A  XYZ.
La production A  ϵ fournit uniquement l’Item A .
 ANALYSE ASCENDANTE :
Analyseur LR :

Intuitivement un item indique la quantité de partie droite

qui a été reconnue, à un moment donné.
Par exemple, le premier item ci-dessus indique l’on espère
voir en entrée une chaine dérivable depuis XYZ.
Le second Item indique que nous venons de voir en
entrée une chaine dérivée de X et que nous espérons
maintenant voir une chaine dérivée de YZ.
Une collection d’ensembles d’items LR(0), fournit la base
de la construction des analyseurs SLR. Pour construire
une collection LR(0) nous définissons une grammaire
augmentée et deux fonctions, fermeture (closure) et
transition (GOTO).
 ANALYSE ASCENDANTE :
Analyseur LR :
Si G est une grammaire d’axiome S, alors G’, la
grammaire augmentée de G, est G avec un nouvel
axiome S‘ et une nouvelle production S’S , la chaine
d’entrée est acceptée quand et seulement quand
l’analyseur est sur le point de réduire S’  S.
La Fermeture d’un Item LR( 0 )
La closure d’un item [ A  α . β] est un ensemble
d’items LR (0) déterminé comme suit :
1- L’item LR (0 ) A  α . β appartient à la closure.
2- Si [ X  α . β] est un item LR( 0) de la closure, si β=
BY où B  λ est une règle de la grammaire alors l’item
LR(0) [B  .λ] doit être ajouté à cette closure.
3- Répéter le pas 2 jusqu’à ce qu’aucun nouvel item LR(
 ANALYSE ASCENDANTE :
Analyseur LR :

Exemple 1:
considérons la grammaire augmentée des expressions :
E’E E  E+T /T T  T* F / F F ( E) / id

Si I est l’ensemble formé de l’unique Item [ E’ 

E]alors :Fermeture(I) contient les Items :
E’ .E E-  .E+T / .T T  .T* F / .F F .( E) / .id

L’opération transition : La deuxième fonction utile est

GOTO( I,X) où I est un ensemble d’items et X est un
symbole de la grammaire . GOTO( I,X) est définie comme
la fermeture de l’ensemble de tous les items A  α X. β
tels que A  α . Xβ appartienne à I GOTO( Ii,X)=closure( [A
 ANALYSE ASCENDANTE :
Analyseur LR :
Exemple2: Si I est l’ensemble des deux Items [E’E. ], [E
 E.+ T], alors GOTO( I ,+) consiste en :
E  E+. T T .T*F T  .F F  . (E) F
 .id
Construction des ensembles d’items L’algorithme décrit
ci-dessous représente la méthode de construction de la
collection canonique d’ensembles d’items LR(0) pour une
grammaire augmentée G’ :
Procédure Items(G’) ;
Début
C :={ fermeture ({[S’S]})} ;
Répéter Pour chaque ensemble d’items I de Cet pour chaque
symbole de
la grammaire X tel que GOTO(I,X) soit non vide et non encore
dans C faire
 ANALYSE ASCENDANTE :
Analyseur LR :
Exemple 3:La collection canonique d’ensembles d’items
LR(0) pour la grammaire de l’exemple 1 est :

Nous pouvons schématiser ces

ensembles d’items LR(0) « états
de l’automate »et la fonction
GOTO « arcs de transition »à
 ANALYSE ASCENDANTE :
alyseur LR (1) simple ou SLR(1) :
La méthode SLR est la moins puissante des trois
en termes du nombre de grammaires pour
lesquelles elle réussit, mais elle est la plus simple
à implanter. La méthode SLR est donc un bon
truction de lapour
point de départ table d’analyse
étudier l’analyse SLR
LR
La table d’analyse SLR(1) est composée de deux
parties ACTION et GOTO.
1/ Construire C={ I0,I1……,In} la collection des
ensembles d’items LR( 0 ) pour G’
2 : Si dans Ii , il existe un item LR( 0 ) A α . aβ
où a est un terminal et si GOTO( Ii,a)=Ij alors
 ANALYSE ASCENDANTE :
alyseur LR (1) simple ou SLR(1) :
ruction de la table d’analyse SLR ( suite
3 : Si dans Ii , il existe un item LR( 0 ) S’ S. alors
mettre dans la case (i, #) l’action accepter
4 : Si dans Ii, il existe un item LR( 0 ) A α .
alors pour chaque symbole appartenant à Follow
(A) mettre dans la case (i,a) de la table l’action rj
où j est le numéro de la règle Aα de la
grammaire.
5 : Si dans Ii, il existe un item LR(0) A α . Xβ où X
est un non terminal et si GOTO(Ii,X)=Ij alors
mettre dans la case (i,X) de la table le numéro j.
 ANALYSE ASCENDANTE :
Analyseur LR :
Exemple : la table d’analyse SLR(1) de la grammaire G
est laidsuivante
( )
:+ * # E T F
0 S5 S1 1 2 3
1 S6 Ac
c
2 R1 R2 S5 R2
3 R4 R4 R4 R4 8 2 3
4 S5 S5
5 R6 R6 R6 R6
6 D4 D4 9 3
7 S1 S6
1
8 R1 R1 S7 R1
9 R1 R1 S7 R1
10 R3 R3 R3 R3
 ANALYSE ASCENDANTE :
Analyseur LR (1) :

Items valide: Nous disons que l’item A β1.β2 est

valide pour un préfixe viable αβ1 s’il existe une dérivation
S’ αAw αβ1β2w Rappelons que dans la méthode SLR,
l’état I indique une action réduire par A α à la vue du
terminal a si l’ensemble des items Ii , contient l’item Aα.
Et a appartient à follow (A).
Cependant, dans certains cas , quand l’état i apparait en
sommet de la pile, le préfixe viable β α de la pile est tel
que βA ne peut être suivi par a dans aucune proto-phrase.
Par conséquent, réduire par Aα est invalide à la vue de a
On va mettre plus d’informations dans les Items de
manière à mieux contrôler les caractères qui peuvent être
arrivés après. On incorpore l’information supplémentaire
dans l’état en redéfinissons les items de façon qu’ils
 ANALYSE ASCENDANTE :
Analyseur LR (1) :

Construction des ensembles d’items LR(1) :

La forme générale d’item devient [Aα.β , a] où A  αβ
est une règle de la grammaire et ‘a’ un terminal. ‘a’ est
appelé lookhead ou entité de prelecture de l’item LR(1) ;
1 indiquant la longueur du second composant appelé
prévision de l’item. la prévision n’a aucun effet dans un
item de la forme [A  α.β , a] avec β≠ϵ, mais un item de
la forme [A  α. , a] implique une action réduire par A  α
uniquement lorsque le prochain symbole en entrée est a.
La méthode pour construire la collection des ensembles
d’items LR(1) valides est essentiellement la même que
celle utilisée pour construire la collection canonique des
ensembles d’items LR(0). Nous avons uniquement besoin
de modifier deux procédures Fermeture « closure » et
 ANALYSE ASCENDANTE :
Analyseur LR (1) :

Fermeture :
La closure de l’item LR(1) [A α.β , a] contient
1-l’item LR( 1) ) [A  α.β , a] lui même
2-si β= Bγ où B est un non terminal et si B  δ ajouter
l’item [B .δ ,b] où b est un terminal de First1 (γa).
3-itérer le pas 2 jusqu’à ce qu’aucun items ne puisse être
ajouté.

Transition :
La fonction GOTO( Ii,X) existe si dans Ii, il existe un item
de la forme : [A α.Xβ , a] et dans ce cas elle est égale à
la closure de l’item [AαX.β , a]
 ANALYSE ASCENDANTE :
nalyseur LR (1) Exemple :
mple : Soit la grammaire donnée par :
S CC ……(1) C  aC ……(2) C  c …… (3)
Nous commençons par augmenter cette grammaire
par S’S La fermeture de [S’.S, #] ici on a A=
S’, α=ϵ , B=S , γ=ϵ et a= #, la fonction fermeture
nous dit d’ajouter [B .δ ,b] pour chaque production B 
δ et chaque terminal b de premier (γ a).
Puisque γ =ϵ et a= # b peut uniquement être #,Par
conséquent nous ajoutons [S .CC, #] Nous
continuons à calculer Fermeture de [S .CC, #] ici on a
A= S, α=ϵ , B=C , γ=C , a= #et premier(C#)={a,c}
nous ajoutons
L’ensemble les items
d’item initial :est :
Io :[C .aC,a],
S’ .S ,# [C .aC,c],
S .CC,# [C .c,a]
C .aC,[Ca/c
.c,c]C .c , a/c
I1 = GOTO(Io,S) S’  S., #
 ANALYSE ASCENDANTE :
Analyseur LR (1) :
Construction de la table LR(1)
1. Construire C= { Io,I1,………In}, la collection des ensembles
d’items LR( 1) pour G’
2. L’état i de l’analyseur est construit à partir de Ii, les actions
d’analyse pour l’état i sont déterminées de la façon suivante :
a./ Si [A α.aβ , b] est dans Ii, remplir Action [i,a] avec
dj où j est tel que GOTO(Ii,a)=Ij
b. /Si [A α ., a] est dans Ii , A≠S’ remplir Action [i,a]
avec rj où j est le num de la règle A α dans la
grammaire.
c. / Si [ S’S. #] est dans Ii remplir action(i,#) avec
accepter
[Link] transitions GOTO pour l’état i sont déterminées comme
suit : si GOTO(Ii,A)= Ij alors placer dans la case (i,A) le
 ANALYSE ASCENDANTE :
Analyseur LR (1) :
La table ci-dessous représente la table canonique
d’analyse de la grammaire
a étudiée
c #: S C
0 S4 S4 1 2
1 ACC
2 S6 S7 5
3 S3 S3 8
4 R3 R3
5 R1
6 S6 S6 9
7 R3
8 R2 R2
9 R2

Analyser la chaine : aacaac

 ANALYSE ASCENDANTE :
Analyseur LR (1) :

À suivre