Université El Arbi Ben M’Hidi Oum El Bouaghi
Faculté de sciences exactes et Sciences de la nature et de la vie
Département de Mathématique
Niveau : 3éme années licence SI Dimanche 14 mai 2023 Nom : …………………………….
Module : Compilation Durée 1h 30 m Prénom : ………………………….
Groupe : ………………………….
Examen Final
Exercice 01 (6 points) : choisir les bonnes réponses
1. Une grammaire LR (1) est aussi 2. Que signifie une erreur de syntaxe ?
a. SLR (1). ☐ a. Une erreur dans la logique du programme ☐
b. LR (0). ☐ b. Une erreur dans la sortie du programme ☐
c. LL (1). ☐ c. Une erreur dans la structure du programme ☒ 1
d. Aucune de ces réponses. 1 ☒ d. Une erreur dans l'exécution du programme ☐
3. Une grammaire LR (0) est aussi 4. Dans l'analyse lexicale, le rôle des expressions régulières est de :
a. SLR (1). ☒ a. Définir la syntaxe d'un langage de programmation ☐
1
b. LR (1). ☒ b. Reconnaître et catégoriser les lexèmes ☒1
c. LALR (1). ☒ c. Spécifier les règles de grammaire ☐
d. Aucune de ces réponses. ☐ d. Générer du code machine ☐
5. Une grammaire SLR (1) est aussi 6. Une grammaire ambiguë est une grammaire :
a. LR (0). ☐ 1. Qui permet plusieurs interprétations pour la même entrée. ☒ 1
b. LR (1). ☒ 2. Sans aucune règle ☐
c. LALR (1). 1 ☒ 3. Avec une seule interprétation possible ☐
d. Aucune de ces réponses. ☐ 4. Qui ne reconnaît que les mots-clés ☐
Exercice 02 (6.25 points) :
𝑆 → 𝐸 ;𝑆 | 𝜖
𝐸 →𝐸+𝑇|𝑇
𝐺1 ∶ {
𝑇 →𝑇∗𝐹|𝐹
𝐹 → 𝑖𝑑 | (𝐸)
1. Donnez la suite de dérivation à gauche du mot "id * id + id ;".
S → E ; S → E + T ; S → T + T ; S → T * F + T ; S → F * F + T ; S → id * F + T ; S → id * id + T ;
S → id * id + F ; S → id * id + id ; S → id * id + id ; 0.5
2. Dessinez l'arbre de dérivation du mot "id * id + id ;".
0.5
3. Est-ce que G1 est LL (1), justifiez sans passer par le tableau.
Non, G1 n'est pas LL (1) car il a des récursivités à gauches. 0.5
4. Si non, éliminez la cause, la nouvelle grammaire G' est-elle LL (1) ? (Utiliser la table).
𝑆 → 𝐸 ;𝑆 | 𝜖
𝐸 → 𝑇𝐸 ′
𝐸 → +𝑇𝐸 ′ |𝜖 0.5
′
𝐺′ :
𝑇 → 𝐹𝑇 ′
𝑇 →∗ 𝐹𝑇 ′ |𝜖
′
{ 𝐹 → 𝑖𝑑 | (𝐸)
N Suivant ; + * id ( ) #
S # S→E;S S→E;S S→𝜖
E ;,) E → TE’ E → TE’
E’ ;,) E’ → 𝜖 E’ → +TE’ E’ → 𝜖
T +,;,) T → FT’ T → FT’
T’ +,;,) T’ → 𝜖 T’ → 𝜖 T’ → *FT’ T’ → 𝜖
F *,+,;,) F → id F → (E)
1.5 1.5
Le tableau ne comporte pas de conflit, la grammaire est donc LL (1) 0.25
5. En utilisant le tableau d'analyse LL (1) de G1 ou G', analyser le mot « id * id + id ; »
Etat de la pile Entrée Action
#S id * id + id ; # Dépiler (S), Empiler (S, ; , E)
#S ;E id * id + id ; # Dépiler (E), Empiler (E’ , T)
#S ;E’T id * id + id ; # Dépiler (T), Empiler (T’ , F)
#S ;E’T’F id * id + id ; # Dépiler (F), Empiler (id)
#S,E’T’id id * id + id ; # Dépiler (id)
#S ;E’T’ * id + id ; # Dépiler (T’), Empiler (T’, F , *)
#S ;E’T’F* * id + id ; # Dépiler (*)
1 #S ;E’T’F id + id ; # Dépiler (F), Empiler (id)
#S ;E’T’id id + id ; # Dépiler (id)
#S ;E’T’ + id ; # Dépiler (T’)
#S ;E’ + id ; # Dépiler (E’), Empiler (E’, T , +)
#S ;E’T+ + id ; # Dépiler (+)
#S ;E’T id ; # Dépiler (T), Empiler (T’, F)
#S ;E’T’F id ; # Dépiler (F), Empiler (id)
#S ;E’T’id ;# Dépiler (id)
#S ;E’T’ ;# Dépiler (T’)
#S ;E’ ;# Dépiler (E’)
#S ; ;# Dépiler ( ; )
#S # Dépiler (S)
# # Accepter
Exercice 03 (7.75 points) :
𝑁→𝑀𝐿𝐹𝑃
𝑀 → −| 𝜖
𝐿→𝑐𝐵
𝐺2 ∶ 𝐵 →𝑐𝐵|𝜖
𝐹 → ,𝐿 | 𝜖
{𝑃 → 𝐸 𝑀 𝐿 | 𝜖
1. Est-ce que G2 est SLR ?
La table des suivants 𝑅1 ∶ 𝑁 → 𝑀 𝐿 𝐹 𝑃
N Suivant 𝑅2 ∶ 𝑀 → −
N {#} 𝑅3 ∶ 𝑀 → 𝜖
M {c} 𝑅4 ∶ 𝐿 → 𝑐 𝐵
L {,,#,E} 1.5 𝑅5 ∶ 𝐵 → 𝑐 𝐵
𝐺2 ∶
B {,,#,E} 𝑅6 ∶ 𝐵 → 𝜖
F {E,#} 𝑅7 ∶ 𝐹 → , 𝐿
P {#} 𝑅8 ∶ 𝐿 → 𝜖
𝑅9 ∶ 𝑃 → 𝐸 𝑀 𝐿
{ 𝑅10 ∶ 𝑃 → 𝜖
LA TABLE SLR
STATE ACTION ALLER_À
- C , E # N M L B F P
0 S3 R3 1 2
1 ACC
2 S5 4
3 R2
4 S 7 R8 R8 6
5 S 9 R6 R6 R6 8
0.25 * 15 6 S11 R10 10
7 S5 12
8 R4 R4 R4
9 S 9 R6 R6 R6 13
10 R1
11 S3 R3 14
12 R7 R7
13 R5 R5 R5
14 S5 15
15 R9
Le tableau ne comporte pas de conflit, la grammaire est donc SLR (1) 0.25
2. Est-ce que G2 est LR (0), justifier sans passer par la table.
Non, car il y a plusieurs conflits dans les états de l'automate 0.75
3. Si la grammaire n'est pas LR(0), citez au moins deux conflits possibles.
a. Dans l'état I0, il y a un conflit shift/reduce dans le terminal « c »
b. Dans l'état I4, il y a un conflit shift/reduce dans le terminal «, »
c. Dans l'état I5, il y a un conflit shift/reduce dans le terminal « c » 0.5
d. Dans l'état I6, il y a un conflit shift/reduce dans le terminal « E »
e. Dans l'état I9, il y a un conflit shift/reduce dans le terminal « c »
f. Dans l'état I11, il y a un conflit shift/reduce dans le terminal « - »
g. Dans l'état I14, il y a un conflit shift/reduce dans le terminal « c »
4. Analyser le mot « - c c , c »
Etat de la pile Entrée Action
0 -cc,c# SHIFT (-), état = 3
0-3 cc,c# R2, DÉPILER (2)
0M cc,c# Changement d’état = 2
0M2 cc,c# SHIFT (c), état = 5
0M2c5 c,c# SHIFT (c), état = 9
1 0M2c5c9 ,c# R6 DÉPILER (0)
0M2c5c9B ,c# Changement d’état = 13
0M2c5c9B13 ,c# R5 , DÉPILER (4)
0M2c5B ,c# Changement d’état = 8
0M2c5B8 ,c# R4 , DÉPILER (4)
0M2L ,c# Changement d’état = 4
0M2L4 ,c# SHIFT ( , ), état = 7
0M2L4,7 c# SHIFT (c), état = 5
0M2L4,7c5 # R6 , DÉPILER (0)
0M2L4,7c5B # Changement d’état = 8
0M2L4,7c5B8 # R4 , DÉPILER (4)
0M2L4,7L # Changement d’état = 12
0M2L4,7L12 # R7 , DÉPILER (4)
0M2L4F # Changement d’état = 6
0M2L4F6 # R10 , DÉPILER (0)
0M2L4F6P # Changement d’état = 10
0M2L4F6P10 # R1 , DÉPILER (8)
0N # Changement d’état = 1
0N1 # Accepter
