LI324(1) : Langages formels

Cours magistraux : Pascal Amsili
Travaux dirigés : Marie Candito

CM : Vendredi, 15:30-17:30, salle 124 site Rentiers
TD : Mardi, 09:00-11:00, salle 124 site Rentiers
Premier cours : Vendredi 26 septembre 2008, premier TD le 30 septembre

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 du cours

01 23/09/08 TD Pas de séance
26/09/08 CM Ch0. Panorama
Ch1. Langages rationnels (1)
    [Rappels:] (poly)
  1. Expressions rationnelles
  2. Automates finis
  3. Théorèmes d'équivalence
Voir aussi l'excellent polycopié de Yvon & Demaille
02 30/09/08 TD [Révisions: Automates à états finis] feuille de TD 1
03/10/08 CM Ch1. Langages rationnels (2)
  1. Propriétés des langages rationnels
Ch2. Langages algébriques (1)
    [Rappels:] (poly)
  1. Transformation de grammaire
03 07/10/08 TD Suite feuille de TD 1 (minimisation, lemme de pompage). Correction partielle feuille 1
10/10/08 CM Ch2. Langages algébriques (2)
  1. Transformations de grammaires (suite)
04 14/10/08 TD Transformations de grammaires algébriques
Feuille de TD 2
17/10/08 CM Ch2. Langages algébriques (3)
  1. Transformations de grammaires (suite)
  2. Automates à piles
05 21/10/08 TD Nettoyage de grammaires algébriques - Implémentation en python / NLTK
Correction partielle Feuille de TD 2 (suppression productions-ε)
24/10/08 CM Ch2. Langages algébriques (4)
  1. Automates à piles
  2. Correspondance AP-CFG
  3. Propriétés des langages algébriques
06 28/10/08 TD Suite nettoyage de grammaires algébriques - Implémentation en python / NLTK
Correction complète Feuille de TD 2
Indications python/NLTK
31/10/08 CM Ch2. Langages algébriques (5)
  1. Propriétés des langages algébriques
07 04/11/08 TD Automates à pile
Feuille de TD 3
Corrigé
07/11/08 CM Ch2. Langages algébriques (6)
Ch3. Introduction au parsing (1)
08 11/11/08 TD Pas de séance (Armistice 1918)
13/11/08 TD Devoir sur table - Enoncé
Devoir sur table - Corrigé
14/11/08 CM Ch3. Introduction au parsing (2)
09 18/11/08 TD Correspondance Automate à pile / Grammaire. Parsing naïf
Feuille de TD 4  
21/11/08 CM Ch3. Introduction au parsing (3)
Ch4. Parsing tabulaire (1)
10 25/11/08 TD Analyse LL1 (PREMIER / SUIVANT)
Feuille de TD 5  
28/11/08 CM Ch4. Parsing tabulaire (2)
11 02/12/08 TD Suite analyse LL1
Correction PREMIER / SUIVANT
Implémentation python : correction  
05/12/08 CM Ch4. Parsing tabulaire (3)
Ch5. Les générateurs d'analyseurs
12 09/12/08 TD Analayse CYK
-- Feuille de TD 6
-- Canevas python pour l'implémentation de CYK  
12/12/08 CM Ch5. Les générateurs d'analyseurs (TP)
  • Le site de téléchargement de ply (Python Lex Yacc).
  • 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.
13 16/12/08 TD
-- Correction Feuille 6 : algo CYK
-- CORRECTION de l'implémentation de CYK, + extraction des analyses complètes  
 

Plan indicatif

  • Ch1. Langages rationnels
  • Ch2. Langages algébriques
  • Ch3. Introduction au parsing
  • Ch4. Parsing tabulaire
  • Ch5. Les générateurs d'analyseurs

Contrôles

Modalités
  • Contrôle continu : un devoir sur table (mi-semestre, 40%) et une épreuve écrite (session d'examen de janvier, 60%).
  • Contrôle final : une épreuve écrite pendant la session d'examen de janvier-février (100%).
  • Session de rattrapage (sept.) : pour tous : une épreuve écrite pendant la session d'examen de septembre (100%).
  • Aucune note n'est conservée entre février et septembre
Calendrier
  • DST n°1 : semaine du 10 novembre, créneau à fixer.
  • Examen : session de janvier 2009
  • Rattrapage: session de juin 2009
    Lundi 15 juin 2009, de 16h30 à 18h30, salle 065E (Halle aux Farines)
Annales
voir ma page d'archives
 
 

    Références bibliographies et liens

    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.

Home page Amsili February 07 2011