Compilation (INF564)

J'assure ce cours depuis 2005-2006. J'encadre également les travaux dirigés.

Aperçu

Le cours consiste à étudier et à écrire un compilateur d'un langage impératif simple, baptisé Pseudo-Pascal, vers l'assembleur MIPS. Il permet de comprendre l'étendue et le franchissement du fossé qui sépare langages de haut niveau et langages machine. Il permet également de découvrir des techniques et algorithmes non triviaux et de les exprimer dans un langage de très haut niveau, à savoir Objective Caml. Pour en savoir plus, consultez ces quelques transparents de présentation.

Matériau

Mis dès à présent à votre disposition, mais néanmoins susceptible d'évolution à tout moment.

• Les transparents du premier cours: architecture MIPS (5 janvier 2011);
• Les transparents du deuxième cours: syntaxe, sémantique et interprétation de Pseudo-Pascal (12 janvier 2011);
• Les transparents du troisième cours: analyse lexicale et syntaxique (19 janvier 2011);
• Les transparents du quatrième cours: sélection d'instructions (26 janvier 2011) (séance assurée par Nicolas Pouillard);
• Les transparents du cinquième cours: création du graphe de flot de contrôle (2 février 2011);
• Les transparents du sixième cours: explicitation de la convention d'appel (9 février 2011);
• Les transparents du septième cours: analyse de durée de vie et construction du graphe d'interférences (16 février 2011);
• Les transparents du huitième cours: coloriage du graphe d'interférences (2 mars 2011);
• Les transparents du neuvième cours: arrière du petit compilateur; ramassage de miettes; exceptions (9 mars 2011);
• L'examen écrit aura lieu le 16 mars 2011.
• Une fiche rappelant la syntaxe abstraite de Pseudo-Pascal.
• Une fiche définissant la sémantique de Pseudo-Pascal.
• Téléchargez le code source complet du petit compilateur (version du ...). Pour le compiler, il vous faut GNU make, ocaml et menhir (tous disponibles en salles machines).
• Consultez le code source en ligne. Les modules sont groupés de façon logique et accompagnés d'une courte explication de façon à vous donner une vision d'ensemble de l'architecture du compilateur. Le code est coloré pour en augmenter la lisibilité. De plus, lorsque vous passez votre souris au-dessus d'une variable, son type apparaît!
• Il n'y a pas de poly. J'ai préféré consacrer mon temps à la réécriture complète du petit compilateur qui sert de support au cours.

Références

• Cet excellent manuel, dû à Jim Larus, décrit l'architecture MIPS et son simulateur spim. Les sections A.1 à A.6 se lisent comme un roman: lisez-les donc dès le premier cours! Attention, les définitions des termes caller-saved et callee-saved en marge de la page A.23 ont été interchangées par erreur. Les sections A.9 et A.10 expliquent le simulateur spim et le jeu d'instructions du processeur MIPS.
• Deux très courts documents vous aideront à utiliser spim et xspim.
• Le manuel de référence d'Objective Caml et en particulier la description de sa librairie standard seront utiles. Voici en particulier deux liens directs vers la documentation des signatures Set.S et Map.S, qui définissent les opérations fournies par les instances des modules Set et Map.
• quelques antisèches à propos d'Objective Caml permettent de se remémorer les points les plus importants: le langage, les outils, la librairie standard, le mode emacs.
• Le manuel de référence de Menhir pourra également être utile.
• Le livre Modern Compiler Implementation in ML, d'Andrew Appel, est une excellente introduction à la compilation. Le livre aborde de nombreux sujets que je ne peux traiter en cours, et vous conduit également à écrire votre propre compilateur en ML. Il existe deux versions du livre dans lesquelles le langage d'implantation du compilateur est Java ou C.
• Pour en savoir (beaucoup) plus sur l'analyse syntaxique, le livre Parsing Techniques - Second Edition, de Dick Grune et Ceriel J. H. Jacobs, est excellent et intégralement disponible en ligne.

Remerciements

Merci à Luc Maranget, qui assurait précédemment ce cours, pour son aide. Merci également à Xavier Leroy, dont le compilateur certifié a fortement inspiré l'architecture du petit compilateur que je présenterai en cours.

Contact

Envoyez vos questions ou commentaires à François Pottier.