I53 - Compilation et théorie des langages

La compilation est un processus essentiel dans le domaine de l'informatique qui consiste à transformer un programme écrit dans un langage de haut niveau en un programme équivalent en langage machine, compréhensible par un ordinateur. La théorie des langages formels accompagne ce processus en fournissant un cadre mathématique pour décrire et analyser la structure des langages de programmation. Ce cours explore les principes fondamentaux de la compilation et de la théorie des langages via la conception d'un compilateur élémentaire du langage algorithmique utilisé en cours vers la machine RAM déjà étudiée en L2 à l'aide des outils flex et bison.

Prérequis

• Programmation en C et Python (modularité, outils make ...)
• Base de l'algorithmique et structures de données (récursivité, pile, file, arbre ...)
• Mathématiques pour l'informatique (logique, raisonnement par récurrence ...)

Objectifs

À la fin de ce cours, les étudiants devraient être en mesure de:

• Comprendre les concepts fondamentaux des langages formels et des différentes opérations algébriques agissant sur ceux-ci.
• Concevoir et manipuler des automates finis pour la reconnaissance de langages réguliers.
• Analyser et créer des grammaires formelles simples, en se concentrant sur les grammaires LL.
• Identifier clairement les différentes phases du processus de compilation ainsi que leur role respectif
• Comprendre la structure en machine d'un programme informatique
• Concevoir et manipuler une table des symboles pour gérer les informations sur les variables.
• Utiliser les outils flex et bison afin de développer des analyseurs lexicaux et syntaxiques capable de produire un arbre abstrait.
• Générer du code à partir d'un arbre abstrait pour une machine fictive.
• Appliquer des techniques élémentaires d'optimisation de code.

Ressources pédagogique

• "Compilers: Principles, Techniques, and Tools" by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.

Évaluation

• Examen écrit terminal de fin de semestre: 50%
• Projet de travaux pratiques (compilateur ALGO->RAM): 40%
• Participation aux exercices: 10%

Sommaire

Chapitre 1: Introduction à la compilation

• Compilation des langages usuels
• Rappel sur la machine RAM
• Structure d'un compilateur
• Phases de compilation

Chapitre 2: Évaluation des expressions arithmétiques

• Analyseur lexical et syntaxique
• Arbre d'analyse syntaxique
• Associativité et priorité des opérateurs
• Algorithme de descente récursive
• Génération de code

Chapitre 3: Analyse lexicale

• Mots et langages
• Expressions régulières et langages réguliers
• Automates finis déterministes et non-déterministes
• Déterminisation des AFN
• Conversion des expressions régulières en AF
• Automate minimal

Chapitre 4: Analyse syntaxique

• Grammaire non-contextuelles
• Nettoyage des grammaires
• Analyse récursive descente
• Analyse syntaxique prédictive

Chapitre 5: Conception d'un compilateur ALGO->RAM

• Structure d'un programme en machine RAM
• Traduction dirigée par la syntaxe
• Techniques d'optimisations

Travaux Pratiques

1. gcc, interprête Python, Makefile:

   • sujet: compil_TP1.pdf
   • fichier: crible.tar

2. Traducteur d'expressions arithmético-booléennes élémentaire:

   • sujet: compil_TP2.pdf

3. Compilateur d'expressions régulières en automate fini

   • sujet: compil_TP3.pdf
   • fichiers: automates.tar

4. Introduction à Flex et *Bison

   • sujet: compil_TP4.pdf
   • fichiers: flex_bison.tar

5. Compilateur Algo / RAM

   • sujet: arc_doc.pdf
   • fichiers: projet_arc.tar