COMPILATION

Chapitre 0 : Introduction

Chapitre 1 : L’analyse lexicale

Chapitre 2 : L’analyse syntaxique

Chapitre 3 : Les formes intermédiaires

Chapitre 4 : L’analyse sémantique

 INTRODUCTION

1\ Les différentes phases d’un compilateur :

1) Analyse lexicale : le rôle de cette analyse est de déterminer

les mots ou entités appartenant au langage à compiler et de
construire le dictionnaire des entités appelé table des symboles,
le résultat de cette analyse est appelé chaîne codée

2) Analyse syntaxique : son rôle est de vérifier si la structure de

la chaîne codée obtenue est conforme à la grammaire
syntaxique du langage considéré

3) Génération du code intermédiaire et analyse sémantique :

cette phase consiste à générer à partir d’une entité syntaxique
un code simplifié de bas niveau et permet de vérifier si la
chaîne codée est correcte du point de vue sens

4) Optimisation du code : cette phase vise à optimiser le code

du point de vue place mémoire et rapidité d’exécution, à noter
qu’elle est optionnelle

5) Génération du code objet : c'est la dernière phase de

compilation, le compilateur traduit le code obtenu à partir des 4
précédentes étapes et le transforme en code machine qui peut
maintenant être directement exécuter par la machine
2\ Table des symboles :
C’est une table contenant les mots clés, les caractères
spéciaux ainsi que les informations concernant les entités du
programme à compiler, elle est construite dans l’analyse
lexicale et est mise à jour au fur et à mesure dans les autres
étapes de la compilation
 L’ANALYSE LEXICALE

1\ Définition :
L’analyse lexicale consiste à partir d’un programme qui est une
suite de caractères et de :
- Spécifier les différentes entités lexicales
- Eliminer les blancs ainsi que les commentaires s’ils existent
- Coder les différentes entités lexicales
- Construire la table des symboles

2\ Entités lexicales :
il existe 4 types d’entité lexicale :
- les identificateurs : x / y …
- les mots clés : if then else for BEGIN END …
- les constantes : 5 / -2 / 4.13 …
- les séparateurs : ; / : / { / } …

Remarque : les mots clés et les séparateurs sont une donnée

du programme, ils sont donc connus à l'avance, les
identificateurs et les constantes sont donnés par l’utilisateur

3\ Implémentation d’un analyseur lexical :

Les entités lexicales sont décrites à l’aide de grammaires
d’expressions régulières, qui sont reconnues par des automates
à états finis, la représentation d’un automate en mémoire se fait
à l’aide d’une matrice, appelé matrice de transition
Les lignes de la matrice représentent les états de l’automate,
les colonnes représentent les terminaux

Algorithme de reconnaissance d’une entité lexicale :

Début
Lecture de la donnée ;
tc ← 1er caractère de la chaîne à analyser ;
Ec ← état initial de l’automate ;
Tant que (Ec ≠ ∅) et (⎤ fin de chaîne) faire
Ec ← T(Ec, tc) ; /* T = la table de transition */
tc ← ts ;
Fait ;
Si (Ec = ∅) alors
‘chaîne incorrecte lexicalement’ ;
Sinon
Si (Ec n’est pas final) alors
‘chaîne incorrecte lexicalement’ ;
Sinon
‘chaîne correcte’ ;
coder l’entité ;
insérer dans la table des symboles ;
Fsi ;
Fsi ;
Fin.
 L’ANALYSE SYNTAXIQUE

1\ Définition :
L’analyse syntaxique a pour rôle la vérification de la forme et de
la succession des entités lexicales, cette vérification est faite à
l’aide de la grammaire spécifique au langage, appelée
grammaire syntaxique.

Grammaire syntaxique : c’est une grammaire formée de règles

de production permettant d’engendrer tous les programmes
écrits dans un langage donné, chaque règle possède un
membre gauche de production (MGP) et un membre droit de
production (MDP)

Arbre syntaxique : c’est un arbre dont la racine est l’axiome de

la grammaire syntaxique, les nœuds représentent les membres
droits de production et les feuilles, la chaîne à analyser
syntaxiquement. On dit qu'une grammaire est ambigüe s'il
existe au moins 2 arbres de dérivation pour une même chaine

2\ Elimination de la récursivité gauche :

Une analyse descendante ne peut se faire sur une grammaire
récursive gauche, il faut donc l’éliminer, on distingue 2 types de
récursivité gauche : directe et indirecte

1) récursivité gauche directe : une grammaire est dite récursive

