LI324(1) : Langages formels

CM : Mardi, 14:00-16:00, salle 105 îlot Jussieu à partir du 25/10 : 14:30-16:30
TD : Jeudi, 09:00-11:00, salle 124, 30, rue du château des rentiers, 13e
Premier cours : 27 septembre 2005, premier TD le 06 octobre
Pas de séance le mardi 1er nov. (Toussaint), mardi 8 novembre, mardi 15 novembre
Séance de rattrapage prévue le mercredi 14 décembre, de 11h30 à 13h00, salle 124, 30, rue du château des rentiers.

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 des points de vue informatique et linguistique. On y évoquera : les machines à états finis (machine de Turing, automates...) ; les langages réguliers ; les grammaires formelles et la hiérarchie de Chomsky ; les notions de décidabilité, énumérabilité ; le problème et les algorithmes de parsing ; la traduction dirigée par la syntaxe.


 

Plan du cours

  • Ch 0 : Introduction : les problèmes liés aux langages formels
  • Ch 1 : Langages rationnels (TD1, TD2)
  • Ch 2 : Langages algébriques
  • Ch 3 : Machines de Turing (TD)
  • Ch 4 : Problème de parsing (poly)
  • Ch 5 : Traduction dirigée par la syntaxe (poly1, poly2, poly3, TD)
  • Ch 6 : Lex & Yacc (essentiellement TP) (poly1, poly2)
    • 14/12/05 : lex & lex+yacc
      1. Ecrire un lexer « autonome » qui supprime les blancs/tabs (du genre de celui de l'exemple yacc ETF)
      2. Associer ce lexer au parser ETF donné en cours, en ajoutant un makefile
      3. Faire en sorte que ce soit le lexer qui reconnaisse les opérateurs + et x, et que les caractères parasites soient ignorés
      4. Faire en sorte que les constantes entières soient reconnues par le lexer, leur valeur étant transmise au parser par yylval
    • 15/12/05 : yacc + attributs
      1. Réponse possible à la question 3 précédente : fichier lex, fichier yacc, makefile.
      2. Toujours question 4 précédente. Pour vous aider, un exemple pour un langage (simpliste) d'affectation. Fichier lex, fichier yacc.
      3. Implémenter un parser pour la grammaire de l'exercice 7 de la feuille de TD n°1 sur les grammaires. On se contentera d'afficher un message ad hoc si une phrase est reconnue.
      4. Ajouter un attribut qui calcule la profondeur d'enchâssement des relatives
 

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
Annales
voir ma page d'archives 		 
 

    Bibliographie (en travaux)

    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.

    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 une multitude d'ouvrages.

    • Jean-Marie Autebert, Langages algébriques, Masson (Paris), 1987.
    • Barbara Partee, Alice ter Meulen & Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1993.
    • J.E. Hopcroft and Jerry D. Ullman, Introdduction to Automata Theory, Languages, and Computation, Addison Wesley Publishing Co. (Reading, Ma), 1979.
    • A. Aho, R. Sethi & J. Ullman : Compilateurs, principes, techniques et outils, Interéditions, 1989.
    • D. Jurafsky & J. Martin : Speech and Language Processing, Prentice Hall, 2000.
    • A. Aho & J. Ullman : The Theory of Parsing, Translation, and Compiling, Prentice Hall, 1972.
       
    • A. Aho & J. Ullman : Concepts fondamentaux de l'informatique, Dunod, 1992.
Ma maison-page January 10 2006