Vous êtes ici

  1. Accueil
  2. Compilation et Théorie des langages

Compilation et Théorie des langages

Compilation et Théorie des langages

En pratique :

Volume horaire de cours : 24
Volume horaire global de TD : 6
Volume horaire global de TP : 30
Langue principale : français

Compétences à acquérir

Le cours se décompose en trois parties : la première sur la théorie des langages et la deuxième sur les techniques de compilation et la troisième sur les techniques d'optimisation. Ce cours a pour objectif de donner aux étudiants les outils théoriques et pratiques permettant de comprendre l'architecture des compilateurs et de créer des compilateurs.


Modalités d’organisation et de suivi

La première partie aborde les éléments fondamentaux de théorie des langages, nécessaires pour la construction de compilateur. Dans un premier temps, nous donnons les définitions et les propriétés de base des mots et des langages. Nous traitons des expressions rationnelles, des automates finis déterministes et non-déterministes, et de l'équivalence des langages associés, ainsi que des algorithmes de passage à ces différentes représentations. La minimisation d'un automate fini est abordée ainsi que le lemme de l'étoile. Ensuite, la notion de grammaire est introduite. Les grammaires régulières hors-contextes sont présentées. Pour ces dernières, la notion de dérivation et d'arbre syntaxique sont introduites. Enfin, les algorithmes de transformation et de normalisation sont présentés.
La deuxième partie aborde les techniques de compilation. Elle décrit les méthodes d'analyse lexicale et syntaxique, en particulier une méthode déterministe descendante(grammaires LL(1)) et une méthode générale ascendante (algorithme CKY). Dans un deuxième temps, l'objectif est de démystifier le processus de compilation et de permettre à l'étudiant de comprendre les processus qui se déroulent quand un programme se compile puis s'exécute. On aborde successivement les aspects algorithmiques (structures de contrôle, variables), procéduraux (compilation et exécution de procédures et de fonctions, paramètres) et enfin objet (notion de classe, d'objet, de création d'objets, de méthodes). L'accent est mis sur le caractère dynamique de la gestion de la mémoire. Le langage source étudié est un langage ad hoc simple intitulé nilNovi. Le langage objet produit est un langage pour machine virtuelle de type «byte code».
Mots clés: analyse syntaxique, compilation, interprétation, gestion de mémoire, production de code objet, machine virtuelle, pile, tas, table d'identificateurs.


Bibliographie, lectures recommandées

Aho, A. V., Monica S.. Lam, Sethi, R.,& Ullman, J. D. (2007). Compilateurs: principes, techniques et outils. Pearson Education.


Pré-requis

Pré-requis obligatoires

Algorithmique de base
Développement Objet