gauche directe si elle s’écrit de cette façon : A → A α / β
c’est-à-dire qu’un non terminal donne lui-même, pour l’éliminer
on suit cette règle :
Soit la règle de production : A → Aα1 / Aα2 / β1 / β2
A est récursive gauche direct, elle devient alors :
A → β1 / β2 / β1A' / β2A’
Α’ → α1 / α2 / α1A’ / α2A'

En d’autres termes A va donner tous les MDP qui n’était pas

collés à A (β1 et β2) puis ces même MDP on va leur coller A’
(β1A’ et β2A’), ensuite A’ qui est un nouveau non terminal va
donner tous les MDP qui était collés à A (α1 et α2) puis ces
même MDP on va leur coller A’ (α1A’ et α2A’)

Exemple :

Soit G la grammaire suivante :

S → Abc / Baa / AB
A → AaB / Ab / aSc / ε
B → bB / ε

On commence par repérer la règle qui contient la récursivité

gauche, dans ce cas c’est la A, on identifie ensuite les α et β,
ce qui donne : A → AaB / Ab / aSc / ε , on applique la règle :

S → Abc / Baa / AB
A → aSc / ε / aScA’ / A’ (car εA’ = A’)
A’ → aB / b / aBA’ / bA’
B → bB / ε
Remarque : la récursivité droite ne pose pas de problème,
donc les règles de types : A → αA sont correctes, on ne
s’intéresse qu’à la récursivité gauche

2) récursivité gauche indirecte : une grammaire est dite

récursive gauche indirecte si on part d’un non terminal A et
après quelques règles on revient vers le même A, par exemple :
A→B/α
B→A/β

L’élimination se fait en 2 étapes :

1- transformer la grammaire en récursive gauche directe par
substitution
2- éliminer la récursivité gauche directe en utilisant la règle vu
précédemment pour la rendre non récursive gauche

Exemple :

Soit G la grammaire suivante :

S → Ac / b
A → Bd / a
B → Ac / d

On remarque que la récursivité gauche indirecte se trouve au

niveau du A car A → B puis B → A , on substitue alors le B
dans A comme suit : A → (Ac / d) d / a donc A → Acd / dd / a
On obtient alors la grammaire G’ suivante :
S → Ac / b
A → Acd / dd / a
B → Ac / d

Maintenant qu’on s’est débarrassé de la récursivité gauche

indirecte, on élimine la directe en appliquant la règle vu
précédemment et on obtient alors la grammaire G’’ suivante :

S → Ac / b
A → dd / a / ddA’ / aA’
A’ → cd / cdA’
B → Ac / d

3\ Factorisation d’une grammaire :

Une des conditions permettant de faire une analyse syntaxique
descendante déterministe est la factorisation.
Une grammaire est dite non factorisée si elle contient une règle
de type : A → aB / aC ou A → Bc / Bd
Pour factoriser une grammaire on prend en facteur l’élément
commun entre les différent MDP et on lui colle un nouveau non
terminal qui mène vers ces MDP

Exemple :
Soit la règle : A → aX / aY / aZ / α / β , après factorisation :
A → aE/ α / β
E→X/Y/Z
4\ L’ensemble des débuts et suivants :

Ensemble des débuts : c’est l’ensemble des terminaux

susceptible de commencer un mot, 5 règles à respecter :

1) A → αβB
- deb(A) = {α}

2) A → B
- deb(A) = deb(B) = {β}

3) A → Bα
B → βcC
- deb(A) = deb(B) = {β}

4) A → Bα
B→β|ε
- deb(A) = deb(B) + deb(A si B = ε) = {β, α}
- deb(B) = {β, ε}

5) S → ABC et A → ε et B → ε et C → ε alors {ε} ⊆ deb(S)

Exemple :
Soit la grammaire suivante : L’ensemble des débuts :
S → ABC Deb(S) = {a, b, c, d}
A → aA | ε Deb(A) = {a, ε}
B → bB | cB | ε Deb(B) = {b, c, ε}
C → dC | da | dA Deb(C) = {d}

Ensemble des suivants : c’est l’ensemble des terminaux qui

viennent immédiatement après un non-terminal, 5 règles à
respecter :

1) Si A → Bα alors α ⊆ suiv(B)

2) Si S → ABα et B → ε alors α ⊆ suiv(A)

3) Si A → B alors suiv(A) – {ε} ⊆ suiv(B)

4) Si A → BC et C → ε alors suiv(A) – {ε} ⊆ suiv(B)

5) Si S → AB alors deb(B) – {ε} ⊆ suiv(A)

Exemple :
S → ABC
A → aA | ε
B → bB | cB | ε
C → dC | da | dA

Pour déterminer l’ensemble des suivants on aura besoin de

l’ensemble des débuts calculé précédemment :

