Chapitre I

Introduction à la Compilation

1 Compilateurs

2 Phases de Compilation

3 Qualité d’un compilateur

4 Outils pour la construction de compilateurs

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 1 / 19

 Compilateurs

Introduction

Évolution des langages

Langage machine
Langage assembleur
Langages évolués :
Algorithmiques : C, PASCAL, ADA
Logiques : PROLOG
Langages de 4ème génération

Qu’est ce qu’un compilateur ?

Un compilateur est un programme qui lit un programme écrit dans
un premier langage (langage source) et le traduit en un
programme équivalent écrit dans un autre langage (le langage
cible).

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 2 / 19

 Compilateurs

Introduction

Au cours de ce processus de traduction

Le compilateur signale à son utilisateur la présence d’erreurs dans
le programme source.

PSource Compilateur PAssembleur

Messages d’erreur

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 3 / 19

 Phases de Compilation

1. Phases de compilation

On distingue deux catégories :

Phases d’analyse
Partitionne le programme source en ses constituants et en crée une
représentation intermédiaire.
Phases de synthèse ou de production
Construit le programme cible à partir de la représentation
intermédiaire.

Phase d’analyse Phase de production

Analyse lexicale Génération de code intermédiaire
Analyse syntaxique Optimisation de code
Analyse sémantique Génération de code

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 4 / 19

 Phases de Compilation

2. Structure d’un compilateur

PSource

Analyse lexicale

Gestion de la Analyse Syntaxique Gestion des

table de erreurs
symboles Analyse sémantique

Génération de code
intermédiaire

Table des Optimisation de code

identificateurs,
mots réservés Génération de code
et constantes machine

PCible

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 5 / 19

 Phases de Compilation

2. Structure d’un compilateur

PSOURCE

Partie frontale

Partie terminale

PASSEMBLEUR

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 6 / 19

 Phases de Compilation

2. Structure d’un compilateur

PSOURCE

Analyse

Partie frontale
Génération de code
intermédiaire

PLI

Générateur de code
Partie terminale machine

PASSEMBLEUR

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 6 / 19

 Phases de Compilation

3. Analyse lexicale

Analyse lexicale ou linéaire

Au cours de laquelle le flot de caractères formant le programme
source est lu de gauche à droite.
Ce flot de caractères est groupé en unités lexicales qui sont une
suite de caractères ayant une signification collective
Ces unités lexicales (tokens) : identificateurs, constantes,
opérateurs, séparateurs (parenthèses ou points virgules) ou mots
clefs du langage

Flot de Analyseur Flot d’unités

caractères Lexical lexicales

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 7 / 19

 Phases de Compilation

3. Analyse lexicale

Exemple
L’analyse lexicale de l’instruction d’affectation :
position := initiale + vitesse*60
Regroupe les caractères formant cette instruction en des unités
lexicales qui sont les suivantes :
1 L’identificateur position ;
2 Le symbole d’affectation := ;
3 L’identificateur initiale ;
4 Le signe + ;
5 L’identificateur vitesse ;
6 Le signe * ;
7 Le nombre 60 ;

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 8 / 19

 Phases de Compilation

4. Analyse syntaxique

Analyse syntaxique, hiérarchique ou grammaticale

Consiste à regrouper les unités lexicales du programme source en
structures grammaticales qui seront utilisées par le compilateur
pour synthétiser le résultat
Les phrases grammaticales sont représentées par un arbre
syntaxique dont les feuilles concordent avec la suite d’unités
lexicales en les parcourant de gauche à droite.

Unité lexicale
PSOURCE
Analyseur Analyseur
Lexical Syntaxique
Obtenir prochaine
unité lexicale

Table des
Symboles

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 9 / 19

 Phases de Compilation

4. Analyse syntaxique

Exemple
L’instruction position := initiale + vitesse*60 est générée par la
grammaire :
P → id := Exp ;
Exp → id|nb|(Exp)|Exp + Exp|Exp ∗ Exp
L’analyse syntaxique génère l’arbre syntaxique suivant :
P

id := Exp
Exp + Exp

id Exp * Exp

id nombre
Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 10 / 19
 Phases de Compilation

5. Analyse sémantique

