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

  1. Analyse lexicale
    Automates finis, théorie des analyseurs lexicaux, optimisations, outil Lex.
  2. Analyse syntaxique
    Grammaires algébriques, analyse descendante/ascendante, gestion des erreurs, outil Yacc.
  3. Grammaires attribuées
    Evaluation dynamique, test de Kennedy-Warren, grammaires S-attribuées, schémas de traduction.
  4. Compilateur simple
    Organisation de la mémoire, traduction dirigée par la syntaxe, algorithme de Sethi-Ullman.
  5. Fonctions
    Activations, pile de controle, conventions d’appel, fonctions imbriquées.
  6. Production de code intermédiaire
    Représentations intermédiaires, forme SSA, optimisations élémentaires.
  7. Sélection d’instructions
    Pavage, complexité, programmation dynamique, algorithme de Koes & Goldstein
  8. Allocation de registres
    Interférences, coalescing, complexité, algorithmes « historiques » (Chaitin, Briggs), algorithmes de référence (IRC, Linear scan).
  9. Analyse de programme
    Analyse statique/dynamique, complexité, analyse de flot de données, exemples, limites.
  10. Compilation polyédrique
    Contrôle statique, opération, analyse de dépendences, ordonnancement, génération de code.
  11. Compilation des langages à objet
    Descripteurs, liaison dynamique, résolution des méthodes abstraites, héritage multiple.

Références

  1. Modern compiler implementation in C. Andrew Appel. Cambridge press.
  2. Compilers: principles, techniques and tools. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman. Interéditions.
  3. Parsing theory, volumes I et II. Seppo Sippu and Eljas Soisalon-Soininen. EATCS Monographs on Theoretical Computer Science.
  4. Principles of program analysis. Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Springer.
  5. Theory of linear and integer programming. Alexander Schrijver. Wiley.

Intervenants