«Compilateurs --- Principes, techniques et
outils», de A. Aho, R. Sethi et J. Ullman (Dunod) ;
«Les
compilateurs --- théorie, construction,
génération», de R. Whilhelm et D. Maurer (Masson) ;
«Modern Compiler Design»,
de D. Grune, H. Bal, C. Jacobs et K. Langendoen (Wiley) ;
«Lex & Yacc», de J.
Levine, T. Mason et D. Brown (O'Reilly) ; et
«Programming Languages Pragmatics»,
de M. Scott (Morgan Kaufmann).| semaine |
cours |
TD |
TP |
devoir à la
maison |
auto-évaluation |
| 36 | CM1 présentation générale : calendrier, travaux à rendre (un TP de mise en jambe et un TP «projet de réalisation d'un compilateur»), évaluation (examen terminal et contrôle continu de TP) architecture générale d'un compilateur : le pipe-line des opérations (constitue plus le plan du cours qu'une architecture réelle), diagramme en T CM2 analyse syntaxique : YACC, examen des sorties de YACC (représentation graphique du y.output, décalage/réduction) analyse syntaxique : YACC, comment et pourquoi ça marche (item, completion, item complet, automate des items LR(0) et automate à pile, décalage/réduction/expansion, analyse descendante/ascendante) |
Lire les chapitres 1 et 2.
DM1 (mise en jambe non-encadrée) consulter le HOWTO LEX & YACC, réaliser les expériences proposées, et en préparer les traces d'exécution. Imaginer une variation en décrivant l'objectif visé (ex. provoquer un conflit ou ajouter une commande). Commenter vos expériences et vos observations. Attention : les exemples du HOW TO peuvent devoir être retouchés pour tourner sur votre installation. |
|||
| 37 | CM3 calcul dirigé par la syntaxe : grammaires à attribut, le cas de YACC, héritage, synthèse |
TD1 analyse syntaxique LALR(1) Distribution de la spécification de VSL+ pour les TP 1 à 6 |
Lire le chapitre 3 | Savoir refaire les constructions d'automates LR(0) et LALR(1) du polycopié | |
| 38 |
CM4 système de type : langage de type, règle de typage |
TD2 analyse syntaxique LALR(1) |
Lire le chapitre 4.
Rendre le DM1 en cours : compte-rendu (< 4 pages, hors traces) et traces d'exécution. |
Comprendre les
chapitres 1 et 2. Savoir faire les constructions d'automates LR(0) des examens passés. |
|
| 39 | CM5 génération de code : examen des sorties de GCC, code trois-adresses, expressions, code court-circuit, instructions de contrôle (les 3 programmes d'un diagramme en T) |
TD3 grammaires à attributs |
TP1 grammaire YACC du langage VSL+ (elle aura dû être préparée la semaine qui précède) Cette séance ne doit servir qu'à la mise au point de la grammaire YACC, pas à sa conception. |
Lire le chapitre 5. | Comprendre chapitre 3.
Savoir construire un système de règles sémantiques (attributs) pour un système de règles syntaxiques dans un but donné. Méthodologie : examiner un arbre de dérivation typique, identifier les sources d'information, identifier les sens de propagation, écrire les équations. |
| 40 | CM6 optimisation : examen des sorties de GCC, transformations optimisantes et leur conditions d'application |
TD4 grammaires à attributs et typage |
Rendre le TP1 : fichier .y | Lire le chapitre 6.
DM2 examen des sorties de GCC pour les expressions du style (a+b)*(c+d), (a||b)&&(c||d), !a, !!a, !!!a, etc. examen des sorties de GCC pour la fonction chainer_prio. Commenter vos expériences et vos observations. |
Comprendre le chapitre 4. |
| 41 | CM7 analyse statique : bloc de base, analyse locale (activité, élimination de code mort) |
TD5 génération de code trois-adresses |
Lire le chapitre 7.1-2 | Comprendre le chapitre 5.
Savoir imaginer les opérations internes impliquées par une construction linguistique donnée, que ce soit lors de la compilation (ex. typage) ou lors de l'exécution (ex. génération de code). Essayer avec examens passés. |
|
| 42 | CM8 analyse statique : analyse globale (visibilité), algorithmes de calcul (programmes bien structurés, programmes généraux, calcul itératif d'un point-fixe) |
TD6 introduction à l'optimisation de code trois-adresses |
TP2 objectif : compilateur VSL+ sans fonctions ni prototypes |
Lire chapitre 7.3-4 Rendre le DM2 en cours : compte-rendu (< 4 pages, hors traces) et traces d'exécution. |
Savoir raisonner informellement sur la dynamique des programmes. |
| 43 | |
|
TP3 | ||
| 44 Vacances de Toussaint |
|
||||
| 45 | CM9 génération de code : allocation de registre (coloriage de graphe), optimisations locales Conclusion : de beaux algorithmes pour acquérir une vision globale d'un programme via des observations locales |
TD7 : optimisation et analyse de
flot de donnée |
Rendre le TP2-3 pour
le lundi
soir (6/11) |
Lire le chapitre 8. | Comprendre le chapitre 6 |
| 46 | TD8 analyse de flot de donnée |
TP4 objectif : compilateur VSL+ complet et testé |
Savoir formaliser les raisonnements les plus simples et leur trouver une solution algorithmique. | ||
| 47 | TD9 fin analyse flot de données - étude d'un sujet d'examen |
TP5 (publication d'une partie des jeux de test) |
Comprendre le
chapitre 7. Savoir formaliser des analyses statiques dans le cadre de l'analyse de flot de donnée. Identifier les domaines de valeurs, le sens de propagation, et les opérateurs de convergence. Essayer avec examens passés. |
||
| 48 | TP6 | ||||
| 49 | Rendre le TP4-5-6 pour le vendredi soir (8/12) | Savoir mettre en
oeuvre YACC
dans une application. Recenser le répertoire d'algorithmes exposés dans ce cours. Analyser points communs et différences. |