Université Aix Marseille - L3 Informatique Compilation TD3-4
ANALYSEUR SYNTAXIQUE LL(1)
1. Toy grammars
Considérons les trois grammaires suivantes qui sont simplement là pour l’entraı̂nement à manipuler
les algorithmes de suppression de la récursivité à gauche, de factorisation, de calcul des ensembles
PREMIER et SUIVANT, et de construction de tables d’analyse.
E → +ET|T
S → Ta|SaSb A → Bac|Bb
G1 : G2 : G3 : T → *TF|F
T → Sb|Tb|b B → Ad|Bc|ε
F → a
Exercice 1. Récursivité gauche et factorisation
(1) Rendre ces trois grammaires non récursives à gauche et factorisées, si elles ne le sont pas
déjà. Vous obtiendrez ainsi les grammaires G01 , G02 et G03 .
Exercice 2. Ensembles PREMIER
Idée générale de l’algorithme de calcul des ensembles PREMIER :
— Étapes d’initialisation :
— Si A → ε, ajouter ε à PREMIER(A)
— Si A → a α, ajouter a à PREMIER(A)
— Étape récurrente jusqu’à ce que rien ne soit ajouté :
— Si A → α1 . . . αn :
ajouter PREMIER(α1 ) à PREMIER(A)
de plus, si ε ∈ PREMIER(α1 ), ajouter PREMIER(α2 ) à PREMIER(A). . .et ainsi de
suite.
(1) Calculer les ensembles PREMIER pour chacune des grammaires G01 et G02 .
Exercice 3. Ensembles SUIVANT
Idée générale de l’algorithme de calcul des ensembles SUIVANT :
— Étape d’initialisation :
— Mettre ⊥ dans l’ensemble SUIVANT de l’axiome.
— Si A → α B β, ajouter PREMIER(β)\{ε} à SUIVANT(B ) .
— Étape récurrente jusqu’à ce que rien ne soit ajouté :
— Si A → α B ou A → α B β, avec ε ∈ PREMIER(β), ajouter SUIVANT(A) à
SUIVANT(B).
(1) Calculer les ensembles SUIVANT pour chacune des grammaires G01 et G02 .
Exercice 4. Tables d’analyse LL(1)
Idée générale de l’algorithme de construction de la table d’analyse LL(1) : Pour chaque Ri ∈ P
de la forme A → α :
— Pour chaque terminal a ∈ PREMIER (α), ajouter Ri à la cellule de ligne A et de colonne
a, notée T (A, a).
— Si ε ∈ PREMIER(α), ajouter Ri à T (A, b) pour chaque terminal b ∈ SUIVANT(A). Aussi,
si ε ∈ PREMIER(α) et que ⊥ ∈ SUIVANT(A), ajouter Ri à T (A, ⊥).
Indiquer un cas d’erreur pour toutes les cellules de T restées vides.
(1) Construire la table d’analyse LL(1) de G01 et G02 . Ces deux grammaires sont-elles LL(1) ?
1
2 ANALYSEUR SYNTAXIQUE LL(1)
2. La grammaire du langage L
Exercice 5. Analyse LL(1)
On considère la grammaire du langage L suivante, où PG est l’axiome :
(1) PG → ODV LDF (35) IVIDE → ;
(2) ODV → LDV ; (36) EXP → CONJ OOUEXP
(3) ODV → ε
(37) OOUEXP → | EXP
(4) LDV → DV LDVB (38) OOUEXP → ε
(5) LDVB → , DV LDVB (39) CONJ → NEG OETCONJ
(6) LDVB → ε
(40) OETCONJ → & CONJ
(7) DV → int idv OTT (41) OETCONJ → ε
(8) OTT → [ nb ] (42) NEG → ! COMP
(9) OTT → ε (43) NEG → COMP
(10) LDF → DF LDF (44) COMP → E COMPB
(11) LDF → ε
(45) COMPB → = E COMPB
(12) DF → idf LP ODV IB (46) COMPB → < E COMPB
(13) LP → ( OLDV ) (47) COMPB → ε
(14) OLDV → LDV (48) E → T EB
(15) OLDV → ε (49) EB → + T EB
(16) I → IAFF (50) EB → - T EB
(17) I → IB (51) EB → ε
(18) I → ISI (52) T → F TB
(19) I → ITQ
(20) I → IAPP (53) TB → * F TB
(21) I → IRET (54) TB → / F TB
(22) I → IECR (55) TB → ε
(23) I → IVIDE (56) F → ( EXP )
(24) IAFF → VAR = EXP ; (57) F → nb
(58) F → APPF
(25) IB → { LI } (59) F → VAR
(26) LI → I LI (60) F → lire ( )
(27) LI → ε (61) VAR → idv OIND
(28) ISI → si EXP alr IB OSINON (62) OIND → [ EXP ]
(29) OSINON → sin IB (63) OIND → ε
(30) OSINON → ε (64) APPF → idf ( LEXP )
(31) ITQ → tq EXP fr IB (65) LEXP → EXP LEXPB
(32) IAPP → APPF ; (66) LEXP → ε
(33) IRET → ret EXP ; (67) LEXPB → , EXP LEXPB
(34) IECR → ecr ( EXP ) ; (68) LEXPB → ε
(1) Montrer que la grammaire donnée est LL(1).
