CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique

Présentation

Module CSC 4536 – Compilation : De l'algorithme à la porte logique
Cours de voie d'ouverture, école d'ingénieur deuxième année.
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é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)
    • 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"
    • Interpretation à 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)
    • Arbre de Syntaxe Abstraite
    • Interpretation sur arbre : évaluation, boucles
    • Arbre de Syntaxe et typage objet
    • Patron de conception Visiteur et parcours d'arbre

  • Bonus
    Bootstrap
    Bootstrap
    • Paradoxe du boostrap
    • Compiler un compilateur brainfuck écrit en brainfuck ?!?
    • Comparaison performances compilation vs interpretation
  • Bonus
    Exercices libres
    Exercices libres
    Des exercices 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
    • TP
      (180mn)
      Étapes 0 et 1
    • Memento

      Sections 1 à 4
    • Langage Minijava
    • Structure du compilateur
    • Analyse lexicale et Syntaxique
    • Arbre de syntaxe Abstraite
  • Compil2
    Analyse Sémantique (1/2)
    • Cours
      (30mn)
      Chapitre 7 (début)
    • TP
      (150mn)
      Étape 2
    • Memento

      Sections 5 à 7
    • Phases de Compilation
    • Analyse sémantique
      • Principes
      • Arbres décorés, attributs sémantiques
    • Table des 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éfiaire
    • Partie avant et arrière d'un compilateur
    • Linearisation, 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)
      Étape 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