Introduction to language theory and compiling

Formal Langages and grammars. Chomsky classification. Regular expressions. Automata (finite pushdown, Turing machine). Compiler, lexical analyser, parser. Descending and ascending parsers: LL(k), LR(k), LALR(k). Semantic analysis, typing systems and code generation.

The learning outcomes are:

1. to master basic language theory (language, automata, grammars, non-determinism, associated algorithms)
2. to be able to explain those notions in an intuitive manner, but also using the adequate mathematical formalism
3. to master the basics of compilers
4. to understand and to be able to justify Chomsky hierarchy
5. to master the theory behind top-down and bottom-up parsers (including LL and LR grammars)
6. to be able to apply all the theoretical notions by specifying and writing a small compiler that interfaces with the internal language of LLVM

Cours ayant celui-ci comme co-requis

The learning activities are:
- Ex-cathedra lectures
- practicals
- a project that consists in 3 parts

References, bibliography, and recommended reading

• J. E. Hopcroft, R. Motwani, and J. D. Ullman ; Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, New York, 2001.
• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Compilers : Principles, Techniques and Tools", Addison-Wesley, 1986
• John R. Levine, Tony Mason, Davy Brown. Lex et YACC, O'Reilly ed, 1992.

Course notes

• Podcast
• Université virtuelle
• Syllabus

Contacts

Prof. Gilles Geeraerts

• bureau: Département d'Informatique, CPI 212, Campus de la Plaine, bureau 2 N8 117.

• tel: 55 96

• e-mail: gigeerae [at] ulb.ac.be

• web: http://di.ulb.ac.be/verif/ggeeraer

Campus

Plaine

Method(s) of evaluation

• written examination
• Project

written examination

Project

The exam is normally a written exam, testing the students' skills regarding the "language theory" part of the course (the "compiler" part is tested  by the project). If the sanitary situation does not allow a written exam on site in January or August, it will be moved online (and maybe replaced by an oral exam).

Mark calculation method (including weighting of intermediary marks)

Project: 8 points out of 20
Exam: 12 points out of 20

Language(s) of evaluation

• english