Introduction to language theory and compiling

Langages, grammaires formelles. Types de langage, classification de Chomsky. Automates finis, ensembles et grammaires réguliers. Grammaires context-free, formes normales. Automates à pile. Analyseurs lexicaux, syntaxique descendant et ascendants, LL(k), LR(k), LALR(k). Analyse sémantique et systèmes de typage.
La langue d'enseignement est l'anglais

À l'issue du cours, les étudiants doivent:

1. Maîtriser les notions de base de la théorie des langages formels (notion de langage, automates, grammaires, non-déterminisme et les algorithmes associés)
2. Être capable d'expliquer ces notions de manière intuitive, mais aussi en utilisant le formalisme mathématique adéquat
3. Maîtriser les principes de bases des compilateurs
4. Comprendre et être capable d'expliquer et de justifier la hiérarchie de Chomsky
5. Maîtriser les notions théoriques de parsers descendants et ascendants, ainsi que les notions de grammaires LL et LR associées
6. Être capables de mettre toutes les notions théoriques du cours en pratique en réalisant un compilateur qui s'intègre à LLVM (essentiellement, spécifier le langage en utilisant des outils formels, réaliser le scanner, le parser et la phase de traduction vers le langage intermédiaire d'LLVM)

Cours ayant celui-ci comme co-requis

Cours ex-cathedra complétés par des travaux pratiques et un projet en trois partie consistant à réaliser un petit compilateur
 

Références, bibliographie et lectures recommandées

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

Support(s) de cours

• Podcast
• Syllabus
• Université virtuelle

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

Méthode(s) d'évaluation

• Examen écrit
• Projet

Examen écrit

Projet

L'examen est un examen écrit portant sur la matière "théorie des langages" (l'aspect "compilateur" étant évalué principalement par le projet).

Construction de la note (en ce compris, la pondération des notes partielles)

L'examen vaut pour 12 points de la note finale, et le projet vaut pour 8 points. Il n'y a pas de second session pour le projet !

Langue(s) d'évaluation

• anglais