Institut Supérieur d’Informatique Filière : LFI 2
et de Mathématiques de Monastir
Département d'Informatique
TD 3 : Analyse Syntaxique, Grammaires
Enseignante : Wided BEN ABID Groupe : TD
EXERCICE 1
Soit la grammaire suivante G décrivant de façon très simplifiée un document HTML :
DOC -> H B
H -> <head> TXT </head>
B -> <body> TXT </body>
TXT -> CAR | CAR TXT
CAR -> ε|l’ensemble des lettres et des chiffres, l’espace.
Rappel : ε désigne le mot vide.
Remarque : les éléments non terminaux sont en majuscules.
Remarque : un élément entre < et > est appelé balise de début et un élément entre </
et > est appelé balise de fin.
1. Donner explicitement le quadruplet <VT, VN, S, P> de G.
2. Donner deux mots quelconques appartenant au langage engendré par G.
3. Donner l’arbre de dérivation du document :
<head></head><body>Examen</body>
4. Proposer une grammaire propre G1.
5. Proposer une modification de G (notée G2) pour prendre en compte le fait que le
texte compris entre les balises <body> et </body> puisse ou non contenir des couples
de balises <A> </A> entre lesquelles on peut également trouver du texte.
Exemples …<body> examen</body>
…<body> <A> examen </A></body>
…<body> <A> examen </A> TLC</body>
…<body> <A> examen </A> TLC <A> examen </A> TLC </body>
6. Utiliser la grammaire G2 pour donner un arbre de dérivation pour le mot :
<head></head><body> voici <A> ma </A> page en <A> html </A> </body>
CORRECTION EXERCICE 1:
DOC -> H B (P1)
H -> <head> TXT </head> (P2)
B -> <body> TXT </body> (P3)
TXT -> CAR | CAR TXT (P4)
CAR -> ε|l’ensemble des lettres et des chiffres, l’espace. (P5)
1) VT= {<head>,</head>,<body>,</body>, l’ensemble des lettres et des
chiffres, l’espace}
VN= {DOC, H, B, TXT, CAR}
S= DOC
P: c’est l’ensemble de tous les règles de production (P5),(P4),(P3),(P2),(P1)
2) Exemple de 2 mots appartenant au langage engender par G:
<head></head><body></body>, <head> wided </head><body></body>
3)
DOC
H B
<head> TXT </head> <body> TXT </body>
CAR CAR
ε
Examen
4) Une grammaire est dite propre si elle ne contient aucune production de type
A→ ε. Si on a A→ ε, il faut remplacer les A se trouvant dans la partie droite
de toutes règles de production par ε.
Dans cette exemple on a CAR→ ε donc La grammaire G devient :
DOC -> H B (P1)
H -> <head> TXT </head> | <head></head> (P2)
B -> <body> TXT </body> | <body></body> (P3)
TXT -> CAR | CAR TXT (P4)
CAR -> l’ensemble des lettres et des chiffres, l’espace. (P5)
5)
DOC -> H B (P1)
H -> <head> TXT </head> (P2)
B -> <body> TXT </body> (P3)
TXT -> CAR | CAR TXT| <A> TXT </A> TXT (P4)
CAR -> ε |l’ensemble des lettres et des chiffres, l’espace. (P5)
6)
EXERCICE 2
Soit la grammaire G dont les règles de production sont les suivantes :
E : axiome
1. Donner explicitement le quadruplet <VT, VN, S, P> de G.
2. De quel type est cette grammaire ? Justifier.
3. Soit les deux mot w=10*5*2*(11+4) w’=5*(10+6)+20
Donner un arbre de dérivation pour ces deux mots, conclure.
CORRECTION EXERCICE 2:
P1
P2
P3
P4
P5
1) VT= {+, *, (,), nb}
VN= {E, E’, T, T’, F}
S= E
P= {P1, P2, P3, P4, P5}
2) Cette grammaire est de type 2 car les règles de production sont sous la forme
de A→B avec AЄ VN et BЄ(VNUVT)*
3) E→TE’→FT’E’→nbT’E’→nb*FT’E’→nb*nbT’E’→nb*nb*FT’E’→
nb*nb*nbT’E’→nb*nb*nb*FT’E’→nb*nb*nb*(E)T’E’→
nb*nb*nb*(TE’)T’E’→nb*nb*nb*(FT’E’)T’E’→
nb*nb*nb*(nbT’E’)T’E’→nb*nb*nb*(nbE’)T’E’→
nb*nb*nb*(nb+TE’)T’E’→nb*nb*nb*(nb+FT’E’)T’E’→
nb*nb*nb*(nb+nbT’E’)T’E’→nb*nb*nb*(nb+nbE’)T’E’→
nb*nb*nb*(nb+nb)T’E’→nb*nb*nb*(nb+nb)E’→ nb*nb*nb*(nb+nb)
D’où le résultat 10*5*2*(11+4)
Arbre de dérivation de mot 10*5*2*(11+4)
T E’
F T’ ε
nb * F T’
nb * F T’
nb * F T’
( E ) ε
T E’
F T’ + T E’
nb ε F T’ ε
nb ε
Arbre de dérivation de mot 5*(10+6)+20
T E’
F T’
nb * F T’ + T E’
( E ) ε F T’ ε
nb ε
T E’
F T’ + T E’
nb ε F T’ ε
nb ε
EXERCICE 3
Soit la grammaire G dont les règles de production sont les suivantes :
S -> L B (P1)
B -> :S | :=L (P2)
E -> a | L (P3)
J -> ,EJ|) (P4)
L -> (EJ (P5)
S: axiome
1. Donner explicitement le quadruplet <VT, VN, S, P> de G.
2. De quel type est cette grammaire ? Justifier.
3. Donner un arbre de dérivation pour le mot (a) ::=(a)
4. Calculer l’ensemble Premiers
5. Calculer l’ensemble Suivants
6. Construire la table d’analyse LL de G
CORRECTION EXERCICE 3
1) VT= {‘ :’ , ‘=’, ‘(’, ‘)’, ‘a’, ‘,’, }
VN= {S, L, B, E, J}
S= S
P= {P1, P2, P3, P4, P5}
2) Cette grammaire est de type 2.
3) Le mot (a) ::=(a) n’appartient pas à la grammaire G.
4) PREMIER(S) = PREMIER(L) = { ( }
PREMIER(B) = { : }
PREMIER(E) ={ a ∪ PREMIER(L)} = { a, ( }
PREMIER(J) = {‘ ,’ , ‘)’}
5) SUIVANT(S) = {$ ∪ SUIVANT(B) }= {$}
SUIVANT(B) = { SUIVANT(S)}= {$}
SUIVANT(E) = PREMIER(J) = {‘,’ , ‘)’}
SUIVANT(L) =PREMIER(B) ∪ SUIVANT(B) ∪ SUIVANT(E)= { :, $, ‘,’, )}
SUIVANT(J) = {‘ ,’ , ‘)’}
6)
: = a , ( ) $
S S→LB
B → :S
B
B→ :=L
E E→a E→L
J J→,EJ J→)
L L→(EJ)
PILE Entrée Sortie
$S (a) ::=(a)$ S→LB
$ BL (a) ::=(a)$ L→(EJ
$BJE( (a) ::=(a)$
$ BJE a) ::=(a)$ E→a
$ BJa a) ::=(a)$
$ BJ ) ::=(a)$ J→) Le mot (a) ::=(a) n’appartient
$B) ) ::=(a)$ pas au langage généré par cette
grammaire G.
$B ::=(a)$ B→ :S Remarque : On utilise cette
reconnaissance sauf dans le cas
$ S: ::=(a)$
où la grammaire est de type
$S :=(a)$ S→LB LL(1).
$ BL :=(a)$ L→ (EJ
$ BJE( :=(a)$ ERREUR !!
EXERCICE 4
Soit la grammaire G suivante :
S -> SaTS |b
T -> bST|a|b|
S: axiome
1. Donner 4 mots générés par cette grammaire.
2. Construire la table d’analyse LL de G.
3. La grammaire G est elle LL(1) ? Justifier.
CORRECTION EXERCICE 4
S -> SaTS |b
T -> bST|a|b|
2) PREMIER(S) ={b}
PREMIER(T) = {a,b, }
SUIVANT(S) = {$, a ∪ PREMIER(T)\{ } }= {$,a,b}
SUIVANT(T) = { PREMIER(S)}= {b}
a b $
S→b
S
S→SaTS
T→b
T T→a T→bST
T→
3) Il y a plus qu’une réduction dans divers cases de la table d’analyse, donc ce n'est
pas une grammaire LL(1).
