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

> Formation > Cursus ingénieur

Théorie des langages 2 - 3MMTL2

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 : 16.5
    • TD : 16.5
    Crédits ECTS : 3.0

Objectifs

Introduction aux techniques utilisées de description et d’analyse des langages. Application aux langages de programmation. Présentation des notions de bases de la théorie de la calculabilité : algorithmes, fonctions calculables, problèmes indécidables

Contact Sylvain BOULME, Nicolas PELTIER

Contenu

I Analyse syntaxique des langages hors-contextes

  • Syntaxe et sémantique des langages informatiques: traduction dirigée par la syntaxe.
  • Rappels sur les grammaires hors-contextes: arbres de dérivation, ambiguïté.
  • Formalisation de sémantiques simples par grammaires attribuées. Notion de méta-interpréteur (Bison-Yacc et AntLR).
  • Structure d'un interpréteur complexe: analyse lexicale, analyse syntaxique, notion de syntaxe abstraite.
  • Théorie des plus petits points fixes de Kleene.
  • Analyse syntaxique LL(1). Calculs de directeurs LL(1).
  • Programmation d'un analyseur LL(1) en langage C.
  • Ouverture: analyse syntaxique au-délà de LL(1) (e.g. LR(1) et LL(*))

II Calculabilité
1. Calcul, algorithme, machine de Turing, fonctions partielles calculables
2. Propriétés :
Existence de fonctions non calculables, Indécidabilité du problème de l’arrêt, Existence d’algorithmes universels
3. Problèmes de décision sur les langages et les programmes.
Preuves par réduction: indécidabilité du problème de l'ambiguïté des grammaires hors-contextes.



Prérequis

Théorie des Langages 1
Programmation en langage C

Contrôles des connaissances

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

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : examen écrit.
Salle spécifique :
Durée : 3h
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 :


N1=E1
N2=E2

Bibliographie

A. Aho, R. Sethi, J. Ullman : Compilers. Principles, Techniques and Tools, Addison-Wesley 1987
Pierre Berlioux, Michel Lévy : Théorie des langages, polycopié Ensimag
N. J. Cutland : Computability. Cambridge University Press 1980

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