Cours Compilation
Dr Fatou KAMARA-SANGARE
UFR de Sciences Appliquées et de Technologie
Université Gaston Berger de Saint-Louis
Chapitre Introductif
Programmation dans le cadre général.
1
Traduire l’algorithme dans un langage de programmation
=
Programme source
2
Traduire ce programme source dans une forme qu’un
ordinateur puisse exécuter
=
Compilation /interprétation
3
Lancer le programme traduit
=
exécution
Programmation dans le cadre général.
Définitions
Définition
Un compilateur est un programme qui
1. lit un programme écrit dans un langage de programmation, appelé
langage source en indiquant les éventuelles erreurs détectées dans le
programme source ;
2. traduit ce programme dans un autre langage, appelé langage cible.
Définition
Un compilateur est chargé de transformer un programme source en instructions
exécutables par la machine. Il est constitué de plusieurs phases. Chaque phase
transforme le programme source en une représentation intermédiaire.
Définitions
Programme Compilateur Programme cible
Source
Erreur
Définitions
Exemple 1 :
Fichier.C Compilateur Fichier.o
Erreur
Exemple 2 :
[Link] Programme cible [Link]
Erreur
Définitions
Interpréte
L’interprète est un type répandu de langage qui effectue en même temps la
traduction et l’exécution
Un interprète est un programme qui prend en entrée un programme source et
les données et calcule le résultat
Le principe de fonctionnement est le suivant :
1. lire une instruction
2. exécuter l’instruction
3. passer à l’instruction suivante
4. recommencer
Définitions
Interpréte
Programme Interprète Résultat
source
Données
Exemples de langages interprétés
Exemple 1 : Python
[Link] interprète Résultat
Données
Exemple 2 : prolog
[Link] interprète Résultat
Données
Etude comparative
Avantages inconvénients
Langage compilé La phase de traduction est effectuée Phase de traduction complexe
une seule fois
Eventuellement non portable
Exécution rapide
Un langage compilé assure la
sécurité du code
Langage interprété Phase de traduction simple La phase de traduction est effectuée
plusieurs fois pour chaque exécution
plus précis dans ses diagnostics
d’erreurs Exécution est lente
Certaines erreurs peuvent
éventuellement être ignorées
C’est quoi un compilateur
Programme
Cible
Programme
source
Phase d’analyse
Phase de synthèse
Compilateur 12
Introduction
Phases d’un compilateur
La partie analyse permet de vérifier la validité du programme source. L'analyse
décompose le code source en ses constituants et permet de créer une
représentation intermédiaire. Elle regroupe les étapes suivantes :
1. Analyse lexicale
2. Analyse syntaxique
3. Analyse sémantique
La partie synthèse produit le langage cible en fonction des représentations
intermédiaires obtenues pendant l’étape de l’analyse et des informations obtenues
de la table des symboles. Elle regroupe les étapes suivantes :
1. Génération de code
2. Optimisation de code
3. Production de code
La table des symboles conserve des informations sur l’ensemble du programme
source. Elle rassemble toutes les informations des identificateurs.
Phases d’un compilateur :
Analyse lexicale
Décomposition du programme source (suite de caractères ) en un ensemble de
lexèmes ou mots.
Un lexème est une suite de caractères significative associé à une unité lexicale de
la forme nom d’unité lexicale, valeur d’attribut
nom d’unité lexicale = symbole abstrait (identificateur, opérateur, …)
valeur d’attribut = une entrée de la table des symboles
Phases d’un compilateur :
Analyse lexicale
Supposons par exemple qu’un programme source contienne l’affectation
(1) position =initiale + vitesse*60
Lexème identificateur référence Représentation
Intermédiaire
position id1 1 < id1,1>
= <=>
initiale id2 2 <id2, 2>
+ <+>
vitesse id3 3 <Id3,3>
* <*>
60 < 60 >
Représentation de (1) après l’analyse lexicale :
< id1,1>< = ><id2, 2>< + ><Id3,3>< * >< 60 >
Phases d’un compilateur :
Analyse lexicale
En résumé
L’analyse lexical permet de
Traduire une suite de caractères en une suites de lexèmes (mots)
Déterminer la classe d’appartenance du lexème
Pré-requis
Langages réguliers (expression régulière, grammaire
régulière)
Phases d’un compilateur :
Analyse Syntaxique
Elle reçoit une suite d’unités lexicales générée par l’analyseur lexical et vérifie le
code source est syntaxiquement correcte par rapport à la grammaire du langage
Elle utilise le nom d’unité lexicale pour créer une représentation intermédiaire
Représentation intermédiaire = arbre abstrait dans lequel les nœuds abstraits et
les feuilles représentent respectivement les non terminaux et les terminaux
On distingue
1. Analyseur Syntaxique Descendant où l’arbre est construit en partant de la
racine vers les feuilles
2. Analyseur Syntaxique Ascendant où l’arbre est construit en partant des
feuilles vers la racine
Phases d’un compilateur :
Analyse Syntaxique
L'analyse syntaxique
1. reçoit une chaîne d’unités lexicales de l’analyseur lexical
2. vérifie que la chaîne est produite par la grammaire du langage en
a. construisant un arbre d’analyse pour les programmes bien formés
b. signalant des erreurs dans le cas contraire
Le principe de la vérification
Soit G la grammaire du langage
Soit m un lexème (mot) reçu de l’analyseur lexical
Alors l’analyseur syntaxique doit vérifier si m appartient au langage
généré par G
Phases d’un compilateur :
Analyse Syntaxique
En d’autres termes
1. Définir la grammaire du langage G
2. Demander un lexème (mot) m à l’analyseur lexical
3. vérifier si m appartient au langage généré par G
a. Si m est une phrase du langage alors
Produire l’arbre de dérivation (arbre de syntaxe)
b. Sinon
Corriger l’erreur
Phases d’un compilateur :
Analyse Syntaxique
Représentation de (1) après l’analyse lexicale :
< id1,1>< = ><id2, 2>< + ><Id3,3>< * >< 60 >
Position
+
*
Initiale
vitesse 60
Phases d’un compilateur :
Analyse Syntaxique
L’analyseur syntaxique (parseur)
utilise les premiers composants des unités lexicales pour
Construire l’arbre d’analyse
gérer les erreurs
a pour Pré-requis une grammaire non contextuelle
Phases d’un compilateur :
Analyse Sémantique
Elle utilise l’arbre abstrait produit lors de la phase d’analyse syntaxique et la table
des symboles pour vérifier que le programme source est sémantiquement correct
vis-à-vis de la définition du langage.
Elle permet de contrôler si le programme source contient des erreurs
sémantiques (Utilisation d’une variable non définie, Multiplication d’un entier par
une chaîne de caractères, …).
L’analyseur sémantique dispose d’un contrôleur de type qui permet de vérifier que
les opérandes de chaque opérateur sont valides.
Phases d’un compilateur :
Analyse Sémantique
Si dans l’exemple (1)
les variables position, initiale et vitesse sont des réels alors
60 représente une constante entière
Alors
L’entier est converti en réel
=
Position
+
*
Initiale
vitesse Conversion
Entier-réel
60.0
Phases d’un compilateur :
Génération de code
A l’issue de analyse sémantique, une représentation intermédiaire est produite.
Elle est très proche de la machine
Elle a deux impératifs : être facile à produire et être facile à traduire vers
une machine
Le code intermédiaire généré pour position = initiale + vitesse*60 après la phase
d’analyse est la suivante
t1 inttofloat(60)
t2 id3*t1
t3 id2+t2
Id1=t3
Phases d’un compilateur :
Optimisation de code
Cette phase consiste à optimiser le code obtenu lors de la phase de génération de
code. il en résulte un code intermédiaire qui s'exécute plus facilement.
Elle permet d’améliorer la représentation intermédiaire. L’amélioration repose sur
la rapidité, la taille du code, …
La conversion de 60 vers un réel peut se faire une seule fois durant toute la
compilation. Ainsi, l'opérateur inttofloat sera remplacé par 60.0 et t2 et t3 peuvent
être supprimés
t1 id3*60.0
Id1=id2+t1
Phases d’un compilateur :
Production de code
Cette phase consiste à désigner pour chaque variable des registres ou des
adresses mémoires. Les instructions sont traduites en instructions machine qui
effectuent la même tâche.
LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R 2
STF id1, R1
Les différentes étapes
Programme source
Analyse Lexicale
Production de code
Partie analyse Partie Synthèse
Analyse Syntaxique Optimisation de code produit le langage
• décompose le cible en fonction des
code source en représentation
ses constituants sémantique Génération de Code intermédiaires
obtenues pendante
• Produit une l’étape de l’analyse et
représentation des informations
intermédiaire obtenues de la table
des symboles
Table des Symboles
Gestion des erreurs
La table des symboles
Elle est une structure de données qui rassemble toutes les informations utiles
concernant les variables et les fonctions ou procédures du programme
Pour toute variable, elle garde l’information de :
son nom
son type
sa portée
son adresse en mémoire
Pour toute fonction, elle garde l’information de :
son nom
sa portée
le nom et le type de ses arguments, ainsi que leur mode de passage
éventuellement le type du résultat qu’elle fournit
Suite de caractères
Code pour la machine cible Générateur de code
Suite de caractères Code pour la machine cible
Analyseur lexical Générateur de code
Suite d’unités lexicales
Représentation intermédiaire
Analyseur Syntaxique
Optimiseur de code Indépendante
Arbre abstrait
de la machine
Arbre abstrait
Représentation intermédiaire
Analyseur Sémantique
Code intermédiaire 29
Générateur de code intermédiaire
Introduction
Analyseur lexical Analyseur syntaxique Analyseur Sémantique
Position = initiale + vitesse * 60 Id1 = id2 + id3 *60
Table Des symbole =
LDF R2, id3
MULF R2, R2, #60.0 Position
LDF R1, id2 id1 position +
ADDF R1, R1, R2 *
id2 initiale Initiale
STF id1, R1
id3 vitesse vitesse Conversion
Entier-réel
60
Optimiseur de code Générateur de code
Production de code
t1 inttofloat(60)
t1 id3*60.0 T2id3+t1
Id1=id2+t1 T3id2+t2 30
Id1=t3
Introduction
Plan du cours
I. Analyse lexicale
II. Analyse Syntaxique
III. Analyse Sémantique
1. Aho, Lam Sethi, Ullman : « Compilateurs : principes, techniques et outils »,
deuxième éditions, 2007, ISBN : 978-2-7440-7037-2