Analyse LL
Licence info S5
TD COMPIL – 2012-2013
Exercice 1 : Listes à la Lisp
On s’intéresse à la grammaire suivante G d’axiome L, de terminaux {a, (, )}, décrivant des listes à
la Lisp (L signifie liste et S signifie suite d’éléments ) :
L→(S) | a
S→LS |
On donne pour cette grammaire la table d’analyse suivante :
( a ) #
L L→(S) L→a erreur erreur
S S→LS S→LS S→ erreur
Soit m le mot (a()).
Q 1.1 : Donner la suite des piles résultant de l’analyse de m par l’automate LL(1) associé à G. Construire
en même temps l’arbre syntaxique et la dérivation gauche pour m. 2
Q 1. 2 : En suivant les conventions du cours, donner les méthodes (signature et corps) de l’analyseur
récursif descendant qui reconnaissent respectivement les non-terminaux L et S. 2
Exercice 2 : Itinéraire et analyse syntaxique descendante
On s’intéresse à une grammaire GI des instructions (très simplifiées) délivrées par un logiciel de calcul
d’itinéraire, du style avancer 100m, au panneau Lille tourner à gauche, avancer 20m, tourner à droite .
On utilise pour ce faire les symboles GO (avancer Xm), TL (turn left), TR (turn right) et PAN (panneau).
On a GI = {VT , VN , route, P } avec VT = { GO, TL, TR, PAN }, VN = { route, inst, panneau, turn } et
P contient les productions :
route → inst | inst route
inst → GO | panneau turn
turn → TL | TR
panneau → | PAN
Q 2.1 : Cette grammaire n’est pas LL(1) : pourquoi ? 2
Q 2.2 : Donner une grammaire G0I équivalente à GI et qui vous semble LL(1). 2
Q 2.3 : Calculer les ensembles Premier et Suivant pour G0I . 2
Q 2. 4 : Donner la table d’analyse LL(1) de G0I . Justifier en utilisant cette table que G0I est une
grammaire LL(1). 2
Q 2. 5 : En suivant les conventions du cours, donner les méthodes (signature et corps) de l’analyseur
récursif descendant qui reconnaissent respectivement le non-terminal panneau et le non-terminal inst. 2
Q 2. 6 : G0I est-elle une grammaire ambiguë ? Le langage L(G0I ) est-il algébrique ? régulier ? Justifier
vos réponses. 2
Exercice 3 : Pour bien comprendre les calculs de Premier et Suivant
Soit la grammaire suivante (légèrement alambiquée) d’axiome S et de terminaux {a, b, e, d, f} :
TD COMPIL Analyse LL
S → ABC | DAD
A → aA |
B → bB |
C → eC |
D → dD | f
Q 3.1 : Construire la table d’analyse de cette grammaire et montrer qu’elle est LL(1). 2
Q 3.2 : Que se passe-t-il si :
1. on remplace C → par C → e ?
2. on remplace B → par B → a ?
3. si on ajoute B → a ?
4. on remplace D → par D → d ?
2
Exercice 4 : Forme eBNF, grammaire LL(*)
On reprend la grammaire GI de l’exercice 2.
Q 4.1 : Donner une grammaire G00I , sous forme eBNF, équivalente à GI . 2
Q 4.2 : La grammaire G00I vous semble-t-elle LL(*) ? 2
Exercice 5 : Forme eBNF et grammaires LL(*) à opérateurs
Q 5.1 : On considère la grammaire suivante, que vous connaissez par coeur :
E → E+E | E−E | E∗E | E/E | id | (E)
Donner une grammaire équivalente sous forme eBNF, LL(*), en considérant les associativités et priorités
des opérateurs standard. 2
Q 5.2 : On considère la grammaire de terminaux {a, +, * }, d’axiome E et de productions :
E → E+C | C C → CS | S
S → S∗ | X X→a
Quel est le langage engendré par cette grammaire ? Donner une grammaire équivalente sous forme eBNF,
qui est LL(*). 2
Q 5.3 : On considère la grammaire de requètes suivante :
req → req join req | req union req | select cond ( req ) | id
Donner une grammaire équivalente sous forme eBNF, LL(*), en sachant que l’opérateur de jointure est
prioritaire sur celui d’union, que l’opérateur d’union est associatif à gauche, et celui de jointure l’est à
droite. 2
