Université Badji Mokhtar-Annaba Année : 2022/2023

Faculté de Technologie Licence 3

Département d’Informatique 22/01/2023
Examen Semestriel : Compilation
Duré 01h30

Exercice 1 : (5.5 pts)

1.

a. 𝑖𝑛𝑡 𝑎 = 2, 𝑏 = 3 ; b. 𝑎 = ((𝑏 + 𝑐) ∗ 𝑑;
𝑏𝑜𝑜𝑙𝑒𝑎𝑛 𝑎 = 𝑏 + 𝑐 = 3 ; 0.5 pt
0.5 pt

- Compilation : la variable a ne peut pas être - Compilation : une parenthèse fermante qui
déclarée 2 fois. manque (ou une parenthèse ouvrante de
plus).
- Compilation : opération booléenne d’égalité
au lieu d’une affectation. (== au lieu de =)
c. 𝑖𝑓 ( 𝑎 <= 0 ) {𝑥 = 2 / 𝑎 } 𝑒𝑙𝑠𝑒 𝑥 = d. 𝑖𝑛𝑡 𝑡𝑎𝑏[5] ;
𝑎; 𝑡𝑎𝑏[5] = 2 ; 0.5 pt
0.5 pt
- Compilation : un point-virgule qui manque - Exécution : La taille du tableau = 5 mais les
( 𝑥 = 2 / 𝑎;) indices prennent les valeurs entre [0 − 4]
- Exécution : une division par 0 si la variable 𝑎 (l’indice 5 n’existe pas).
prend la valeur 0 (vu que le teste est 𝑎 <= 0)
2. L’expression régulière de l’adresse IP v4 est formée de 4 chiffres qui ne dépassent pas 255 : (\d peut
remplacer l’intervalle [0-9])
a. 0 0.5 pt
b. De 1 à 99 : [1-9][0-9] (La solution [0-9]{1, 2} est acceptée pour remplacer a. et b. ) 0.5 pt
c. De 100 à 199 : 1[0-9]{1,2} (La solution (0|1)?[0-9]{1,2} peut remplacer a. b. et c.)
0.5 pt
d. De 200 à 249 : 2[0-4][0-9]
0.5 pt
e. De 250 à 255 : 25[0-5]
𝐸𝑅 = 0|[1 − 9][0 − 9]|1[0 − 9]{1,2}|2[0 − 4][0 − 9]|25[0 − 5] \. 0|[1 − 9][0 − 9]|1[0 − 9]{1,2}|2[0
− 4][0 − 9]|25[0 − 5] \. 0|[1 − 9][0 − 9]|1[0 − 9]{1,2}|2[0 − 4][0 − 9]|25[0 − 5] \. 0|[1
− 9][0 − 9]|1[0 − 9]{1,2}|2[0 − 4][0 − 9]|25[0 − 5]
Toute solution proche de la correction est acceptée. Les expressions régulières suivantes sont comptées
comme suit :
0.5 pt
o [0 − 9]{1,3}. [0 − 9]{1,3}. [0 − 9]{1,3}. [0 − 9]{1,3}
o (0|[1 − 9][0 − 9]|1[0 − 9]{1,2}|2[0 − 4][0 − 9]|25[0 − 5] \. ){3} 0|[1 − 9][0 − 9]|1[0 −
9]{1,2}|2[0 − 4][0 − 9]|25[0 − 5] 2 pts
 3.
1 2 3 4 5 6
Chaine GRIS GRAS GRS MAISON MAISON MAISON
Expression GR(.)+S GR(.)?S GR(.)?S M(.)+N M(.)+([a- M(.)+(O)+N
régulière z])+N
Vrai Vrai Vrai Vrai Faux Vrai

0.25 pt 0.25 pt 0.25 pt 0.25 pt 0.25 pt 0.25 pt

Exercice 2 : (7 pts)
Soit la grammaire 𝐺 = ({[, ], 𝑑, 𝑒}, {𝑆, 𝑇, 𝑈}, 𝑆, 𝑃) avec les règles de production 𝑃 suivantes :
𝑆 → [𝑇]
𝑇
→ 𝑇𝑈|𝜀
𝑈
→ 𝑑|𝑒|𝑆
1. Cette grammaire est-elle récursive à gauche ? Justifier. (1 pt)
o Oui elle est récursive à gauche car elle contient une production avec une récursivité à gauche
1 pt
immédiate : 𝑇 → 𝑇 𝑈
2. Cette grammaire n’est pas LL(1), pourquoi ? (1 pt) Transformer la en une grammaire 𝐺’ de type LL(1). (1
pt)
1 pt o Cette grammaire n’est pas LL(1) car elle est récursive à gauche.
o Pour la rendre LL(1) il faut éliminer la récursivité à gauche :
𝑇 → 𝑇′
1 pt
𝑇′ → 𝑈𝑇 |𝜀
3. Construire la table d’analyse prédictive LL(1) de la grammaire 𝐺’. (2 pts)
Non- Premier Suivant
Terminal
1 pt 𝑆 [ 𝑑, 𝑒, [, ], $
𝑇 𝜀, 𝑑, 𝑒, [ ]
𝑇’ 𝜀, 𝑑, 𝑒, [ ]
𝑈 𝑑, 𝑒, [ 𝑑, 𝑒, [, ]

[ ] 𝑑 𝑒 $
𝑆 𝑆 → [𝑇]
𝑇 𝑇 → 𝑇′ 𝑇 → 𝑇′ 𝑇 → 𝑇′ 𝑇 → 𝑇′ 1 pt
𝑇’ 𝑇′ → 𝑈𝑇 𝑇′ → 𝜀 𝑇′ → 𝑈𝑇 𝑇′ → 𝑈𝑇
𝑈 𝑈→ 𝑆 𝑈→ 𝑑 𝑈→𝑒

4. Analyser le mot [𝑑 [ ] 𝑒] par un analyseur LL(1). (2 pts)

Pile Entrée Sortie
 1 $𝑆 [𝑑 [ ]𝑒]$ 𝑆 → [𝑇]
2 $]𝑇[ [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
3 $]𝑇 [𝑑 [ ]𝑒]$ 𝑇 → 𝑇′
4 $]𝑇′ [𝑑 [ ]𝑒]$ 𝑇′ → 𝑈𝑇
5 $]𝑇′𝑈 [𝑑 [ ]𝑒]$ 𝑈→ 𝑑
6 $]𝑇′𝑑 [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
7 $]𝑇′ [𝑑 [ ]𝑒]$ 𝑇′ → 𝑈𝑇
8 $]𝑇′𝑈 [𝑑 [ ]𝑒]$ 𝑈→ 𝑆
9 $]𝑇′𝑆 [𝑑 [ ]𝑒]$ 𝑆 → [𝑇]
10 $]𝑇′]𝑇[ [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
11 $]𝑇′]𝑇 [𝑑 [ ]𝑒]$ 𝑇 → 𝑇′
12 $]𝑇′]𝑇′ [𝑑 [ ]𝑒]$ 𝑇′ → 𝜀
13 $]𝑇′] [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
14 $]𝑇′ [𝑑 [ ]𝑒]$ 𝑇′ → 𝑈𝑇
15 $]𝑇′𝑈 [𝑑 [ ]𝑒]$ 𝑈→𝑒
16 $]𝑇′𝑒 [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
17 $]𝑇′ [𝑑 [ ]𝑒]$ 𝑇′ → 𝜀
18 $] [𝑑 [ ]𝑒]$ Comparer, Dépiler, avancer
19 $ [𝑑 [ ]𝑒]$ Chaine acceptée

