Compilation

GL4
 Qu'est ce que la compilation ?

• Un compilateur est un logiciel particulier qui traduit un programme écrit

dans un langage de haut niveau (par le programmeur) en instructions
exécutables (par un ordinateur).

• Terminologie:
– code exécutable= code machine=code objet=code cible
– Code source=programme source
Chaîne de développement d'un
programme
 Compilateurs versus interpréteurs
• Un compilateur est un programme de traduction automatique d'un
programme écrit dans un langage source en un programme écrit dans un
langage cible.
Exemples de langages compilés : Pascal, C, C++, ADA, Fortran, Cobol, etc …

• un interprèteur exécute lui même au fur et à mesure les opérations

spécifiées par le programme source, sans produire de code cible:
– Il analyse une instruction après l'autre puis l'exécute immédiatement.
– A l'inverse d'un compilateur, il travaille simultanément sur le
programme et sur les données.
– Exemples de langages interprétés : BASIC, Scheme, Caml, LISP, Perl,
Prolog, HTML, PHP, etc.
 Compilateurs versus interpréteurs
• L'interpréteur doit être présent sur le système à chaque fois que le
programme est exécuté, ce qui n'est pas le cas avec un compilateur.

• Généralement les interpréteurs sont assez petits, mais le programme est

plus lent qu'avec un langage compilé.

• Avec les interpréteurs, on ne peut pas cacher le code (et donc garder des
secrets de fabrication), toute personne ayant accès au programme peut le
consulter et le modifier.

• Les langages interprétés sont souvent plus simples à utiliser et tolèrent

plus d'erreurs de codage que les langages compilés.
 Langages P-codes
• Il existe des langages qui sont à mi-chemin de l'interprétation et de la
compilation. On les appelle langages P-code ou langages intermédiaires:
– code source traduit (compilé) dans une forme binaire compacte (du
pseudo-code ou p-code) qui n'est pas encore du code machine.
– Lorsque l'on exécute le programme, ce P-code est interprété.
• Par exemple en Java, le source est compilé pour obtenir un fichier
(.class) ''byte code'' qui sera interprété par une machine virtuelle.

• Les interpréteurs de p-code peuvent être relativement petits et rapides, si

bien que le p-code peut s'exécuter presque aussi rapidement que du
binaire compilé. En outre les langages p-code peuvent garder la flexibilité
et la puissance des langages interprétés.
 Pourquoi ce cours
• La compilation n'est pas limitée à la traduction d'un programme
informatique écrit dans un langage de haut niveau en un programme
directement exécutable par une machine, cela peut aussi être :
– la traduction d'un langage de programmation de haut niveau vers un
autre langage de programmation de haut niveau. Par exemple une
traduction de Pascal vers C, ou de Java vers C++, ou de ...
– la traduction d'un langage quelconque vers une autre langage
quelconque (ie pas forcément de programmation) : word vers html,
pdf vers ps, ...
– Interpréteurs de commandes
Lorsque le langage cible est aussi un langage de haut niveau, on parle
plutôt de traducteur.
– la traduction d'un langage de programmation de bas niveau vers un
autre langage de programmation de haut niveau. Par exemple pour
retrouver le code C à partir d'un code compilé (piratage, récupération
de vieux logiciels, ...)
 Bibliographie succincte

• A. Aho, R. Sethi, J. Ullman, Compilateurs : principes, techniques et outils,

InterEditions 1991.
• N. Silverio, Réaliser un compilateur, Eyrolles 1995.
 Structure d'un compilateur

La compilation se décompose en deux phases :

• une phase d'analyse (Partie frontale):
– Analyse lexicale: reconnaissance des variables, instructions,
opérateurs, etc.
– Analyse syntaxique: élaboration de la structure syntaxique du
programme
– Analyse sémantique: vérification de certaines propriétés
sémantiques.
• une phase de synthèse et de production(Partie finale): production
du code cible.
 Analyse lexicale
• Dans cette étape, il s'agit de reconnaître les "types" des "mots" lus.
Pour cela, on lit le programme source de gauche à droite et les
caractères sont regroupés en unités lexicales.

• L'analyse lexicale se charge de:

– éliminer les caractères superflus (commentaires, espaces, ...)
– identifier les parties du texte qui ne font pas partie à proprement
parler du programme mais sont des directives pour le compilateur
– identifier les symboles qui représentent des identificateurs, des
constantes réelles, entière, chaînes de caractères, des opérateurs
(affectation, addition, ...), des séparateurs (parenthèses, points
virgules, ...), les mots clefs du langage, ... C'est cela que l'on appelle
des unités lexicales.

• Outils théoriques utilisés : expressions régulières et automates à

états finis
 Analyse syntaxique

• Il s'agit de regrouper les unités lexicales en structures

