Ministre de l’Enseignement supérieur et de la Recherche Scientifique

Université Abderrahmane Mira Bejaia

Faculté des sciences exactes
Département d’informatique
Licence académique 3ème année

Cours compilation

Chapitre 5 : Analyse LR

1
Licence 3 Cours compilation Chapitre 5

Introduction
Nous introduisons un modèle général d’analyse syntaxique ascendante connu sous le nom
Décalage-Réduction. La méthode d’analyse la plus connue et applicable est l’analyse LR, qui peut
en principe être utilisé par tous les langages de programmation.

5.1 Principe de la méthode Décalage-Réduction

L’analyse par Décalage-Réduction a pour but de construire un arbre syntaxique pour une chaine
source, ce processus peut être considéré comme la réduction d’une chaine 𝜔 vers l’axiome de la
grammaire.
Exemple 1 :
Soit la grammaire G suivante :
< 𝐵𝑙𝑜𝑐 >→ 𝐵𝑒𝑔𝑖𝑛 < 𝐿𝐷 >; < 𝐿𝐼 > 𝑒𝑛𝑑
{< 𝐿𝐷 > → < 𝐿𝐷 >; 𝑑 ⁄𝑑
< 𝐿𝐼 > → < 𝐿𝐼 >; 𝑖⁄𝑖
Analyser la chaine : Begin d ; d ; i ; i end.
L’arbre syntaxique de la chaine est :

Table d’analyse :

2
Licence 3 Cours compilation Chapitre 5

Pile Chaine Action

# Begin d ; d ; i ; i end # Décalage
# Begin d ; d ; i ; i end # Décalage
# Begin d ; d ; i ; i end # Réduction < 𝐿𝐷 > → 𝑑
# Begin <LD> ; d ; i ; i end # Décalage
# Begin <LD> ; d ; i ; i end # Décalage
# Begin <LD> ; d ; i ; i end # Réduction< 𝐿𝐷 > →< 𝐿𝐷 >; 𝑑
# Begin <LD> ; i ; i end # Décalage
# Begin <LD> ; i ; i end # Décalage
# Begin <LD> ; i ; i end # Réduction < 𝐿𝐼 > → 𝑖
# Begin <LD> ; <LI> ; i end # Décalage
# Begin <LD> ; <LI> ; i end # Décalage
# Begin <LD> ; <LI> ; i end # Réduction < 𝐿𝐼 > →< 𝐿𝐼 >; 𝑖
# Begin <LD> ; <LI> end # Décalage
# Begin <LD> ; <LI> end # Réduc <𝐵𝑙𝑜𝑐>→𝐵𝑒𝑔𝑖𝑛<𝐿𝐷>;<𝐿𝐼>𝑒𝑛𝑑
#<Bloc> # Chaine acceptée

Remarque
Cette méthode est impuissante, car elle ne résout pas le problème d’indéterminisme. Pour cela,
on rajoute des outils tels que des méthodes LR.

5.2 Analyse LR
Une analyse LR(K) est définie comme suit :

 L : Left to right (de gauche à droite);

 R : Constructing a rightmost derivation in reverse (Construire une dérivation à droite dans
le sens inverse);
 K : nombre de symboles de prévision pour prendre une décision d’analyse (Décalage ou
Réduction).
5.2.1 Propriétés
LR est une méthode par Décalage-Réduction sans retour arrière, la classe de grammaires
analysées par la méthode LR est un sur ensemble des grammaires analysées par la méthode LL.
Un analyseur LR peut détecter aussi tôt que possible une erreur de syntaxe.
5.2.2 Remarque
Pour pouvoir faire de l’analyse LR, il faut que la grammaire soit non-ambiguë. Il existe deux
méthodes d’analyse LR
1. Méthode des contextes
2. Méthode des Items

3
Licence 3 Cours compilation Chapitre 5

5.3 Méthode des contextes

5.3.1 L’analyse LR(0)
5.3.1.1Définition des contextes gauches et des contextes droits
𝜃𝛼, 𝜔 respectivement contexte gauche et contexte droit de la règle A → 𝛼;
𝑆 →∗ 𝜃𝛼𝛽
𝑠𝑖 { 𝑒𝑡 avec 𝜃 ne peut être réduit avant.
𝛽 → 𝜔
Avec 𝜃, 𝛼 ∈ (𝑇 ∪ 𝑁)∗ 𝑒𝑡 𝜔 ∈ 𝑇 ∗
• 𝜃𝛼 : contenu de la pile a la réduction de 𝛼 en A;
• 𝜔: Reste de la chaine à la réduction de 𝛼 en A.

Exemple 2 :
Soit la grammaire G1 suivante :
𝑆 → 𝐴𝐵𝑐
{𝐴 → 𝑎
𝐵 →𝑏

Règle Contexte gauche Contexte droit

𝑆 → 𝐴𝐵𝑐 #ABc #
𝐴 →𝑎 #a bc#
𝐵 →𝑏 #Ab c#

Exemple 3 : Soit la grammaire G2 suivante :

𝑆 → 𝐴𝐵
{𝐴 → 𝑎𝐴⁄𝑎
𝐵 → 𝑏𝐵⁄𝑏
Règle Contexte gauche Contexte droit

𝑆 → 𝐴𝐵 #AB #
𝐴 → 𝑎𝐴 #𝑎𝑎∗ 𝐴 𝑏𝑏 ∗ #
𝐴 →𝑎 #𝑎∗ 𝑎 𝑏𝑏 ∗ #
𝐵 → 𝑏𝐵 #𝐴𝑏 ∗ 𝑏𝐵 #
𝐵 →𝑏 #𝐴𝑏 ∗ 𝑏 #
5.3.2. Définition des contextes LR(k)
Les contextes LR(k) de la règle A → 𝛼, sont obtenus en concaténant les contextes gauches et les
k premiers caractères des contextes droits.
Formellement
4
Licence 3 Cours compilation Chapitre 5

Si (𝜃, 𝜔) est un contexte de la règle A → 𝛼, alors le contexte LR(K) de A est 𝜃. 𝑑𝑒𝑏𝑢𝑡𝑘(𝜔).

Exemple 4 :
Soit la grammaire G1 de l’exemple précédent :
𝑆 → 𝐴𝐵
{𝐴 → 𝑎𝐴⁄𝑎
𝐵 → 𝑏𝐵⁄𝑏
Règle Contexte gauche Contexte droit Contexte LR(1)

𝑆 → 𝐴𝐵 #AB # #AB#
𝐴 → 𝑎𝐴 #𝑎𝑎∗ 𝐴 𝑏𝑏 ∗ # #𝑎𝑎∗ 𝐴𝑏
𝐴 →𝑎 #𝑎∗ 𝑎 𝑏𝑏 ∗ # #𝑎∗ 𝑎𝑏
𝐵 → 𝑏𝐵 #𝐴𝑏 ∗ 𝑏𝐵 # #𝐴𝑏 ∗ 𝑏𝐵#
𝐵 →𝑏 #𝐴𝑏 ∗ 𝑏 # #𝐴𝑏 ∗ 𝑏#

𝜃 ∈ 𝑐𝑜𝑛𝑡𝑒𝑥𝑡𝑒 𝐿𝑅(𝑘) 𝑑𝑒 𝐴 → 𝛼
G est une grammaire LR(k) ssi {
𝜃. 𝜔 ∈ 𝑐𝑜𝑛𝑡𝑒𝑥𝑡𝑒 𝐿𝑅(𝑘) 𝑑𝑒 𝐵 → 𝛽
Alors
𝐴=𝐵
{𝛼 = 𝛽
𝜔=𝜀
En d’autres termes, il n’y a pas d’inclusion entre les contextes.

5.3.3. Implémentation de la méthode des contextes

1. Construire les contextes gauches est droits ;
2. Vérifier si la grammaire est LR(k) ;
3. Construire un automate déterministe reconnaissant les contextes LR(k) ;
4. Traduire l’automate en une table d’analyse ;
5. Faire l’analyse en exploitant la table d’analyse.

5.3.4. Construction de l’automate reconnaissant les contextes LR(k)

Les mots des contextes LR(k) sont équivalents aux expressions régulières (concaténation, union,
itération ….). Nous associons un automate d’états finis aux différentes expressions régulières de
la manière suivante :

5
Licence 3 Cours compilation Chapitre 5

• Chaque état final de cet automate d’états finis correspond à une réduction.
• Chaque transition est étiquetée par un symbole ∈ (𝑇 ∪ 𝑁)∗ ∪ {#}.

L’automate d’états finis noté A correspondant aux contextes LR(1) de la grammaire G1 est :

5.3.5 Traduction de l’automate en table d’analyse

Le tableau suivant représente la table d’analyse de la grammaire G 2

a b # S A B

S0 D,6 1 2
S1 CA
S2 D,4 3
S3 𝑆 → 𝐴𝐵
S4 D,4 𝐵→𝑏 5
S5 𝐵 → 𝑏𝐵
S6 D,6 𝐴→𝑎 7
S7 𝐴 → 𝑎𝐴

5.3.6 Algorithme d’analyse LR(1)

Initialement la pile contient (#0)
Lire T[Tête de pile, tc].

6
Licence 3 Cours compilation Chapitre 5

Si vide alors Erreur

Si c’est un décalage alors, empiler le terme courant (tc) et l’état.
Si c’est une réduction alors
1. Dépiler le membre droit de production ;
2. Empiler le membre gauche de production ;
3. Empiler T[sommet de la pile précédente, MGP]
Si CA alors fin de procédure d’analyse et chaine correcte.
5.3.6.1 Exemple d’analyse

Pile Chaine Action

#0 aabbb# D6
#0a6 abbb# D6
#0a6a6 bbb# R𝐴→𝑎
#0a6A7 bbb# R 𝐴 → 𝑎𝐴
#0A2 bbb# D4
#0A2b4 bb# D4
#0A2b4b4 b# D4
#0A2b4b4b4 # R 𝐵→𝑏
#0A2b4b4B5 # R 𝐵 → 𝑏𝐵
#0A2b4B5 # R 𝐵 → 𝑏𝐵
#0A2B3 # R 𝑆 → 𝐴𝐵
#0S1 # CA

5.3.6.2 Remarque :
• Une grammaire récursive gauche directe en S n’est pas LR(0);
• Une grammaire qui est LR(K) est LR(k+1) ;
• Une grammaire est LR(k) ssi la table d’analyse est mono définie.

5.4 Méthode des items

Une autre variante de la technique d’analyse syntaxique ascendante LR se base sur le
principe des items. Nous définissons les items comme une position d’analyse.

7
Licence 3 Cours compilation Chapitre 5

5.4.1 Définition d’un item

Un item LR d’une grammaire est une règle de production avec un point (.) dans le
membre droit de production.
À la règle 𝐴 → 𝑋𝑌𝑍 correspond les items suivants :
𝐴 →. 𝑋𝑌𝑍
𝐴 → 𝑋. 𝑌𝑍
𝐴 → 𝑋𝑌. 𝑍
𝐴 → 𝑋𝑌𝑍.

5.4.1 Définition d’un item

Un item peut être représenté par un couple d’entiers (n,m) ou (n) représente le numéro
de la règle et (m) représente la position d’un point d’analyse.
Un item de la forme 𝐴 → 𝛼. 𝛽 représente une situation d’analyse où on a déjà reconnu une
chaine dérivable à partir de 𝛼 et on s’attend à reconnaitre une chaine dérivable à partir de 𝛽

5.4.2 Définition d’un item LR(1)

Un item LR(1) est un élément de la forme [𝐴 → 𝛼. 𝛽, 𝑎] 𝑜𝑢 𝛼, 𝛽 ∈ (𝑇 ∪ 𝑁)∗ 𝑒𝑡 𝑎 ∈ 𝑇 ∪
{#} 𝑒𝑡 𝐴 → 𝛼𝛽 ∈ à 𝑙𝑎 𝑔𝑟𝑎𝑚𝑚𝑎𝑖𝑟𝑒 𝐺.
Exemple :
[𝐴 →. 𝑐𝐵𝑑, 𝑎], [𝐴 →. 𝑐𝐵𝑑, #]

5.4.3 Fermeture transitive d’un ensemble t’item LR(1)

Soit I l’ensemble des items LR(1) ;
Début

𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑖𝑡𝑒𝑚 [𝐴 → 𝛼. 𝐵𝛽, 𝑎] ∈ 𝐼 𝑒𝑡

𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑟è𝑔𝑙𝑒 : 𝐵 → 𝛾 𝑒𝑡
𝑐ℎ𝑎𝑞𝑢𝑒 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 𝑏 𝐷𝑒𝑏1(𝛽𝑎) 𝑞𝑢𝑖 𝑛′ 𝑒𝑠𝑡 𝑝𝑎𝑠 𝑑é𝑗à 𝑑𝑎𝑛𝑠 𝐼
𝐴𝑗𝑜𝑢𝑡𝑒𝑟 [𝐵 →. 𝛾, 𝑏] 𝑑𝑎𝑛𝑠 𝑙 ′ 𝑒𝑛𝑠𝑒𝑚𝑏𝑙𝑒 𝐼;
𝐽𝑢𝑠𝑞𝑢′ à 𝑐𝑒 𝑞𝑢′ 𝑖𝑙 𝑛′ 𝑦 𝑎 𝑝𝑙𝑢𝑠 𝑑′ 𝑖𝑡𝑒𝑚 𝑎 𝑎𝑗𝑜𝑢𝑡𝑒𝑟 à 𝐼

Exemple 5 : Soit la grammaire G suivante.

Calculer les items LR(1) tels que I = {[𝐸 → 𝐸+. 𝑇, #]}

8
Licence 3 Cours compilation Chapitre 5

𝐸 → 𝐸 + 𝑇⁄𝑇
𝑇 → 𝑇 ∗ 𝐹 ⁄𝐹
{
𝐹 → (𝐸)⁄𝑖

Solution :
La fermeture de I = {[𝐸 → 𝐸+. 𝑇, #], [𝑇 →. 𝑇 ∗ 𝐹, #], [𝑇 →. 𝐹, #], [𝑇 →. 𝑇 ∗ 𝐹, ∗], [𝑇 →
. 𝐹, ∗], [𝐹 → (𝐸), #], [𝐹 →. 𝑖, #], [𝐹 → (𝐸), ∗], [𝐹 →. 𝑖, ∗]}
5.4.4 Définition de la fonction GOTO d’un ensemble t’item LR(1)
Soit I l’ensemble des items LR(1), X ∈ (𝑇 ∪ 𝑁)
Fonction GOTO(I, X)
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑠𝑦𝑚𝑏𝑜𝑙𝑒 𝑋 𝑑𝑒 𝐺 𝑒𝑡
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑖𝑡𝑒𝑚 : [𝐴 → 𝛼. 𝑋𝛽, 𝑎] 𝑓𝑎𝑖𝑟𝑒
𝐺𝑂𝑇𝑂(𝐼, 𝑋) = 𝐹𝑒𝑟𝑚𝑒𝑡𝑢𝑟𝑒(𝐽)
𝐽 é𝑡𝑎𝑛𝑡 𝑙 ′ 𝑒𝑛𝑠𝑒𝑚𝑏𝑙𝑒 𝑑′ 𝑖𝑡𝑒𝑚𝑠[𝐴 → 𝛼𝑋. 𝛽, 𝑎]

Exemple 6 : Soit la grammaire G suivante.

Calculer les items LR(1) tel que I = {[𝐸 → 𝐸+. 𝑇, #]}
I = {[𝐸 → 𝐸+. 𝑇, #], [𝑇 →. 𝑇 ∗ 𝐹, #], [𝑇 →. 𝐹, #], [𝑇 →. 𝑇 ∗ 𝐹, ∗], [𝑇 →. 𝐹, ∗], [𝐹 →
(𝐸), #], [𝐹 →. 𝑖, #], [𝐹 → (𝐸), ∗], [𝐹 →. 𝑖, ∗]
𝐺𝑜𝑡𝑜(𝐼, +) = ∅, 𝐺𝑜𝑡𝑜(𝐼,∗) = ∅, 𝐺𝑜𝑡𝑜(𝐼, 𝑖) = ∅
𝐺𝑜𝑡𝑜(𝐼, 𝑖) = {[𝐹 → 𝑖. , #], [𝐹 → 𝑖. , ∗]}
𝐺𝑜𝑡𝑜(𝐼, 𝐹) = {[𝑇 → 𝐹. , #], [𝑇 → 𝐹. , ∗]}

5.4.5 Ensemble canonique des items LR(1)

Soit l’ensemble canonique des items appelés C
Début C = Fermeture([𝑍 →. 𝑆, #])
𝑅𝑒𝑝𝑒𝑡𝑒𝑟
𝑃𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑒𝑛𝑠𝑒𝑚𝑏𝑙𝑒 𝑑′ 𝑖𝑡𝑒𝑚 𝐼(𝑐) 𝑒𝑡
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑠𝑦𝑚𝑏𝑜𝑙𝑒 𝑋 ∈ (𝑁 ∪ 𝑃) 𝑡𝑒𝑙 𝑞𝑢𝑒
𝑙𝑎 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛 𝐺𝑜𝑡𝑜(𝐼, 𝑋) 𝑛′ 𝑒𝑠𝑡 𝑝𝑎𝑠 𝑣𝑖𝑑𝑒 𝑒𝑡 𝑛′ 𝑒𝑠𝑡 𝑝𝑎𝑠 𝑑𝑎𝑛𝑠 𝐶
𝑓𝑎𝑖𝑟𝑒
𝑎𝑗𝑜𝑢𝑡𝑒𝑟 𝐺𝑜𝑡𝑜(𝐼, 𝑋) à 𝐶;
Faite
Jusqu’à ce qu’il n’y est plus d’items à ajouter à C.
Exemple 7 : Soit la grammaire G suivante.
𝑆 → 𝐴𝐴
𝐺3 : {
𝐴 → 𝑎𝐴⁄𝑏
Calculer les différents items
Solution :
𝐼0 = {[𝑍 →. 𝑆, #], [𝑆 →. 𝐴𝐴, #], [𝐴 →. 𝑎𝐴, 𝑎], [𝐴 →. 𝑎𝐴, 𝑏], [𝐴 →. 𝑏, 𝑎], [𝐴 →. 𝑏, 𝑏]}
𝐼1 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝑆) = {[𝑍 → 𝑆. , #]}

9
Licence 3 Cours compilation Chapitre 5

𝐼2 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐴) = {[𝑆 → 𝐴. 𝐴, #], [𝐴 →. 𝑎𝐴, #], [𝐴 →. 𝑏, #]}

𝐼3 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝑎) = {[𝐴 → 𝑎. 𝐴, 𝑎], [𝐴 → 𝑎. 𝐴, 𝑏], [𝐴 →. 𝑎𝐴, 𝑎], [𝐴 →. 𝑎𝐴, 𝑏], [𝐴 →. 𝑏, 𝑎], , [𝐴 →. 𝑏, 𝑏]}
𝐼4 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝑏) = {[𝐴 → 𝑏. , 𝑎], [𝐴 → 𝑏. , 𝑏]}
𝐼5 = 𝐺𝑜𝑡𝑜(𝐼2 , 𝐴) = {[𝐴 → 𝐴𝐴. , #]}
𝐼6 = 𝐺𝑜𝑡𝑜(𝐼2 , 𝑎) = {[𝑆 → 𝑎. 𝐴, #], [𝐴 →. 𝑎𝐴, #], [𝐴 →. 𝑏, #]}
𝐼7 = 𝐺𝑜𝑡𝑜(𝐼7 , 𝑏) = {[𝐴 → 𝑏. , #]}
𝐼8 = 𝐺𝑜𝑡𝑜(𝐼3 , 𝐴) = {[𝐴 → 𝑎𝐴. , 𝑎], [𝐴 → 𝑎𝐴. , 𝑏]}
𝐼3 = 𝐺𝑜𝑡𝑜(𝐼3 , 𝐴)
𝐼9 = 𝐺𝑜𝑡𝑜(𝐼6 , 𝐴) = {[𝑆 → 𝑎𝐴. , #]}
𝐼6 = 𝐺𝑜𝑡𝑜(𝐼6 , 𝐴)
𝐼4 = 𝐺𝑜𝑡𝑜(𝐼3 , 𝑏)
𝐼7 = 𝐺𝑜𝑡𝑜(𝐼6 , 𝑏)

5.4.6 Construction de l’automate d’états finis correspondant à l’ensemble des items

Soit les étapes suivantes pour construire l’automate d’états finis:
1. Un ensemble d’items 𝐼𝑖 Corresponds à un état i;
2. La fonction Goto correspond à une transition dans l’automate ;
3. Un ensemble d’items contenant un item spécifique de la forme [𝐴 → 𝛼. , 𝑎] Corresponds
à un état final. 3

Le tableau suivant représente la table d’analyse de la grammaire G 3

a b # S A

0 D,3 D,4 1 2

1 CA

2 D,6 D,7 5

3 D,3 D,7 8

4 𝐴 →𝑏 𝐴 →𝑏

10
Licence 3 Cours compilation Chapitre 5

5 𝑆 → 𝐴𝐴

6 D,6 D, 7 9

7 𝐴→𝑏

8 𝐴 → 𝑎𝐴 𝐴 → 𝑎𝐴

9 𝐴 → 𝑎𝐴

5.3.4.2 Remarque :
• Une grammaire récursive gauche directe en S n’est pas LR(0);
• Une grammaire qui est LR(K) est LR(k+1) ;
• Une grammaire est LR(k) ssi la table d’analyse est monodéfinie.

11