Suiv(S) = {#} Deb(S) = {a, b, c, d}

Suiv(A) = {b, c, d, #} Deb(A) = {a, ε}
Suiv(B) = {d} Deb(B) = {b, c, ε}
Suiv(C) = {#} Deb(C) = {d}

5\ Méthodes d'analyse syntaxiques :

Pour faire une analyse syntaxique on dispose de 2 méthodes :
1) Méthode descendante : par dérivation
2) Méthode ascendante : par réduction

Et maintenant qu’on sait comment :

- éliminer la récursivité gauche
- factoriser une grammaire
- déterminer l’ensemble des débuts et suivants

On peut désormais utiliser les méthodes d’analyse syntaxique

descendantes
6\ Méthodes descendantes :
Ces méthodes consistent à commencer à partir de l'axiome et
faire une série de dérivation jusqu'à atteindre la chaîne
d'entrée, on va s’intéresser à 2 méthodes particulières : la
descente récursive et l’analyse LL(1)

1) Descente récursive : cette méthode consiste à associer une

procédure à chaque non-terminal de la grammaire, lorsque
l'analyseur rencontre un non-terminal, il appelle la procédure
correspondante pour ce non-terminal, cette procédure analyse
les symboles suivants dans la chaîne d'entrée et appelle les
procédures correspondantes pour les non-terminaux qu'elle
rencontre, cette analyse se poursuit jusqu'à ce que tous les
symboles de la chaîne d'entrée soient analysés

Pour appliquer cette méthode il faut remplir ces 3 conditions :

1- La grammaire ne doit pas être récursive gauche
2- La grammaire doit être factorisée
3- Si A → α1 / α2 / .... / αn alors les intersections doivent être
deux à deux disjointes, c’est-à-dire que leurs intersections = ∅

2) Analyse LL(1) : cette méthode utilise une table d'analyse

pour prédire les règles de production à appliquer à chaque
étape de l'analyse, cette table est construite à partir de la
grammaire et de l'ensemble des premiers et des suivants de
chaque non-terminal de la grammaire, les lignes contiennent les
Non terminaux de la grammaire, et les colonnes, les terminaux,
chaque entrée non définie de la table d’analyse LL(1)
correspond à une erreur, la table d’analyse d’une grammaire
LL(1) doit être monodéfinie (Au plus une règle par case)
On dit qu’une grammaire est LL(1) si elle est :
1- Non récursive gauche
2- Factorisée
3- Table d’analyse monodéfinie

Remarque : il existe une autre condition qu’on peut utiliser à la

place de la 3e condition précédente :
Si A → α1 / α2 / ... / αn alors :
Debut(αi) ∩ Debut(αj) = Ø, ∀ i, j avec i ≠ j

7\ L’analyse descendante :
Pour vérifier si un mot respecte la syntaxe fournit par la
grammaire on lui applique une analyse descendante, cette
méthode étant un peu compliqué à expliquer sur un PDF, je
vous redirige vers ces 2 vidéos qui l’explique très bien :
Explication de l'analyse & Exemple d'application de l'analyse

8\ Méthodes ascendantes :
C’est l’inverse de la dérivation, elle consiste à remplacer un
membre droit de production par son membre gauche, et
continuer ainsi jusqu’à arriver à l’axiome, c’est le principe de
réduction, on va voir ces 3 méthodes : L’analyse LR, l’analyse
SLR et l’analyse LALR

1) Analyse LR :
C’est une méthode d'analyse efficace et déterministe qui
consiste en des décalages et réductions, elle utilise une pile et
une table d’analyse LR, pour construire la table d’analyse LR
on utilise la méthode des items

Méthode des items : un item est une production de la

grammaire avec un point repérant une position de son MDP, la
partie gauche du point représente ce qui a été réduit, et la
partie droite ce qui reste à analyser
Un item LR(1) est de la forme [A → α.β, t] , pour construire
l’ensemble des items nous avons besoin de 2 fonctions :
- la fermeture d'un item
- la fonction GOTO

Remarque : Le problème de l’analyse LR(1) est la table

d’analyse, elle peut contenir des centaines de milliers d’états ce
qui fait qu’elle est très couteuse à implémenter, pour remédier à
cela, on a pensé à une méthode d’analyse plus simple avec
une table plus réduite, c’est les analyse SLR

2) Analyse SLR :
1- Construction de l’ensemble des items LR(0)
2- Construction de la table d’analyse SLR(1)
3- Si la table est monodéfinie alors la grammaire est SLR(1)

Remarque : Le problème de l’analyse SLR est que très peu de

