Vincent Balat

Cours de compilation 2009/2010

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.

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 2 (et non 3 comme dit au premier cours) mais les notes de projet seront individuelles.

Voici l'énoncé du projet.

Vous pouvez récupérer le code fourni avec la commande darcs get lucien:/ens/henry/compil/projet-codefourni depuis le réseau de l'UFR.

L'utilisation de darcs est obligatoire, même si vous faites le projet seul. Vous devrez montrer lors de la soutenance que vous avez fait régulièrement des patchs au cours du semestre. Pensez à les faire régulièrement. Un seul gros patch à la fin du semestre n'est pas une bonne solution !

Liens

Salles et horaires sur le site de l'UFR
Chargés de TD/TP : Jaap Boender, Mehdi Dogguy et Grégoire Henry.

Calendrier et notes de cours

Les notes de cours apparaîtront ici progressivement :

23 septembre 2009 : Introduction
PDF
30 septembre 2009 : Assembleur MIPS
PDF
example.s
factiter.s
7 octobre 2009 : 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 (obligatoire) : Au départ, on ne réserve pas de place pour les paramètres des fonctions appelées. Avant chaque appel de fonction on réserve la place nécessaire pour ses paramètres (en déplaçant sp), puis on remet sp à sa place initiale juste après l'appel.
14 octobre 2009 : Rappels d'analyses lexicale et syntaxique, arbre de syntaxe abstraite
PDF
21 et 28 octobre 2009 : Table des symboles, niveaux, décalages
PDF
3 novembre 2009 : Génération de code intermédiaire
PDF Mise à jour du 17/11
11 novembre 2009 : férié
18 novembre 2009 : Linéarisation du code intermédiaire
25 novembre 2009 : Production de code assembleur et allocation naïve
PDF
2 décembre 2009 : Analyse de durée de vie des variables et allocation des registres par coloriage de graphes
PDF

Ces notes de cours sont très largement tirées de celles de Roberto Di Cosmo d'il y a quatre ans, elles-mêmes inspirées du cours de Didier Rémy et du livre d'Andrew Appel.

Archive du cours 2008/2009

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

Le processeur MIPS et l'émulateur MARS

Voici une brève documentation du processeur MIPS (en fait d'un autre émulateur appelé SPIM), avec toutes les instructions.

Télécharger l'émulateur Mars pour l'utiliser chez vous. Voici quelques informations sur Mars.

Langage OCaml : Bibliographie et liens

Xavier Leroy et al. The Objective Caml system : documentation and user's manual
manuel en ligne (à toujours avoir sous la main)
Page de OCaml à l'INRIA
Emmanuel Chailloux, Pascal Manoury et Bruno Pagano. Développement d'Applications avec Objective Caml. O'Reilly, 2000
disponible en ligne
Guy Cousineau et Michel Mauny. Approche fonctionnelle de la programmation. Dunod, 1995
(cf lien1 et lien2).
Pierre Weis et Xavier Leroy. Le langage Caml Dunod, 1999.
Catherine Dubois et Valérie Ménissier-Morain. Apprentissage de la programmation avec OCaml. Hermès, 2004
(cf lien).
Louis Gacogne. Programmation par l'exemple en Caml. Ellipse, 2004
(cf lien).
Philippe Narbel. Programmation fonctionnelle, générique et objet : Une introduction avec le langage OCaml. Vuibert, 2005
(cf lien).