Dans cette phase, on opère certains contrôles (contrôles de type,

par exemple) afin de vérifier que l’assemblage des constituants du
programme a un sens. On ne peut pas, par exemple, additionner
un réel avec une chaı̂ne de caractères, ou affecter une variable à
un nombre.
Dans le contrôle de type, l’analyseur sémantique peut insérer des
opérations de conversion pour les expressions d’entier vers réel.
Nous distinguons deux types d’erreurs sémantiques :
sémantiques statiques : contrôlées au moment de la compilation
(variable non déclarée, incompatibilité de type, portée d’une
variable)
sémantiques dynamiques : contrôlées au moment de l’exécution
(division par zéro, boucles infinies, débordement mémoire)

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 11 / 19

 Phases de Compilation

5. Analyse sémantique

Exemple
Une Contrainte sémantique doit être vérifiée :
L’opérateur de multiplication doit être appliqué à deux opérandes de
même type (entier, entier) ou (réel, réel)
Pour notre exemple, Vitesse est un réel et 60 est un nombre entier,
il faut alors convertir 60 d’entier vers réel (60.0)

Var P
position, Initiale, Vitesse : réel;
id := Exp
Analyseur Sémantique
Exp + Exp
Table des id de variables
N° Lexème Type id Exp * Exp
1 Position Réel
id nombre
2 Initiale Réel entier vers réel
3 Vitesse Réel 60 60.0

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 12 / 19

 Phases de Compilation

6. Phase de génération de code intermédiaire

Phase de génération de code intermédiaire

Au cours de laquelle la séquence d’instructions du programme est
traduite en une séquence d’instructions dans un langage
intermédiaire (le langage pour machine à pile, le langage C, )
La représentation intermédiaire doit avoir être :
1 facile à produire
2 facile à traduire en langage cible

Exemple : traduction en un code à trois adresses

Temp1 := EntierVersR éel(60) ;
Temp2 := Temp1 ∗ id3 ;
Temp3 := id2 + Temp2 ;
id1 := Temp3 ;

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 13 / 19

 Phases de Compilation

7. Optimisation de code

Optimisation de code
Cette phase tente d’améliorer le code produit de telle sorte que le
programme résultant soit plus rapide : élimination du code d’une
fonction jamais appelée, propagation des constantes, extraction
des boucles des invariants de boucle.

Exemple
Temp1 := id3 ∗ 60.0 ;
id1 := id2 + Temp1 ;

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 14 / 19

 Phases de Compilation

8. Génération de code cible

Génération de code cible

Il s’agit de produire les instructions en langage cible qui est dans
ce cas défini par le type de processeur utilisé.

Exemple
Génération de code intermédiaire (Machine VON NEUMAN)
Machine à registres
MOVF id3, R2
MULF 60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 15 / 19

 Phases de Compilation

9. Phases parallèles

1. Gestion de la table des symboles

La table des symboles Contient des informations sur les différents
symboles et les attributs associés.
Par exemple les mots clés (ou réservés) et les identificateurs de
variables en spécifiant l’unité lexicale id et leurs attributs : type,
adresse, etc
A chaque fois qu’une unité lexicale id est trouvée par l’AL, le
lexème associé est inséré dans la table des symboles s’il n’a pas
été déjà inséré et l’AL retourne id et un pointeur vers une entrée
de la table des symboles.

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 16 / 19

 Phases de Compilation

7. Phases parallèles

2. Gestion des erreurs

Chaque phase peut rencontrer des erreurs. Il s’agit de les
détecter et d’informer l’utilisateur le plus précisément possible :
erreur de syntaxe, erreur de sémantique...
Un compilateur qui se contente d’afficher syntax error n’apporte
pas beaucoup d’aide lors de la mise au point.

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 17 / 19

 Qualité d’un compilateur

Qualité d’un compilateur

Fournir le maximum d’erreurs en une seule compilation

Rapidité

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 18 / 19

 Outils pour la construction de compilateurs

Outils pour la construction de compilateurs

Écriture en langage évolué

Constructeurs automatiques de compilateurs : LEX et YACC

Générateur automatique
d’analyseur syntaxique
Grammaire non
Analyseur Syntaxique
contextuelle du Yacc Écrit en C ou en LPascal
langage
Générateur automatique
d’analyseur lexical
Description
des unités Lex Analyseur lexical
lexicales du Écrit en C ou en LPascal
langage

Yousra Bendaly Hlaoui (ISITCOM) Introduction à la compilation 2011-2012 19 / 19