Compilation
I. Introduction
Jacques Farre
[Link]@[Link]
[Link]
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
1/17
Plan du cours et modalites de contole
le cours comprend 3 parties
introduction et analyse lexicale (3 s
eances)
analyse syntaxique (5 s
eances)
analyse s
emantique et interpretation (4 seances)
contr
oles
1 examen final de 2h (40%)
projet (30%, fait en grande partie pendant les TPs ; lactivit
e
en TP sera prise en compte dans cette note)
3 interrogations en TD de 30 mn (30%)
18 fevrier (analyse lexicale)
25 mars (analyse syntaxique)
6 mai (analyse semantique et interpretation)
pr
esence aux TDs et TPs obligatoire (sinon malus)
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
2/17
Introduction
Compilation : traduction dun langage dans un autre
pas seulement des langages de programmation : langages de
script, dinterrogation, de description (LaTeX, XML . . . )
pas seulement pour obtenir un programme ex
ecutable :
enjoliveurs, editeurs syntaxiques . . .
concepts et outils utilis
es dans de nombreux autres domaines :
web, bases de donnees, traitement des langues naturelles . . .
Concepts et outils fondamentaux
th
eorie des langages (grammaires, automates)
s
emantiques formelles
algorithmes et structures de donn
ees varies
principes de g
enie logiciel
Vous rencontrerez in
evitablement un jour ou lautre un
probl`eme de compilation dans votre vie professionnelle
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
3/17
Terminologie
langage source : celui quil faut analyser
langage objet : celui vers lequel il faut traduire
langage machine ou dassemblage : langage machine sous
forme symbolique
traducteur : passage dun langage `
a un autre, par exemple
pr
eprocesseur : dun sur-langage de L vers L (C par exemple)
assembleur : du langage dassemblage vers le code machine
binaire
editeur de liens : dun ensemble de sous-programmes en binaire
relogeable (les .o de linux par exemple) vers un programme
executable
compilateur : traduction dun langage source (g
eneralement)
de haut niveau vers un langage de plus bas niveau
d
ecompilateur : programme qui essaye de reconstruire le
programme source `a partir du code objet
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
4/17
Compilateur et interpr`ete
donn
ees
programme
en langage
source
COMPILATEUR
programme
en langage
objet
donn
ees
INTERPRETATION
programme
en langage
source
forme
interne
TRADUCTION
avantages et inconv
enients de chaque mod`ele
compilateur : produit du code machine programme efficace
mais pas toujours portable
interpr`
ete : programme portable mais moins efficace, mais qui
peut manipuler le code source (meta-programmation)
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
5/17
Compilation croisee
Les traducteurs (compilateurs et interpr`
etes) sont des
programmes comme les autres
ils sont
ecrits dans un certain langage de programmation
la diff
erence est quils prennent des programmes comme
donnees et produisent (compilateurs) du code executable
Diagramme en T :
Compilateur de S
vers un code O
implante sur
une machine X :
compilateur de S vers O sur machine X
programme
ecrit en
langage S
par exemple, compilateur Objective C sur un
PC pour processeur embarque
LANGAGE
SOURCE S
LANGAGE
OBJET O
programme
ex
ecutable
sur machine O
LANGAGE
DEXECUTION X
machine X
compilateur de Objective C pour processeur ARM
compilation sur machine Intel
programme en
Objective C
Objective C Code ARM
programme en
code ARM
Compilateur
en code 80x86
PC
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
6/17
Comment obtenir un compilateur ?
on l
ecrit dans un langage E (de haut niveau si possible)
on suppose quon dispose dun compilateur de ce langage sur
une machine X
par exemple, un compilateur de Java
ecrit en C sur un PC :
S = Java, O = JVM, E = langage C, X = code intel core
LANGAGE
LANGAGE
LANGAGE
LANGAGE
SOURCE S
OBJET O
SOURCE S
OBJET O
LANGAGE
DECRITURE E
LANGAGE
LANGAGE
LANGAGE
SOURCE E
OBJET X
DEXECUTION X
LANGAGE
DEXECUTION X
machine X
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
7/17
Comment obtenir un auto-compilateur ?
si on veut
ecrire le compilateur dans son propre langage S
ecrire dabord un compilateur dun sous-ensemble S de S en
E, et le compiler
ecrire ensuite en S le compilateur de S
cest ce quon appelle un bootstrap du compilateur
LANGAGE
LANGAGE
LANGAGE
LANGAGE
SOURCE S
OBJET O
SOURCE S
OBJET O
LANGAGE
DECRITURE E
LANGAGE
LANGAGE
SOURCE E
OBJET X
LANGAGE
DEXECUTION X
LANGAGE
DEXECUTION X
LANGAGE
LANGAGE
SOURCE S
OBJET O
machine X
LANGAGE
LANGAGE
LANGAGE
DECRITURE S
SOURCE S
OBJET O
LANGAGE
LANGAGE
SOURCE S
OBJET O
LANGAGE
DEXECUTION O
LANGAGE
DEXECUTION X
machine X
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
8/17
Compilateurs monolithiques
les premiers compilateurs
etaient monolitiques : ils pouvaient
travailler en 1 seule passe (les langages etaient encore simples)
autant de compilateurs que de couples (langage, machine
cible), soit m n
langage
source 1
COMPILATEUR 1-1
langage
objet 1
langage
source 1
COMPILATEUR 1-n
langage
objet n
langage
source 2
COMPILATEUR 2-n
langage
objet n
langage
source m
COMPILATEUR m-1
langage
objet 1
langage
source m
COMPILATEUR m-n
langage
objet n
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
9/17
Compilateurs modulaires
langage
source
PARTIE
AVANT
repr
esentation
interm
ediaire
PARTIE
`
ARRIERE
langage
objet
partie avant (analyse) : analyses lexicale, syntaxique,
semantique (cours de L3)
partie arri`
ere (synth`ese) : optimisation, production de code
(cours de M1)
avantages de cette d
ecomposition : m parties avant + n
parties arri`eres permettent davoir m n compilateurs
langage
source 1
PARTIE
AVANT 1
langage
source m
PARTIE
AVANT m
repr
esentation
interm
ediaire
PARTIE
`
ARRIERE
1
langage
objet 1
PARTIE
langage
objet n
`
ARRIERE
n
le langage objet peut
etre celui dune machine virtuelle
(JVM . . . ) : le programme resultant sera portable
on peut interpr
eter la representation intermediaire
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
10/17
Schema synthetique de la partie avant
COMPILATEUR
demande
lanalyse
syntaxique
ANALYSEUR
SYNTAXIQUE
demande
un lex`eme
construit
repr
esentation
interm
ediaire
renvoie un
lex`
eme
ANALYSEUR
LEXICAL
demande
lanalyse
semantique
consulte
ANALYSEUR
SEMANTIQUE
TRAITEMENT
DES ERREURS
langage
source
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
11/17
Justification de larchitecture de la partie avant
du point du vue lexico-syntaxique
le programme source est plein de bruits (espaces inutiles,
commentaires . . . )
pour la grammaire, de nombreux symboles sont
equivalents
(identificateurs, nombres . . . )
ce qui justifie le pr
e-traitement (en general au vol) du texte
source par lanalyseur lexical
du point de vue s
emantique
existence de r
eferences en avant (utilisation dun identificateur
avant sa declaration par exemple)
unification du traitement de constructions
equivalentes
(attr=0 et [Link]=0 par exemple) ou proches (boucles
notamment)
ce qui justifie la m
emorisation (sous forme intermediaire) du
texte `a compiler
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
12/17
Concepts et structures de donnees utilises
analyse lexicale : langages r
eguliers, expressions reguli`eres,
automates finis pour lessentiel, mais aussi tables dadressage
disperse, arithmetique
analyse syntaxique : grammaires hors-contexte, automates `
a
pile (analyseurs descendants ou ascendants), attributs
semantiques
analyse s
emantique : diverses semantiques formelles (mais
lanalyse semantique est souvent codee `a la main), equations
de type, table de symboles
repr
esentation interm
ediaire : arbre ou graphe le plus
generalement
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
13/17
Un exemple
Soit en Java : if (i==0) --ifou;
analyse lexicale : reconnatre les lex`
emes : mot-cle if (mais
pas dans lidenticateur ifou), reconnatre i et ifou comme
lex`emes de la classe identificateur, 0 comme de la classe des
nombres entiers, -- comme un seul lex`eme, et pas la suite - analyse syntaxique et repr
esentation interm
ediaire :
analyser le texte selon la r`egle de grammaire :
instruction MOT-IF ( condition ) instruction
et construire (par exemple) un sous-arbre comme
IF
sous-arbre de
la condition
sous-arbre de
linstruction
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
14/17
Un exemple (suite)
Soit en Java : if (i==0) --ifou;
analyse s
emantique :
analyse de nom : v
erifier que i et ifou sont bien declares, et
declares comme des variables (ou des attributs) ; met en uvre
la table des symboles, qui permet de memoriser les symboles
declares (classes, attributs, methodes, variables locales et
param`etres . . . )
analyse de type : v
erifier que le type de i ou celui de ifou est
compatible avec les operations effectuees ; met en uvre des
equations de type du genre int == int bool
peut travailler en 1 ou plusieurs parcours de la repr
esentation
intermediaire (selon la complexite du langage)
peut transformer/enrichir/normaliser la repr
esentation
intermediaire
par exemple, si ifou est un attribut, representer de la meme
mani`ere --ifou et --[Link]
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
15/17
Proprietes dun bon compilateur
Reconnatre tout le langage, et rien que le langage (ou alors
avoir un mode permettant dinformer des constructions non
standards)
sinon, on accepte des programmes non portables
Ne pas se restreindre `
a des constructions humainement
lisibles : beaucoup de programmes sont crees par des
programmes
Indiquer de facon claire les erreurs et
eviter les messages
derreur en cascade (bien que la source de lerreur ne soit pas
toujours evidente)
Traduire correctement vers le langage cible, et en donnant le
meilleur code possible
Etre
raisonnablement rapide (utiliser des algorithmes quasi
lineaires)
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
16/17
Bibliographie
Les bases
Compilateurs. Dick Grune , Henry E. Bal , Ceriel J.H. Jacobs ,
Koen G. Langendoen, Dunod 2002
Compilateurs - Principes, techniques et outils - Avec plus de
200 exercices. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey
D. Ullman, Pearson Education, 2007
Compiler Design. Reinhard Wilhelm et Dieter Maurer,
Adison-Wesley, 1995.
Pour les mordus de th
eorie
The Theory of Parsing, Translation and Compiling (2 volumes).
Alfred V. Aho et Jeffrey D. Ullman, Prentice-Hall 1972
Parsing Theory (2 volumes). Seppo Sippu et Eljas
Soisalon-Soininen, Springer-Verlag 1992
Universit
e de Nice - Sophia Antipolis Licence 3 Informatique 2012-2013
17/17
