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.

Pré-requis: les étudiants suivant ce cours sont censés maîtriser l'essentiel du programme du cours « bases formelles du TAL », tel qu'il est résumé dans ce polycopié.

Organisation des séances

sem. date salle Description Liens
1 19/01 cm 310 Ch1. Langages algébriques (1) poly: rappels
21/01 td 309 Langages rationnels
poly: supp. ε-transitions 		feuille n°1
2 26/01 td 309 Langages algébriques feuille n°2
28/01 td 309 TP: NFA (sans ε-trans.) → DFA sujet
3 02/02 cm 310 Ch1. Langages algébriques (2)  
04/02 cm 309 Ch1. Langages algébriques (3)  
4 09/02 cm 310 Ch1. Langages algébriques (4) diapos
11/02 td 309 Langages algébriques feuille n°4
5 16/02 cm 310 Ch2. Introduction au parsing (1)  
18/02 td 309 Parsing, transf. et automates à pile feuille n°5
6 23/02 cm 310 Ch2. Introduction au parsing (2) poly: algo ascendant
25/02 td 309 Parsing et automates à piles feuille n°6
7 02/03 cm 310 Ch2. Introduction au parsing (3) poly: table LL(1), automate LR(0)
04/03 td 309 Contrôle continu
8 09/03 cm 310 Ch3. Parsing tabulaire (1) table
11/03 td 309 Analyse ascendante feuille n°8
9 16/03 cm 310 Ch3. Parsing tabulaire (2)
Ch4. Machine de Turing (1)
Polys: Def + exemple MT; MT mots-jumeaux.
18/03 td 309    
10 23/03 cm 310 Ch4. Machine de Turing (2)
Poly: classes de langages
25/03 td 309    
11 30/03 cm 310 Ch5. Traduction dirigée par la syntaxe
Polys: système de traduction; problème de traduction; système d'attributs; interprétation
01/04 td 309    
12 06/04 cm 310 --- Pas de séance (lundi férié) ---
08/04 cm 309 CCG  
13 13/04 td 309 PLY et logique Énoncé
slides PLY
 

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
Liens