grammaire sont compatible avec cette méthode, l’analyse LALR
a alors été conçue, c’est une méthode intermédiaire du point de
vue puissance, elle est souvent suffisante et produit des tables
de même importance que SLR
3) Analyse LALR(1) :
1- Construction de l’ensemble des items LR(1)
2- Pour chaque cœur d’item présent dans I, trouver tous les
états ayant ce même cœur et les remplacer par leur union
3- Construire la table d’analyse
4- Si la table est monodéfinie alors la grammaire est LALR(1)

9\ Notion d’ambiguïté :
Une grammaire ambigüe veut dire qu’elle accepte plusieurs
arbres syntaxiques, pour monter qu'une grammaire est
ambiguë il suffit de prendre une chaine et de construire 2
arbres syntaxiques différents

Astuce : si les opérateurs arithmétiques sont tous sur la même

ligne alors la grammaire est ambigüe

Pour lever l'ambigüité d'une grammaire il faut définir des

priorités, puis on va créer de nouveaux non-terminaux qui vont
relier entre les différents niveaux de priorités, on commencera
par les opérateurs les moins prioritaires, les plus prioritaires se
trouveront à la fin, à noter que le choix des priorités est
arbitraire, plusieurs configurations sont possibles

Remarque : une grammaire ambiguë est :

- non LL
- non LR
- non SLR
- non LALR
Exemple :

Soit la grammaire G suivante :

E  E + E | E x E | E / E | E - E | (E) | nb

La grammaire augmentée de G est comme suit :

Z  E#
EE+E
EExE
EE/E
E  (E)
E  nb

G est ambigüe, pour lever l’ambigüité on va définir quelques

priorités : * et / > + et - > () et nb

La nouvelle grammaire G’ est :

Z  E#
EE+A|E–A|A
AAxB|A/B|B
B  (E) | nb
 LES FORMES INTERMÉDIAIRES

1\ Définition :
On appelle forme intermédiaire, une forme dont l’ensemble des
instructions est composé d’un opérateur et de 2 opérandes
Un opérande peut être une constante, une variable, un nom de
procédure, un opérateur peut être arithmétique ou logique

On va s’intéresser à 4 formes intermédiaires :

• Forme postfixée
• Forme préfixée
• Quadruplés
• Arbre abstraite

2\ Forme postfixée :

Notation : opérande1 opérande2 opérateur

fp(t1 opérateur t2) = fp(t1) fp(t2) opérateur

fp(opérateur t) = fp(t) opérateur
fp(constante) = constante
fp(variable simple) = variable simple
Evaluation d’une expression en notation postfixée : on utilise
une pile pour sauvegarder les opérandes, voici l’algorithme :

Si (tc est opérande) alors

Empiler(t1) ;
tc := tc + 1 ;
Sinon
Si (tc est opérateur binaire) alors
Dépiler(opde2) ;
Dépiler(opde1) ;
Évaluer(tc, opde1, opde2, temporaire) ;
Empiler(temporaire) ;
tc := tc + 1 ;
Sinon
Dépiler(opde) ;
Évaluer(tc, opde, , temporaire) ;
Empiler(temporaire) ;
tc := tc + 1 ;
Fsi ;
Fsi.

Exemple :
Soit l’expression : a - c + d * e

Sa forme postfixée est : a c - d e * +

Évaluation de l’expression :

Forme postfixée d’une affectation :

Var := <expression>  fp(Var) fp(<expression>) :=

Exemple : x := x+y*z  x x y z * + :=

Forme postfixée d’un branchement inconditionnel :

Goto etiq  etiq BRL

Forme postfixée d’un branchement conditionnel :

<opérande1> <opérande2> <opérateur de comparaison>
<opérande1> : forme post de la condition
<opérande2> : position dans la chaine post fixée.
<opérateurs de comparaison> : se fait par rapport à zéro
On a 6 opérateurs de comparaison :
• BZ (=0) • BNZ (≠0) • BP (>0)
• BM (<0) • BPZ (≥0) • BMZ (≤0)

Forme postfixée d’une déclaration de tableau :

Soit la déclaration de tableau : Array V[U1:L1,............, Un:Ln]*
Les Li et Ui sont les bornes de tableau, donc des expressions
arithmétiques de type entier

Fp : fp(U1) fp(L1) … fp(Un) fp(Ln) V ADEC

ADEC : opérateur de déclaration de tableau

Exemple :
Soit la déclaration d’un tableau : Array A [a+b : c*d , 5*x : z-y]

Fp : fp(a+b) fp(c*d) fp(5*x) fp(z-y) A ADEC

Fp : fp(a) fp(b) + fp(c) fp(d) * fp(5) fp(x) * fp(z) fp(y) - A ADEC
Fp : a b + c d * 5 x * z y - A ADEC

Forme postfixée pour la référence d’un élément de tableau :

Soit l’élément : A [<expression 1>, ..., <expression n>]

Fp : fp(<expression 1>) … fp(<expression n>) A SUBS

