T.D.

No1 Théorie des langages et compilation

Traducteurs dirigés par la syntaxe
Grammaires attribuées
Compilateurs simples en une passe

Section : IF4

Exercice 1
Supposons qu’un robot puisse être commandé pour se déplacer d’un pas vers l’est, le nord, l’ouest
ou le sud à partir de sa position initiale.
Par exemple si nous supposons que le robot est initalement dans la position (0,0), après exécution
des instructions :

début ouest sud est est est nord nord

le robot doit être à la position (2,1).

1. En utilisant la notion de grammaires attribuées, construire une définition dirigée par la syntaxe
pour traduire une séquence d’instruction en une position du robot.
Proposer pour répondre à cette question deux versions : la première utilise des attributs
synthétisés et la seconde utilise des attributs hérités.

2. Pour chacune des versions proposées précédemment, donner l’arbre syntaxique décoré pour
début ouest sud.

3. Dans un langage algorithmique, proposer une implémentation les deux versions trouvées précédemment.
Vous pouvez utiliser sans les réécrire les procédures accepter et SymboleSuivant introduites
au chapitre 2 du cours.

4. Exécuter à la main chacun des algorithmes sur le texte source début ouest sud.

Exercice 2
Ecrire une définition dirigée par la syntaxe traduisant des entiers binaires en nombres décimaux.
Construire un arbre décoré pour l’entrée 01011.

1
Exercice 3
Construire un schéma de traduction dirigé par la syntaxe qui traduit des nombres écrits en chiffres
romains en entiers décimaux.

Exercice 4
Construire un schéma de traduction dirigé par la syntaxe qui traduit des expressions arithmétiques
infixées en expressions préfixées où un opérateur apparaı̂t avant ses opérandes ; par exemple, −x y
est la notations préfixée de x − y. Construire les arbres décorés pour les entrées 9 − 5 + 2 et
9 − 5 ∗ 2.

Exercice 5
Ecrire le code associé à la traduction d’expressions arithmétiques infixées en postfixées.
On érira le code associé à :

• l’analyseur lexical,

• l’analyseur syntaxique prédictif,

• la gestion de la table des symboles Pour la gestion de la table des symboles il faut écrire les
algorithmes associés à :

– la fonction Chercher(s) permettant de rendre l’indice de l’entrée de la table des symbole

correspondante à la chaı̂ne s si celle ci existe sinon 0, et
– la fonction Inserer(s, t) permettant de ranger dans la table des symboles la chaı̂ne s ainsi
que l’unité lexicale associée t et de rendre l’indice correspondant.

• le traitement d’erreurs.

2
 T.D. No2 Théorie des langages et compilation
Analyse lexicale

Enseignant : Khaled Bsaı̈es et Imen Fassi Section : IF4

Exercice 1

Identifier les lexèmes, les unités léxicales, les attributs et les modèles qui dénotent les unités lexicales dans
le programme suivant. Discuter les différentes manières de traiter les mots clés. Donner le contenu de la
table des symboles à la fin de l’analyse.

function max (i, j : integer) : integer ; { retourne le maximum des entiers i et j }

begin if i > j then max:=i else max := j end;

Exercice 2

On considère un langage construit sur l’alphabet {a, b}.

• Donner l’expression régulière correspondante aux mots se terminant par abb

• Construire un automate fini deterministe reconnaissant ce langage.

• Construire un analyseur lexical en donnant les diagrammes de transition permettant de reconnaı̀tre

le langage composé par les mots se terminant par a, les mots se terminant par abb et les mots se
terminant par ab.

Exercice 3

• Ecrire une ”spécification Lex” qui compte le nombre de voyelles, consonnes et caractères de ponctuations
d’un texte en entré.
• Ecrire une ”spécification Lex” qui supprime les lignes qui commencent par p ainsi que tous les entiers,
remplace les o par des * et retourne le reste inchangé.

1
 T.D. No3 Théorie des langages et compilation
Analyse syntaxique descendante

Section : IF4

Exercice 1
On propose la grammaire suivante décrivant les instructions si-alors-sinon pour remédier à l’ambiguı̈té
du <<sinon en supens>>:
instr → si exp alors instr
|instr close
intstr close → si exp alors instr close sinon instr
|autre
Montrer que cette grammaire est encore ambiguë.

Exercice 2
Considérons la grammaire suivante :

S→(L)|a
L→L,S|S

1. Eliminer la récursivité gauche de cette grammaire

2. Construire un analyseur prédictif récursif pour cette grammaire. Expliciter le comportement

de l’analyseur sur les phrases :

