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.

• e-mail: gilles.geeraerts [at] ulb.be

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

Campus

Plaine

Method(s) of evaluation

• written examination
• Project
• Practice exam

written examination

Project

Practice exam

• Out-of-session examination

• The examination is a written examination covering the “Language Theory” part of the course.
• The “Compiler” component is assessed through the project.

Mark calculation method (including weighting of intermediary marks)

The examination accounts for 12 points of the final grade, while the project accounts for 8 points. There is no second-session assessment for the project, which must be completed during the first semester (a detailed schedule is available on the Université Virtuelle platform).
Please note that, when calculating the final grade, any component for which the grade is less than one third of the available points will be reduced to 0.
For example, a student who receives 7/8 for the project and 3/12 for the examination will have their examination grade reduced to 0, resulting in a final grade of 7/20.
This rule is intended to ensure that students engage fully with both components of the course, which are assessed relatively independently of each other.
The project assessment is divided into three parts:

• Part 1 (Scanner): 1 point. This grade is awarded on the basis of the submitted code.

• Part 2 (Parser): 3.5 points. The parser code must be submitted but will not be graded directly. After the Part 2 submission deadline, a special graded practical session will be organised to assess students’ ability to implement a parser. This assessment will be based on the code they submitted. Only students who have submitted their parser code will be allowed to participate in this session.

• Part 3 (Code Generation): 3.5 points. This part will be assessed in the same way as the parser: students must first submit their code on the Virtual University platform, after which their work will be assessed during a practical session. This part is worth 3.5 points.

The purpose of this assessment method is to verify that students are able to independently perform the tasks required as part of the project.

The course instructor reserves the right to invite any student to an additional oral interview in order to verify their personal command of the content of the submitted examination, particularly when inconsistencies in the examination prevent the instructor from properly assessing the student’s level of mastery of the knowledge and skills targeted by the course.

Language(s) of evaluation

• english