Théorie des langages 2 - 3MMTL2

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.

Théorie des Langages 1
Programmation en langage C

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

Le cours est programmé dans ces filières :

• Cursus ingénieur - Tronc Commun - Semestre 6

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

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

• Equipe Bases théoriques de l'informatique
• Equipe Algorithmique-Mathématiques discrètes

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

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