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 4 : Analyse LL

1
Licence 3 Cours compilation Chapitre 4

4.1. Introduction
L’analyse LL est une analyse descendante pour un sous-ensemble de grammaires non
contextuelles, elle analyse l’entré de gauche à droite (Left to right) et en construit une dérivation
à gauche (Leftmost derivation) les grammaires analysables de cette façon sont nommées
grammaire LL.

4.2. Construction des ensembles Début et Suivant

4.2.1. Règle de calcul des débuts (𝜶)
Soit𝛼 ∈ (𝑇 ∪ 𝑁)∗ , début(𝛼 ) est défini étant l’ensemble des symboles de 𝑇 ∪ {𝜀}, qui
débute la séquence dérivée à partir de 𝛼.
Les règles de calculs de l’ensemble des débuts sont :
1. Si 𝐴 → 𝛼1 | 𝛼2 | … |𝛼𝑛 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝐴) = 𝑑𝑒𝑏(𝛼1 ) ∪ 𝑑𝑒𝑏(𝛼2 ) ∪ … ∪ 𝑑𝑒𝑏(𝛼𝑛 )
𝑎𝑣𝑒𝑐 𝛼𝑖 ∈ (𝑇 ∪ 𝑁)∗ 𝑒𝑡 𝑖 ∈ [1, 𝑛]
2. 𝑑𝑒𝑏(𝑎) = {𝑎}
3. 𝑑𝑒𝑏(𝑎𝛾) = {𝑎} 𝑎𝑣𝑒𝑐 𝑎 ∈ 𝑇 𝑒𝑡 𝛾 ∈ (𝑇 ∪ 𝑁)∗
4. 𝑑𝑒𝑏(𝜀) = {𝜀}
5. 𝑑𝑒𝑏(𝐴𝛾) 𝑎𝑣𝑒𝑐 𝐴 ∈ 𝑁 𝑒𝑡 𝛾 ∈ (𝑇 ∪ 𝑁)∗ 𝑖𝑙 𝑒𝑥𝑖𝑠𝑡𝑒 𝑑𝑒𝑢𝑥 𝑐𝑎𝑠:
a. 𝑠𝑖 𝐴 ↛∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝐴𝛾) = 𝑑𝑒𝑏(𝐴)
b. 𝑠𝑖 𝐴 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝐴𝛾) = 𝑑𝑒𝑏(𝐴) − {𝜀} ∪ 𝑑𝑒𝑏{𝛾}

4.2.2. Règle de calcul des suivants (𝑨)

