-
Partager cette page
Introduction to language theory and compiling
Titulaire(s) du cours
Gilles GEERAERTS (Coordonnateur)Crédits ECTS
5
Langue(s) d'enseignement
anglais
Contenu du cours
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
Objectifs (et/ou acquis d'apprentissages spécifiques)
À l'issue du cours, les étudiants doivent:
- 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)
- Être capable d'expliquer ces notions de manière intuitive, mais aussi en utilisant le formalisme mathématique adéquat
- Maîtriser les principes de bases des compilateurs
- Comprendre et être capable d'expliquer et de justifier la hiérarchie de Chomsky
- Maîtriser les notions théoriques de parsers descendants et ascendants, ainsi que les notions de grammaires LL et LR associées
- Ê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)
Pré-requis et Co-requis
Cours ayant celui-ci comme co-requis
Méthodes d'enseignement et activités d'apprentissages
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
Autres renseignements
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
Campus
Plaine, Solbosch
Evaluation
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 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.
Langue(s) d'évaluation
- anglais