Théorie des langages : Td 9 analyse ll
Télécharger PDFTD 9 - Analyse LL(1)
Question 1
On considère la grammaire G = ({a, b, c}, {S}, S, {S → aSa | bSb | c}).
a. Quel est le langage engendré par cette grammaire ?
Le langage engendré par cette grammaire est L = {anbmcn | n ≥ 0, m ≥ 0}.
b. Construire la table d’analyse LL(1) de la grammaire G
La table d’analyse LL(1) pour G est la suivante :
- S → c si le symbole suivant est $.
- S → aSa si le symbole suivant est a.
- S → bSb si le symbole suivant est b.
c. Simuler l’analyse prédictive pour les mots bacabetbcba
Les mots bacabetbcba ne sont pas dans le langage L.
Question 2
Soit la grammaire G = ({a, b}, {S}, S, {S → aSa | bSb | ε}).
a. Quel est le langage engendré par cette grammaire ?
Le langage engendré par cette grammaire est L = {anbman | n ≥ 0, m ≥ 0}.
b. Montrer que G n’est pas LL(1) en construisant sa table d’analyse
La table d’analyse LL(1) pour G contient des conflits :
- S → aSa si le symbole suivant est a.
- S → bSb si le symbole suivant est b.
- S → ε si le symbole suivant est $.
- S → aSa | S → ε si le symbole suivant est a (conflit).
- S → bSb | S → ε si le symbole suivant est b (conflit).
Question 3
Soit la grammaire G = ({;, if, (, ), begin, bla, end, else}, {INSTR, EXPR, BLOCK, SEQ, REST}, INSTR, P) où l’ensemble des règles P est :
- INSTR → EXPR ; | BLOCK | if (EXPR) BLOCK REST
- EXPR → bla | ε
- BLOCK → begin SEQ end
- SEQ → INSTR SEQ | ε
- REST → else INSTR | ε
a. Quelles sont les variables effaçables ?
Les variables effaçables sont EXPR et SEQ.
b. Donner la table des ensembles PREMIER
| Variable | PREMIER |
|---|---|
| INSTR | {;, if, begin} |
| EXPR | {bla} |
| BLOCK | {begin} |
| SEQ | {;, if, begin, ε} |
| REST | {else, ε} |
c. Relations du type PREMIER(A) ⊆ SUIVANT(B) impliquées par les productions de G
- PREMIER(EXPR) ⊆ SUIVANT(INSTR) (production INSTR → EXPR ;).
- PREMIER(BLOCK) ⊆ SUIVANT(INSTR) (production INSTR → BLOCK).
- PREMIER(SEQ) ⊆ SUIVANT(BLOCK) (production BLOCK → begin SEQ end).
- PREMIER(INSTR) ⊆ SUIVANT(SEQ) (production SEQ → INSTR SEQ).
- PREMIER(REST) ⊆ SUIVANT(INSTR) (production INSTR → if (EXPR) BLOCK REST).
Relations du type SUIVANT(A) ⊆ SUIVANT(B) impliquées par les productions de G
- SUIVANT(EXPR) ⊆ SUIVANT(INSTR) (production INSTR → EXPR ;).
- SUIVANT(INSTR) ⊆ SUIVANT(SEQ) (production SEQ → INSTR SEQ).
- SUIVANT(BLOCK) ⊆ SUIVANT(REST) (production INSTR → if (EXPR) BLOCK REST).
- SUIVANT(REST) ⊆ SUIVANT(INSTR) (production INSTR → if (EXPR) BLOCK REST et REST effaçable).
d. Table des ensembles SUIVANT
| Variable | SUIVANT |
|---|---|
| INSTR | {;, if, begin, $} |
| EXPR | {;, )} |
| BLOCK | {else, $} |
| SEQ | {;, if, begin, end, $} |
| REST | {;, if, begin, $} |
e. Analyse du mot begin bla; ;end$
Arbre de dérivation et analyse LL(1) :
- INSTR → BLOCK
- BLOCK → begin SEQ end
- SEQ → INSTR SEQ
- INSTR → EXPR ;
- EXPR → bla
- SEQ → ε
Dérivation gauche :
- INSTR → BLOCK → begin SEQ end → begin INSTR SEQ end → begin EXPR ; SEQ end → begin bla ; SEQ end → begin bla ; ε end → begin bla ; end
f. Peut-on remplacer la production SEQ → INSTR SEQ par SEQ → SEQ INSTR ?
Non, on ne peut pas remplacer cette production car cela modifierait l’ordre de dérivation et la structure du langage. La production SEQ → INSTR SEQ permet d’ajouter des instructions à gauche, tandis que SEQ → SEQ INSTR les ajouterait à droite, ce qui changerait le comportement de l’analyseur.
g. Peut-on supprimer la variable REST en remplaçant les productions ?
Non, on ne peut pas supprimer la variable REST sans modifier la grammaire et introduire des ambiguïtés. La production INSTR → if (EXPR) BLOCK REST permet de gérer correctement la fin des instructions après un if et son else.
h. Que se passe-t-il si on remplace INSTR → if (EXPR) BLOCK REST par INSTR → if (EXPR) INSTR REST ? Peut-on y remédier ?
Cette modification introduit une récursion à gauche dans la production INSTR → if (EXPR) INSTR REST, ce qui empêche l’analyse LL(1). Pour y remédier, il faudrait transformer cette production en une forme non récursive à gauche, par exemple :
- INSTR → if (EXPR) BLOCK REST (forme originale).
- Ajouter une nouvelle variable pour éviter la récursion.
Question 4
Soit la grammaire G d’axiome D et de terminaux {int, float, ;, id}, définie par :
- D → T L
- T → int | float
- L → L ; id | id
a. Pourquoi cette grammaire n’est pas LL(1) ?
Cette grammaire n’est pas LL(1) car la production L → L ; id | id introduit un conflit de décalage-réduction. En effet, si le symbole suivant est id, il n’est pas possible de déterminer si la production L → L ; id ou L → id doit être appliquée.
b. Proposer une grammaire LL(1) équivalente et construire sa table d’analyse
Grammaire LL(1) équivalente :
- D → T L'
- T → int | float
- L → id L'
- L' → ; L | ε
Table d’analyse LL(1) :
- D → T L' si le symbole suivant est int ou float.
- T → int si le symbole suivant est int.
- T → float si le symbole suivant est float.
- L → id L' si le symbole suivant est id.
- L' → ; L si le symbole suivant est ;.
- L' → ε si le symbole suivant est $.
FAQ
1. Qu’est-ce qu’une variable effaçable dans une grammaire ?
Une variable effaçable est une variable qui peut produire la chaîne vide (ε) et qui n’est pas nécessaire pour l’analyse syntaxique. Elle est souvent utilisée pour simplifier les règles de grammaire.
2. Pourquoi la grammaire LL(1) est-elle importante en compilation ?
La grammaire LL(1) est importante car elle permet de construire des analyseurs syntaxiques prédictifs efficaces et simples, qui lisent l’entrée de gauche à droite et utilisent une pile pour stocker les symboles non terminaux.
3. Comment résoudre un conflit dans une table d’analyse LL(1) ?
Un conflit dans une table d’analyse LL(1) peut être résolu en modifiant la grammaire pour éliminer les ambiguïtés, en utilisant des variables supplémentaires ou en transformant les productions pour éviter la récursion à gauche.