Solutions du TD-5, 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.NOT, parseFactor()) ;
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.AND, r, parseFactor()) ;
}
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.AND, f, parseFactor()) ;
} 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.
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 all, Env part, Bool exp) {
if (part == null) { // all a toutes ses valeurs fixées
return eval(exp, all) ;
} else {
part.value = true ; // sous-ensembles contenant value
if (!enum (all, part.next, exp))
return false ;
part.value = false ; // sous-ensembles ne contenant pas value
return enum (all, part.next, exp) ;
}
}
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.
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.