Université A/Mira Bejaia

Département d’Informatique
Licence Académique (L3)
Année Universitaire 2015/2016

EMD Compilation
Exercice N° 1 (6 points)

Soit G3 la grammaire des expressions logiques

𝑬 → 𝑬 𝒐𝒖 𝑻⁄𝑻
𝒑𝟑 = { 𝑻 → 𝑻 𝒆𝒕 𝑭⁄𝑭
𝑭 → 𝒏𝒐𝒏 𝑭⁄(𝑬)⁄𝒗𝒓𝒂𝒊 ∕ 𝒇𝒂𝒖𝒙

1. Donner l’arbre syntaxique de l’expression : non (vrai ou faux) et (non (vrai et faux)).
2. Eliminer la récursivité à gauche de G3 et factoriser si nécessaire.
3. Calculer les ensembles Début et Suivant des non-terminaux de la nouvelle grammaire.
4. La grammaire obtenue est-elle LL(1) ?
5. Donner la table d’analyse LL(1) correspondante.

Exercice N° 2 (7 points)

Soit la grammaire G1
𝑺 → 𝑨𝑺𝑩⁄𝜺
𝒑𝟏 = {𝑨 → 𝒂𝑨𝒄 ∕ 𝒄
𝑩 → 𝒃𝑩𝑨⁄𝜺

1. Quelle est la forme générale des mots (le langage) générés par la grammaire G1.
2. Calculer les début1, suivant1, début2, suivant2.
3. G1 est LL(1), LL(2), LL(k) ?
a. Si elle est LL(k) analyser la chaine aacbac#.
b. Sinon montrer qu’elle n’est pas LL(k).

Exercice N° 3 (7 points)

Soit la grammaire G2
𝑪 → 𝑫𝒅⁄𝑬𝒆 ∕ 𝒇
𝒑𝟐 = { 𝑫 → 𝑪𝒄
𝑬 → 𝑪𝒄

1. G2 est-elle LR(0), si elle ne l’est pas, est-elle LR(1) (par la méthode des items) ?
2. Si la grammaire est LR(0) ou LR(1), Analyser la chaine 𝒇𝒄𝒅𝒄𝒆# (en utilisant la table
d’analyse LR).

Page 1/1 Bon courage.

 Solution de l’examen
Solution de l’exercice 1

1. Arbre syntaxique de la chaine : non (vrai ou faux) et (non (vrai et faux)) 1

E

T et F

Non F ( E )

( E )
T

E ou T
F

non F
T F

( E )
F faux
T

vrai
T et F

F faux

vrai

2. Suppression de la récursivité gauche : 1

𝑬 → 𝑻𝑬′
𝟎. 𝟓 {
𝑬′ → 𝒐𝒖 𝑻𝑬′⁄𝜺
𝑻 → 𝑭𝑻′
𝟎. 𝟓 { ′
𝑻 → 𝒆𝒕 𝑭𝑻′ ⁄𝜺
𝑭 → 𝒏𝒐𝒏 𝑭⁄(𝑬)⁄𝒗𝒓𝒂𝒊 ∕ 𝒇𝒂𝒖𝒙

1
 3. Calcul des ensembles Début

0.5 0.5
Debut Suivant
E non, (, vrai , faux $, )
E’ ou,  $, )
T non, (, vrai , faux $, ), ou
T’ et,  $, ), ou
F non, (, vrai , faux $, ), ou, et

4. G est-elle LL(1) ? 1
a. G est factorisée et non récursive gauche (0.25)
b. Vérification des conditions :
i. E  TE’ : LL(1) car un seul MDP
ii. E’  ouTE’ /  :
0.25 c1, c2 : Vérifiée
c3: Deb(ouTE’)  Suiv (E’) = {ou}  {$, )} =  Vérifiée
iii. T  FT’ : LL(1) car un seul MDP
iv. T’  et FT’/
0.25 c1, c2 : Vérifiée
c3: Deb(et FT’)  Suiv (T’) = {et}  {$, ), ou} =  Vérifiée
v. F → non F | (E) | vrai | faux
c1 : Vérifiée car les débuts des MDPS sont disjoints
0.25
c2 et c3 vérifiées car pas de MDP qui se dérive sur .
Donc G est LL(1).
5. La table d’analyse. 2