SUBS : opérateur de référence à un élément de tableau
Exemple :
Soit l’élément : A [a+b, c*d, n-z]

Fp : fp(a+b) fp(c*d) fp(n-z) A SUBS

Fp : fp(a) fp(b) + fp(c) fp(d) * fp(n) fp(z) - A SUBS
Fp : a b + c d * n z - A SUBS

Forme postfixée d’une instruction conditionnelle :

fp [ IF <cond> THEN <inst1> ELSE <inst2> ]

else : position du 1er symbole dans la chaine post fixée de

<inst2>

Fin : position dans la chaine post fixée qui suit immédiatement

le dernier symbole de fp(<inst2>)

Exemple :
Soit la condition : IF a≠b THEN b := b*a ELSE c := a*c
3\ Forme préfixée :
Notation : opérateur opérande1 opérande2
fp(t1 opérateur t2) = opérateur fp(t1) fp(t2)
fp(opérateur t) = opérateur fp(t)

La forme préfixée est l’inverse de la postfixée, on commence

par l’opérateur puis viennent les opérandes

4\ Quadruplés :
Notation : (opérateur, opérande1, opérande2, Temporaire)

Exemple :
Soit l’opération : a * b / c + d en d’autres termes ((a*b) / c) + d
1- (*, a, b, T1)
2- (/, T1, c, T2)
3- (+, T2, d, T3)

Quadruplé de l’affectation :
Var := <expression>  ( :=, T, ,Var)

Quadruplé du branchement inconditionnel :

Goto etiq  (BRL, etiq, , )
 (BR, N°quadruplé, , )

Quadruplé du branchement conditionnel : 2 cas possibles

1) Cas opérateur unaire (comparaison par rapport à 0) :
(Opérateur, N° quadruplé, Temporaire, )

Les opérateurs sont les mêmes que dans la forme postfixée :

• BZ (=0) • BNZ (≠0) • BP (>0)
• BM (<0) • BPZ (≥0) • BMZ (≤0)

2) Cas opérateurs binaires (comparaison de deux opérandes) :

(Opérateur, N° quadruplé, T1, T2)

Les opérateurs sont :

• BE (=0) • BNE (≠0) • BG (>0)
• BL (<0) • BGE (≥0) • BLE (≤0)

Quadruplé d’une condition :

Exemple : if (a ≠ b) then b := a*b else c := a*c

1- (BE, else(5), a, b)
2- (*, b, a, T1)
3- ( :=, T1, , b)
4- (BR, Fin(7), , )
5- (*, a, c, T2)
6- ( :=, T2, , c)
7-
Quadruplé d’une déclaration de tableau :
Pour construire ce quadruplé il faut d’abord calculer les
quadruplés de la borne inférieure (T1.1) et supérieure (T1.2) de
la première dimension ensuite on créer le quadruplet avec
l’opérateur BOUNDS : (BOUNDS, T1.1, T1.2, ) et on fait cela
pour chaque dimension i du tableau : (BOUNDS, Ti.1, Ti.2, )
jusqu’à la dernière dimension : (BOUNDS, Tn.1, Tn.2, ), enfin
en ajoute le dernier quadruplet : (ADEC, nomTableau, , )

Exemple :
Soit la déclaration de tableau suivante : Array A [1:i+j-k , 2:c-d]

1- (+, i, j, T1)
2- (-, T1, k, T2)
3- (BOUNDS, 1, T2, )
4- (-, c, d, T3)
5- (BOUNDS, 2, T3, )
6- (ADEC, A, , )

Quadruplé d’un pour la référence d’un élément de tableau :

On calcule le quadruplet de l’expression 1 et on le met dans T1,
et on fait cela pour chaque expression i jusqu’à l’expression n
qu’on va mettre dans Tn, puis on créer le quadruplet final
comme suit : (Opérateur, A[T1,........., Tn], opérande, résultat)

Exemple :
Soit l’affectation suivante : x := T[x+y, a*b] * 6
1- (+, x, y, T1)
2- (*, a, b, T2)
3- (*, T[T1,T2], 6, T3)
4- ( :=, T3, ,x)

5\ Arbre abstrait :
C’est une représentation sous forme d’arborescence des
relations entre les opérandes et les opérateurs

Exemple : i * i + i Affectation :

Branchement inconditionnel : Condition :

Déclaration d’un tableau : Élément d’un tableau :

 ANALYSE SÉMANTIQUE

1\ Définition :
L’analyse sémantique permet de donner un sens à ce qui été
reconnu dans l’analyse syntaxique, cette phase vérifie :
• Si un IDF a été bien déclaré
• La concordance des types dans une expression
• L’utilisation correcte d’une étiquette
• et bien d’autres choses …

