On présentera dans ce cours les bases avancées de la théorie des
langages formels, aussi bien du point de vue mathématique que du point
de vue informatique (avec une préoccupation linguistique). Le but est
d'aborder d'une part la problématique de l'analyse syntaxique
automatique (
parsing), centrale en TAL, et d'autre part
celle de la
compilation, problématique plutôt
informatique mais qui inspire de nombreuses applications de TAL et de
linguistique formelle.
Organisation des séances
sem. |
date |
salle |
Description |
Liens |
1 |
21/01 |
cm 310 |
Ch1. Langages algébriques (1) |
poly: rappels |
25/01 |
td 309 |
Langages rationnels, algébriques |
feuille n°1
|
2 |
28/01 |
cm 310 |
Pas de séance (CNU) |
|
01/02 |
td 309 |
Langages algébriques |
feuille n°2
|
3 |
04/02 |
cm 310 |
Ch1. Langages algébriques (2) |
|
08/02 |
td 309 |
Transformations de grammaires |
feuille n°3
|
4 |
11/02 |
cm 310 |
Ch1. Langages algébriques (3) |
|
15/02 |
td 309 |
Grammaires et automates à pile |
feuille n°4 |
5 |
18/02 |
cm 310 |
Ch1. Langages algébriques (4) |
|
22/02 |
td 309 |
Analyse descendante |
feuille n°5 |
6 |
25/02 |
cm 310 |
Ch2. Introduction parsing (1) |
|
01/03 |
td 309 |
Révisions |
feuille
n°6 |
7 |
04/03 |
cm 310 |
pas de séance |
|
08/03 |
td 309 |
------ Devoir sur Table------- |
8 |
11/03 |
cm 310 |
Ch2. Introduction parsing (2) |
|
15/03 |
td 309 |
Parsing ascendant (shift-reduce, LL) |
feuille n° 7 |
9 |
18/03 |
cm 310 |
Ch2. Introduction parsing (3) |
|
22/03 |
tp 309 |
Implémentation d'un analyseur LR(0) (1) |
énoncé |
10 |
25/03 |
tp 309 |
Implémentation d'un analyseur LR(0) (2) |
|
29/03 |
cm 310 15:30 |
Ch4. Parsing tabulaire (1) |
|
11 |
01/04 |
cm 310 |
pas de séance |
|
05/04 |
cm 310 15:30
|
Ch4. Parsing tabulaire (2)
Ch5. Machines de Turing (1) |
poly: Def +
exemple MT |
12 |
08/04 |
cm 310 |
Ch5. Machines de Turing (2)
|
polys: MT
mots-jumeaux, classes de langages |
12/04 |
tp 309 |
|
|
13 |
15/04 |
cm 310 |
Ch6. Syntax-driven translation
|
système de traduction
problème de traduction
système d'attributs
interprétation
|
19/04 |
tp 309 |
|
|
14 |
22/04 |
cm 310 |
Ch7. TAG |
|
Références et liens
Généralités. Les ouvrages d'Aho, Ullman, et collaborateurs,
presque tous traduits en français, constituent une source excellente
pour la plupart des sujets vus dans ce cours. Mais on pourra aussi
consulter avec profit l'excellent manuel (Partee, ter Meulen &
Wall 93), qui traite aussi la plupart des aspects de ce cours (sauf la
traduction dirigée par la syntaxe et la compilation), d'une façon
moins complète, mais souvent mise en perspective par rapport au
traitement du langage naturel et à la linguistique.
Les bases des
automates sont présentées, avec des exercices, dans le
chapitre 17 de (Partee, ter Meulen & Wall, 93), mais les
algorithmes vus en cours n'y sont pas présentés. Les algorithmes de
minimisation, déterminisation, élimination des epsilon-transitions
sont présentés dans (Hopcroft & Ullman, 79). L'algorithme de
conversion d'une expression rationnelle en automate est décrit dans
tous les manuels ; celui qui convertit un automate en expression
rationnelle (algorithme de Mac Naughton et Yamada) est décrit dans
(Autebert 87, pp. 88) (d'une façon assez technique).
Les
langages algébriques (
context-free) sont de loin
les classes de langages les plus étudiées, et sont décrits dans tous
les manuels évoqués. On pourra consulter (Autebert, 1987) pour une
approche très mathématique. Voir aussi le chapitre 18 de (Partee,
ter Meulen & Wall, 93), avec une section sur les
automates à
pile.
A propos des
machines de Turing (évoquées dans le chapitre
2), on peut de nouveau se reporter à (Partee, ter Meulen & Wall,
93). On peut aussi consulter les manuels sur la complexité
algorithmique et la théorie du calcul (
theory of computation).
Enfin, le texte intégral des articles de Turing, accompagné de
préfaces très éclairantes, le tout en français, se trouvent dans
(Turing/Girard 1995).
La problématique de l'
analyse syntaxique est détaillée, par
exemple, au chapitre 4 de (Aho et al 2000), mais avec un point de
vue « compilation » (algos LL, LR, LALR). Pour un point de
vue plus linguistique, avec en particulier le problème des grammaires
ambiguës et le parsing tabulaire, on pourra se reporter au polycopié
de François Yvon.
Enfin, pour
lex & yacc et leurs variantes, c'est
toujours (Levine et al, 1990) qui reste la référence (de nombreux
polycopiés en ligne sur Internet, aussi).
Références
- Jean-Marie Autebert, Langages algébriques, Masson (Paris), 1987.
- Alfred Aho & Jeffrey Ullman : The Theory of Parsing,
Translation, and Compiling, Prentice Hall, 1972.
- Alfred Aho, Ravi Sethi and Jeffrey Ullman, Compilateurs,
Dunod (Paris), 2000. [Traduction de Compilers, Addison-Wesley, 1986]
- Daniel Jurafsky & James Martin : Speech and Language Processing,
Prentice Hall, 2000.
- J.E. Hopcroft and Jerry D. Ullman, Introduction to Automata
Theory, Languages, and Computation, Addison Wesley Publishing
Co. (Reading, Ma), 1979.
-
John Levine, Tony Mason and Doug Brown, lex & yacc, O'Reilly, 1990.
- Barbara Partee, Alice ter Meulen & Robert
E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1993.
Liens