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.

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

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

Campus

Plaine, Solbosch

Méthode(s) d'évaluation

• Examen écrit
• Projet
• Examen pratique

Examen écrit

Projet

Examen pratique

• Examen hors-session

• L'examen est un examen écrit portant sur la matière "théorie des langages"
• L'aspect "compilateur" est évalué 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 seconde session pour le projet, qui doit être réalisé durant le premier quadrimestre (horaire détaillé disponible sur l'UV).
Attention, dans le calcul de la note finale, la note d'une partie qui est inférieure au tiers des points sera ramenée à 0.
Par exemple, un étudiant dont les notes sont de 7/8 au projet et de 3/12 à l'examen, verra sa note d'examen ramenée à 0, ce qui signifie que sa note finale sera de 7/20.
Cette mesure a été prise afin de faire en sorte que les étudiantes et étudiants s'investissent dans les deux parties du cours, qui sont évaluées de façon relativement indépendante.
L'évaluation du projet est divisée en trois partie:

• Partie 1 (scanner): 1 point attribué sur base du code remis
• Partie 2 (parser): le code du parser doit être remis mais ne sera pas évalué. Une séance spéciale, notée, de travaux pratiques, sera organisée après la remise de la Partie 2 pour évaluer la capacité des étudiantes et étudiants à réaliser un parser. Cette évaluation sera basée sur le code remis. Seuls les étudiantes et étudiants qui auront rendu le code du parser pourront participer à cette séance. Elle vaut pour 3,5 points
• Partie 3 (génération de code): sera évaluée comme le parser: remise du code sur l'UV, puis évaluation à travers une séance pratique après la remise, pour 3,5 points

Langue(s) d'évaluation

• anglais