Cours de compilation 2008/2009
Le but de ce cours est d'étudier les techniques de compilation.
Il est complété par un projet obligatoire consistant en l'écriture
d'un compilateur.
Les techniques d'analyses lexicale et syntaxique (outils Lex et Yacc)
ont été vues en 3e année de licence.
Ce cours se concentrera donc sur les parties propres
d'un compilateur, de l'arbre de syntaxe abstraite à
la génération de code pour une machine cible.
Important : Inscrivez-vous tous à la liste de diffusion
Sujets abordés
- Représentation de code source (syntaxe abstraite).
Structures de données pour les syntaxes abstraites.
- Analyse statique : construction de tables
d'environnements et typage.
- Environnements dynamiques,
modèle d'exécution utilisant une pile,
mécanismes d'appels de procédures.
- Production de code intermédiaire.
- Transformation de code intermédiaire,
production de code assembleur.
- Techniques d'allocation des registres.
- Techniques d'optimisation.
- Allocation de mémoire, aspects statiques et dynamiques.
- Garbage collection.
- Machines virtuelles, exemple de la machine JAVA.
- Traitement des langages objets :
représentation dynamique de la hiérarchie de classes,
interprétation dynamique des messages.
Pré-requis
Langages formels, analyse syntaxique,
bonne connaissance du langage OCaml.
Bibliographie
- Aho, Sethi, Ullman : Compilateurs : Principes, techniques et outils, Inter ditions, 1989.
- Appel: Modern Compiler Implementation in ML, Cambridge University Press, 1998
- Levine, Mason, Brown : Lex et Yacc (Traduction), Editions O'Reilly Internationnal Thomson, 1994.
Soutenances et examen
Date des soutenances : lundi 12 janvier.
Inscrivez-vous au secrétariat bureau 417 (Janis Sitalapresad)
7 rue Watt 4e étage jusqu'à vendredi 16h30.
Projet à rendre par email avec le rapport avant le dimanche 11
janvier minuit.
Examen le mardi 6 à 15h30 en salles 574F et 575F.
Projet
Le projet est partie intégrante du cours,
et sa note correspond à un examen pratique.
Il n'est pas possible d'obtenir de dispense de projet.
Le projet est à faire par groupes de 3 mais
les notes de projet seront individuelles.
Voici l'énoncé du projet.
Pour récupérer le code fourni, tapez :
darcs get /ens/letouzey/compil/projet-codefourni
ou, depuis l'extérieur de l'université :
darcs get http://www.pps.jussieu.fr/~balat/compilation/projet-codefourni
Calendrier et notes de cours
Les notes de cours apparaîtront ici progressivement :
- 24 septembre 2008 : Introduction
- PDF
- 1er octobre 2008 : Assembleur MIPS
- PDF
example.s
factiter.s
- 8 octobre 2008 : Appel de fonctions
- PDF
factorielle récursive naïve boguée
factorielle récursive correcte
Fibonacci récursive,
d'après le code fourni par GCC (adapté pour MARS).
Conventions d'appel pour le projet :
Réserver dès le départ la place nécessaire dans le bloc
pour les paramètres des fonctions appelées. $sp
ne bouge pas pendant le corps de la fonction.
- 15 et 22 octobre 2008 : Rappels d'analyses lexicale et syntaxique, arbre de syntaxe abstraite
- PDF
- 22 octobre 2008 : Table des symboles, niveaux, décalages
- PDF
- 29 octobre et 5 novembre 2008 : Génération de code intermédiaire
- PDF
- 12 novembre 2008 : Production de code assembleur
- PDF
- 19 novembre 2007 : Allocation naïve des registres et analyse de durée de vie des variables
- PDF
- 26 novembre 2007 : Allocation des registres par coloriage de graphes
- 3 décembre 2007 : Fin du coloriage de graphes, exemples
- 10 décembre 2007 : GC
- PDF
(pas de chapitre 9) (version préliminaire)
Ces notes de cours sont très largement tirées de celles de
Roberto Di Cosmo d'il y a trois ans, elles-mêmes inspirées du
cours de Didier Rémy et du livre d'Andrew Appel.
Archive du cours 2007/2008
TD et TP
- Semaine 1 : Pas de TD ni TP
- Semaine 2 : Assembleur MIPS
- PDF
- Semaine 3 : Assembleur MIPS
- PDF
- Semaine 4 : Assembleur MIPS
- PDF,
runtime.s
- Semaine 5 : Arbre de syntaxe abstraite
- PDF
- Semaine 6 et 7 : Niveaux et décalages
- PDF
- Semaine 8 : Code intermediaire
- PDF
- Semaine 8 : Code intermediaire
- PDF
- Semaine 10 : Munch
- PDF