LI 032 : Langages formels et automates
& LI 035 : Analyse syntaxique automatique

Responsables : Pascal Amsili & Alexis Nasr

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é.

La seconde partie de ce cours sera consacrée à l'étude du processus permettant de construire à partir d'une phrase, une représentation du « sens » de cette dernière. Ce processus (on parle de « traduction dirigée par la syntaxe » est généralement divisé en 2 etapes. La première étape consiste à associer un arbre syntaxique à une phrase d'un langage (langage formel (langage de programmation, par exemple) ou langage naturel). On parle d'analyse syntaxique automatique (ou parsing).

La seconde étape consiste à construire un objet non linguistique (du sens) à partir de la structure syntaxique. Cet objet peut être une suite d'instructions pour un ordinateur si l'on se situe dans le cadre des langages de programmation ; ou une formule logique s'il s'agit de langages naturels.

On réalisera dans le cadre de ce cours, en guise d'application, un analyseur sommaire inspiré de la sémantique formelle de Montague (voir aussi LG033).

Remarque : il est conseillé de suivre aussi le cours de sémantique formelle LG 033.

Emploi du temps

 LI032 (S1)LI035 (S2)
Horaires : Jeudi
13:00 à 15:00		 Jeudi
09:00 à 11:00
Salle : 11, RdC 3, patio 42-43 
Premier cours Jeudi 17 Octobre Jeudi 13 Février

Modalités de contrôle

Mêmes modalités pour LI032 et LI035
  • Contrôle continu
    Un DST (40%) et un partiel en fin de semestre (60%)
  • Contrôle terminal
    Un examen en fin de semestre (100%)

Plan indicatif (LI032)

    Introduction & Rappels
  • (17/10) (PA) Rappels mathématiques
  • (24/10) (PA) Rappels en langages formels
    Langages rationnels
  • (31/10) (PA) Transformations d'automates (1)
  • (07/11) (PA) Transformations d'automates (2)
  • (14/11) (PA) Grammaires régulières
  • (21/11) (PA) Théorème de Kleene
     
  • (28/11) (PA) Partiel
     
    Langages hors-contexte
  • (05/12) (AN) Automates à pile
  • (12/12) (AN) Grammaires hors contexte (1)
  • (19/12) (AN) Grammaires hors contexte (2)
    Machines de Turing
  • (09/01) (PA) Machines de Turing
  • (15/01) (PA) Langages de type 0 & 1, décidabilité

Plan indicatif (LI035)

    Analyse syntaxique automatique
  • (13/02) (AN)
  • (20/02) (AN)
  • (27/02) (AN)
  • (06/03) (AN)
     
    Traduction dirigée par la syntaxe
  • (13/03) (PA) Principes (1)
  • (20/03) (PA) Principes (2)
     
  • (27/03) (AN) Partiel
     
  • (03/04) (AN) Lex & Yacc (1)
     
  • (24/04) (AN) Lex & Yacc (2)
  • (01/05*) (AN) Génération d'automates (1)
  • (08/05*) (AN) Génération d'automates (2)
  • (13/05) (PA) Génération de formes logiques (1)
  • (22/05) (PA) Génération de formes logiques (2)
  • (29/05*) (PA) Génération de formes logiques (3)
    (*) : séances tombant un jour férié, à rattraper.

Contrôles

    LI032
  • Devoir sur table n° 1 : jeudi 28 novembre horaire et salle habituels.
  • Examen final (pour tous les étudiants) :
    Vendredi 31 janvier 2003, Amphi X3 (1, rue G. de la Brosse), de 08:30 à 11:30
    LI035
  • Devoir sur table n° 1 : jeudi 27 mars horaire et salle habituels.
  • Examen final (pour tous les étudiants) : session de juin

Polycopiés

  • Exercices concernant les langages rationnels (format PS ou PDF).
  • Chapitre 4 « traduction dirigée par la syntaxe » (format PS ou PDF).
  • Projet sur l'interprétation des formules logiques : version 1. Autres versions et bibliothèques ICI.

Bibliographie

http://www.linguist.jussieu.fr/~amsili/Ens03/LI032.html lun mai 26, 2003 Ma maison-page