Université d’Oum El Bouaghi Module : Compilation
3-ème année Licence Informatique/SI 28/02/2021
Dr. Sofiane ZAIDI
Corrigé de l’examen
Question de cours (6 points), chaque réponse sur 2 points
Choisissez-vous une réponse pour chacune des questions suivantes :
1. La compilation est constituée des phases suivantes :
• Analyse lexicale, analyse syntaxique, analyse sémantique, et génération de code
2. L’erreur suivante : fi ( a == f(x) ) au lieu de if ( a == f(x) ), est une erreur :
• Syntaxique
3. Dans l’analyse syntaxique ascendante, la réduction d’une chaine est une :
• L’inverse d’une dérivation à droite
Remarque : (il faut écrire la réponse pour chaque question sur la feuille de réponses).
Exercice 1 (8 points)
Soit la grammaire LL(1) suivante:
S → ABC | DAD
A → aA | ε
B → bB | ε
C → eC | ε
D → dD | f
Ou l’axiome est {S}, les terminaux sont {a, b, e, d, f}, et les non terminaux sont {S, A, B, C,
D}
1. Construire les ensembles PREMIER et SUIVANT pour cette grammaire. (2,75 points)
PREMIER(S) = {a, b, e, ε, d, f}
PREMIER(A) = {a, ε}
PREMIER(B) = {b, ε}
PREMIER(C) = {e, ε}
PREMIER(D) = {d, f}
--------------------------------------------------------------------------------------------------------
PREMIER(a) = {a}
PREMIER(b) = {b}
PREMIER(e) = {e}
PREMIER(d) = {d}
PREMIER(f) = {f}
--------------------------------------------------------------------------------------------------------
SUIVANT(S) = {$}
SUIVANT(A) = {b, e, $, d, f}
1/3
Université d’Oum El Bouaghi Module : Compilation
3-ème année Licence Informatique/SI 28/02/2021
Dr. Sofiane ZAIDI
SUIVANT(B) = {e, $}
SUIVANT(C) = {$}
SUIVANT(D) = {a, d, f, $}
2. Établir la table d'analyse de cette grammaire. (2,5 points)
PREMIER (ABC) = {a, b, e, ε}
PREMIER (DAD) = {d, f}
a b e d f $
S S → ABC S → ABC S → ABC S → DAD S→ DAD S → ABC
A A → aA A→ε A→ε A→ε A→ε A→ε
B B → bB B→ε B→ε
C C → eC C→ε
D D → dD D→f
1. Simuler l'analyse de l'expression abe par un analyseur descendant LL(1). (2,75 points)
Pile Entrée Sortie
$S abe$
$ CBA abe$ S → ABC
$ CBAa abe$ A → aA
$ CBA be$
$ CB be$ A→ε
$ CBb be$ B → bB
$ CB e$
$C e$ B→ε
$ Ce e$ C → eC
$C $
$ $ C→ε
L’analyse syntaxique descendante de l’expression abe à était réalisée avec succès
(puisque nous avons trouvé à la fin $ dans la pile et $ dans le tampon d’entrée).
Exercice 2 (6 points)
Soit la grammaire SLR(1) suivante:
S → BB
B → aB | b
Ou l’axiome est {S}, les terminaux sont {a, b}, et les non terminaux sont {S, B}
1. Construire la collection canonique d’ensemble d’items LR(0). (3,5 points)
2/3
Université d’Oum El Bouaghi Module : Compilation
3-ème année Licence Informatique/SI 28/02/2021
Dr. Sofiane ZAIDI
2. Construire la table d’analyse pour cette grammaire. (2,5 points)
SUIVANT(S) = {$}
SUIVANT(B) = {a, b, $}
(0) S' → S
(1) S → BB
(2) B → aB
(3) B→b
Action Successeur
a b $ S B
0 d3 d4 1 2
1 Accepter
2 d3 d4 5
3 d3 d4 6
4 r3 r3 r3
5 r1
6 r2 r2 r2
3/3
