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: gilles.geeraerts at ulb.be

• web: https://verif.ulb.be/ggeeraer

Campus

Plaine

Method(s) of evaluation

• written examination
• Project

written examination

Project

The exam is  a written exam, testing the students' skills regarding the "language theory" part of the course (the "compiler" part is tested  by the project).

Mark calculation method (including weighting of intermediary marks)

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

Moreover, all students must achieve at least one third of the grade in each part for this part to be taken into account in the final grade. Concretely, this means that any grade strictly lower than 4/12 for the exam will be turned into 0/12, and any grade strictly lower than 2.66/8 for the project will also be turned into 0/8.

Example: A student who has 7/8 for the project but 3/12 for the exam gets 7+0=7/20 for the final grade.

This is to ensure that students devote a minimal amount of effort to the two main objectives of the course which are equally important.

Language(s) of evaluation

• english