L’ensemble des suivants (𝐴) avec 𝐴 ∈ 𝑁 est défini comme étant l’ensemble de (𝑇 ∪ {#})
pouvant suivre immédiatement le non-terminal A dans la dérivation à partir de l’axiome.
Les règles de calcul de l’ensemble des suivants sont :
1. {#} ∈ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡(𝑆) 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑆 𝑒𝑠𝑡 𝑙 ′ 𝑎𝑥𝑖𝑜𝑚𝑒
2. 𝑆𝑖 ∃ 𝑀𝐷𝑃 𝛼𝐴𝑎𝛽 𝑎𝑣𝑒𝑐 𝛼, 𝛽 ∈ (𝑇 ∪ 𝑁)∗ , 𝑎 ∈ 𝑇 𝑒𝑡 𝐴 ∈ 𝑁, 𝑎𝑙𝑜𝑟𝑠 𝑎 ∈ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡(𝐴).
3. 𝑆𝑖 ∃ 𝑀𝐷𝑃 𝛼𝐴𝐵𝛽 𝑎𝑣𝑒𝑐 𝛼, 𝛽 ∈ (𝑇 ∪ 𝑁)∗ , 𝐴, 𝐵 ∈ 𝑁, 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝐵𝛽) − {𝜀} ⊂ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡(𝐴).
4. 𝑆𝑖 ∃ 𝑢𝑛𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝐴 → 𝑥1 𝑥2 … 𝑥𝑛 𝐵 𝑎𝑣𝑒𝑐 𝑥𝑖 ∈ (𝑇 ∪ 𝑁)∗ 𝑎𝑙𝑜𝑟𝑠
 𝑆𝑢𝑖𝑣(𝐴) ⊂ 𝑠𝑢𝑖𝑣(𝐵)
 𝑠𝑖 𝜀 ∈ 𝑑𝑒𝑏(𝐵) 𝑎𝑙𝑜𝑟𝑠 𝑠𝑢𝑖𝑣 (𝐴) ⊂ \𝑠𝑢𝑖𝑣 (𝑥𝑛 )
.
.
 𝑠𝑖 𝜀 ∈ 𝑑𝑒𝑏(𝑥2 ) 𝑎𝑙𝑜𝑟𝑠 𝑠𝑢𝑖𝑣 (𝐴) ⊂ \𝑠𝑢𝑖𝑣 (𝑥1 )

Exemple 1 :
Soit la grammaire 𝐺1 suivante

2
Licence 3 Cours compilation Chapitre 4

𝑆 → 𝐴𝐵𝑐|𝑎𝑆𝑐
𝐴 → 𝜀| 𝑎𝐴𝐵
{
𝐵 → 𝑏𝐶|𝜀
𝐶 → 𝐵𝑐|𝑎𝐶|𝜀
Ensemble des débuts :
𝑑𝑒𝑏(𝑆) = 𝑑𝑒𝑏(𝐴𝐵𝑐) ∪ 𝑑𝑒𝑏(𝑎𝑆𝑐) = 𝑑𝑒𝑏(𝐴) − {𝜀} ∪ 𝑑𝑒𝑏(𝐵) ∪ {𝑐} ∪ {𝑎}
𝑑𝑒𝑏(𝐴) = 𝑑𝑒𝑏(𝜀) ∪ 𝑑𝑒𝑏(𝑎𝐴𝐵) = {𝜀} ∪ {𝑎}
𝑑𝑒𝑏(𝐵) = 𝑑𝑒𝑏(𝑏𝐶) ∪ 𝑑𝑒𝑏(𝜀) = {𝑏} ∪ {𝜀}
𝑑𝑒𝑏(𝐶) = 𝑑𝑒𝑏(𝐵𝑐) ∪ 𝑑𝑒𝑏(𝑎𝑐) ∪ 𝑑𝑒𝑏(𝜀) = 𝑑𝑒𝑏(𝐵) − {𝜀} ∪ {𝑐} ∪ {𝑎} ∪ {𝜀}
Ensemble des suivants :
𝑠𝑢𝑖𝑣(𝑆) = {#} ∪ {𝑐}
𝑠𝑢𝑖𝑣(𝐴) = 𝑑𝑒𝑏(𝐵𝑐) ∪ 𝑑𝑒𝑏(𝐵)
𝑠𝑢𝑖𝑣(𝐵) = 𝑑𝑒𝑏(𝑐) ∪ 𝑠𝑢𝑖𝑣(𝐴)
𝑑𝑒𝑏(𝐶) = 𝑠𝑢𝑖𝑣(𝐵)
Tableau des débuts et des suivants :

Début suivant
𝑺 𝑎 𝑏 𝑐 # 𝑐
𝑨 𝜀 𝑎 𝑏 𝑐
𝑩 𝑏 𝜀 𝑏 𝑐
𝑪 𝑎 𝑏 𝑐 𝜀 𝑏 𝑐

4.3. Définition d’une grammaire LL(1)

Une grammaire est dite LL(1) ssi elle vérifie les conditions suivantes :
Pour toute grammaire de type 2 et pour toute paire de règles de productions 𝐴 → 𝛼|𝛽
1. 𝐷𝑒𝑏(𝛼) ∩ 𝑑𝑒𝑏(𝛽) = ∅
2. 𝑠𝑖 𝛼 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝛽 ↛∗ 𝜀
3. 𝑠𝑖 𝛼 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝛽) ∩ 𝑠𝑢𝑖𝑣(𝐴) ≠ ∅

Remarques
 Une grammaire est LL(1), si on arrive à décider de l’appartenance d’une chaine à
un langage au vu d’un seul caractère ;
 Une grammaire récursive à gauche n’est pas LL(1) ;
 Une grammaire non factorisée n’est pas LL(1).

3
Licence 3 Cours compilation Chapitre 4

Exemple 2 :
Soit la grammaire 𝐺1 de l’exemple 1
𝑆 → 𝐴𝐵𝑐|𝑎𝑆𝑐
𝐴 → 𝜀| 𝑎𝐴𝐵
{
𝐵 → 𝑏𝐶|𝜀
𝐶 → 𝐵𝑐|𝑎𝐶|𝜀
𝐺1 est-elle LL(1)
𝐺1 n’est pas récursive à gauche et elle est factorisé, alors elle peut être LL(1) ;
Règle N° 1 (S)
Cond 1 : 𝑑𝑒𝑏(𝐴𝐵𝑐) ∩ 𝑑𝑒𝑏(𝑎𝑆𝑐) = {𝑎} Alors S n’est pas LL(1)
Règle N° 2 (A)
Cond 1 : 𝑑𝑒𝑏(𝜀) ∩ 𝑑𝑒𝑏(𝑎𝐵𝐴) = ∅
Cond 2 : 𝑠𝑖 𝜀 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑎𝐵𝐴 ↛∗ 𝜀
Cond 3 : 𝑠𝑖 𝜀 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏(𝑎𝐵𝐴) ∩ 𝑠𝑢𝑖𝑣(𝐴) = ∅ Alors la règle A est LL(1)
Règle N° 3 (B)
Cond 1 : 𝑑𝑒𝑏(𝑏𝐶) ∩ 𝑑𝑒𝑏(𝜀) = ∅
Cond 2 : 𝜀 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝑏𝐶 ↛∗ 𝜀
Cond 3 : 𝑑𝑒𝑏(𝑏𝐶) ∩ 𝑠𝑢𝑖𝑣(𝐵) = {𝑏} Alors la règle B n’est LL(1)
Règle N° 4 (C)
Cond 1 : 𝑑𝑒𝑏(𝐵𝑐) ∩ 𝑑𝑒𝑏(𝑎𝐶) ∩ 𝑑𝑒𝑏(𝜀) = ∅
Cond 2 : 𝜀 →∗ 𝜀 𝑎𝑙𝑜𝑟𝑠 𝐵𝑐 ↛∗ 𝜀 𝑒𝑡 𝑎𝐶 ↛∗ 𝜀
Cond 3 : 𝑑𝑒𝑏(𝐵𝑐) ∩ 𝑠𝑢𝑖𝑣(𝐶) = {𝑐} Alors la règle C n’est LL(1)
Les règles S, B, C ne sont pas LL(1), alors la grammaire 𝐺1 n’est pas LL(1).

4.4 Analyse LL(1)

Pour pouvoir faire de l’analyse LL(1), il faut que la grammaire soit LL(1), non récursive à
gauche et factorisée.
L’analyseur est composé de 4 éléments :

 Table d’analyse ;
 Pile d’analyse ;

4
Licence 3 Cours compilation Chapitre 4

 Chaine d’entrée ;
 Algorithme d’analyse.
4.4.1 Règles de construction de la table d’analyse
Soit la grammaire G LL(1) et soit Table [A, a] la table d’analyse LL(1). La table d’analyse
LL(1) est un tableau ou les lignes représentent les non-terminaux de la grammaire (𝐴 ∈ 𝑁) et les
colonnes représentent les terminaux de la grammaire (𝑎 ∈ 𝑇 ∪ {#}).
La table d’analyse est construite comme suit :
1- Pour chaque règle de la forme 𝐴 → 𝛼 de la grammaire G :
a. ∀𝑎 ∈ 𝑑𝑒𝑏𝑢𝑡(𝛼), 𝑎𝑗𝑜𝑢𝑡𝑒𝑟 𝑙𝑎 𝑟è𝑔𝑙𝑒 𝐴 → 𝛼 à 𝑙𝑎 𝑡𝑎𝑏𝑙𝑒 𝑇𝑎𝑏𝑙𝑒[𝐴, 𝑎];
b. 𝑠𝑖 𝜀 ∈ 𝑑é𝑏𝑢𝑡 (𝐴), 𝑎𝑙𝑜𝑟𝑠 ∀ 𝑏 ∈ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡 (𝐴), 𝑎𝑗𝑜𝑢𝑡𝑒𝑟 𝑙𝑎 𝑟è𝑔𝑙𝑒 𝐴 →
𝛼 à 𝑙𝑎 𝑐𝑎𝑠𝑒 𝑡𝑎𝑏𝑙[𝐴, 𝑏];
2- Toutes les autres cases sont des erreurs.
Exemple : Soit la grammaire suivante

𝐸 → 𝑇𝐸 ′
𝐸 ′ → +𝑇𝐸 ′ | 𝜀
G = 𝑇 → 𝐹𝑇′
𝑇 ′ →∗ 𝐹𝑇 ′ | 𝜀
{ 𝐹 → 𝑖 | (𝐸 )
G est-elle LL(1) ? Construire la table d’analyse LL(1).
Ensemble des débuts et des suivants

Début Suivant
E 𝑖, ( #, )
E’ +, 𝜀 #, )
T 𝑖, ( +, #, )
T’ ∗, 𝜀 +, #, )
F 𝑖, ( ∗, #, )

La grammaire est-elle LL(1)

Pour la paire 𝐸 ′ → +𝑇 𝐸 ′ | 𝜀

1- 𝐷𝑒𝑏(+𝑇𝐸 ′ ) ∩ 𝑑𝑒𝑏 (𝜀) = ∅

2- 𝐸 ′ → 𝜀 𝑚𝑎𝑖𝑠 + 𝑇𝐸 ′ ↛ 𝜀
3- 𝑑𝑒𝑏(+𝑇𝐸 ′ ) ∩ 𝑠𝑢𝑖𝑣(𝐸 ′ ) = ∅
Pour la paire 𝑇 ′ → ∗ 𝐹 𝑇 ′ | 𝜀

5
Licence 3 Cours compilation Chapitre 4

1- 𝐷𝑒𝑏(∗ 𝐹𝑇′) ∩ 𝑑𝑒𝑏 (𝜀) = ∅

2- 𝑇 ′ → 𝜀 𝑚𝑎𝑖𝑠 ∗ 𝐹𝑇 ′ ↛ 𝜀
3- 𝑑𝑒𝑏(∗ 𝐹𝑇 ′ ) ∩ 𝑠𝑢𝑖𝑣(𝑇 ′ ) = ∅
Construction de la table d’analyse :

𝒊 + ∗ ( ) #
𝑬 𝑇𝐸 ′ 𝑇𝐸′
𝑬′ +𝑇𝐸 ′ 𝜀 𝜀
𝑻 𝐹𝑇′ 𝐹𝑇′
𝑻′ 𝜀 ∗ 𝐹𝑇 𝜀 𝜀
𝑭 𝑖 (𝐸)

4.4.2. Algorithme d’analyse LL(1)

On dispose de la chaine d’entrée composée d’un marqueur de fin (#), d’une table
d’analyse LL(1). La pile contient à un instant donné des symboles de la grammaire avec un #
comme marque de fond. Initialement, la pile contient l’axiome de la grammaire avec un #.
𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎𝒆
𝑫𝒆𝒃𝒖𝒕
𝑻𝒄 ← 𝟏𝒆𝒓 𝒄𝒂𝒓𝒂𝒄𝒕è𝒓𝒆 𝒅𝒆 𝒍𝒂 𝒄𝒉𝒂𝒊𝒏𝒆
𝑬𝒎𝒑𝒊𝒍𝒆𝒓 (#𝑺)
𝑭𝒊𝒏𝑨𝒏𝒂𝒍𝒚𝒔𝒆 ← 𝒇𝒂𝒖𝒙
𝑻𝒂𝒏𝒕 𝒒𝒖𝒆 ¬ 𝒇𝒊𝒏𝑨𝒏𝒂𝒍𝒚𝒔𝒆 𝒇𝒂𝒊𝒓𝒆
𝑺𝒊 𝒔𝒐𝒎𝒎𝒆𝒕 𝒅𝒆 𝒑𝒊𝒍𝒆 ∈ 𝑻 𝒂𝒍𝒐𝒓𝒔
𝑺𝒊 𝒕𝒄 = 𝒔𝒐𝒎𝒎𝒆𝒕 𝒑𝒊𝒍𝒆 𝒂𝒍𝒐𝒓𝒔
𝒕𝒄 ← 𝒕𝒔;
𝑫é𝒑𝒊𝒍𝒆𝒓;
𝑺𝒊𝒏𝒐𝒏 𝒄𝒉𝒂𝒊𝒏𝒆 𝒊𝒏𝒄𝒐𝒓𝒓𝒆𝒄𝒕𝒆
𝑭𝒊𝒏𝑨𝒏𝒂𝒍𝒚𝒔𝒆 ← 𝒗𝒓𝒂𝒊
𝑭𝒊𝒏 𝒔𝒊
𝑺𝒊𝒏𝒐𝒏 𝒔𝒊 𝒔𝒐𝒎𝒎𝒆𝒕 ∈ 𝑵 𝒂𝒍𝒐𝒓𝒔
𝑺𝒊 𝑻[𝒔𝒐𝒎𝒎𝒆𝒕 𝒅𝒆 𝒑𝒊𝒍𝒆, 𝑻𝑪] = ∅ 𝒂𝒍𝒐𝒓𝒔
𝑪𝒉𝒂𝒊𝒏𝒆 𝒊𝒏𝒄𝒐𝒓𝒓𝒆𝒄𝒕
𝑭𝒊𝒏𝑨𝒏𝒂𝒍𝒚𝒔𝒆 ← 𝒗𝒓𝒂𝒊
𝑺𝒊𝒏𝒐𝒏 𝑨 ← 𝒔𝒐𝒎𝒎𝒆𝒕 𝒅𝒆 𝒑𝒊𝒍𝒆
𝑫𝒆𝒑𝒊𝒍𝒆𝒓;
𝑬𝒎𝒑𝒊𝒍𝒆𝒓 𝒍𝒆 𝒎𝒐𝒕 𝒎𝒊𝒓𝒐𝒊𝒓 𝒅𝒆 𝒍𝒂 𝒓è𝒍𝒈𝒍𝒆 𝑻[𝑨, 𝑻𝒄] ;
𝑭𝒊𝒏 𝒔𝒊
𝑺𝒊𝒏𝒐𝒏 𝒔𝒊 𝑻𝒄 = ′#′ 𝒂𝒍𝒐𝒓𝒔
𝑪𝒉𝒂𝒊𝒏𝒆 𝒄𝒐𝒓𝒓𝒆𝒄𝒕𝒆
𝑭𝒊𝒏𝑨𝒏𝒂𝒍𝒚𝒔𝒆 ← 𝒗𝒓𝒂𝒊
𝑺𝒊𝒏𝒐𝒏 𝒄𝒉𝒂𝒊𝒏𝒆 𝒊𝒏𝒄𝒐𝒓𝒓𝒆𝒄𝒕𝒆
𝑭𝒊𝒏 𝒂𝒏𝒂𝒍𝒚𝒔𝒆 ← 𝒗𝒓𝒂𝒊
𝑭𝒊𝒏 𝒔𝒊
𝑭𝒊𝒏 𝒔𝒊
𝑭𝒊𝒏 𝒕𝒒; 𝑭𝒊𝒏

6
Licence 3 Cours compilation Chapitre 4

Exemple analyser la chaine 𝑖 + 𝑖 #

𝑷𝒊𝒍𝒆 𝑪𝒉𝒂𝒊𝒏𝒆 𝑻𝒄 𝑨𝒄𝒕𝒊𝒐𝒏

#𝐸 𝑖+𝑖# 𝑖 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝑇𝐸′
#𝐸′𝑇 𝑖+𝑖# 𝑖 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝐹𝑇′
#𝐸′𝑇′𝐹 𝑖+𝑖# 𝑖 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝑖
#𝐸′𝑇′𝑖 𝑖+𝑖# 𝑖 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝐸′𝑇′ +𝑖 # + 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝜀
#𝐸′ +𝑖 # + 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 + 𝑇𝐸′
#𝐸′𝑇 + +𝑖 # + 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝐸′𝑇 𝑖# 𝑖 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝐹𝑇′
#𝐸′𝑇′𝐹 𝑖# 𝑖 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝑖
#𝐸′𝑇′𝑖 𝑖# 𝑖 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝐸′𝑇′ # # 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝜀
#𝐸′ # # 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝜀
# # # 𝐶ℎ𝑎𝑖𝑛𝑒 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑒 ‼!

4.5 Analyse LL(K)

Dans les méthodes syntaxiques par la descente récursive et prédictive utilisées pour
analyser des grammaires LL(1), un seul symbole est consulté pour décider de la règle à dériver.
On peut généraliser ces deux méthodes en leur donnant la faculté de consulter les K prochains
terminaux de la chaine d’entrée, on obtient des analyseurs syntaxiques pouvant traiter des
classes plus larges de grammaires.
Exemple : Soit la grammaire G
𝑆 → 𝑎𝑏𝑆|𝑎𝑐𝑆|𝑏
et une chaine qu’on veut dériver à partir de S.
 Si seul le premier symbole qui est consulté, on ne peut pas décider de la règle à appliquer
parmi (1) et (2). G n’est pas LL(1) ;
 Si nous disposons de 2 symboles de 𝜔, soit 𝜔 = 𝑎𝑐 𝜔′, on peut décider que c’est la règle
2 qui doit être appliquée, donc G est LL(2).

4.5.1 Règle de calcul des débutk

𝑫𝒆𝒃𝒌 = {𝝎 ∈ 𝑻𝒌 |𝜶 →∗ 𝝎𝜸, 𝜸 ∈ (𝑻 ∪ 𝑵)∗ } ∪ {𝝎 ∈ 𝑻𝒍 , 𝒍 < 𝒌 | 𝜶 →∗ 𝝎}
Les étapes de construction de l’ensemble débutk :
1. 𝑠𝑖 𝐴 → 𝛼1 |𝛼2 | … |𝛼𝑛 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏𝑘 (𝐴) = 𝑑𝑒𝑏𝑘 (𝛼2 ) ∪ 𝑑𝑒𝑏𝑘 (𝛼2 ) ∪ … ∪ 𝑑𝑒𝑏𝑘 (𝛼𝑛 )
2. 𝑑𝑒𝑏𝑘 (𝜀) = 𝜀
𝑙
3. 𝑑𝑒𝑏𝑘 (𝜔) = {𝜔′𝑠𝑖 𝜔 ∈ 𝑇 ′ 𝑒𝑡′′ 𝑙 ≤ 𝑘𝑙
𝜔 𝑠𝑖 𝜔 = 𝜔 𝜔 ∈ 𝑇 𝑒𝑡 𝑙 > 𝑘 𝑒𝑡 𝜔′ ∈ 𝑇 𝑘
4. 𝑑𝑒𝑏𝑘 (𝛽𝛾) = 𝑑𝑒𝑏𝑘 (𝑑𝑒𝑏𝑘 (𝛽). 𝑑𝑒𝑏𝑘 (𝛾))

4.5.2 Règle de calcul des suivantk

𝒔𝒖𝒊𝒗𝒌 (𝑨) = {𝝎|𝒁 →∗ 𝜶𝑨𝜷#𝒌 , 𝝎 ∈ 𝒅𝒆𝒃𝒌 (𝜷#𝒌 ) 𝒆𝒕 𝝎 ∈ 𝑻𝒌 }

7
Licence 3 Cours compilation Chapitre 4

Les étapes de construction de l’ensemble Suivk .

1. 𝑠𝑖 𝐵 → 𝛼𝐴𝛽 𝑎𝑙𝑜𝑟𝑠 𝑑𝑒𝑏𝑘 (𝛽. 𝑠𝑢𝑖𝑣𝑘 (𝐵) ⊂ 𝑠𝑢𝑖𝑣𝑘 (𝐴)) 𝑎𝑣𝑒𝑐 𝛼 𝑒𝑡 𝛽 ∈ (𝑇 ∪ 𝑁)∗
2. #𝑘 ∈ 𝑠𝑢𝑖𝑣𝑘 (𝑆) 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑆 𝑒𝑠𝑡 𝑙 ′ 𝑎𝑥𝑖𝑜𝑚𝑒
3. 𝑠𝑖 𝐵 → 𝛼𝐴 𝑎𝑙𝑜𝑟𝑠 𝑠𝑢𝑖𝑣𝑘 (𝐵) ⊂ 𝑠𝑢𝑖𝑣𝑘 (𝐴)
4. 𝑑𝑒𝑏𝑘 (𝛽𝛾) = 𝑑𝑒𝑏𝑘 (𝑑𝑒𝑏𝑘 (𝛽). 𝑑𝑒𝑏𝑘 (𝛾))

4.5.3 Les grammaires LL(k)

Une grammaire est LL(k) cela implique que pour chaque couple de règle 𝐴 → 𝛼|𝛽

𝐷𝑒𝑏𝑘 (𝑑𝑒𝑏𝑘 (𝛼). 𝑠𝑢𝑖𝑣𝑘 (𝐴)) ∩ 𝐷𝑒𝑏𝑘 (𝑑𝑒𝑏𝑘 (𝛽). 𝑠𝑢𝑖𝑣𝑘 (𝐴)) = ∅
Exemple : La grammaire G suivante est-elle LL(k) ?
𝑍→𝑆
{𝑆 → 𝑎𝐴𝑎𝑎| 𝑏𝐴𝑏𝑎
𝐴 → 𝑏|𝜀
a. G est-elle LL(1) ?
 G n’est pas récursive à gauche ;
 G est factorisée ;
 On vérifie les trois conditions.

𝑃𝑜𝑢𝑟 𝑆 → 𝑎𝐴𝑎𝑎|𝑏𝐴𝑏𝑎
𝐶1 − 𝐷𝑒𝑏(𝑎𝐴𝑎𝑎) ∩ 𝑑𝑒𝑏(𝑏𝐴𝑏𝑎) = {𝑎} ∪ {𝑏} = ∅
La règle S est LL(1)

𝑃𝑜𝑢𝑟 𝐴 → 𝑏|𝜀
𝐶1 − 𝐷𝑒𝑏(𝑏) ∩ 𝑑𝑒𝑏(𝜀) = ∅
𝐶2 − 𝑏 ≠ 𝜀
𝐶3 − 𝐷𝑒𝑏(𝑏) ∩ 𝑠𝑢𝑖𝑣(𝐴) = {𝑏} ∪ {𝑎, 𝑏} = {𝑏}
A n’est pas LL(1) dont la grammaire n’est pas LL(1)

b. G est-elle LL(2)

Calcule de l’ensemble des déb2 et suiv2

𝐷𝑒𝑏2 (𝑆) = 𝐷𝑒𝑏2 (𝑎𝐴𝑎𝑎) ∪ 𝐷𝑒𝑏2 (𝑏𝐴𝑏𝑎)

𝐷𝑒𝑏2 (𝑆) = 𝑎. 𝐷𝑒𝑏1 (𝐴𝑎𝑎) ∪ 𝑏. 𝐷𝑒𝑏1 (𝐴𝑏𝑎) = {𝑎𝑏, 𝑎𝑎} ∪ {𝑏𝑏}
𝐷𝑒𝑏2 (𝐴) = 𝐷𝑒𝑏2 (𝑏) ∪ 𝐷𝑒𝑏2 (𝜀) = {𝑏, 𝜀}
𝑆𝑢𝑖𝑣2 (𝑆) = {##}

𝑆𝑢𝑖𝑣2 (𝐴) = 𝐷𝑒𝑏2 (𝑎𝑎. 𝑠𝑢𝑖𝑣2 (𝑆)) ∪ 𝐷𝑒𝑏2 (𝑏𝑎. 𝑆𝑢𝑖𝑣2 (𝑆))={aa, ba}

8
Licence 3 Cours compilation Chapitre 4

𝑫𝒆𝒃𝟐 𝑺𝒖𝒊𝒗𝟐
𝑺 𝑎𝑎, 𝑎𝑏, 𝑏𝑏 ###
𝑨 𝑏, 𝜀 𝑎𝑎, 𝑏𝑎

S est LL(1) alors elle est LL(2)

𝑃𝑜𝑢𝑟 𝐴 → 𝑏|𝜀
𝐷𝑒𝑏2 (𝑏. 𝑠𝑢𝑖𝑣2 (𝐴)) ∩ 𝑠𝑢𝑖𝑣2 (𝐴) = {𝑏𝑎, 𝑏𝑏} ∩ {𝑎𝑎, 𝑏𝑎} = {𝑏𝑎}
A n’est pas LL(2) alors G n’est pas LL(2).

c. G est-elle LL(3)

Calcule de l’ensemble des déb3 et suiv3

𝐷𝑒𝑏3 (𝑆) = 𝐷𝑒𝑏3 (𝑎𝐴𝑎𝑎) ∪ 𝐷𝑒𝑏3 (𝑏𝐴𝑏𝑎)

𝐷𝑒𝑏3 (𝑆) = 𝑎. 𝐷𝑒𝑏2 (𝐴𝑎𝑎) ∪ 𝑏. 𝐷𝑒𝑏2 (𝐴𝑏𝑎) = {𝑎𝑏𝑎, 𝑎𝑎𝑎} ∪ {𝑏𝑏𝑏, 𝑏𝑏𝑎}
𝐷𝑒𝑏3 (𝐴) = 𝐷𝑒𝑏3 (𝑏) ∪ 𝐷𝑒𝑏3 (𝜀) = {𝑏, 𝜀}
𝑆𝑢𝑖𝑣3 (𝑆) = {###}

𝑆𝑢𝑖𝑣3 (𝐴) = 𝐷𝑒𝑏3 (𝑎𝑎. 𝑠𝑢𝑖𝑣3 (𝑆)) ∪ 𝐷𝑒𝑏3 (𝑏𝑎. 𝑆𝑢𝑖𝑣3 (𝑆)) = {𝑎𝑎#, 𝑏𝑎#}

𝑫𝒆𝒃𝟑 𝑺𝒖𝒊𝟑
𝑺 𝑎𝑎𝑎, 𝑎𝑏𝑎, 𝑏𝑏𝑏, 𝑏𝑏𝑎 ###
𝑨 𝑏, 𝜀 𝑎𝑎#, 𝑏𝑎#

S est LL(1) alors elle est LL(3)

𝑃𝑜𝑢𝑟 𝐴 → 𝑏|𝜀
𝐷𝑒𝑏3 (𝑏. 𝑠𝑢𝑖𝑣3 (𝐴)) ∩ 𝑠𝑢𝑖𝑣3 (𝐴) = {𝑏𝑎𝑎, 𝑏𝑏𝑎} ∩ {𝑎𝑎#, 𝑏𝑎#} = ∅
A est LL(3) alors G est LL(3)

4.5.4. Construction de la table d’analyse LL(k).

𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚𝑒
𝐷𝑒𝑏𝑢𝑡
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑛𝑜𝑛 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 𝐴 𝑑𝑒 𝑁 𝑓𝑎𝑖𝑟𝑒
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝑟è𝑔𝑙𝑒 𝐴 → 𝛼 𝑓𝑎𝑖𝑟𝑒
𝑝𝑜𝑢𝑟 𝑐ℎ𝑎𝑞𝑢𝑒 𝜔 ∈ 𝑑𝑒𝑏𝑘 (𝛼. 𝑠𝑢𝑖𝑣𝑘 (𝐴))𝑓𝑎𝑖𝑟𝑒
𝑇[𝐴][𝜔] ← 𝐴 → 𝛼
𝑓𝑖𝑛 𝑝𝑜𝑢𝑟
𝑓𝑖𝑛 𝑝𝑜𝑢𝑟
𝑓𝑖𝑛 𝑝𝑜𝑢𝑟
𝑓𝑖𝑛

9
Licence 3 Cours compilation Chapitre 4

Table d’analyse de l’exemple précédent.

𝒂𝒃𝒂 𝒂𝒂𝒂 𝒃𝒃𝒃 𝒃𝒃𝒂 𝒃𝒂𝒂 𝒂𝒂# 𝒃𝒂#

𝑺 𝑆 → 𝑎𝐴𝑎𝑎 𝑆 → 𝑎𝐴𝑎𝑎 𝑆 → 𝑏𝐴𝑏𝑎 𝑆 → 𝑏𝐴𝑏𝑎
𝑨 𝐴→𝑏 𝐴→𝑏 𝐴→𝜀 𝐴→𝜀

Analyser la chaine bbba#

𝑷𝒊𝒍𝒆 𝑪𝒉𝒂𝒊𝒏𝒆 𝑻𝒄 𝑨𝒄𝒕𝒊𝒐𝒏

#𝑆 𝑏𝑏𝑏𝑎# 𝑏 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝑏𝐴𝑏𝑎
#𝑎𝑏𝐴𝑏 𝑏𝑏𝑏𝑎# 𝑏 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝑎𝑏𝐴 𝑏𝑏𝑎# 𝑏 𝐷é𝑝𝑖𝑙𝑒𝑟 𝑒𝑡 𝑒𝑚𝑝𝑖𝑙𝑒𝑟 𝑙𝑒 𝑚𝑜𝑡 𝑚𝑖𝑟𝑜𝑖𝑟 𝑏
#𝑎𝑏𝑏 𝑏𝑏𝑎 # 𝑏 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝑎𝑏 𝑏𝑎# 𝑏 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
#𝑎 𝑎# 𝑎 𝐴𝑣𝑎𝑛𝑐𝑒𝑟 𝑒𝑡 𝐷é𝑝𝑖𝑙𝑒𝑟
# # # 𝐶ℎ𝑎𝑖𝑛𝑒 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑒 ‼!

10