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

I Langages hors-contexte
1. Propriétés des grammaires hors-contexte
Arbres de dérivation, ambiguïté
2. Analyse syntaxique des grammaires hors-contexte
Analyse syntaxique non déterministe (ascendante, descendante)
Analyse déterministe, langages déterministes, langages et grammaires LL(1)

II Application à la définition et la compilation des langages de programmation
1. lexicographie, syntaxe, sémantique statique et sémantique à l’exécution
2.Architecture d’un compilateur : analyseurs lexical et syntaxique
3. Grammaires d’attributs et sémantique statique

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

Théorie des Langages 1

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

Un examen écrit(E).

N1=E1
N2=E2