[Compilation] Choix d'une méthode d'analyse

Version imprimable

Bonjour à tous,

je suis en train d'implémenter (en Python) la spécification de XPath du W3C, et je m'interroge sur la méthode d'analyse adéquate. Voici un extrait de la grammaire en question, celui qui concerne les opérations arithmétiques :
Code:

1 2 3 4 5 6 7 8 9 [25] AdditiveExpr ::= MultiplicativeExpr | AdditiveExpr '+' MultiplicativeExpr | AdditiveExpr '-' MultiplicativeExpr [26] MultiplicativeExpr ::= UnaryExpr | MultiplicativeExpr MultiplyOperator UnaryExpr | MultiplicativeExpr 'div' UnaryExpr | MultiplicativeExpr 'mod' UnaryExpr [27] UnaryExpr ::= UnionExpr | '-' UnaryExpr
Voilà où j'en suis de mes réflexions : l'analyse LL(1) m'est interdite, car les règles sont (massivement) récursives à gauche ; même problème avec la descente récursive. Je vais donc sans doute devoir opter pour une analyse ascendante, et a priori la technique de la précédence d'opérateurs conviendrait, et ne serait pas trop complexe à coder.

J'ai deux questions à soumettre à votre sagacité :

1°) Suis-je complètement à côté de la plaque, quant aux prémisses du choix de la méthode d'analyse ?
2°) Que me conseilleriez-vous ?

:merci:

04/10/2005, 18h14
ludovic.fernandez

C'est trés vieux pour moi et bien que ne connaissant pas la complexité algorithmique de ce type de méthode, pourquoi ne pas simplement supprimer la récursivité à gauche dans un premier temps ?

Ludo
04/10/2005, 18h22
GrandFather

Citation:

C'est trés vieux pour moi et bien que ne connaissant pas la complexité algorithmique de ce type de méthode, pourquoi ne pas simplement supprimer la récursivité à gauche dans un premier temps ?

Je l'avais tenté, mais le problème est que si j'inverse la règle pour avoir une récursivité à droite, l'analyse porte en priorité sur les chaînes les plus courtes et je me retrouve avec un problème de précédence d'opérateurs (bref, ça calcule faux !).
04/10/2005, 18h33
ludovic.fernandez

Citation:

Envoyé par GrandFather

... et je me retrouve avec un problème de précédence d'opérateurs (bref, ça calcule faux !).

cad ? un langage à pile ? (c'est plus par curiosité)
04/10/2005, 18h46
GrandFather

La spécification du W3C ne donne que la grammaire et les règles de fonctionnement, mais la méthode d'analyse du langage est laissée à la discrétion de celui qui implémente.

En fait, j'avais opté au départ pour un interpréteur, donc pour une analyse LL avec un calcul au fur et à mesure de l'analyse, ne nécessitant donc pas de pile. J'avais (naïvement) interverti les éléments de chaque règle pour éviter les boucles infinies, avant de me rendre compte que ça ne respectait pas la précédence des opérateurs.
04/10/2005, 21h20
DrTopos

As-tu essayé ça:

ftp://ftp.fourthought.com/pub/BisonGen/
04/10/2005, 21h43
Trap D
Juste une question sur
Code:

1 2 [27] UnaryExpr ::= UnionExpr | '-' UnaryExpr
Ça veut dire que tu admets des choses comme

- - - - - 3 ?

ou j'ai rien compris :cry:
04/10/2005, 21h44
GrandFather

Citation:

Envoyé par DrTopos

As-tu essayé ça:

ftp://ftp.fourthought.com/pub/BisonGen/

Bison génère du code en C, il me semble... :?

En tout cas, merci DrTopos, je vais étudier cela... :)
04/10/2005, 21h45
GrandFather

Citation:

Envoyé par Trap D

Ça veut dire que tu admets des choses comme

- - - - - 3 ?

ou j'ai rien compris :cry:

Tout à fait. :)
C'est l'opérateur (arithmétique) de plus haute priorité de la grammaire.
04/10/2005, 21h56
Trap D

D'accord, donc tu n'utilises pas les parenthèses ?
Tu ne peux pas utiliser la notation polonaises ? tu n'aurais plus de problème de précédence.

