Introduction to technics for language description and analysis. Application to programming languages. Basic notions of computability theory (algorithms, computable functions, undecidability).

I Context-free languages
1. Context-free grammars
2. context-free analysing (general top-down and bottom-up algorithms, LL(k) method)

II Programming language descriptions and analysis
1. lexicography, syntax, static and dynamic semantics
2.Compiler architectures : lexical and syntactic analysers
3. Attributes grammars and static semantics

II Computability theory
1. Turing machines, computable functions
2. existence of incomputable functions, undecidability of the halting problem
3. decision problems on languages.

Language Theory 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

One written exam

N1=E1
N2=E2