grammaticales, de découvrir la structure du programme.
L'analyseur syntaxique sait comment doivent être
construites les expressions, les instructions, les déclarations
de variables, les appels de fonctions, ...
– Exemple. En C, une sélection simple doit se présenter sous la
forme : if ( expression ) instruction
Si l'analyseur syntaxique reçoit la suite d'unités lexicales
MC_IF IDENT OPREL ENTIER ...
il doit signaler que ce n'est pas correct car il n'y a pas de ( juste
après le if

• Outils théoriques utilisés : grammaires et automates à pile

 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, ...

• Outil théorique utilisé : schéma de traduction dirigée par la

syntaxe
 Phases de production:
Génération de code
• Il s'agit de produire les instructions en langage cible.
• En règle générale, le programmeur dispose d'un calculateur concret
(cartes équipées de processeurs, puces de mémoire, ...). Le langage cible
est dans ce cas défini par le type de processeur utilisé.
• Mais si l'on écrit un compilateur pour un processeur donné, il n'est alors
pas évident de porter ce compilateur (ce programme) sur une autre
machine cible

C'est pourquoi on introduit des machines dites abstraites qui font abstraction des
architectures réelles existantes. Ainsi, on s'attache plus aux principes de traduction, aux
concepts des langages, qu'à l'architecture des machines.

• En général, on produira dans un premier temps des instructions pour

une machine abstraite (virtuelle). Puis ensuite on fera la traduction de
ces instructions en des instructions directement exécutables par la
machine réelle sur laquelle on veut que le compilateur s'exécute.
 Phases de production: Optimisation
du code
• Il s’agit d’optimiser le code produit

• Exemples d’optimisations possible:

– Détections de sous-expressions communes dans les expressions
arithmétiques
– Détection d’invariants dans les boucles
– Détection du code mort (Dead code)
– Etc.
 Phases parallèles
• Gestion de la table des symboles:
– La table des symboles est la structure de données utilisée servant à
stocker les informations qui concernent les identificateurs du
programme source (par exemple leur type, leur emplacement
mémoire, leur portée, visibilité, nombre et type et mode de passage
des paramètres d'une fonction, ...)
Le remplissage de cette table (la collecte des informations) a lieu lors
des phases d'analyse. Les informations contenues dans la table des
symboles sont nécessaires lors des analyses syntaxique et sémantique,
ainsi que lors de la génération de code.
• 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 lexicale,
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.
– Mécanismes de reprise de l’analyse
Récapitulatif: structure d’un compilateur
• Pendant toutes les années 50, les compilateurs furent tenus
pour des programmes difficiles à écrire. Par exemple, la
réalisation du premier compilateur Fortran nécessita 18
hommes-années de travail (1957).

• Contrairement à une idée souvent répandue, la plupart des

compilateurs sont réalisés (écrits) dans un langage de haut
niveau, et non en assembleur (facilité de manipulation,
maintenance et portabilité) Par exemple, une version du
compilateur C++ est écrite en C
• Le plus souvent, un compilateur produit du code pour le
microprocesseur sur lequel il s’exécute: compilateur natif

• Mais ce n’est pas toujours le cas:

– On peut également faire de la compilation croisée qui permet
de créer des compilateurs pour des architectures multiples
– On utilise fréquemment les compilateurs croisés pour produire
du code sur les machines embarquées, qui ne disposent souvent
pas de ressources suffisantes pour faire tourner leur propre
compilateur.
• Il est même possible d'écrire un compilateur pour un langage L dans ce
langage L (gcc est écrit en C ) : On utilise un mécanisme d’auto-compilation
(boot-strap):
– un compilateur ou évaluateur élémentaire écrit dans un langage de
bas niveau
– des compilateurs de plus en plus avancés écrits dans le langage de
haut niveau
Le premier compilateur, A-0 System (pour le langage A-0) est
écrit par Grace Hopper, en 1952.
 Plan du cours
I. Analyse lexicale [Link] dirigée par la
1. Principe syntaxe
2. Mise en oeuvre 1. - Définition dirigée par la
II. Analyse syntaxique syntaxe
1. Analyse descendante 2. - Arbre syntaxique décoré
a. Table d'analyse LL(1) 3. - Attributs synthétisés et
b. Analyseur syntaxique hérités
c. Grammaire LL(1) 4. - Attributs synthétisés
d. Récursivité à gauche 5. - Attributs hérités
e. Grammaire propre 6. - Evaluation des attributs
f. Factorisation à gauche IV. Analyse sémantique
2. Analyse ascendante 1. - Principe
a. Analyse SLR(1) 2. - Exemple de contrôleur de
b. AnalyseLR(1) type
c. Analyse LALR(1) V. Génération de code
d. Relations entre les 1. - Code intermédiaire à 3
classes de grammaire adresses
2. - Exemples de générateurs