GIS
3ème année
Jeudi 3 Mars 2016
Devoir surveillé de Langages et Traducteurs (Correction)
Tout document papier autorisé
(la calculatrice fournie par Polytech Lille est acceptée)
Durée : 2 heures
Exercice 1 (3 points)
Question 1 Construisez un automate qui reconnaı̂t le langage dénoté par l’expression régulière aabb(a|b)∗ (bb|aa)∗
construite sur l’alphabet {a,b}.
SOLUTION
a,b b
q6
b
a a b b epsilon
q0 q1 q2 q3 q4 q5
a
a q7
• Code couleur du graphe :
− En bleu, les transitions correspondant à l’expression régulière aabb
− En rouge, les transitions correspondant à l’expression régulière (a|b)∗
− En vert, les transitions correspondant à l’expression régulière (bb|aa)∗
• Attention, si les états q4 et q5 sont confondus, le langage reconnu par l’automate est
aabb(a|b|bb|aa)∗
Question 2 Construisez une grammaire pour le langage L = {w ∈ {a,b,c}∗ | ∃m, n ∈ N2 tq w = an bn cm am }.
SOLUTION
S → XY
X → aXb | ε
Y → cY a | ε
Question 3 Déterminez sous forme d’expression régulière le langage engendré par la grammaire G = < V, T, P, S >
avec V = {S, X, Y }, T = {0, 1}, et P l’ensemble des productions suivantes :
S → XY
X → 0X | ε
Y → 10X | ε
SOLUTION : L(G) = 0∗ (ε | 100∗ ) = 0∗ | 0∗ 100∗
1/8
Exercice 2 (5 points)
Soit l’automate A = ({1, 2, 3, 4, 5, 6, 7}, {a, b}, δ, 1, {2, 6, 7}) défini par la table de transitions δ suivante :
a b
1 {2} ∅
2 {5} {3, 4}
3 ∅ {2}
4 {3, 4} ∅
5 {6, 7} ∅
6 {6} ∅
7 ∅ {7}
Question 1 Dessinez le graphe de l’automate A.
SOLUTION
b 3
a
1 2 a
a
b a
a
4
6
a
5
a b
Question 2 Montrez que les mots abaaab et abb sont reconnus par l’automate A.
SOLUTION : Faire un chemin sans justification ne suffit pas. Il faut donner une justification.
a b a a a b
Mot abaaab : 1 2 4 4 4 3 2
1 est l’étal initial de l’automate A et 2 un étal final de cet automate. Il existe donc
un chemin étiqueté par abaaab partant de l’état initial et aboutissant dans un état
final de A donc abaaab est reconnu par A.
a b b
Mot abb : 1 2 3 2
1 est l’étal initial de l’automate A et 2 un étal final de cet automate. Il existe donc
un chemin étiqueté par abb partant de l’état initial et aboutissant dans un état final
de A donc abb est reconnu par A.
2/8
Question 3 Construisez et dessinez, en utilisant la méthode vue en cours, un automate déterministe A0 équivalent à
l’automate A.
SOLUTION
Table de transitions de l’automate A0 :
a b
{1} {2} −
{2} {5} {3, 4}
{5} {6, 7} −
{3, 4} {3, 4} {2}
{6, 7} {6} {7}
{6} {6} −
{7} − {7}
Graphe de l’automate A0 :
{6}
a
b
a
{5} {6,7}
b
a
{7}
a
a
{1} {2}
b
b
{3,4}
Question 4 Exprimez le langage L(A) sous la forme d’une expression régulière.
SOLUTION : L(A) = a(ba∗ b)∗ | a(ba∗ b)∗ aa(a∗| b∗ ) = a(ba∗ b)∗ ε | aa(a∗| b∗ )
Exercice 3 (4 points)
La grammaire définie ci-dessous n’est pas LL(1). indiquez le plus précisèment possible pourquoi elle n’est pas LL(1)
et utilisez le cours et les TD pour transformer cette grammaire en une grammaire LL(1).
Soit la grammaire G = < {S, X} , {a, b} , P , S > avec P l’ensemble des productions suivantes :
S → SaXS | b
X → bbbSX | bbb | a | ε
SOLUTION :
La grammaire G n’est pas LL(1) pour 2 raisons :
− Elle est récursive gauche : S → SaXS
− Elle est non factorisée à gauche : X → bbbSX et X → bbb
3/8
En appliquant le cours, nous obtenons la grammaire suivante :
S → bS 0
S0 → aXSS 0 | ε
X → bbbX 0 | a | ε
X0 → SX | ε
Exercice 4 (3 points)
Soit la grammaire G = < V, T, P, A > avec V = {A, A0 , B, B 0 , C}, T = {ou, et, non, vrai, faux, (, )}, et P l’ensemble
des productions suivantes :
A → B A0
A0 → ou B A0 | ε
B → C B0
B0 → et C B 0 | ε
C → non C | (A) | vrai | faux
Question 1 Montrez que le mot non(vrai et vrai et faux) est une phrase de la grammaire G.
SOLUTION : Faire une dérivation ou un arbre d’analyse ne suffit pas. Il faut donner une justification.
B A0
C B0 ε
non C ε
( A )
B A0
C B0 ε
vrai et C B0
vrai et C B0
faux ε
non(vrai et vrai et faux) est un mot constitué uniquement de terminaux et ce mot est la frontière
d’un arbre d’analyse donc non(vrai et vrai et faux) est une phrase de la grammaire G.
4/8
Question 2 La grammaire G est forte LL(1) et sa table d’analyse est la suivante :
$ ou et non vrai faux ( )
A A → B A0 A → B A0 A → B A0 A → B A0
A0 A0 → ε A0 → ou B A0 A0 → ε
B B → C B0 B → C B0 B → C B0 B → C B0
B0 B0 → ε B0 → ε B 0 → et C B 0 B0 → ε
C C → non C C → vrai C → faux C → (A)
Q 2.1 : Appliquez l’algorithme d’analyse prédictive pour décider si le mot non(vrai) est une phrase de G.
SOLUTION : La réponse est constituée du tableau de l’algorithme et de la conclusion sur le fait que le
mot est une phrase ou non.
Reconnu Entrée Pile Actions
non(vrai) $ A$ Sortir A → B A0
non(vrai) $ B A0 $ Sortir B → C B 0
non(vrai) $ C B 0 A0 $ Sortir C → non C
0 0
non(vrai) $ non C B A $ Reconnaı̂tre( non )
0 0
non (vrai) $ CB A $ C → (A)
non (vrai) $ (A ) B 0 A0 $ Reconnaı̂tre( ( )
0 0
non( vrai) $ A)B A $ A → B A0
non( vrai) $ B A0 ) B 0 A0 $ B → C B0
non( vrai) $ C B 0 A0 ) B 0 A0 $ C → vrai
0 0 0 0
non( vrai) $ vrai B A ) B A $ Reconnaı̂tre( vrai )
0 0 0 0
non(vrai )$ B A )B A $ B0 → ε
non(vrai )$ A0 ) B 0 A0 $ A0 → ε
non(vrai )$ ) B 0 A0 $ Reconnaı̂tre( ) )
0 0
non(vrai) $ B A $ B0 → ε
non(vrai) $ A0 $ A0 → ε
non(vrai) $ $ Succès car Pile et Entrée vides
non(vrai) est une phrase de la grammaire G
Q 2.2 : Appliquez l’algorithme d’analyse prédictive pour décider si le mot vrai et ou est une phrase de G.
SOLUTION :
Reconnu Entrée Pile Actions
0
vrai et ou $ A$ Sortir A → B A
0
vrai et ou $ BA $ Sortir B → C B 0
vrai et ou $ C B 0 A0 $ Sortir C → vrai
0 0
vrai et ou $ vrai B A $ Reconnaı̂tre( vrai )
0 0
vrai et ou $ B A $ B 0 → et C B 0
vrai et ou $ et C B 0 A0 $ Reconnaı̂tre( et )
0 0
vrai et ou $ CB A $ Erreur car pas de sortie pour M (C, ou)
vrai et ou n’est pas une phrase de la grammaire G
5/8
Exercice 5 (5 points)
Soit la grammaire G = < V, T, P, Entier > avec V = {Entier, Signe, Liste, Chiffre}, T = {+, −, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
et P l’ensemble des productions suivantes :
Entier → Signe Liste
Signe → +|−
Liste → Liste Chiffre | Chiffre
Chiffre → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Cette grammaire reconnaı̂t tous les entiers signés : +12, −3453, +3, . . .
Soit la définition dirigée par la syntaxe suivante :
Productions Règles sémantiques
Entier → Signe Liste Liste.p = 0
Si (Signe.neg) Alors Entier.val = −Liste.val
Sinon Entier.val = Liste.val
FSi
Signe → + Signe.neg = FAUX
Signe → − Signe.neg = VRAI
Liste → Liste1 Chiffre Liste1 .p = Liste.p + 1
Chiffre.p = Liste.p
Liste.val = Liste1 .val + Chiffre.val
Liste → Chiffre Chiffre.p = Liste.p
Liste.val = Chiffre.val
Chiffre → 0 Chiffre.val = 0
Chiffre → 1 Chiffre.val = 10Chiffre.p
Chiffre → 2 Chiffre.val = 2 × 10Chiffre.p
Chiffre → 3 Chiffre.val = 3 × 10Chiffre.p
Chiffre → 4 Chiffre.val = 4 × 10Chiffre.p
Chiffre → 5 Chiffre.val = 5 × 10Chiffre.p
Chiffre → 6 Chiffre.val = 6 × 10Chiffre.p
Chiffre → 7 Chiffre.val = 7 × 10Chiffre.p
Chiffre → 8 Chiffre.val = 8 × 10Chiffre.p
Chiffre → 9 Chiffre.val = 9 × 10Chiffre.p
6/8
Question 1 Construisez l’arbre d’analyse décoré pour l’entier suivant : −8106
SOLUTION :
Entier val = −8106
Signe neg = FAUX p=0
Liste val = 8106
p=0
p=1
Liste val = 8100 Chiffre nbaM = 3
p=1
p=2
Liste val = 8100 Chiffre val = 0
6
p=2
p=3 val = 102
Liste val = 8000 Chiffre 0
p=3 val = 8 × 103
Chiffre 1
Question 2 Définissez complètement les attributs p, val et neg utilisés dans la définition dirigée par la syntaxe : attribut
synthétisé ou hérité, type de valeur (entier, réel, caractère, booléen, . . .), symbole(s) de la grammaire associé(s) et rôle.
SOLUTION :
• Attribut p :
− Attribut : Hérité
− Type : Entier
− Symboles associés : Non-terminaux Liste et Chiffre
− Rôle : Position de chaque chiffre constituant l’entier reconnu permettant le calcul de sa
valeur décimale
• Attribut neg :
− Attribut : Synthétisé
− Type : Booléen
− Symbole associé : Non-terminal Signe
− Rôle : VRAI si et seulement l’entier reconnu est négatif
• Attribut val :
− Attribut : Synthétisé
− Type : Entier
− Symboles associés : Non-terminaux Chiffre, Liste et Chiffre
− Rôle : Valeur décimale de l’entier reconnu
7/8
Question 3 Transformez la définition dirigée par la syntaxe en schéma de traduction dirigé par la syntaxe.
SOLUTION :
Entier → Signe { Liste.p = 0 ; } Liste { Si (Signe.neg) Alors Entier.val = −Liste.val
Sinon Entier.val = Liste.val
FSi }
Signe → + { Signe.neg = FAUX ; }
Signe → − { Signe.neg = VRAI ; }
Liste → { Liste1 .p = Liste.p + 1 ; } Liste1
{ Chiffre.p = Liste.p ; } Chiffre { Liste.val = Liste1 .val + Chiffre.val ; }
Liste → { Chiffre.p = Liste.p ; } Chiffre { Liste.val = Chiffre.val ; }
Chiffre → 0 { Chiffre.val = 0 ; }
Chiffre → 1 { Chiffre.val = 10Chiffre.p ; }
Chiffre → 2 { Chiffre.val = 2 × 10Chiffre.p ; }
Chiffre → 3 { Chiffre.val = 3 × 10Chiffre.p ; }
Chiffre → 4 { Chiffre.val = 4 × 10Chiffre.p ; }
Chiffre → 5 { Chiffre.val = 5 × 10Chiffre.p ; }
Chiffre → 6 { Chiffre.val = 6 × 10Chiffre.p ; }
Chiffre → 7 { Chiffre.val = 7 × 10Chiffre.p ; }
Chiffre → 8 { Chiffre.val = 8 × 10Chiffre.p ; }
Chiffre → 9 { Chiffre.val = 9 × 10Chiffre.p ; }
Remarques :
− Une action calculant la valeur d’un attribut hérité d’un non-terminal doit se trouver avant
ce non-terminal
− Une action calculant la valeur d’un attribut synthétisé d’un non-terminal doit se trouver
après ce non-terminal
8/8
