TD Analyse syntaxique
Exercice 2
Soit la grammaire
S → AaB
A → CB | Bb | ϵ
B→b
C→c| ϵ
1 – Construire l’ensemble des PREMIER et SUIVANT pour cette grammaire.
2 – Établir la table d’analyse et montrer que cette grammaire n’est pas LL(1).
Correction
1 – PREMIER(S) = {a,b,c}
PREMIER(A) = {c,b, ϵ}
PREMIER(B) = {b}
PREMIER(C) = {c, ϵ}
SUIVANT(S) = {$}
SUIVANT(A) = {a}
SUIVANT(B) = {b,$,a}
SUIVANT(C) = {b}
2 – Table d’analyse
a b c $
S S → AaB S → AaB S → AaB
A A→ϵ A → CB A → CB
A → Bb
B B→b
C C→ϵ C→c
Cette grammaire n'est pas LL(1) puisque la table d'analyse possède une cellule contenant plus d'une
règle.
Exercice 3 :
Soit la grammaire G définie par les règles :
S→0S|0S1S|ε
En construisant deux arbres distincts pour le mot w= 001, montrer que G est ambigue
Correction :
G est ambigue, car le mot w= 001 admet deux arbres de dérivation distincts :
Arbre 1
0 S
0 S 1 S
ϵ ϵ
Arbre 2
0 S 1 S
0 S
ϵ ϵ
Exercice 4 :
Soit la grammaire G
E→E+T|T
T→T∗F|F
F→(E)|a
Transformer G en grammaire non récursive.
Correction :
On appliquant la règle :
Remplacer toute règle de la forme A → Aα| β par
A → βA’
A’ → αA’| ϵ
On aura une nouvelle grammaire équivalente a G mais non récursive :
E−→T E′
E′−→+T E′|ε
T−→F T′
T′−→∗F T′|ε
F−→(E)|a
Exercice 5 :
S→ SaAb| bBaS| ε
A→bAa| ε
B→aBb| ε
1. Cette grammaire est une grammaire hors contexte puisque elle est de la forme
A →β avec A ∈ N et β ∈ (N ∪ T)*
2. On remarque 3 ε productions dans cette grammaire. On va procéder à supprimer ces trois cas.
Cas 1 :
S → ε Donne :
S →SaAb| bBaS|aAb|bBa
Cas 2 :
A→ε Donne :
S →SaAb| bBaS|aAb|bBa[Sab|ab
A→bAa| ba
Cas 3 :
B→ε Donne :
S →SaAb| bBaS|aAb|bBa|baS|ba
B→aBb| ab
Donc la nouvelle grammaire sans les ε productions :
S →SaAb| bBaS|aAb|bBa|baS|ba
A→bAa| ba
B→aBb| ab
