Ensimag Rubrique Formation 2022

Grammaires et compilation - 3MM1GC

  • Volumes horaires

    • CM 22.5
    • Projet -
    • TD 22.5
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 5.0

Objectif(s)

Ce cours vise à donner aux élèves les bases de la théorie des langages hors-contextes et de ses applications à l'analyse syntaxique et la compilation. L'enseignement déroule deux fils conducteurs. Le premier est un fil conducteur "pratique": programmer (en C ou en Java) des traitements sur des langages formels (e.g. formules propositionnelles ou langages de programmation). Le deuxième est un fil conducteur "théorique": formalisation de la syntaxe de langages (ie des ensembles de mots) à l'aide de systèmes d'équations mutuellement récursives, et formalisation de leurs sémantiques dans une approche "dirigée par la syntaxe". Au départ du cours, la pratique prend de l'avance sur la théorie... Mais, petit-à-petit la théorie finit par rattraper la pratique et lui proposer des solutions.

Au délà des connaissances purement techniques, le cours porte 3 messages essentiels dans la formation des informaticiens:
1) Les notations mathématiques sont de même nature que les langages de programmation, même si elles n'ont pas les mêmes objectifs. Tandis qu'avec la programmation, on cherche à faire traiter un problème efficacement par une machine, en mathématiques, on cherche à résoudre précisément un problème à l'aide d'un cerveau humain. Dans les deux domaines, on a la même exigence de rigueur et d'absence d'ambiguïté.
2) La formalisation mathématique aide à programmer: elle procure notamment l'abstraction utile pour aborder des problèmes avec une grande généralité.
3) La théorie des langages est réflexive. On veut formaliser les langages. Pour cela, on se donne des notations (donc un langage) pour formaliser les langages. Une telle démarche réflexive est née au coeur d'une branche des mathématiques appelée la logique. En informatique, elle aboutit typiquement à des outils pour automatiser la programmation: compilateurs, compilateurs d'interpréteurs, etc.

Responsable(s)

Sylvain BOULME

Contenu(s)

*Ce cours est donné en Période(s) Académique(s) 2 et 3*

*Analyse syntaxique (Période 2)*

  • Introduction à l'interprétation des langages informatiques
  • Théorie des plus petits points fixes de Kleene
  • Définitions de langages hors-contextes par BNF
  • Arbres d'analyses
  • Définition de sémantiques formelles par BNF avec attributs (traduction dirigée par la syntaxe)
  • Syntaxes abstraites, arbres de syntaxe abstraite
  • Grammaires génératives, classification de Chomsky
  • Analyse syntaxique LL(1)
  • TP en C: manipulations de formules propositionnelles (e.g. évaluation, mise en forme normale négative, etc).

*Compilation (Période 3)*

  • Etude d'un compilateur pour un mini-Java utilisé dans le projet de compilation qui clot l'année.
  • Etudes des étapes successives : analyse lexicale, syntaxique, vérifications contextuelles, puis génération de code.

Prérequis

Equivalence entre automates finis et expressions régulières.

Contrôle des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : 1 TP en temps libre (sur chaque période) donnant 1 point de bonus/malus à l'exam de la période.

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : 2 examens écrits (1 par période)
Salle spécifique : non
Durée : 2h (chaque examen)
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents autorisés
Matériel (ex : calculatrices): aucun matériel autorisé.

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : 1 examen écrit
Salle spécifique : non
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents autorisés
Matériel (ex : calculatrices): aucun matériel autorisé.

  • Un examen par période donne la note de chaque période: NP2 et NP3
  • Note Bilan Intermédiaire: NB2 := NP2.
  • La note de session 1 est la moyenne pondérée des 2 examens :
    NFS1 := (NP2+4*NP3)/5
  • La note de session 2 est la note de l'examen de rattrapage :
    NFS2 := NR.

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2023/2024

Informations complémentaires

Code de l'enseignement : 3MM1GC
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

  • Introduction to automata theory, languages, and computation de Hopcroft, Motwani & Ullman (2007)
  • Compilers: Principles, Techniques and Tools de Aho, Lam, Sethi & Ullman (1988/2007)
  • The Definitive ANTLR 4 Reference - Terence Parr (2013)