Cours de compilation - Master 1 IF, ENS Lyon

Le but de ce cours est de donner aux étudiants une vision globale du fonctionnement d'un compilateur pour un langage impératif. Un compilateur pour un sous-ensemble de C vers la machine DigMIPS est construit étape par étape en TP.

Cours

J'ai choisi de dispenser ce cours au tableau, à l'ancienne... Vous ne trouverez donc que quelques slides sur la partie back-end.

1. Analyse lexicale.
   Expressions régulières, automates, descriptions lexicales, interprétation
2. Analyse syntaxique.
   Grammaires, analyse prédictive LL(k), analyse ascendante LR(k)
3. Grammaires attribuées.
   Attributs, actions, grammaires S-attribuées, schémas de traduction, grammaires attribuées générales
4. Types.
   Types statiques, types dynamiques, typage fort, typage faible, polymorphisme
5. Organisation des données.
   Pile, enregistrements d'activation, tas, organisation des tableaux et des structures, construction, traduction des fonctions
6. Traduction dirigée par la syntaxe.
   Schémas de traductions (expressions arithmétiques, conditions, contrôle)
7. Représentations intermédiaires.
   Code intermédiaire, graphe de flot de contrôle, flot de données (DAG), flot de données (SSA), simplifications ("optimisations")
8. Sélection des instructions. slides
   Pavage d'arbres (programmation dynamique), pavage de DAG (ILP, Koes-Goldstein), complexité
9. Ordonnancement. slides
   Sur les arbres (Sethi-Ullman) et les DAG (décomposition en arbre + Sethi-Ullman, randomisation)
10. Allocation des registres. slides
    Interférences, affinités, coloriage biaisé (Chaitin), iterated register coalescing (Appel et George), linear scan (Sarkar), allocation de la pile
11. Analyse statique (introduction à l').
    Sémantique concrète/abstraite, interpétation abstraite, élargissement. Application: invariants simples (intervalles).

TD/TP

1. Architecture cible: DigMIPS. TP TP_en
   Mise à niveau en C++. TP TP_en
2. Analyse lexicale. TP TP_en
   Fichiers: [src0_automaton.tgz] [src0_flex.tgz] [src1_lexer.tgz]
   Corrigé: [flex_corrige.tgz] [lexer_corrige.tgz]
3. Analyse syntaxique. TP TP_en
   Fichiers: [LL.tar.gz] [src0_if.tar.gz] [src1_stmt.tar.gz] [src2_parser.tar.gz] [src3_ETF.tar.gz]
   Corrigé: [LL_correction.tar.gz] [src0_if_correction.tar.gz] [src0_stmt.tar.gz] [src0_parser.tar.gz])
4. Types. TP TP_en TD_en
   Fichier: [dcc_types.tgz]
   Corrigé: [dcc_types_corrige.tgz]
5. Organisation des données. TD TP TP_en
   Fichier: [tp4_src.tgz]
   Corrigé: [tp4_src_correction.tgz])
6. Traduction dirigée par la syntaxe. TD TP TP_en
   Fichier: [tp5_src.tgz]
   Corrigé: [tp5_src_corrige.tgz]
7. Représentations intermédiaires. TP TP_en TD TD_en
   Fichier: [src_tp6.tar.gz]
   Corrigé: [ri_corrige.tar.gz]
8. Génération de code. TP TP_en TD_en [td_corrigé]
   Fichier: [digcc.tgz]
9. Analyse statique. TP_en
   Fichiers: [apron.c] [code.c] [gcd.c]

Partiels/examens passés

• 2009-2010: DM, examen.
• 2010-2011: partiel, examen.
• 2011-2012: partiel, examen.
• 2012-2013: partiel, examen examen (english version).
• 2013-2014: partiel, partiel (english version).

Références

1. Modern compiler implementation in C. Andrew Appel. Cambridge press.
2. Modern compiler design. Dick Grune, Henri Bal, Ceriel Jacobs et Koen Langendoen. Wiley editions.
3. Engineering a compiler. Keith Cooper et Linda Torczon. Morgan Kauffman editions.
4. Compilers: principles, techniques and tools. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman. Interéditions.