Le schéma de traduction est composé de 3 choses :

• Grammaire sémantique (transformée)
• Code intermédiaire
• Routines sémantiques

L’analyse sémantique consiste à rajouter au code intermédiaire

généré précédemment des routines sémantiques
Une routine sémantique est appelée à chaque fois qu’un
contrôle sémantique est nécessaire, on a donc 2 cas : l’analyse
descendante et l’analyse ascendante

2\ Cas de l’analyse descendante :

Pour insérer une routine sémantique au sein d’une règle, on
introduit un non-terminal qui dérive en ε

Si A  αβ alors la règle devient : A  αBβ et B  ε

Instruction conditionnelle :
IF <exp-bool> THEN <inst1> ELSE <inst2>

Forme intermédiaire sous forme de quadruplés :

On a donc besoin de 3 routines sémantiques :

IF <exp-bool> <A> THEN <inst1> <B> ELSE <inst2> <C>

<A>  ε : Permet la génération d’un branchement vers debut

else, si <exp-bool> est fausse, sauvegarde de l’étiquette de BZ

<B>  ε : Génération d’un BR, sauvegarde de l’étiquette de

BR, et Mise à jour de l’étiquette de BZ

<C>  ε : Mise à jour de l’étiquette de BR

QUAD : Matrice des quadruplés

Qc : le 1er quadruplé libre dans la matrice QUAD

Les routines sémantiques :

Routine <A> :
Debut
QUAD(Qc) := (BZ, , <exp-bool>.temp, ) ;
Sauv-BZ := Qc ;
Qc := Qc + 1;
Fin.

Routine <B> :
Debut
QUAD(Qc) := (BR, adresse de la fin , , ) ;
Sauv-BR := Qc ;
Qc := Qc + 1 ;
QUAD(Sauv-BZ, 2) := Qc ;
Fin.

Routine <C> :
Debut
QUAD(Sauv-BR, 2) := Qc ;
Fin.
Instruction While :
WHILE <condition> DO <Inst>

Forme intermédiaire sous forme de quadruplés :

Grammaire transformée (associée) :

WHILE <A> <condition> <B> DO <Inst> <C>

<A>  ε : permet la sauvegarde du début While afin d’y revenir

<B>  ε : permet le test de la condition
<C>  ε : Générer un branchement BR au début du While et
mettre à jour le BZ

Les routines sémantiques :

Routine <A> :
Debut
Sauv-deb := Qc ;
Fin.
Routine <B> :
Debut
QUAD(Qc) := (BZ, , <condition>.temp, ) ;
Sauv-BZ := Qc ;
Qc := Qc + 1 ;
Fin.

Routine <C> :
Debut
QUAD(Qc) := (BR, Sauv-deb, , ) ;
Qc := Qc + 1 ;
QUAD(Sauv-BZ, 2) := Qc ;
Fin.

Expressions arithmétiques :

Soit la grammaire suivante :

ET+E
TF*T/F
F  i / (E)

On remarque que la grammaire est récursive droite, ce qui fait

que l’associativité se fait de droite à gauche

On transforme la grammaire afin d’avoir l’associativité de

gauche à droite :
E  T {+T}*
T  F {*F}*
F  i / (E)

Cette nouvelle grammaire est équivalente à l’ancienne sauf que

celle-ci est LL(1)

Insertion des procédures sémantiques :

E  T {+T <A>}*
T  F{*F <B>}*
F  i<C> / (E)
<A>  ε
<B>  ε
<C>  ε

<A>  ε : se déclenche après +T pour générer le quadruplet de

l’addition : T + T

<B>  ε : se déclenche après *F pour générer le quadruplet de

la multiplication : F * F

<C>  ε : générer les quadruplets d’addition (i+i) et

multiplication (i*i)

La grammaire est LL(1), on peut donc lui faire une descente

récursive, on doit alors écrire les procédures : E, T, F, A, B et C
Analyse Syntaxico- Sémantique par la descente récursive :

Procédure E (X : entité, Y : Type ; B : Boolean)

