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 cet article Facebook Twitter Linked In
  • Volumes horaires

    • CM : 13.5
    • TD : 15.0
    • TP : 4.5
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 3.0
  • Responsables : Nicolas PELTIER

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

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 : tous documents autorisés
Matériel (ex : calculatrices): aucun matériel autorisé
Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen: écrit
Salle spécifique : non
Durée : 1h30
Documents autorisés: tous documents autorisés
Matériel: aucun matériel autorisé
Commentaires :

N1=E1
N2=E2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Tronc Commun - Semestre 6
cf. l'emploi du temps 2020/2021

Informations complémentaires

Code de l'enseignement : 3MMTL2
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

  • J. Hopcroft, R. Motwani, J. Ullman : Introduction to Automata Theory, Languages, and Computation. (3rd edition, 2006).
  • Pierre Berlioux, Michel Lévy : Théorie des langages, polycopié Ensimag
  • T. Parr: The Definitive ANTLR 4 Reference (2nd edition, 2013).
  • N. J. Cutland : Computability. Cambridge University Press 1980
  • A. Aho, M. Lam, R. Sethi, J. Ullman : Compilers. Principles, Techniques and Tools, Addison-Wesley (2nd edition, 2013).

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

mise à jour le 15 janvier 2017

Université Grenoble Alpes