Grammaires et compilation - 3MM1GC

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.

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.

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