Debut
Var : opérande1, opérande2 : entité ;
Type1, Type2 : Type ;
T(opérande1, Type1, b) ;
Si (b = faux) Alors aller à fin Fsi ;
Tant que tc = ‘+’ Faire
tc := tc + 1 ;
T(opérande2, Type2,b) ;
Si (b = faux) Alors aller à fin Fsi ;
A(opérande1, Type1, opérande2, Type2, X, Y) ;
opérande1 := X ;
opérande2 := Y ;
Fait ;
X := opérande1 ;
Y := Type1 ;
Fin.
Procédure T (X : entité, Y : Type, b : Boolean) ;
Debut
Var : opérande1, opérande2 : entité ;
Type1, Type2 : Type ;
F(opérande1, Type1, b) ;
Si (b = faux) Alors aller à fin Fsi ;
Tant que tc = ‘*’ Faire
tc := tc + 1 ;
F(opérande2, Type2,b) ;
Si (b = faux) Alors aller à fin Fsi ;
B(opérande1, Type1, opérande2, Type2, X,Y) ;
opérande1 := X ;
Type1 := Y ;
Fait ;
X := opérande1 ;
Y := Type1 ;
Fin.
Procédure F (X : entité, Y : Type ; b : Boolean)
Debut
Si (tc = ‘(‘) Alors
tc := tc + 1 ;
E(X, Y, b) ;
Si (b = faux) Alors aller à fin Fsi ;
Si (tc = ‘)’) Alors tc := tc + 1 ;
Sinon b = faux ;
Fsi ;
Sinon
Si (tc = id) alors
C(opérande1, Type1, X Y) ;
tc := tc + 1 ;
Sinon b = faux ;
Fsi ;
Fsi ;
Fin.

Procédure <A> (opérande1, opérande2 : entité ;

Type1, Type2 : Type ; b : Boolean)
Début
Vérifier compatibilité des types des deux opérandes ;
CréerTemp (X) ;
Générer (+, opérande1, opérande2, X) ;
Y := calcul type (type1, type2) ;
Fin.
Procédure <B> (opérande1, opérande2 : entité ;
Type1, Type2 : Type ; b : Boolean)
Début
Vérifier compatibilité des types des deux opérandes ;
CréerTemp (X) ;
Générer (*, opérande1, opérande2, X) ;
Y := CalculType (Type1, Type2 ) ;
Fin.

Procédure <C> (opérande1 : entité; Type1 : Type ; b : Boolean)

Début
lookup (id.nom, p) ;
Si (p = 0) alors b = faux ;
Sinon X := p.nom ;
Y := p. type ;
Fsi :
Fin.

Lookup : cette fonction prend en entrée le id.nom d’un élément

et fait une recherche dans la TS, si elle le trouve elle va
retourner sa position P, sinon elle retourne 0, cela veut dire
qu'on a recherché un idf non déclaré

3\ Cas de l’analyse ascendante :

Si <A>  αβ et une routine doit être insérée entre α et β Alors :
<A>  <B> β et <B>  α
Instruction conditionnelle :
IF <exp-bool> THEN <Inst1> ELSE <Inst2>

Forme intermédiaire sous forme post fixée :

Pf(<exp-bool>) else BZ Pf(<Inst1>) fin BR Pf(<Inst2>)

Grammaire transformée :
<Inst-IF>  <debut-inst-if> <Inst2> R3
<debut-inst-if>  <debut-if> <Inst1> ELSE R2
<debut-if>  IF <exp-bool> THEN R1

Pf : vecteur de la forme post fixée

i : 1ère position libre dans Pf

Les routines sémantiques :

Routine R1 Routine R2 Routine R3

Debut Debut Debut
Sauv-BZ := i ; Sauv-BR := i ; Pf(Sauv-BR) := i ;
i :=i+1 ; i := i+1 ; Fin.
Pf(i) := BZ ; Pf(i) := BR ;
i :=i+1 ; i := i+1 ;
Fin. Pf(Sauv-BZ) := i ;
Fin.
Expressions arithmétiques sous forme de quadruplés :

Soit la grammaire G :
EE+T/T
TT*F/F
F  id / (E)

Et la chaine : a + b * c

On utilise une pile des opérandes à 3 champs :

- 1er champ : le MGP
- 2e champ : le nom
- 3e champ : le type

Insertion des routines sémantiques :

E  E+T R6 / T R5
T  T*F R4 / F R3
F  id R1 / (E) R2

R1 : permet la reconnaissance de l’id, de le réduire en F et

d’empiler ses attributs
R2 : permet de réduire E en F, et d’empiler ses attributs
R3 : permet de réduire F en T, et d’empiler ses attributs
R4 : permet d’effectuer la multiplication et de ranger le résultat
R5 : permet de réduire T en E, et d’empiler ses attributs
R6 : permet d’effectuer l’addition et de ranger le résultat

Les routines sémantiques :

Routine R1
Debut
Lookup(id,P) ;
Si (P = 0) Alors
‘Erreur : idf non déclaré’ ;
Sinon
empiler(pile-opérande, F, P.nom, P.type) ;
Fsi ;
Fin.

Routine R2
Debut
opérande := dépiler(pile-opérande) ;
empiler(pile-opérande, F, opérande.nom, opérande.type) ;
Fin.

