L3 année 2021/2022 : Grammaires et Analyse Syntaxique

Modalités de contrôle de connaissances

• session1 = 15% contrôle-TD + 35% projet + 50% examen1
• session2 = max(examen2, 15% contrôle-TD + 35% projet + 50% examen2

Page moodle

Pré-requis

• Langages formels : le cours Automates et Analyse Lexicale du L2, en particulier :
  • expressions rationnelles (comprendre le sens d'une expression rationnelle, écrire des expressions rationnelles dans des cas simples)
  • automates finis déterministes, non-déterministes et avec epsilon-transitions, élimination des epsilon-transitions, algorithme de déterminisation.
  • limitation des automates et expressions rationnelles, en particulier le lemme d'itération (pumping lemma)
• Programmation en OCaml : le cours Programmation Fonctionnelle du L3, en particulier :
  • types de données algébriques (arbres)
  • fonctions récursives définies par distinction de cas (pattern matching), fonctions d'ordre supérieure
  • structuration en modules et compilation des programmes autonomes

Projet

Planning du cours

Numéro	Date	Contenu
1	21/1	Chapitre 1 : Introduction et Rappels [1 transparent par page] [4 transparents par page]
2	28/1	Chapitre 2 : Générateurs d'analyse lexicale [1 transparent par page] [4 transparents par page] [exemples de code]
3	04/2	Chapitre 3 : Grammaires algébriques [transparents comme en amphi] [1 transparent par page] [4 transparents par page]
4	11/2	Chapitre 4 : Introduction à l'analyse LL(1) [transparents comme en amphi] [1 transparent par page] [4 transparents par page] [exemples de code]
5	18/2	Chapitre 5 : Analyse LL(1) dans le cas général [transparents comme en amphi] [1 transparent par page] [4 transparents par page] [exemples de code]
6	25/2	Chapitre 6 : Introduction à l'analyse ascendante [transparents comme en amphi] [1 transparent par page] [4 transparents par page]
-	04/3	pause du L3
7	11/3	Debut du chapitre 7 : Analyse LR(0) et LR(1) (Seulement LR(0) fait le 11/3). Chapitre 7 : [transparents comme en amphi] [1 transparent par page] [4 transparents par page]
8	18/3	Fin du chapitre 7 : LR(1). Debut du chapitre 8.
9	25/3	Chapitre 8 : Utiliser un générateur d'analyse grammaticale moderne [transparents comme en amphi] [1 transparent par page] [4 transparents par page] [exemples de code]
10	01/4	Chapitre 9 : Grammaires et Automates à Pile [transparents comme en amphi] [1 transparent par page] [4 transparents par page]
11	08/4	Chapitre 10 : Propriétés des langages algébriques. [transparents comme en amphi] [1 transparent par page] [4 transparents par page] [exemples de code]
12	15/4	Chapitre 11 : Études de cas. [transparents comme en amphi] [1 transparent par page] [4 transparents par page] [exemples de code]

Liens utils

• Le manual OCaml
• Documentation OCamlLex (regardez sections 13.1 et 13.2)
• Le module Lexing de la bibliothèque standard
• Site web de menhir

Équipe pédagogique

• Balthazar Bauer (TD/TP)
• Isabelle Fagnot (TD/TP)
• Peter Habermehl (TD/TP)
• Matthieu Picantin (TD/TP)
• Ralf Treinen (cours)