Théorie des langages et Compilation [T8IS423M]

Théorie des langages et Compilation [T8IS423M]

En pratique

Nature
Elément constitutif
Volume horaire de TP
14
Volume horaire de TD
6
Volume horaire de CM
24
Volume horaire de travail personnel
46
Langue d'enseignement
Français

Description du contenu de l'enseignement

Le cours se décompose en trois parties : la première sur la théorie des langages, 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.


The course is organized in three main parts: the first one is about language theory, the sedond one focuses on compilers' techniques and the third one is on optimisation techniques. This course aim is to give student the theoretical and practical tools to understand compilers architecture and to build compilers.

 

Organisation

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.


The first part deals with the fundamental elements of language theory, necessary for the construction of a compiler. First, we give the definitions and basic properties of words and languages. We deal with rational expressions, deterministic and non-deterministic finite-state automata, and the equivalence of associated languages, as well as algorithms for switching from representation to another. The minimization of a finite-state automaton is discussed as well as the star lemma. Then, the notion of grammar is introduced. Regular out-of-context grammars are presented. For the latter, the notion of derivation and syntactic tree are introduced. Finally, the transformation and normalization algorithms are presented.

The second part deals with compilation techniques. It describes the lexical and syntactic analysis methods, in particular a descending deterministic method (LL(1) grammars) and a general ascending method (CKY algorithm). Secondly, the objective is to demystify the compilation process and allow the student to understand the processes that take place when a program compiles and then runs. Algorithmic aspects (control structures, variables), procedural aspects (compilation and execution of procedures and functions, parameters) and finally object aspects (notion of class, object, creation of objects, methods) are approached successively. Emphasis is placed on the dynamic nature of memory management. The source language studied is a simple adhoc language called nilNovi. The produced object language is a language for virtual machines using “byte code”.

Keywords: syntax analysis, compilation, interpretation, memory management, production of object code, virtual machine, stack, heap, identifier table.

Informations pédagogiques

Compétences à acquérir

  • Formaliser un langage par une grammaire
  • Caractériser et transformer un langage
  • Manipuler et transformer des automates
  • Ecrire un analyseur syntaxique
  • Ecrire un compilation pour différentes types de langages
  • Mettre en oeuvre des concepts avancés (récursivité, héritage, polymorphisme, etc)

  • Formalize a language using a grammar
  • Characterize and transform a language
  • Manipulate and transform automata
  • Write a syntactic parser
  • Write a compiler for different language types
  • Set up advanced concepts like recursivity, sub-classing, polymorphism

 

Pré-requis recommandés

  • Algorithmique
  • Programmation Orientée Objet

  • Algorithmics
  • Object-oriented programming

Bibliographie, lectures recommandées

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

Dernière modification : mer, 06/01/2021 - 16:34