Présentation
Module CSC4251-4252 (ex CSC4536) – Compilation : De l'algorithme à la porte logiqueCours M1, école d'ingénieur deuxième année, voie d'ouverture.
A travers la réalisation d'un compilateur d'un sous-ensemble de Java vers l'assembleur MIPS, les objectifs du cours se déclinent sur trois directions :
- Étudier l'architecture des processeurs et l'écriture de code assembleur
- Introduire la Théorie des Langages et en maitriser les applications pratiques en informatique. En particulier, les outils de génération de compilateur (compiler's compiler)
- Approfondir la maitrise de la programmation dans un langage évolué :
- Par la compréhension de la façon dont les paradigmes de programmation sont implantés pour leurs exécutions
- Par la pratique dans l'écriture d'un compilateur
Séquencement
- les séances Archi peuvent être entrelacées avec les séances Syntax ou Compil
- les séances Syntax sont prérequises pour les séances Compil et Bonus
-
SéancesSujetsSupportsNotions clés
-
Syntax1Analyse lexicale(1/2)Prolégomènes
Analyse Lexicale(1/2)- Introduction du cours
- compilation / interpretation / traduction
- phases de la compilation
- Analyse lexicale versus syntaxique
- Hiérarchie de Chomsky, catégorie lexicale, grammaire
- Premiers pas d'analyse lexicale
- Expression régulière
- Outil JFlex
- Introduction du cours
-
Syntax2Analyse Lexicale(2/2)
- Théorie des langages
- Automate fini et langage régulier
- Expressions régulières non triviales
- Outillage de code avec JFlex
-
Syntax3Analyse Syntaxique (1/4)
- Grammaire Algébrique
- définition et exemples
- ambiguïté
- syntaxe BNF
- Premiers pas CUP
- couplage avec JFlex, Tokens
- écriture de grammaires
- Grammaire Algébrique
-
Syntax4Analyse Syntaxique (2/4)
- Cours
- Cours Pratique
- TP
- Rendu Moodle JSON
- Analyse Syntaxique LL et LR
- Déterminisme, Ambiguïté et Conflit
- Valeur sémantique des symboles
- Analyse complète d'un langage
-
Syntax5Analyse Syntaxique (3/4)
- "Calculatrice"
- Interprétation à la volée
- Priorité (LR)
- Traitement d'erreur (LR)
-
Syntax6Analyse Syntaxique (4/4)
- Arbre de Syntaxe Abstraite
- Interprétation sur arbre : évaluation, boucles
- Arbre de Syntaxe et typage objet
- Patron de conception Visiteur et parcours d'arbre
-
BonusBootstrapBootstrap
- Paradoxe du bootstrap
- Compiler un compilateur Brainfuck écrit en Brainfuck !
- Comparaison performances compilation vs interprétation
-
BonusTD langagesTD langagesExercices de TD sur la théorie des langages
-
BonusExercices en vracExercices en vracExercices supplémentaires de TP JFlex et CUP en vrac
-
Archi1Archi (1/3)
- Instruction, Registre
- Assembleur et outil MARS
- Structures algorithmiques : if, for,…
- Appel de fonction, variables locales
-
Archi2Archi (2/3)
- Porte logique, unité de calcul, registre
-
Archi3Archi (3/3)
- Mémoire, décodeur d'instructions, microcode
-
Compil1Minijava
- Langage Minijava
- Structure du compilateur
- Analyse lexicale et Syntaxique
- Arbre de Syntaxe Abstraite
-
Compil2Analyse Sémantique (1/2)
- Phases de Compilation
- Analyse sémantique
- Principes
- Arbres décorés, attributs sémantiques
- Table de symboles : liaison et visibilité des identificateurs
-
Compil3Analyse sémantique (2/2)
- Des fonctions sémantiques
- Contrôle de type
-
Compil4Forme Intermédiaire
- Partie avant et arrière d'un compilateur
- Linéarisation, Canonisation
- Code à 3 adresses
-
Compil5Génération MIPS (1/2)
- Allocation mémoire, registre
- Cadre et Convention d'appel
- Sélection d'instruction
-
Compil6Génération MIPS (2/2)
- TP
- Rendu Moodle (2/2)
- Finalisation et Test du compilateur
- Ajouter le type Tableaux d'entiers
- Revoir l'ensemble des phases de compilation