Routine R3
Debut
opérande := dépiler(pile-opérande) ;
empiler(pile-opérande, T, opérande.nom, opérande.type) ;
Fin.
Routine R4
Debut
opérande2 := dépiler(pile-opérande) ;
opérande1 := dépiler(pile-opérande) ;
Si (opérande1.type et opérande2.type sont incompatibles) Alors
‘Erreur : incompatibilités des types’ ;
Sinon
CréerTemp(R) ;
QUAD(Qc) := (*, opérande1.nom, opérande.nom, R);
Qc := Qc + 1 ;
CalculType(opérande1.type, opérande2.type, R-Type) ;
empiler(pile-opérande, T, R, R-Type) ;
Fsi ;
Fin.

Routine R5
Debut
opérande := dépiler(pile-opérande) ;
empiler(pile-opérande, E, opérande.nom, opérande.type) ;
Fin.
Routine R6
Debut
opérande2 := dépiler(pile-opérande) ;
opérande1 := dépiler(pile-opérande) ;
Si (opérande1.type et opérande2.type sont incompatibles) Alors
‘Erreur : incompatibilités des types’ ;
Sinon
CréerTemp(R) ;
QUAD(Qc) := (+, opérande1.nom, opérande.nom, R) ;
Qc := Qc + 1;
CalculType (opérande1.type, opérande2.type, R-Type) ;
empiler(pile-opérande, E, R, R-Type) ;
Fsi ;
Fin.

Instruction de branchement inconditionnel :

On a 2 cas d’utilisation d’une étiquette :

1er cas : 2e cas :

étiquette : <inst> Goto étiquette
Goto étiquette Goto étiquette
Goto étiquette étiquette : <inst>

• Dans le 1er cas, la définition de l’étiquette est connue, donc

l’opérateur BRL peut être directement remplacé par BR vers
début de <inst>
• Dans le 2e cas, la définition de l’étiquette n’est pas connue, on
ne peut pas donc traduite directement Goto en BR

Une étiquette est représentée dans la TS comme suit :

Pour gérer les étiquettes on va utiliser la méthode du chainage

des références

• Dans cette méthode, on génère directement BR, au lieu de

BRL, on lie tous les BR faisant référence à une même étiquette
par la méthode du chainage dans une liste
• Cette liste est créé en utilisant le 2ème champ des quadruplés
BR et le champ adresse de l’étiquette dans la TS
• La champ adresse est le numéro du dernier quadruplé qui fait
référence à l’étiquette

Exemple :
• À la rencontre d’un Goto vers une même étiquette (etiq) : on
génère un BR vers le début du dernier Goto rencontré

• À la rencontre de l’instruction : etiq :<inst> : on met à jour tous

les BR

Schéma de traduction :

<decl-etiq>  Label <list-etiq>

<list-etiq>  <list-etiq>,etiq / etiq
<ref-etiq>  Goto etiq
<inst-etiq>  etiq : <inst>

Découpage de la grammaire :

<decl-etiq>  Label <list-etiq>

<list-etiq>  <list-etiq>,etiq R1 / etiq R1
<ref-etiq>  Goto etiq R2
<inst-etiq>  <debut-inst> <inst>
<debut-inst>  etiq : R3

R1 : permet d’insérer l’étiquette dans la TS

R2 : elle référence une étiquette

R3 : utilisation d’une étiquette

Les routines sémantiques :

Routine R1

Debut
Lookup(tc,P) ;
Si (P = 0) Alors
Insert(tc, P) ;
P.déclare := 1 ;
P.util := 0 ;
P.type := Label ;
P.adresse := 0 ;
Sinon ‘Erreur : double déclaration’ ;
Fsi ;
Fin.
Routine R2

Debut
Lookup(tc,P) ;
Si (P = 0) Alors
‘Erreur : étiquette non déclarée’ ;
Sinon
Si (P.util = 1) Alors // étiquette déjà utilisée
QUAD(Qc) := (BR, P.adresse, , )
Sinon // étiquette non utilisée
QUAD(Qc) := (BR, P.adresse, , ) ;
P.adresse := Qc ;
Fsi ;
Qc := Qc+1 ;
Fsi ;
Fin.
Routine R3

Debut
Lookup(tc,P) ;
Si (P = 0) Alors
‘Erreur : étiquette non déclarée’ ;
Insert( etiq, p) ,
p.type = label, ....
Sinon
Si (P.util = 1) Alors
‘Erreur : double utilisation’ ;
Sinon
a := P.adresse ;
P.util := 1 ;
Tant que (a ≠ 0) Faire
B := QUAD(a, 2) ;
QUAD(a, 2) := Qc ;
A := b ;
Fait ;
Fsi ;
Fsi ;
Fin.

 Résumé des titres