Tu peux t'en sortir en réécrivant les règles récursives à gauche à condition d'introduire les symboles suivants :

Code:

1
2
3
{} pour indiquer un groupement
[] pour indiquer un choix
* pour indiquer une répétition facultative

ce qui donne :

Code:

1
2
AdditiveExpr       ::=  MultiplicativeExpr {[+ -] MultiplicativeExpr}*
MultiplicativeExpr ::=  UnaryExpr {[MultiplyOperator 'div' 'mod'] UnaryExpr}*

et la reconnaissance de la règle AdditiveExpr en pseudo-code Java :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
TreeNode additiveExpr() {
  TreeNode m = multiplicativeExpr();
  if (m == null) {
    // Erreur
  }
 
  Token t = currentToken();
  while (t == PLUS || t == MINUS) {
      nextToken();
      TreeNode n = multiplicativeExpr();
      if (n == null) {
        // Erreur
      }
 
      m = new TreeNode(m, t, n);
      t = currentToken();
    }
  }
  return m;
}

05/10/2005, 05h24
DrTopos

Citation:

Envoyé par GrandFather

Bison génère du code en C, il me semble... :?

Non, justement, BisonGen génère du code en Python (si j'ai bien compris), et il accepte la grammaire au format XML.

L'élimination de la récursion gauche à la main dans une grammaire contenant visiblement plus de 30 règles risque d'être très périlleuse. De toute façon je pense que toute méthode à la main risque d'être périlleuse. J'ai moi aussi fait des parsers à la main et je ne connais pas de programmation plus galère que ça. A tel point que dans mon langage Anubis, j'ai même commencé la réalisation d'un clone de YACC/BISON. Je suis allé jusqu'à la génération de l'automate, mais je n'ai pas encore écrit le code qui transforme cet automate en programme Anubis. Il faut dire qu'avec Anubis, il y a de telles contraintes de type, que c'est un peu un casse-tête.

Je ne sais pas ce que va donner BisonGen, mais si ça marche, il n'y a pas à hésiter. Avec ta grammaire, il se peut que l'automate réalisé par BisonGen contienne plusieurs centaines d'états. Pour la gramaire d'Anubis, qui n'est pas très compliquée quand même, mais qui contient elle aussi plein de récursion gauche, l'automate généré par Bison a 624 états. Autant dire que faire ça à la main est presque suicidaire.

Ce que tu peux faire est de vérifier que l'automate généré par BisonGen est le même que celui généré par BISON. J'ai tout à fait confiance en ce que fait BISON, pour l'avoir utilisé des centaines de fois. Ce serait une sécurité.
05/10/2005, 11h14
GrandFather

Citation:

Envoyé par Trap D

Tu ne peux pas utiliser la notation polonaises ? tu n'aurais plus de problème de précédence.

En fait, la grammaire XPath est partagée entre 4 types de règles (en tout une quarantaine de règles) :
- celles qui régissent l'analyse lexicale
- celles qui traitent des opérations mathématiques (celles que j'ai postées)
- celles qui traitent des opérateurs logiques
- celles qui définissent la recherche dans un arbre XML (ça ressemble à un chemin de fichier Unix, avec des prédicats en plus)
La notation polonaise réglerait mon problème de précédence, mais ne m'arrangerait pas du tout pour implémenter le restant des règles.

herve91 >> Effectivement, ça règlerait le problème des opérations arithmétiques, mais je me vois mal modifier le reste des règles... Comme je n'ai pas le bagage théorique pour pouvoir m'assurer que les deux grammaires resteront équivalentes, je préfère suivre le conseil de DrTopos et essayer de trouver une méthode d'analyse qui ne nécessite pas (ou très peu) de modification de la grammaire. :?

DrTopos >> Ca semble effectivement être la solution optimale, d'autant plus que les créateurs de BisonGen sont également ceux de plateforme 4suite, qui par ailleurs intègre une implémentation de XPath en Python qui fait référence. Un gage de sérieux, a priori. :)

:merci:
10/10/2005, 08h34
GrandFather

Vos conseils m'ont permis d'y voir plus clair, et d'arrêter une décision : je vais transformer la grammaire afin de pouvoir lui appliquer la méthode de la descente récursive.

:merci: à tous !