Ensimag Rubrique Formation 2022

Language theory 2 - 3MMTL2

  • Number of hours

    • Lectures 13.5
    • Projects -
    • Tutorials 17.5
    • Internship -
    • Laboratory works 2.0
    • Written tests -

    ECTS

    ECTS 3.0

Goal(s)

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

Responsible(s)

Xavier NICOLLIN

Content(s)

I Context-free languages
1. Context-free grammars
2. context-free analysing (general top-down and bottom-up algorithms, LL(*) 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.

Prerequisites

Language Theory 1
Python programming skills

Test

One written exam

N1=E1
N2=E2

Calendar

The course exists in the following branches:

  • Curriculum - Core curriculum - Semester 6
see the course schedule for 2023-2024

Additional Information

Course ID : 3MMTL2
Course language(s): FR

The course is attached to the following structures:

You can find this course among all other courses.

Bibliography

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