Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Grammaires et compilation - 3MM1GC

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Volumes horaires

    • CM : 22.5
    • TD : 22.5
    Crédits ECTS : 5.0

Objectifs

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.

Contact Sylvain BOULME

Contenu

*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ôles des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) :
Salle spécifique :
Durée :
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser :
    Commentaires :

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

  • matériel autorisé, préciser :
  • matériel interdit, préciser :
    Commentaires

3 examens de 2h.



  • 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.

Informations complémentaires

Cursus ingénieur->Alternance->Alternance 1ere annee

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)

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 15 janvier 2017

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes