L3 année 2026/2027 : Grammaires et Analyse Syntaxique

Université Paris Cité, Campus des Grands Moulins, Licence Informatique Fondamentale

Modalités de contrôle de connaissances

Page moodle

Les documents des TD et TP seront mis à disposition sur la page moodle de cours.

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)
- Analyse lexicale à l'aide d'un générateur du type LEX
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

Planning préliminaire du cours

Numéro Date Contenu

1 Introduction, rappels

2 OCamllex. Commencer cours 3.

3 Grammaires algébriques

4 Introduction à l'analyse LL(1)

-- pause L2

5 Analyse LL(1) dans le cas général

6 Introduction à l'analyse ascendante, et analyse LR(0)

7 Analyse LR(1)

8 Utilisation de Menhir

9 Terminer le chapitre 8 sur Menhir, puis l'algorithme CYK

10 Lemme d'itération pour les langages algébriques, et propriétés de clôture de la classe des langages algébriques.
Commencer cours 11 sur les automates à pile.

- vacances de printemps

11 Terminer le cours 11 sur les automates à pile

12 Études de cas : langages de données et langages de programmation.

Numéro	Date	Contenu
1		Introduction, rappels
2		OCamllex. Commencer cours 3.
3		Grammaires algébriques
4		Introduction à l'analyse LL(1)
--		pause L2
5		Analyse LL(1) dans le cas général
6		Introduction à l'analyse ascendante, et analyse LR(0)
7		Analyse LR(1)
8		Utilisation de Menhir
9		Terminer le chapitre 8 sur Menhir, puis l'algorithme CYK
10		Lemme d'itération pour les langages algébriques, et propriétés de clôture de la classe des langages algébriques. Commencer cours 11 sur les automates à pile.
-		vacances de printemps
11		Terminer le cours 11 sur les automates à pile
12		Études de cas : langages de données et langages de programmation.

Liens utils OCaml - ocamllex - menhir

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

Équipe pédagogique

Ralf Treinen