Barème : 0.25 pt pour chaque numéro de ligne et étape de comparaison (0.25 pt * 6 = 1.5 pt) + 0.5pt pour
l’acceptation de la chaine.

Exercice 3 : (7.5 pts)

Soit la grammaire 𝐺 = ({∨,∧, ¬, (, ), 𝑏}, {𝑆}, 𝑆, 𝑃) avec les règles de production 𝑃 suivantes :
𝑆 → 𝑆 ∨ 𝑆 | 𝑆 ∧ 𝑆 |¬ 𝑆 | ( 𝑆 )| 𝑏
1. Construire la collection d’ensemble d’items LR(0) (3 pts)
- Augmentation de la grammaire : 𝑆′ → 𝑆
- Collection d’ensembles d’item LR(0) : (de 𝐼 à 𝐼 0.25pt * 12 = 3 pts)
𝐼 = 𝐹𝑒𝑟𝑚(𝑆 → . 𝑆) = {𝑆 → . 𝑆; 𝑆 → . 𝑆 ∨ 𝑆; 𝑆 → . 𝑆 ∧ 𝑆; 𝑆 → . ¬ 𝑆; 𝑆 → . ( 𝑆 ); 𝑆 → . 𝑏}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑆) = {𝑆′ → 𝑆. ; 𝑆 → 𝑆.∨ 𝑆; 𝑆 → 𝑆.∧ 𝑆}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , ¬) = {𝑆 → ¬. 𝑆; 𝑆 → . 𝑆 ∨ 𝑆; 𝑆 → . 𝑆 ∧ 𝑆; 𝑆 → . ¬ 𝑆; 𝑆 → . ( 𝑆 ); 𝑆 → . 𝑏}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , ( ) = {𝑆 → (. 𝑆 ); 𝑆 → . 𝑆 ∨ 𝑆; 𝑆 → . 𝑆 ∧ 𝑆; 𝑆 → . ¬ 𝑆; 𝑆 → . ( 𝑆 ); 𝑆 → . 𝑏}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑏 ) = {𝑆 → 𝑏. }
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 ,∨ ) = {𝑆 → 𝑆 ∨. 𝑆; 𝑆 → . 𝑆 ∨ 𝑆; 𝑆 → . 𝑆 ∧ 𝑆; 𝑆 → . ¬ 𝑆; 𝑆 → . ( 𝑆 ); 𝑆 → . 𝑏}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 ,∧ ) = {𝑆 → 𝑆 ∧. 𝑆; 𝑆 → . 𝑆 ∨ 𝑆; 𝑆 → . 𝑆 ∧ 𝑆; 𝑆 → . ¬ 𝑆; 𝑆 → . ( 𝑆 ); 𝑆 → . 𝑏}
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑆 ) = {𝑆 → ¬ 𝑆. ; 𝑆 → 𝑆.∨ 𝑆; 𝑆 → 𝑆.∧ 𝑆}
𝑇𝑟𝑎𝑛𝑠(𝐼 , ¬) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , ( ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑏 ) = 𝐼
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑆 ) = {𝑆 → ( 𝑆. ); 𝑆 → 𝑆.∨ 𝑆; 𝑆 → 𝑆.∧ 𝑆}
 𝑇𝑟𝑎𝑛𝑠(𝐼 , ¬) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , ( ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑏 ) = 𝐼
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑆 ) = {𝑆 → 𝑆 ∨ 𝑆. ; 𝑆 → 𝑆.∨ 𝑆; 𝑆 → 𝑆.∧ 𝑆}
𝑇𝑟𝑎𝑛𝑠(𝐼 , ¬) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , ( ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑏 ) = 𝐼
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑆 ) = {𝑆 → 𝑆 ∧ 𝑆. ; 𝑆 → 𝑆.∨ 𝑆; 𝑆 → 𝑆.∧ 𝑆}
𝑇𝑟𝑎𝑛𝑠(𝐼 , ¬) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , ( ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 , 𝑏 ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∨ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∧ ) = 𝐼
𝐼 = 𝑇𝑟𝑎𝑛𝑠(𝐼 , ) ) = {𝑆 → ( 𝑆 ). }
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∨ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∧ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∨ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∧ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∨ ) = 𝐼
𝑇𝑟𝑎𝑛𝑠(𝐼 ,∧ ) = 𝐼
2. Etablir la table d’analyse prédictive SLR: pour chaque colonne juste 0.25pt (0.25 pt * 8 = 2 pts), La
présence des 6 conflits = 1 pts.
Action Successeur
∨ ∧ ¬ ( ) 𝑏 $ 𝑆
0 𝑑 𝑑 𝑑 1
1 𝑑 𝑑 Acc
2 𝑑 𝑑 𝑑 7
3 𝑑 𝑑 𝑑 8
4 𝑟 𝑟 𝑟 𝑟
5 𝑑 𝑑 𝑑 9
6 𝑑 𝑑 𝑑 10
7 𝑑 /𝑟 𝑑 /𝑟 𝑟 𝑟
8 𝑑 𝑑 𝑑
9 𝑑 /𝑟 𝑑 /𝑟 𝑟 𝑟
10 𝑑 /𝑟 𝑑 /𝑟 𝑟 𝑟
11 𝑟 𝑟 𝑟 𝑟

3. Est-ce que cette grammaire est une grammaire SLR ? Justifier (1.5 pts)
- Cette grammaire n’est pas SLR (1 pt) car on a obtenu plusieurs cases dans sa table prédictive qui
contiennent plusieurs entrées (plusieurs actions) (0.5 pt).