Programme de l’UE
Le compilateur est un outil fondamental pour l’informaticien, qui se situe au coeur de tout développement informatique. Le but de ce cours est de donner aux étudiants une compréhension globale du fonctionnement d’un compilateur en présentant les aspects fondamentaux de la compilation de code natif pour les langages impératifs et à objets. Un accent particulier sera mis sur les méthodes d’analyse sémantique et d’optimisation de programmes utilisées dans les compilateurs récents (icc, gcc, etc). Ces notions de base seront complétées par un panorama des développements récents de la recherche dans le domaine. Enfin, on insistera sur la mise en oeuvre logicielle des différents aspects de la compilation à travers l’écriture d’un compilateur pour un langage impératif simple dans le cadre des travaux pratiques.
Voir la page www du cours.
Plan indicatif du cours
- Analyse lexicale
Automates finis, théorie des analyseurs lexicaux, optimisations, outil Lex. - Analyse syntaxique
Grammaires algébriques, analyse descendante/ascendante, gestion des erreurs, outil Yacc. - Grammaires attribuées
Evaluation dynamique, test de Kennedy-Warren, grammaires S-attribuées, schémas de traduction. - Compilateur simple
Organisation de la mémoire, traduction dirigée par la syntaxe, algorithme de Sethi-Ullman. - Fonctions
Activations, pile de controle, conventions d’appel, fonctions imbriquées. - Production de code intermédiaire
Représentations intermédiaires, forme SSA, optimisations élémentaires. - Sélection d’instructions
Pavage, complexité, programmation dynamique, algorithme de Koes & Goldstein - Allocation de registres
Interférences, coalescing, complexité, algorithmes « historiques » (Chaitin, Briggs), algorithmes de référence (IRC, Linear scan). - Analyse de programme
Analyse statique/dynamique, complexité, analyse de flot de données, exemples, limites. - Compilation polyédrique
Contrôle statique, opération, analyse de dépendences, ordonnancement, génération de code. - Compilation des langages à objet
Descripteurs, liaison dynamique, résolution des méthodes abstraites, héritage multiple.
Références
- Modern compiler implementation in C. Andrew Appel. Cambridge press.
- Compilers: principles, techniques and tools. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman. Interéditions.
- Parsing theory, volumes I et II. Seppo Sippu and Eljas Soisalon-Soininen. EATCS Monographs on Theoretical Computer Science.
- Principles of program analysis. Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Springer.
- Theory of linear and integer programming. Alexander Schrijver. Wiley.
Intervenants
- Christophe Alias, CR Inria
- Guillaume Iooss, doctorant ENS Lyon