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

There are two main parts to the evaluation that reflect the two main objectives of the course:

• Students will have to write a compiler for a simple imperative language, in group of two students (or individually if they prefer). The projects will consists of three parts, that will have to be handed in according to the schedule given on the Université virtuelle.

• The final exam, will test ’formal language theory’ part, with questions about the theory, and exercises, in the spirit of those reviewed during the practicals.

Mark calculation method (including weighting of intermediary marks)

The project is worth 8 points: 2 points for the first part, and 3 points for the two last parts. The written exam is worth 12 points.

Pay attention that you 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. Then, the sum of the resulting grades is computed to obtain the final grade.

Example: a student who has 6/8 for the project and 5/12 for the exam gets 6+5 = 11/20 for the final grade. 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 (compiler construction and language theory) which are equally important.

Language(s) of evaluation

• english