GIS3 - GIS2A3
Langages et Traducteurs
c Olivier Caron, Franck Seynhaeve
TD n◦ 3 - Traduction Dirigée par la Syntaxe
Exercice 1. Expressions parenthésées
Soit la grammaire G = {V, T, P, L} avec V = {L, S}, T = {a, (, )} et P l’ensemble des productions
suivant :
L → (S) | a
S → LS | ε
Q 1. Soit la définition dirigée par la syntaxe suivante :
Productions Règles sémantiques
L → (S) [Link] = [Link]
L → a [Link] = 1
S → L S1 [Link] = [Link] + S1 .nb
S → ε [Link] = 0
Q 1.1. Définissez complètement l’attribut nb utilisé dans cette DDS : 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.
Q 1.2. Construisez un arbre d’analyse décoré pour la phrase ((a)a).
Q 2. L’expression (((a))(a)) dont l’arbre d’analyse est représenté ci-dessous contient 2 atomes et est de
profondeur 3.
L
( S )
L S
( S ) L S
L S ( S ) ε
( S ) ε L S
L S a ε
a ε
Q 2.1. Complétez la DDS ci-dessus pour calculer la profondeur d’une expression parenthésée.
Q 2.2. Quel type d’attribut avez-vous utilisé ? Quel est le type de la DDS construite ? La DDS est-elle
évaluable par un parcours postfixe ?
1
Exercice 2. Expressions arithmétiques à la LISP
Soit la grammaire G définie par l’ensemble des productions suivant :
E → ent | ( Op E E El )
El → E El | ε
Op → + | ×
avec ent, terminal désignant l’ensemble des entiers. Cette grammaire est LL(1) et génère l’ensemble des
expressions définies par :
– Un entier est une expression.
– (+ e1 e2 . . .en ) et (× e1 e2 . . .en ) sont des expressions si e1 , e2 , . . ., en sont des expressions (n ≥ 2).
Exemple : (× (+ 2 13 7 3) (+ 4 5) ) est une expression.
Q 1. Concevez un STDS pour afficher les expressions en notation infixée.
Exemples : (+ (× 4 5) 3 2) ⇒ ( (4 × 5) + 3 + 2)
(+ 1 2 3) ⇒ (1 + 2 + 3)
Q 2. Concevez un STDS pour afficher la valeur des expressions reconnues par la grammaire de la première
question.
Exemples : (+ (× 4 5) 3 2) ⇒ 25
(+ 1 2 3) ⇒ 6
Exercice 3. Entiers signés
Soit la grammaire G = < V, T, P, Entier > avec V = {Entier, Signe, Liste}, T = {+, −, Chiffre}, P
l’ensemble des productions suivantes :
Entier → Signe Liste
Signe → +|−
Liste → Liste Chiffre | Chiffre
et le terminal Chiffre désignant les chiffres de 0 à 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 ([Link]) Alors [Link] = −[Link]
Sinon [Link] = [Link]
FSi
Signe → + [Link] = FAUX
Signe → − [Link] = VRAI
Liste → Liste1 Chiffre Liste1 .p = Liste.p + 1
[Link] = Liste1 .val + [Link] ×10Liste.p
Liste → Chiffre [Link] = [Link] ×10Liste.p
Q 1. Construisez l’arbre d’analyse décoré pour l’entier suivant : −8106
Q 2. Définissez complètement les attributs p, neg, val et vallex utilisés dans la définition dirigée par
la syntaxe ci-dessus : 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.
Q 3. Transformez la définition dirigée par la syntaxe en schéma de traduction dirigé par la syntaxe.
2
Exercice 4. Occurrences consécutives - Version 1
Soit L le langage dénoté par l’expression régulière (a | b)(ba | aa | ab)∗ . Ce langage est dénoté par la
grammaire G = {Va, Te, P, S} avec Va = {S, T }, Te = {a, b} et P l’ensemble des productions suivantes :
S → aT | bT
T → baT | aaT | abT | ε
Q 1. Construire l’arbre syntaxique pour l’expression aaabaabba.
Q 2. Concevoir une DDS pour calculer le nombre maximum de a consécutifs contenus dans les phrases
du langage L en utilisant les attributs suivants :
− nba, attribut hérité, associé au non-terminal T : Entier - Nombre courant de a consécutifs
− nbaM T , attribut hérité, associé au non-terminal T : Entier - Nombre maximum de a consécutifs
à gauche de T
− nbaM , attribut synthétisé, associé aux non-terminaux S et T : Entier - Nombre maximum de a
consécutifs dans la phrase
Q 3. Construire l’arbre syntaxique décoré pour l’expression aaabaabba.
Q 4. Transformer la DDS précédente en STDS.
Exercice 5. Occurrences consécutives - Version 2
Le langage L de l’exercice précédent est également par la grammaire G 0 = {Va’, Te, P, D} avec Va’ =
{D, S}, Te = {a, b} et P l’ensemble des productions suivantes :
D → S
S → Sba | Saa | Sab | a | b
Répondez aux mêmes questions que dans l’exercice précédent (pour la question 2, vous définirez vos
propres attributs et vous n’utiliserez que des attributs synthétisés).