(a) (a, a)
(b) (a, (a, a))

3. Gérer les erreurs en adoptant la stratégie mode panique.

4. Exécuter l’analyseur à la main sur l’entrée (, (a, ) puis sur l’entrée b(, a

1
Exercice 3
Construire un analyseur prédictif non récursif (itératif) pour la grammaire suivante:
exprb → exprb ou termeb | termeb
termeb → termeb et f acteurb | f acteurb
f acteurb → non f acteurb | ( exprb ) | vrai | faux
Analyser le mot (v et non f ). En mode panique analyser (v et

Exercice 4
Considérons la grammaire:

R → R 0 |0 R | RR | R ∗ | (R) | a | b

Notons que la première barre verticale est le symbole <<ou>> et pas le séparateur d’alternatives.

1. Construire une grammare équivalente non ambiguë qui donne aux opérations de répétition (*),
de concaténation et de choix (|) les priorités et associativités définies au cours.

2. Construire un analyseur prédictif non récursif pour la grammaire non ambiguë des expressions
régulières.

Exercice 5
• Montrer qu’aucune grammaire récursive gauche ne peut être LL(1)
• Montrer qu’aucune grammaire LL(1) ne peut être ambiguë.

Exercice 6
Soit G la grammaire suivante :

exp → exp op exp

exp → (exp) | - exp | id
op → + | - | * | /

Fournir toutes les étapes de développement d’un analyseur syntaxique prédictif, descendant et récursif
pour la grammaire G.
Présenter les diagrammes de transition de G et écrire l’analyseur syntaxique en utilisant un pseudo code
de votre choix.

2
 T.D. No4 Théorie des langages et compilation
Analyse syntaxique ascendante AAPO et SLR

Section : IF4

Exercice 1
Considérons la grammaire :

S→(L)|a
L→L,S|S

(1) Construire une dérivation droite pour (a, (a, a)) et montrer le manche de chaque proto-phrase droite.
(2) Détailler les étapes d’un analyseur par décalage-réduction correspondant à la dérivation droite de (1).

Exercice 2
La table suivante indique les relations de précédence d’opérateurs pour la grammaire de l’exercice 1.

a ( ) , $
a >
. >
. >
.

( <. <. =. <.

) >. >
. >
.

, <. <. .> >

.

$ <. <.

(a) en utilisant ces relations de précédence, analyser les phrases:

1. (a, a)

2. (a, (a, a))

(b) en utilisant le recouvrement d’erreurs en mode panique analyser la phrase (, a

(c) Calculer les fonctions de précédence d’opérateurs.

Exercice 3
Construire les relations de précédence d’opérateurs pour les grammaires suivantes :
• S → aSbS | bSaS | 

• exprb → exprb ou termeb | termeb

termeb → termeb et f acteurb | f acteurb
f acteurb → non f acteurb | ( exprb ) | vrai | faux

1
Exercice 4
Il existe une facon mécanique de produire les relations de précédence d’opérateurs à partir d’une grammaire
d’opérateurs, y compris celles avec des non-terminaux différents. Définissons Tête(A) comme l’ensemble des
terminaux a tel que a soit le terminal le plus à gauche d’une chaı̂ne dérivée de A, et définissons Queue(A)
comme l’ensemble des terminaux qui peuvent être le plus à droite dans une chaı̂ne dérivée de A. Alors pour
les terminaux a et b, nous posons a =. b s’il existe une partie droite de la forme : αaβbγ, où β est soit vide,
soit un unique non-terminal, et α et γ sont arbitraires. Nous posons a <. b s’il existe une partie droite de la
forme : αaAβ et si b est dans Tête(A) ; nous posons a.> b s’il y a une partie droite de la forme : αAbβ et si
a est dans Queue(A). Dans les deux cas, α et β sont des chaı̂nes arbitraires. Nous posons également $ <. b
chaque fois que b est dans Tête(S), où S est l’axiome, et a.> $ à chaque fois que a est dans Queue(S).

1. Avec la grammaire de l’exercice 1 calculer la Tête et Queue pour S et L

2. Vérifier que les relations de précédences de la table de l’exercice 2 sont celles dérivées de cette gram-
maire.

Exercice 5
Soit G la grammaire suivante :
E → E + T |T
T → T F |F
F → F ∗ |a|b
1. Calculer les fonctions PREMIER et SUIVANT pour les non terminaux E, T et F .
2. Construire la grammaire augmentée G0 .
3. Calculer les ensembles d’items.
4. Construire l’automate des préfixes viables.
5. Dresser les tables ACTION et SUCCESSEUR.
6. Reconnaı̂tre a + b∗ .
7. Gérer les erreurs en modfe panique.
8. Analyser ab∗ +.

Exercice 6
Soit G la grammaire suivante :
R → R ∪ R | R ∩ R | R ∗ R | {LIST E}
LIST E → COU P LE , LIST E | LIST E
COU P LE → ( CHIF F RE , CHIF F RE )
Construire les tables SLR ACTION et SUCCESSEUR associées à la grammaire G.

Exercice 7
Soit G la grammaire suivante :
G : {E → E + E | E − E | E ∗ E | E/ E | Chif f re} où E est l’axiome et +, −, ∗, / et Chif f re
sont des terminaux.
1. Construire les tables SLR associées à la grammaire G. Peut-on faire une analyse SLR pour G? Justifier
votre réponse.
2. Si l’on suppose que les
opérateurs +, −, ∗ et / sont associatifs à gauche et que {+, −} ont une priorité inférieure à celle de {∗, /},
proposer des tables SLR sans conflit (Shift-Reduce ou dit aussi décaler-réduire).

2
 T.D. No5 Théorie des langages et compilation
Génération de code intermédiaire

Section : IF4

Exercice 1
Traduire l’expression arithmétique a * - ( b + c ) en :
1. du code à trois adresses ;
2. du code pour une machine à pile.
Même chose pour l’instruction x:=a * - ( b + c ).

Exercice 2
Rappeler le code intermédiaire à trois adresses associé à l’instruction d’itération tant que :
I → tant que E faire I1
Donner les définitions dirigées par la syntaxe permettant de générer du code à trois adresses pour
les instructions conditionnelles simple et double.
I → si E alors I1
I → si E alors I1 sinon I2
Application : Traduire l’instruction suivante en du code pour une machine à trois adresses :

tant que a < b faire si c < d alors x := y + z sinon x := y - z

Exercice 3
Tout compilateur est composé de deux parties : la partie frontale et la partie terminale. Dans la
partie frontale, on effectue l’analyse lexicale, l’analyse syntaxique et sémantique et on génère le
code intermédiaire pour une machine abstraite. Dans cet exercice, on suppose que l’on génère des
instructions intermédiaires LI pour une machine abstraite à pile. La sémantique des instructions LI
est celle utilisée dans le cours.

1. Traduire manuellement l’instruction itérative suivante en langage LI.

tant que a<>b faire si a>b alors a:=a-b sinon b:=b-a fait

2. Soit G la grammaire non contextuelle suivante :

1
 Instruction --> tant que Expression-Booleenne faire Instruction fait
| si Expression-Booleenne alors Instruction sinon Instruction
| id:=Expression-Entiere
Expression-Booleenne --> Variable = Variable
| Variable <> Variable
| Variable > Variable
| Variable < Variable
Expression-entiere --> Variable + Variable
| Variable - Variable
| Variable * Variable
Variable --> id | nombre

Si id est un identificateur de variable et nombre est une nombre entier positif.

Fournir un schéma de traduction dirigé par la syntaxe d’un programme respectant la grammaire
G en un programme équivalent écrit en langage LI.

3. Fournir l’arbre syntaxique (décoré par les actions définis dans le schéma de traduction) de
l’instruction itérative fournie à la question 1.

Instruction Sémantique de l 0 instruction

empiler V Empile V sur la pile
valeurd L Empile le contenue de l 0 emplacement L
valeurg L Empile l 0 adresse de l0 emplacement L
dépiler Supprime le sommet de la pile
affecter La valeur au sommet de la pile est placée à l 0 adresse
située au sous sommet. On dépile ensuite deux f ois.
copier Empile une copie de la valeur en sommet de pile.
mul M ultiplie le contenu du sommet de la pile à celui du
sous sommet. On dépile deux f ois, et on empile le résultat
de la multiplication.
div M ême chose que pour mul
sub M ême chose que pour mul
add M ême chose que pour mul
etiq L Déf inir une étiquette
aller à L La prochaine instruction est celle qui est étiquetèe par L.
aller si faux Enlève le sommet de pile. S 0 il est égale à 0, brachement à L.
aller si vrai Enlève le sommet de pile. S 0 il est dif f érent de 0,
brachement à L.
halte Arrête l 0 exécution
comparer si sup Empile 0 en sommet de pile si le contenu du sous sommet
n0 est pas supérieur à celui du sommet et la valeur 1
sinon, tout en dépilant les deux sommets initiaux de la pile.
comparer si inf M ême chose que pour comparer si sup.
comparer si égal M ême chose que pour comparer si sup.