L'unité d'enseignement « Compilation » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Malenfant, jacques.

Description

Introduction à la compilation. Programme source versus programme cible. Phases de la compilation. Arbres de syntaxe abstraite. Génération de code pour une machine de type MIPS R2000/R3000 (SPIM). Analyse lexicale avec lex. Analyse syntaxique avec yacc. Étude de trois compilateurs écrits en C pour des langages graduellement plus complexes : MIL-0 avec affectations et structures de contrôles de base, MIL-1 avec des blocs et MIL-2 avec les procédures.

Objectifs :

La compilation permet d'aborder un programme fondamental de l'informatique, à savoir celui de la traduction d'un langage informatique (dit langage source) dans un langage cible (l'assembleur dans le cas de la compilation). Plus précisément cet enseignement a les objectifs suivants :

* Comprendre les principes de base de fonctionnement d'un compilateur, de l'analyse du texte source au code assembleur en passant par l'arbre de syntaxe abstraite

* Utiliser les outils classiques d'analyse, Lex et Yacc, sur un exemple concret.

* Voir le rôle de mécanismes fondamentaux de l'informatique (par exemple, automates et piles) pour la traduction d'un langage dans un autre.

* Apprendre à analyser, réutiliser un programme conséquent (plusieurs dizaines de milliers de ligne, ici écrit en C) et à l'enrichir.

Contenu :

Les problèmes de la compilation seront illustrés en utilisant comme langage source, le mini-langage MIL de base qui traite des expressions arithmétiques et comprend les instructions de base (lecture, écriture, boucles, conditionnelle) avec variables globales dans sa version MIL-0, blocs (pour avoir des variables locales) dans sa version MIL-1, procédures et fonctions pour MIL-2. La phase d'analyse sera effectuée en utilisant Lex et Yacc. Cette partie comprendra des cours sur la théorie de langages et des automates nécessaires pour la compréhension de Lex et Yacc. La génération de code produira du code assembleur. L'assembleur visé est SPIM (simulateur de processeurs RISC 32 bits de type MIPS R2000/R3000).

On commencera par réaliser un compilateur complet pour MIL-0, en partant d'une solution existante en C qu'il faudra compléter. On passera ensuite à MIL-1, et à MIL-2 en se contentant des procédures et en ne traitant pas les fonctions, faute de temps.

Préalables et buts pédagogiques

Bibliographie

• A. Aho, R. Sethi, et J.D. Ullman. Compilers. Addison-Wesley, 1986. (Traduction française chez InterÉditions, 1990.)

• C. Fraser et D. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummins, 1995.

Contenu indicatif par semaine

1. Introduction, position du problème, plan du cours, présentation de l'environnement de travail.

2. Analyse lexicale - Théorie.

3. Analyse lexicale - Mise en pratique avec Lex sur MIL-0.

4. Analyse syntaxique - Théorie.

5. Analyse syntaxique - Mise en pratique avec Yacc sur MIL-0.

6. Interprétation de MIL-0.

7. Génération de code pour MIL-0.

8. Ajout des blocs (MIL-1) : analyse lexicale et syntaxe abstraite.

9. Ajout des blocs (MIL-1) : analyse syntaxique et interprétation.

10. Ajout des blocs (MIL-1) : génération de code.

11. Ajout des procédures (MIL-2) : principe.

12. Ajout des procédures (MIL-2) : généralisation.