Université Ferhat Abbas Setif1 Compilation L3A/Ing3A
Faculté des Sciences
Département d’informatique
TD 03 (03 semaine)
Exercice 01 :
Soit les grammaires suivantes :
G1: S → AB A → Aa | bB B → a | Sb
G2: A → a B B→bC C→aC|bC|ɛ
Donnez les dérivations gauche et droite ainsi que l'arbre de dérivation pour les mots :
1. b a a b a a b babaab bababaabb pour G1
2. a b b b a a b pour G2
Exercice 02 :
Appliquer l’algorithme de factorisation sur les grammaires suivantes :
1. S→a E b S | a E b S e B | a E→b c B | b c a B→b a
2. S→A B C D S→A B a D S→A b a
Exercice 03 :
Eliminer les récursivités à gauche des grammaires suivantes (utiliser l’algorithme) :
1. S→S c A | B A→A a | ε B→B b | d |e
2. S→A a | b A→A c | S d | ε
3. S → S a | T S c | d T→TbT|ε
Exercice 04 :
Soit les grammaires :
G1: S → i E t S S’ | a S’ → e S | ε E → b
G2: S → i B t S | i B t S e S | inst B → cond
G3: S → a X a a | b X b a X→bX|ε
1. Calculer les premiers et les suivants des non-terminaux de ces grammaires.
2. Construire leurs tables d’analyse.
3. Déduire à partir de la table d’analyse que les grammaires sont LL(1) ou pas. Justifier votre réponse.
Exercice 05 :
Soit les grammaires suivantes :
G1: S → a | b | ( T ) T→T,S|S chaine: ( a , ( b , a ) , a )
G2: D →id L L → , id | : T T → integer ; | real ; chaine: id , id , id : real ;
G3: E → E ou T | T T → T et F | F F → non F | ( E ) | vrai | faux chaine: vrai et (
faux ou vrai )
1- Supprimer la récursivité gauche et factoriser si nécessaire.
2- Calculer les ensembles PREMIER et SUIVANT des non-terminaux.
3- Donner la table d’analyse LL(1) pour la nouvelle grammaire.
4- Donner la trace d’analyse.
