Discussion :

[GrandFather]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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

[GrandFather]

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 !).

[ludovic.fernandez]

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

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

[DrTopos]

As-tu essayé ça:

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

[Trap D]

Juste une question sur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
[27]    UnaryExpr    ::=    UnionExpr 
                            | '-' UnaryExpr

Ça veut dire que tu admets des choses comme

- - - - - 3 ?

ou j'ai rien compris

[GrandFather]

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

[GrandFather]

Ça veut dire que tu admets des choses comme

- - - - - 3 ?

ou j'ai rien compris

Tout à fait.
C'est l'opérateur (arithmétique) de plus haute priorité de la grammaire.

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

[herve91]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

ce qui donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[DrTopos]

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

[GrandFather]

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.

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

à tous !