Compilation : De l'algorithme à la porte logique

Portail informatique

Présentation

Module CSC4251-4252 (ex CSC4536) – Compilation : De l'algorithme à la porte logique
Cours 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
Plus de détails dans la fiche programme (aussi en vidéo interne).

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éances
    Sujets
    Supports
    Notions clés
  • Syntax1
    Analyse 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
  • Syntax2
    Analyse Lexicale(2/2)
    • Cours
      (50mn)
      Chapitre 2
    • Cours Pratique
      (20mn)
      Memento JFlex : 5 à 7
    • TP
      (110mn)
      Exos JFlex : 4, 5, 6|7, 8
    • Théorie des langages
    • Automate fini et langage régulier
    • Expressions régulières non triviales
    • Outillage de code avec JFlex
  • Syntax3
    Analyse Syntaxique (1/4)
    • Grammaire Algébrique
      • définition et exemples
      • ambiguïté
      • syntaxe BNF
    • Premiers pas CUP
      • couplage avec JFlex, Tokens
      • écriture de grammaires
  • Syntax4
    Analyse Syntaxique (2/4)
    • Cours
      (50mn)
      Chapitre 4
    • Cours Pratique
      (20mn)
      Memento CUP : 5 à 7
    • TP
      (110mn)
      Exos CUP : 4, 5
    • 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
  • Syntax5
    Analyse Syntaxique (3/4)
    • "Calculatrice"
    • Interprétation à la volée
    • Priorité (LR)
    • Traitement d'erreur (LR)
  • Syntax6
    Analyse Syntaxique (4/4)
    • Cours
      (30mn)
      Chapitre 6
    • TP
      (150mn)
      Exos CUP : 8, 9 (, 10, 11)
    • Arbre de Syntaxe Abstraite
    • Interprétation sur arbre : évaluation, boucles
    • Arbre de Syntaxe et typage objet
    • Patron de conception Visiteur et parcours d'arbre

  • Bonus
    Bootstrap
    Bootstrap
    • Paradoxe du bootstrap
    • Compiler un compilateur Brainfuck écrit en Brainfuck ?!?
    • Comparaison performances compilation vs interprétation
  • Bonus
    TD langages
    TD langages
    Exercices de TD sur la théorie des langages
  • Bonus
    Exercices en vrac
    Exercices en vrac
    Exercices supplémentaires de TP JFlex et CUP en vrac

  • Archi1
    Archi (1/3)
    • Instruction, Registre
    • Assembleur et outil MARS
    • Structures algorithmiques : if, for, ..
    • Appel de fonction, variables locales
  • Archi2
    Archi (2/3)
    • TP
      (180mn)
    • Porte logique, unité de calcul, registre
  • Archi3
    Archi (3/3)
    • TP
      (180mn)
    • Mémoire, décodeur d'instructions, microcode

  • Compil1
    Minijava
    • Langage Minijava
    • Structure du compilateur
    • Analyse lexicale et Syntaxique
    • Arbre de Syntaxe Abstraite
  • Compil2
    Analyse 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
  • Compil3
    Analyse sémantique (2/2)
    • Cours
      (20mn)
      Chapitre 7 (fin)
    • TP
      (160mn)
      Étape 3
    • Des fonctions sémantiques
    • Contrôle de type
  • Compil4
    Forme Intermédiaire
    • Partie avant et arrière d'un compilateur
    • Linéarisation, Canonisation
    • Code à 3 adresses
  • Compil5
    Génération MIPS (1/2)
    • Allocation mémoire, registre
    • Cadre et Convention d'appel
    • Sélection d'instruction
  • Compil6
    Génération MIPS (2/2)
    • TP
      (180mn)
      Étapes 6 et 7
    • Rendu Moodle (2/2)

      Étape 8
    • Finalisation et Test du compilateur
    • Ajouter le type Tableaux d'entiers
    • Revoir l'ensemble des phases de compilation