|
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.
|
Plan (indicatif) du cours
|
Organisation des séances
| sem. | Date | Type/loc | Description | Liens |
|---|---|---|---|---|
| 1 | 18/01/2010 | CM, 124 |
Ch0. Panorama
Ch1. Langages rationnels (1) [Rappels:] 1. Expressions rationnelles 2. Automates finis 3. Théorèmes d'équivalence |
plycopiés :
rappels
Voir aussi l'excellent polycopié de Yvon & Demaille (sur les automates). |
| 22/01/2010 | TD, 124 | Automates et algorithmes. | feuille d'exercices n°1 | |
| 2 | 25/01/2010 | CM, 124 |
Ch1. Langages rationnels (2)
4.2.4. Minimisation 5.3.2. Algorithme de McNaughton & Yamada 6.1. Lemme de pompage |
Polycopiés : plan du
chapitre, minimisation
(exemple),
conséquences du lemme de pompage |
| 29/01/2010 | TD, 124 | Automates et algorithmes. | Suite feuille d'exercices n°1, feuille d'exercices n°2 | |
| 3 | 01/02/2010 | CM, 124 |
Ch2. Langages algébriques (1)
0. Rappels sur les grammaires formelles 1. Grammaires algébriques (Propre, quadratiques, dé-récursivation) |
polycopiés: rappels. |
| 05/02/2010 | TD, 124 | Grammaires usuelles + transformations de grammaires | feuille d'exercices n°3 | |
| 4 | 08/02/2010 | CM, 127 |
Ch2. Langages algébriques (2)
1. Grammaires algébriques (Greibach, factorisation gauche) 2. Automates à pile 3. Théorèmes d'équivalence |
|
| 12/02/2010 | TP, 155 | Implémentation du « nettoyage » de grammaires | code: script de départ | |
| 5 | 15/02/2010 | CM, 124 |
Ch2. Langages algébriques (3)
3. Théorèmes d'équivalence 4. Propriétés des langages algébriques |
|
| 19/02/2010 | TD, 124 | Transformations de grammaires | suite feuille n°3 | |
| 6 | 22/02/2010 | CM, 124 |
Ch2. Langages algébriques (4)
4. Propriétés des langages algébriques 5. Décidabilité, expressivité Ch3. Introduction au parsing (1) | polycopiés: argument de shieber 85, machines de Turing, propriétés des langages formels |
| 26/02/2010 | TD, 124 | Transformations de grammaires et automates à pile. | feuille d'exercices n°4 | |
| 7 | 01/03/2010 | CM, 127 |
Ch3. Introduction au parsing (2)
1. Algorithmes naïfs 2. Analyse prédictive |
algos descendants 1, algos descendants 2, algo ascendant, premiers, suivant, |
| 05/03/2010 |
Ch3. Introduction au parsing (3)
Exercices de révision |
feuille d'exercices n°5 | ||
| 8 | 08/03/2010 | CM, 127 | ---------- Devoir sur table ---------- | |
| 12/03/2010 | TD, 155 | Algorithmes naïfs de parsing | ||
| 9 | 15/03/2010 | CM, 124 | Ch3. Introduction au parsing (4) | polycopié : automate LR(0), |
| 19/03/2010 | TD, 124 |
Parsing naïf, parsing prédictif
Retour sur automate LR(0) |
suite feuille n°5, et feuille d'exercices n°6 | |
| 10 | 22/03/2010 | CM, 124 |
Ch3. Introduction au parsing (5)
Ch4. Parsing tabulaire (1) |
|
| 26/03/2010 | TP, 155 | Algorithmes naïfs de parsing (suite) | Propositions de corrigés : voir ici (parsingnaif.i.py) | |
| 11 | 29/03/2010 | CM, 124 | Ch4. Parsing tabulaire (2) | |
| 02/04/2010 | TP, 155 |
Ch4. Parsing tabulaire (3)
Ch5. Générateurs d'analyseurs |
Synthèse graphique Earley
Une présentation de ply, que l'on peut télécharger ici Un exemple de programme ply (la classique calculatrice): ICI TP: Réalisation d'un traducteur littéral français-anglais, dont la couverture linguistique devrait comprendre au moins les phrases suivantes. |
|
| 12 | 05/04/2010 | Pas de séance (Pâques) | ||
| 09/04/2010 | TP, 155 | |||
| 13 | 12/04/2010 | TP, 155 | ||
| 16/04/2010 | Pas de TD |
Références bibliographies et liens (mise à jour à venir)
Généralités. Les ouvrages de Alfred Aho et Jerry Ullman, presque tous traduits en français, constituent une source excellente pour tous les sujets vus dans ce cours. Mais on pourra aussi consulter avec profit l'excellent manuel (Partee, ter Meulen & Wall 93), qui traite tous les 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 grammaires formelles sont traitées dans la plupart des ouvrages cités. Voir par exemple le chapitre 18 de (Partee, ter Meulen & Wall, 93), avec une section sur les automates à pile
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 ». Pour un point de vue plus linguistique, avec en particulier le problème des grammaires ambiguës, 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).
Un ensemble important de documents d'enseignement concernant les langages formels se trouve regroupé sur ce site. On y trouve en particulier l'excellent polycopié de François Yvon et Akim Demaille (sous le titre Théorie des Langages) dont nous utilisons plusieurs extraits dans ce cours.
- 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.