PandaCodeur · Examen 1 / 4

Examen Compilation

Sujet 1 : analyse LL(1) et SLR(1).

Sujet adapté du corrigé de 2023 : 1 h 30, niveau licence, 20 points.

Consignes et rappels

Durée conseillée : 1 h 30. Barème : 6 + 3 + 4 + 7 = 20 points. Traitez les questions avant d’ouvrir les corrections. PREMIER décrit les débuts possibles ; SUIVANT décrit les tokens pouvant suivre un non-terminal. Pour SLR, une réduction A → β se place uniquement sur SUIVANT(A).

1. Questions de cours : 6 points

  • Présenter les grandes phases de compilation (2 points).
  • Dans un contexte attendant if, fi est reconnu comme ID. Classer l’erreur (2 points).
  • Expliquer un attribut synthétisé (2 points).
Afficher la correction expliquée

Analyse lexicale, syntaxique, sémantique, puis génération de code intermédiaire, éventuelle optimisation et génération de code cible. fi est ici un lexème d’identificateur valide : l’erreur est syntaxique car le parseur attend IF. Un attribut synthétisé dépend des attributs des enfants et des informations locales ; par exemple E.val = E1.val + T.val.

2. Décider LL(1) sans table : 3 points

S → b X
X → a Y S X | ε
Y → b S Y | a | b | ε

L’axiome est S. La grammaire est-elle LL(1) ? Donner un conflit suffisant.

Afficher la correction expliquée
Non-terminalPREMIERSUIVANT
S{b}{$, a, b}
X{a, ε}{$, a, b}
Y{a, b, ε}{b}

Pour X, PREMIER(aYSX) = {a}, alors que ε est l’autre branche. Comme SUIVANT(X) = {$,a,b}, le symbole a déclenche les deux choix : X → aYSX et X → ε. La grammaire n’est donc pas LL(1).

Le a apparaît dans SUIVANT(S) car S est suivi de X dans aYSX et X peut commencer par a ; S → bX propage SUIVANT(S) à X. Le b vient notamment de S placé avant Y dans bSY.

3. Une grammaire ambiguë : 4 points

E → ( E ) | E + E | E * E | a

Calculer PREMIER et SUIVANT (2,5 points), construire la table candidate (1 point) puis conclure (0,5 point).

Afficher la correction expliquée
Non-terminalPREMIERSUIVANT
E{(, a}{$, ), *, +}
M()+*a$
EE → ( E ) / E → E + E / E → E * E---E → E + E / E → E * E / E → a-

Les cellules M[E,(] et M[E,a] contiennent chacune trois productions. La grammaire n’est pas LL(1) ; elle est aussi récursive à gauche. Le mot a+a*a possède deux arbres selon le regroupement.

4. Collection LR(0) et table SLR : 7 points

E → B = F | F
F → B
B → + F | a

Construire les états LR(0) (2,5 points), décider SLR(1) (1,5 point), construire la table candidate (2,5 points), puis discuter l’analyse de +a=a (0,5 point).

Afficher la correction expliquée

Numérotation propre à cette page : r1 : E → B = F ; r2 : E → F ; r3 : F → B ; r4 : B → + F ; r5 : B → a. L’axiome augmenté est Z → E.

État I0

Z → · E
E → · B = F
E → · F
F → · B
B → · + F
B → · a

État I1

Z → E ·

État I2

E → B · = F
F → B ·

État I3

E → F ·

État I4

F → · B
B → · + F
B → + · F
B → · a

État I5

B → a ·

État I6

E → B = · F
F → · B
B → · + F
B → · a

État I7

F → B ·

État I8

B → + F ·

État I9

E → B = F ·
DépartSymboleArrivée
I0EI1
I0BI2
I0FI3
I0+I4
I0aI5
I2=I6
I4BI7
I4FI8
I4+I4
I4aI5
I6BI7
I6FI9
I6+I4
I6aI5

Table SLR(1) candidate : d signifie décaler, r réduire,, signale une erreur. Une cellule à deux actions est un conflit.

État=+a$EBF
0-d4d5-123
1---Accepter---
2d6 / r3--r3---
3---r2---
4-d4d5--78
5r5--r5---
6-d4d5--79
7r3--r3---
8r4--r4---
9---r1---
Non-terminalPREMIERSUIVANT
E{+, a}{$}
F{+, a}{$, =}
B{+, a}{$, =}

La chaîne +a=a appartient pourtant au langage : E ⇒ B=F ⇒ +F=F ⇒ +B=F ⇒ +a=F ⇒ +a=B ⇒ +a=a. Le conflit interdit une décision SLR(1) déterministe sans règle supplémentaire ; il ne signifie pas que le mot est hors du langage.