Solutions du TD-5, analyse syntaxique

1  Analyse syntaxique

Étaient données. Lexeme, Lexer et Bool. La solution est LL.

La solution commence par définir une interface avec les lexers dans le style de celle des transparents :
       // Interface avec les lexers a` la JJL
     
  private static Lexer lexer  ;
     
  private static Lexeme curToken ;
     

     
  private static void step () { // un pas en avant
     
    curToken = lexer.next () ;
     
  }
Les variables lexer et curToken sont statiques, car plusieures méthodes statiques de la classe LL doivent y accéder. Ce sont des variables globales.

C'est la méthode parse qui aura la responsabilité d'initialiser lexer.
       static Bool parse (Reader in) {
     
    LL.lexer =  new Lexer (in) ;
     
    ...
Cette méthode étant la seule à ne pas être privée (avec main, qui l'appelle), on est sûr que lexer sera initialisé proprement. Pour curToken, c'est la discipline de programmation dans les méthodes de parsing (parse, parseSum, etc.) qui évitera tout usage innoportun. En particulier, curToken n'est affectée que par la méthode step.

On peut alors se représenter comment est implémenté le flot de lexèmes : curToken est le premier lexème de ce flot, le seul accessible, un appel à step mange ce lexème et le remplace par le suivant. Le dernier lexème du flot est null, ainsi que spécifié par l'énoncé.

Le reste est absolument classique : il y a une méthode par règle de la grammaire LL des propositions. Certains élèves se sont rendu compte que cette grammaire était fausse, la priorité de la négation (!) est incorrecte. Cette erreur se corrige facilement :
F = ...  |  ! F   |  ...    Expressions de base

1.1  Points critiques

Certains élèves répugnent encore à écrire ``Lexeme.FALSE'' et écrivent ``0'' à la place. C'est mal, car alors tout changement de la valeur de la constante Lexeme.FALSE entraînera une catastrophe.

Les vraies erreurs relevées lors du travail pratique proviennent le plus souvent d'une difficulté à bien comprendre comment utiliser le flot de lexèmes. La règle est simple : il faut consommer un lexème reconnu. Par exemple, dans le cas des facteurs (expressions de base) :
     switch (curToken.nature) {
     
    case Lexeme.OPAR// Reconnaissance
     
      step () ;       // Consommation
     
      Bool rpar = parseSum() ;
     
      if (curToken == null || curToken.nature  != Lexeme.CPAR)
     
        error ("parseFactor: ``)'' attendu") ;
     
      step () ;
     
      return rpar;
     
    case Lexeme.NOT:
     
      step () ;
     
      return new Bool (Bool.NOTparseFactor()) ;
     
    case Lexeme.TRUE:
     
      step () ;
     
      return new Bool (Bool.TRUE) ;
     
    case Lexeme.FALSE:
     
      step () ;
     
      return new Bool (Bool.FALSE) ;
     
    case Lexeme.VAR:
     
      String name = curToken.as_var ;
     
      step () ;
     
      return new Bool (name) ;
Il y a un appel step() dès qu'un lexème est identifié.

L'autre erreur fréquente est induite par le choix un peu vicieux d'encoder la fin du flot de lexème (lexème EOF) par null. Cela impose certaines précautions, car null est un lexème valide et peut donc se trouver n'importe où. Autrement dit, les choix de structures de données du lexer ne garantissent nullement que curToken n'est pas null, puisque le fichier peut finir à n'importe quel moment.

Par conséquent, il importera pour, par exemple, tester l'égalité de curToken et du lexème AND, d'écrire :
     if (curToken != null && curToken.nature == Lexeme.AND) {
     
// Ici, curToken est le lexème AND
     
else {
     
// Là, curToken n'est pas le lexème AND
     
}
Du point de vue de la programmation, on doit, à chaque fois que l'on utilise l'accès aux champs ou aux méthodes (l'opérateur ``.''), se poser la question de null et la régler. Au dessus c'est réglé par la séquentialité de ``&&'' qui s'abstient d'exécuter le second argument lorsque le premier est égal à false. Plus généralement, ça se règlera par un test if (curToken == null)...

Enfin, la solution utilise bien la grammaire LL qui induit naturellement des arbres penchant à droite. Mais elle construit l'arbre qui penche à gauche. Par exemple, dans le cas des conjonctions :
      private static Bool parseProd() {
     
    Bool r = parseFactor () ;
     

     
    while (curToken != null && curToken.nature == Lexeme.AND ) {
     
      step () ;
     
      r = new Bool (Bool.ANDrparseFactor()) ;
     
    }
     
    return r;
     
  }
Ou encore, solution récursive équivalente :
      private static Bool parseProd(Bool f) {
     
    if (curToken != null && curToken.nature == Lexeme.AND ) {
     
      step () ;
     
      return parseProd (new Bool (Bool.ANDfparseFactor()) ;
     
    } else
     
      return f;
     
  }
À appeler par parseProd(parseFactor()).

Cet exemple illustre que la construction de l'arbre représenté par le flot de lexèmes peut être déconnectée (un peu) de la reconnaissance proprement dite des phrases de la grammaire. Ou encore, que le résultat de l'analyse syntaxique n'est pas l'arbre de dérivation.

2  Tautologies

La solution est Env et Toto.

La principale difficulté est l'énumération de toutes les valuations de variables. La solution réalise cette enumération comme une énumeration récursive classique de sous-ensembles, avec modification en place de l'environnement (argument part).
       // Enume'ration classique, par modification en place de all
     
  static boolean enum (Env allEnv partBool exp) {
     
    if (part == null) { // all a toutes ses valeurs fixées
     
      return eval(expall) ;
     
    } else {
     
      part.value = true ; // sous-ensembles contenant value
     
      if (!enum (allpart.nextexp))
     
        return false ;
     
      part.value = false ; // sous-ensembles ne contenant pas value
     
      return enum (allpart.nextexp) ;
     
    }
     
  }
Ce codage fait un effort d'éfficacité : il ne suit pas l'idée naturelle de construire la liste de toutes les valuations possibles puis d'appliquer eval à chaque valuation. C'est évidemment meilleur dans le cas où la proposition testée (exp) n'est pas une tautologie, car on évite alors l'énumeration complète. C'est aussi meilleur dans le cas où exp est une tautologie, car alors on alloue pas une énorme liste.

C'est un peu vain car la complexité est énorme (2v, où v est le nombre de variables contenues dans exp).

Voici une autre solution EnvHash et TotoHash, qui utilise la classe Hashtable du package java.util et l'énumeration de Gray.

3  Démonstration du principe du pigeon

La solution est Pigeon.

Le problème de complexité apparaît rapidement. Pour un n donné, la taille de la proposition à vérifier est de l'ordre de n3 (trois boucles for imbriquées dans couple), c'est raisonable. Mais le nombre de variables est en n2 et donc là il faudra faire au pire 2n2 évaluations de taille au pire n3, c'est impossible dès que n vaut cinq ou plus. Le bât blesse d'abord à cause de la méthode de vérification...Faire mieux est probablement impossible en théorie (la vérification que exp est une tautologie est un problème dit NP-complet, c'est à dire disons pour lequel il n'y a pas d'autre solution générale connue que d'énumerer un nombre non-polynomial de configurations), et de fait plutôt difficile en pratique le principe du pigeon étant un test classique et difficile d'évaluation de performance des programmes de démonstration automatiques.

4  Culture

Pour rigoler un peu, voici encore une autre solution, écrite à l'aide de l'encodage objet des arbres.


Ce document a été traduit de LATEX par HEVEA.