Le but de cette UE est de présenter les bases théoriques ainsi que les techniques utilisées pour concevoir et réaliser un compilateur. Les idées et techniques développées dans ce domaine sont si générales et fondamentales qu’un informaticien (et même un scientifique non informaticien) les utilisera très souvent au cours de sa carrière : traitement de données, moteurs de recherche, analyse des textes, etc. Ce cours permet également, aux étudiants, d’approfondir leurs connaissances sur les notions d’algorithmique, d’optimisation et des langages de programmation. Cette UE couvre les thèmes suivants : Langages et Compilateurs : différentes formes des traducteurs, environnement d’un compilateur, structure d’un compilateur, phases de compilation et groupement. Langages formels : alphabet, langages, grammaires, dérivations, phrases, arbre syntaxique, grammaires ambigües. Analyse lexicale : rôle d’un analyseur lexical, unités lexicales et lexèmes, conception d’un analyseur lexical, langages réguliers, expressions régulières, théorème de Kleene, automates finis, construction de Thompson, transformation d’un automate fini non déterministe en automate fini déterministe, optimisation d’un automate fini déterministe, implémentation d’un analyseur lexical, générateur d’un analyseur lexical, LEX. Analyse syntaxique descendante : méthodes d’analyse syntaxique, hiérarchie des grammaires hors-contexte, automate à pile, analyse syntaxique descendante, grammaires LL(K), grammaire non contextuelle prédictive, générateur d’analyseur syntaxique LL(1) non récursif, analyse LL(1) descendante récursive. Analyse syntaxique ascendante : automate à pile LR, analyseurs LR déterministes, automate fini caractéristique, analyseur LR(0), analyseurs LR(1): analyseur SLR et analyseur LALR, utilisation des grammaires ambigües, traitement des erreurs. Analyse sémantique : traduction dirigée par la syntaxe, grammaires attribuées, attributs synthétisés et hérités, grammaires S-attribuées, grammaires L-attribuées, traduction descendante, traduction ascendante. Génération de code intermédiaire : code à trois adresses, affectations, expressions booléennes, évaluation arithmétique, instructions de contrôle, traduction des déclarations, optimisations indépendantes de la machine.

Temps présentiel : 50 heures

Charge de travail étudiant : 75 heures

Méthode(s) d'évaluation : Examen final, Examen partiel