NB : pour chaque erreur dans la table d’analyse on soustrait 0,25

Solution de l’exercice N° 2
Soit la grammaire G1
𝑆 → 𝐴𝑆𝐵 ⁄𝜀
𝑝1 = {𝐴 → 𝑎𝐴𝑐 ∕ 𝑐
𝐵 → 𝑏𝐵𝐴⁄𝜀

1. La forme générale des mots générés par la grammaire G1 est : 1

 (𝑎𝑛 𝑐𝑐 𝑛 )𝑖 (𝑏 𝑘 (𝑎𝑚 𝑐𝑐 𝑚 )𝑘 )𝑖 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑖, 𝑛, 𝑚, 𝑘 ≥ 0

2. Calculer les début1, suivant1, début2, suivant2.

0.25 0.25 0.75 0.75
Debut1 Suivant1 Debut2 Suivant2
S 𝑎 , 𝑐 , 𝜀 #, 𝑏 𝑎𝑎, 𝑎𝑐, 𝑐𝑏, 𝑐𝑎, 𝑐𝑐, 𝑐, 𝜀 𝑏𝑏, 𝑏𝑎, 𝑏𝑐, ## 2
A 𝑎 ,𝑐 #, 𝑎, 𝑐, 𝑏 𝑎𝑎, 𝑎𝑐, 𝑐 𝑎𝑎, 𝑎𝑐, 𝑐𝑏, 𝑐𝑎, 𝑐𝑐, 𝑐#, 𝑏𝑏, 𝑏𝑎, 𝑏𝑐, ##
B 𝑏 ,𝜀 #, 𝑎, 𝑐, 𝑏 𝑏𝑏, 𝑏𝑎, 𝑏𝑐, 𝜀 𝑎𝑎, 𝑎𝑐, 𝑐#, 𝑐𝑏, 𝑏𝑏, 𝑏𝑎, 𝑏𝑐, 𝑐𝑎, 𝑐𝑐, ##

3. G1 est LL(k) ?
0.25 0.25
4
i- La grammaire n’est pas récursive à gauche et elle est factorisé, donc la grammaire peut être
LL(k).
ii- G1 est-elle LL(1) :

Pour la règle S : ……………………………………………………………………0.25

𝐶1 ∶ 𝐷𝑒𝑏𝑢𝑡(𝐴𝑆𝐵) ∩ 𝐷𝑒𝑏𝑢𝑡(𝜀) = {𝑎, 𝑐} ∩ {𝜀} = ∅
𝐶2 ∶ 𝐴𝑆𝐵 ↛ 𝜀
𝐶3 ∶ 𝐷𝑒𝑏𝑢𝑡(𝐴𝑆𝐵) ∩ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡(𝑆) = {𝑎, 𝑐} ∩ {#, 𝑏} = ∅
D’où la règle S est LL(1), donc elle est LL(k).

Pour la règle A : …………………………………………………………………… 0.25

𝐶1 ∶ 𝐷𝑒𝑏𝑢𝑡(𝑎𝐴𝑐) ∩ 𝐷𝑒𝑏𝑢𝑡(𝑐) = {𝑎} ∩ {𝑐} = ∅
𝐶2 ∶ 𝑎𝐴𝑐 ↛ 𝜀 𝑒𝑡 𝑐 ↛ 𝜀
D’où la règle A est LL(1), donc elle est LL(k).

Pour la règle B : …………………………………………………………………….0.5

𝐶1 ∶ 𝐷𝑒𝑏𝑢𝑡(𝑏𝐵𝐴) ∩ 𝐷𝑒𝑏𝑢𝑡(𝜀) = {𝑏} ∩ {𝜀} = ∅
𝐶2 ∶ 𝑏𝐵𝐴 ↛ 𝜀
𝐶3 ∶ 𝐷𝑒𝑏𝑢𝑡(𝑏𝐵𝐴) ∩ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡(𝐵) = {𝑏, 𝑐} ∩ {#, 𝑏, 𝑎, 𝑐} ≠ ∅
D’où la règle B n’est pas LL(1), donc G1 n’est pas LL(1).

iii- G1 est-elle LL(2) : ………………………………………………………………0.75

Les règles S et A sont LL(k) ;
Vérification de la règle B :
𝐶1 ∶ 𝐷𝑒𝑏𝑢𝑡2 (𝑏𝐵𝐴. 𝑠𝑢𝑖𝑣𝑎𝑛𝑡2 (𝐵)0) ∩ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡2 (𝐵) = {𝑏𝑏, 𝑏𝑐, 𝑏𝑐, } ∩ {𝑎𝑎, 𝑎𝑐, 𝑐#, 𝑏𝑏, 𝑏𝑎, 𝑏𝑐, ##} ≠ ∅
D’où la règle B n’est pas LL(2), donc G1 n’est pas LL(2).
D’une manière générale (montrer qu’elle n’est pas LL(k)) :………………………1.75
𝐷𝑒𝑏𝑢𝑡𝑘 (𝑏𝐵𝐴) ∈ 𝑑𝑒𝑏𝑢𝑡𝑘 (𝐵) 𝑒𝑡 𝑠𝑢𝑖𝑣𝑎𝑛𝑡𝑘 (𝐵) = 𝑆𝑢𝑖𝑣𝑎𝑛𝑡𝑘 (𝑆) ∪ 𝑑𝑒𝑏𝑢𝑡𝑘 (𝐴)
𝑂𝑛 𝑎 𝑎𝑢𝑠𝑠𝑖 𝑑𝑒𝑏𝑢𝑡𝑘 (𝐵) ⊂ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡𝑘 (𝑆)
Alors
𝐷𝑒𝑏𝑢𝑡𝑘 (𝑏𝐵𝐴. 𝑠𝑢𝑖𝑣𝑎𝑛𝑡𝑘 (𝐵)) ∩ 𝑠𝑢𝑖𝑣𝑎𝑛𝑡𝑘 (𝐵) = 𝐷𝑒𝑏𝑢𝑡𝑘 (𝑏𝐵𝐴)
Donc la grammaire G1 n’est pas LL(k).
Solution de l’exercice N° 3

Soit la grammaire G2
𝐶 → 𝐷𝑑1 ⁄𝐸𝑒 2 ∕ 𝑓 3
𝑝2 = { 𝐷 → 𝐶𝑐 4
𝐸 → 𝐶𝑐 5
1. G2 est-elle LR(0) (par la méthode des items) ?

Calcul des items LR(0)

𝐼0 = {[𝑍 →. 𝐶], [𝐶 →. 𝐷𝑑], [𝐶 →. 𝐸𝑒], [𝐶 →. 𝑓], [𝐷 →. 𝐶𝑐], [𝐸 →. 𝐶𝑐]} 1.5
𝐼1 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐶) = {[𝑍 → 𝐶. ], [𝐷 → 𝐶. 𝑐], [𝐸 → 𝐶. 𝑐]}
𝐼2 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐷) = {[𝐶 → 𝐷. 𝑑]}
𝐼3 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐸) = {[𝐶 → 𝐸. 𝑒]}
𝐼4 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝑓) = {[𝐶 → 𝑓. ]}
𝐼5 = 𝐺𝑜𝑡𝑜(𝐼2 , 𝑑) = {[𝐶 → 𝐷𝑑. ]}
𝐼6 = 𝐺𝑜𝑡𝑜(𝐼3 , 𝑒) = {[𝐶 → 𝐸𝑒. ]}
𝐼7 = 𝐺𝑜𝑡𝑜(𝐼1 , 𝑐) = {[𝐷 → 𝐶𝑐. ], [𝐸 → 𝐶𝑐. ]}
 On remarque dans l’item 𝐼7 on aura deux réduction dans les mêmes case, la table d’analyse
n’est pas mono défini donc G2 n’est pas LR(0).
Ou bien
 Table d’analyse LR(0) 1
d e f c # C D E
𝐼0 D, 𝐼4 𝐼1 𝐼2 𝐼3
𝐼1 D, 𝐼7 C. A
𝐼2 D, 𝐼5
𝐼3 D, 𝐼6
𝐼4 R, 3 R, 3 R, 3 R, 3 R, 3
𝐼5 R,1 R,1 R,1 R,1 R,1
𝐼6 R,2 R,2 R,2 R,2 R,2
𝐼7 R,4 / R,5 R,4 / R,5 R,4 / R,5 R,4 / R,5 R,4 / R,5

La table d’analyse LR(0) est Multi-définie alors la grammaire G2 n’est pas LR(0), Exemple de cas
de multidéfinition : [𝐼7 , 𝑑], [𝐼7 , 𝑓] … ..

2. G2 est-elle LR(1) (par la méthode des items) 2

Calcul des items LR(1)
𝐼0 = {[𝑍 →. 𝐶, #], [𝐶 →. 𝐷𝑑, #], [𝐶 →. 𝐸𝑒, #], [𝐶 →. 𝑓, #], [𝐷 →. 𝐶𝑐, 𝑑], [𝐸 →. 𝐶𝑐, 𝑒], [𝐶 →
. 𝐷𝑑, 𝑐], [𝐶 →. 𝐸𝑒, 𝑐], [𝐶 →. 𝑓, 𝑐]}
𝐼1 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐶) = {[𝑍 → 𝐶. , #], [𝐷 → 𝐶. 𝑐, 𝑑], [𝐸 → 𝐶. 𝑐, 𝑒]}
𝐼2 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐷) = {[𝐶 → 𝐷. 𝑑, #], [𝐶 → 𝐷. 𝑑, 𝑐]}
𝐼3 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝐸) = {[𝐶 → 𝐸. 𝑒, #], [𝐶 → 𝐸. 𝑒, 𝑐]}
𝐼4 = 𝐺𝑜𝑡𝑜(𝐼0 , 𝑓) = {[𝐶 → 𝑓. , #], [𝐶 → 𝑓. , 𝑐]}

1
 𝐼5 = 𝐺𝑜𝑡𝑜(𝐼2 , 𝑑) = {[𝐶 → 𝐷𝑑. , #], [𝐶 → 𝐷𝑑. , 𝑐]}
𝐼6 = 𝐺𝑜𝑡𝑜(𝐼3 , 𝑒) = {[𝐶 → 𝐸𝑒. , #], [𝐶 → 𝐸𝑒. , 𝑐]}
𝐼7 = 𝐺𝑜𝑡𝑜(𝐼1 , 𝑐) = {[𝐷 → 𝐶𝑐. , 𝑑], [𝐸 → 𝐶𝑐. , 𝑒]}

La table d’analyse LR(1)

d e f c # C D E
𝐼0 D, 𝐼4 𝐼1 𝐼2 𝐼3
𝐼1 D, 𝐼7 C. A
𝐼2 D, 𝐼5
𝐼3 D, 𝐼6
𝐼4 R, 3 R, 3
𝐼5 R,1 R,1
𝐼6 R,2 R,2
𝐼7 R,4 R,5

NB : pour chaque erreur dans la table d’analyse LR(1) on soustrait 0,25

La table d’analyse LR(1) est Mono-définie alors la grammaire G2 est LR(1),

3. Analyser la chaine 𝒇𝒄𝒅𝒄𝒆# 1.5

Pile Chaine Action
𝐼0 𝑓𝑐𝑑𝑐𝑒# 𝐷é𝑐𝑎𝑙𝑎𝑔𝑒 𝐼4
𝐼0 𝑓𝐼4 𝑐𝑑𝑐𝑒# 𝑅é𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑅 3
𝐼0 𝐶𝐼1 𝑐𝑑𝑐𝑒# 𝐷é𝑐𝑎𝑙𝑎𝑔𝑒 𝐼7
𝐼0 𝐶𝐼1 𝑐𝐼7 𝑑𝑐𝑒# 𝑅é𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝐼4
𝐼0 𝐷𝐼2 𝑑𝑐𝑒# 𝐷é𝑐𝑎𝑙𝑎𝑔𝑒 𝐼5
𝐼0 𝐷𝐼2 𝑑𝐼5 𝑐𝑒# 𝑅é𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑅 1
𝐼0 𝐶𝐼1 𝑐𝑒# 𝐷é𝑐𝑎𝑙𝑎𝑔𝑒 𝐼7
𝐼0 𝐶𝐼1 𝑐𝐼7 𝑒# 𝑅é𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑅 5
𝐼0 𝐸𝐼3 𝑒# 𝐷é𝑐𝑎𝑙𝑎𝑔𝑒 𝐼6
𝐼0 𝐸𝐼3 𝑒𝐼6 # 𝑅é𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑅 2
𝐼0 𝐶𝐼1 # Chaine Acceptée