USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
FICHE TD 2
ANALYSE SYNTAXIQUE DESCENDANTE
Exercice 1
Soit la grammaire G = ({a, b, := , +} , {S, E} , S , { S → b := E , E → +EE / a})
1) Donner l’analyseur par Procédures récursives et Analyser la chaîne b := +a+aa
2) Donner l’analyseur syntaxique LL(1) et Analyser la chaîne b := +a+aa
3) Pour chaque analyseur, Déduire l’arbre de dérivation (s’il existe) pour la chaîne analysée.
Exercice 2
Soient les grammaires suivantes :
G1= ({a,b}, {S,A}, S, {S→Aa, A→bA|ε})
G2= ({x,y,z}, {S,T}, S, { S→xTz, T→yT|ε})
G3= ({0,1}, {S,T,F}, S, {S→T0, T→1F|ε, F→0F|ε})
G4= ({e, f, g, h}, {S, T, U}, S, {S→ Te | hTf | Uf| hUe, T→ g, U→ g})
1) Quel est le langage généré par chaque grammaire
2) Calculer l’ensemble des débuts et suivants pour les grammaires G1, G2, G3 et G4.
3) a. Montrer si les grammaires G1, G2, G3, G4 sont LL(1) ou pas ?
b. Appliquer les transformations nécessaires pour les grammaires non LL(1).
c. Prouver que les grammaires obtenues sont LL(1).
Exercice 3
Soit la grammaire G= ({id, non, ou, et, (, )}, {A, B, C}, A, P) qui génère les expressions
logiques suivantes :
A → A ou B / B
B → B et C / C
C → non C/ (A) / id
1) Eliminer la récursivité à gauche et factoriser si nécessaire.
2) Donner la table d’analyse prédictive de la nouvelle grammaire. Est-elle LL(1) ?
3) Expliciter le comportement de l’analyseur sur le mot w= non (id ou id) et id
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
FICHE TD 2 (CORRIGE ET REMARQUES)
ANALYSE SYNTAXIQUE DESCENDANTE
Exercice 2
G1= ({a,b}, {S,A}, S, {S→Aa, A→bA|ε})
G2= ({x,y,z}, {S,T}, S, { S→xTz, T→yT|ε})
G3= ({0,1}, {S,T,F}, S, {S→T0, T→1F|ε, F→0F|ε})
G4= ({e, f, g, h}, {S, T, U}, S, {S→ Te | hTf | Uf| hUe, T→ g, U→ g})
1) débuts et suivants pour les grammaires G1, G2, G3 et G4.
G1 S A
début a,b a, ε
suivants $ a
G2 S T
début x y, ɛ
suivants $ z
G3 S T F
début 0, 1 1, ɛ 0, ɛ
suivants $ 0 0
G4 S T U
début g,h g g
suivants $ e, f e, f
G1= ({a,b},{S,A},S,{S→Aa, A→bA|ε})
Langage généré : L(G1) = {bna tq n≥0} voici des exemples. : a, ba, bba, ...
G1 est LL1car
Pour A on a: FIRST(bA) ∩ et FIRST(ε) = ∅ ; OK
FIRST(bA) ∩ FOLLOW(A) = ∅ OK
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
G2= ({x,y,z}, {S,T}, S, { S→xTz, T→yT|ε})
Langage généré : L(G2)= {xynzt q n≥0} (ex. : xz, xyz, xyyz, ...)
G2 est LL(1) (preuve avec les théorèmes)
Règle sur T: T→yT|ε i. Début (yT) Début(ɛ) = {y} {ɛ}= OK!
ii. Début (yT) Suivant(T)= {y} {z} = OK!
G3= ({0,1}, {S,T,F}, S, {S→T0, T→1F|ε, F→0F|ε})
Langage généré : L(G3) ={0}∪{10n tq : n≥1}. ou bien L(G3)= {1n0m tq : n={0,1} et m≥1}.
G3 n’est pas LL(1) (preuve avec les théorèmes)
Règles sur F: F→ 0F| ɛ i. Début(0F) Début(ɛ) = {0} {ɛ}= OK!
ii. Début(0F) Suivant(F)= {0} {0}={0}≠ non vérifié!
Transformation : définir une nouvelle grammaire
S→0|10H
H→0H|ε
Vérification :
Pour S → 0 | 1 0 H on a : Début(0) Début(1 0 H) = {0} {1}= OK!
Pour H → 0 H | ε on a : Début (0H) Début(ɛ) = {0} {ɛ }= OK!
Début (0H) Suivant(H)= {0} {$}= OK !
G4= ({e, f, g, h}, {S, T, U}, S, {S→ Te | hTf | Uf| hUe, T→ g, U→ g})
G4 génère un ensemble finis de mots. L(G4) ={"ge", "gf", "hge", "hgf"}.
G4 est non LL(1) car elle n’est pas factorisée
Ou bien si on s’intéresse à S on a : Début( (hTf) Début( (hUe)= {h} {h}= {h} ≠
Transformation :
Il faut factoriser sur f et h
S→ Te | hTf | Uf| hUe
T→ g
U→ g
On remplace T et U par G dans la règle de S : S→ ge | hgf | gf| hge
S→ gT| hgU
T→ e| f
U→ f| e
La nouvelle grammaire est
G4’= ({e, f, g, h}, {S, T, U}, S, {S→ gT| hgU, T→ e| f, U→ f| e})
G4’ est LL(1)
Règles sur S: S→ gT| hgU i. Début (gT) Début (hgU) = {g} {h}= OK!
Règles sur T: T→ e| f i. Début(e) Début(f) = {e} {f}= OK!
Règles sur U: U→ f| e i. Début(f) Début(e) = {f} {e}= OK!
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026
Exercice 3
A → A ou B / B
B → B et C / C
C → non C/ (A) / id
1) Eliminer la récursivité à gauche et factoriser si nécessaire.
A → B A’ (R1)
A’ → ou B A’ | 𝜺 (R2) (R3)
B → C B’ (R4)
B’ → et C B’ | 𝜺 (R5) (R6)
C → non C | (A) | id (R7) (R8) (R9)
Aucune factorisation n’est nécessaire
2) Donner la table d’analyse prédictive de la nouvelle grammaire. Est-elle LL(1) ?
A A’ B B’ C
Début non, (, id ou, 𝜺 non, (, id et, 𝜺 non, (, id
suivant ), $ ), $ ou, ), $ ou,), $ et, ou, ), $
Table d’analyse prédictive:
id non ou et ( ) $
A R1 R1 R1
A’ R2 R3 R3
B R4 R4 R4
B’ R6 R5 R6 R6
C R9 R7 R8
Comme la table d’analyse n’est pas multi définie donc la grammaire G est LL(1)
3) Expliciter le comportement de l’analyseur sur le mot w= non (id ou id) et id
USTO-Département d’informatique L3SI+ING3
COMPILATION 2025-2026