Langages formels

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 Ch1. Langages rationnels Ch2. Langages algébriques Ch3. Introduction au parsing Ch4. Parsing tabulaire Ch5. Les générateurs d'analyseurs

Organisation des séances

sem.	date	salle	Description	Liens
1	lun. 23 janv. 12	CM, 065E	Ch1. Langages rationnels (1)	Polycopiés: identités rationnelles, extensions de notation, automates: définitions
	mar. 24 janv. 12	TD, 226C	Automates et algorithmes (I)	feuille n°1
2	lun. 30 janv. 12	CM, 065E	Pas de séance (CNU)
	mar. 31 janv. 12	TD, 226C	Pas de séance (CNU)
3	lun. 06 févr. 12	CM, 065E	Ch1. Langages rationnels (2)	polycopiés (distribués en TD): complémentation et intersection, théorèmes d'équivalence, automates et grammaires régulières, McNaughton & Yamada
	mar. 07 févr. 12	TD, 226C	Automates et algorithmes (II)	feuille n°2
4	lun. 13 févr. 12	CM, 065E	Ch1. Langages rationnels (3) Ch2. Langages algébriques (1)	polycopiés: rappels grammaires
	mar. 14 févr. 12	TD, 226C	Transformations de grammaires	feuille n°3
5	lun. 20 févr. 12	CM, 065E	Pas de séance
	mar. 21 févr. 12	TD, 226C	Pas de séance
6	lun. 27 févr. 12	CM, 065E	Ch2. Langages algébriques (2)
	mar. 28 févr. 12	TD, 226C	Transformation de grammaires (suite)	feuille n°3 (suite)
7	lun. 05 mars 12	CM, 065E	Ch2. Langages algébriques (3) Ch3. Introduction au parsing	Polycopié: argument de Shieber
	mar. 06 mars 12	CM/TD, 538C	Ch3. Introduction au parsing (1) Transformation de grammaires (suite)	Polycopiés: algos naïfs descendants, algos naïfs ascendants. Versions python: td_trop_naif, td_standard, td_buprp, td_shift-red feuille n°3 (suite)
8	lun. 12 mars 12	CM, 065E	Ch3. Introduction au parsing (2)	Polycopiés: table LL
	mar. 13 mars 12	TD, 538C	---Devoir sur table---
9	lun. 19 mars 12	CM, 065E	Ch3. Introduction au parsing (3) Ch4. Parsing tabulaire (1)	Polycopié: table LR(0)
	mar. 20 mars 12	CM/TD/TP, 538C	Ch4. Parsing tabulaire (2) Exercices (feuille 4) Mesure de complexité CYK	Code : une implémentation
10	lun. 26 mars 12	CM, 065E	Ch4. Parsing tabulaire (3)
	mar. 27 mars 12	TP, 452C	Retour sur la complexité de CYK TP: implémentation de earley	poly: étude de complexité code: canevas (earley)
11	lun. 02 avr. 12	CM, 065E	Ch5. Compilateurs et générateurs d'analyseurs	Polycopiés: grammaires sur X*xY*, systèmes d'attributs, génération de code
	mar. 03 avr. 12	TP, 538C	Ch5. Compilateurs et générateurs d'analyseurs TP: ply	Une présentation de ply, que l'on peut télécharger ici Un exemple de programme ply (la classique calculatrice): ICI TP: arbres ébauche de corrigé
12	lun. 09 avr. 12	CM, 065E	Pas de séance (férié)
	mar. 10 avr. 12	TP, 538C	TP ply: normalisation de formules logiques	énoncé tp

Références bibliographies 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

• La page du cours Théorie des Langages Formels d'Akim Demaille, co-auteur avec François Yvon d'un très complet polycopié en français sur la théorie des langages formels.