Automates, langage et compilation

Ce cours de spécialité présente les fondements théoriques des langages (langages formels, automates, grammaires) et leur application à la construction de compilateurs et d’interpréteurs. Au-delà du compilateur, ces techniques sont quotidiennes pour l’ingénieur logiciel : validation d’entrées par expressions régulières, langages dédiés de règles métier, analyse de fichiers et de formats, outils d’analyse statique et de qualité du code. Les TP guidés conduisent à la réalisation complète d’un interpréteur pour un mini-langage, EPIScript.

Objectifs d’apprentissage

• Manipuler expressions régulières et automates finis (déterminisation, minimisation) ;
• Réaliser un analyseur lexical et définir la syntaxe d’un langage par une grammaire hors contexte non ambiguë ;
• Construire des analyseurs syntaxiques LL(1) et comprendre l’analyse LR (SLR, LALR) ;
• Mettre en œuvre l’analyse sémantique (table des symboles, typage, grammaires attribuées) ;
• Générer et optimiser du code intermédiaire ; réaliser un interpréteur complet.

Prérequis

Algorithmique et structures de données (arbres, piles, tables de hachage), mathématiques discrètes (ensembles, relations), programmation en Python ou Java.

Plan du cours

1. Leçon 1 — Langages formels, expressions régulières et automates finis
2. Leçon 2 — Analyse lexicale et grammaires hors contexte
3. Leçon 3 — Analyse syntaxique descendante et ascendante
4. Leçon 4 — Analyse sémantique et génération de code

Modalités d’évaluation

Volume horaire : 20 h de cours magistraux, 20 h de travaux dirigés, 20 h de travaux pratiques, 60 h de travail personnel (6 crédits). Évaluation : contrôle continu (TD, TP guidés et projet d’interpréteur, quiz) et examen terminal écrit.

Bibliographie

• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2^e éd., Pearson (traduction française : Compilateurs : principes, techniques et outils).
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson.
• Michael Sipser, Introduction to the Theory of Computation, Cengage.
• Terence Parr, The Definitive ANTLR 4 Reference, Pragmatic Bookshelf.
• Andrew W. Appel, Modern Compiler Implementation in Java, Cambridge University Press.