Université Ibn Tofaïl Année universitaire 2021-2022
Faculté des Sciences
Département d’Informatique
KENITRA
Compilation
SMI – Semestre 5
Série n° 3
Exercice 1 :
La grammaire Gphrase ci-dessous génère des phrases simples du français du type sujet-verbe-
complément.
R1 : P→ S v C
R2 : S→ GN
R3 : C→ GN |
R4: GN→ art n OGP | pron
R5: OGP→ prep GN |
Avec Vt= {v, art, n, pron, prep, }, Vn = {P, S, C, GN, OGP} et P : Axiome.
a) Soit le mot w = pron v art n prep art n. Donner pour w, une dérivation droite, une
dérivation gauche et un arbre syntaxique.
b) Calculer l’ensemble Premier pour chaque non-terminal de la grammaire Gphrase
c) On modifie la première règle (R1) qui est maintenant R1 : P→ S v C OGP. Montrer que la
nouvelle grammaire est ambiguë.
Exercice 2 :
On considère la grammaire G = (Vt , Vn , P , S) avec Vt= {a, +, *}, Vn = {S} et Axiome=S
P = {S → SS+ |SS*| a}.
a) Donner l'ensemble des mots de longueur 1 puis 2 puis 3 et 4
b) Soit le mot w = aa+a*. Donner pour w, une dérivation droite, une dérivation gauche et
un arbre syntaxique.
c) G est-elle ambiguë ? Justifier la réponse
d) Calculer l’ensemble Premier pour les non terminaux.
Exercice 3 :
On considère la grammaire G = (Vt , Vn , P , S) avec Vt= {a, +, *}, Vn = {S} et Axiome=S
P = {S → AaB, A→ CB|Bb|, B→b , C→ c|}.
a) Construire les ensembles PREMIER et SUIVANT pour cette grammaire.
1
b) Etablir la table d’analyse et montrer que cette grammaire n’est pas LL(1)
Exercice 4 :
On considère la grammaire G = (Vt , Vn , P , A) avec Vt= {a, b}, Vn = {A} et
P = {A → aAb |AA| bAa | ε }.
a) Tout mot commençant par a se termine-t-il par b ?
b) Donner l'ensemble des mots de longueur 1 puis 2 puis 3 et 4
c) Soit le mot w = aabbbaab. Donner pour w, une dérivation droite, une dérivation gauche
et un arbre syntaxique.
d) G est-elle ambiguë ? Justifier.
Exercice 5 :
Soit la grammaire G = (Vt , Vn , P , A) avec Vt= {ch, nb ,+ ,* ,++ ,** ,( ,) },
Vn = {A, B, E, F, T} et A : axiome
A A ++ B | A ** E | B
B (A) | ch
E E + T | T
T T * F |F
F (E)| nb
Vérifier si cette grammaire est LL(1) ? Sinon la rendre de type LL(1) ?
Exercice 6 :
Soit G la grammaire définie par :
E F+E | F-E | F
F -F|(E)| nb
({ +,-,(,),nb} est l’ensemble des terminaux de G. Le signe ‘-‘ est un opérateur unaire ou binaire.
1. G est-elle LL(1) ? Justifier
2. Factoriser à gauche, par F, l’ensemble des règles E F+E | F-E | F. Ecrire la grammaire
G’, équivalente à G, obtenue par factorisation.
3. Calculer les ensembles Premiers et Suivants. Construire la table d’analyse pour la
grammaire G’.
4. Donner l’algorithme d’analyse prédctive. Faites dérouler l’analyseur sur la phrase –nb+nb,
enfaisant apparaître à chaque étape, le contenu de la pile, ce qui reste à lire de la phrase et
la règle à appliquer.