Eric van der Vlist wrote:
>Bonjour,
>
>
re,
>Le lundi 28 février 2005 à 14:07 +0100, Laurent Jouanneau a écrit :
>
>
>>Bonjour,
>>
>>Ça fait un petit moment que je suis abonné à la liste, mais ceci est mon
>>premier message. Petite présentation donc : je suis développeur d'appli
>>basée sur le framework de Mozilla (C++/XPCOM/XUL etc..), fondateur du
>>site http://xulfr.org, co-fondateur du site http://openweb.eu.org.
>>
>>
>
>Bien!
>
>
>
>>Je réalise actuellement un validateur RelaxNG, et j'ai un petit souci
>>avec le pattern <text />.
>>
>>Si j'ai bien compris les specs (et le livre d'Eric sur RelaxNG ;-), le
>>pattern <text /> est "positif" quand :
>>- il y a un noeud texte (ou cdata) avec du texte
>>- il y a un noeud texte (ou cdata) avec seulement des caractères "blancs"
>>- quand il n'y a pas de noeud texte.
>>
>>(cf :
>>* http://books.xmlschemata.org/relaxng/ch05s02.html#id2821949 "More
>>precisely, it matches zero or more text nodes"
>>* http://www.relaxng.org/spec-20011203.html#text-pattern "a text element
>>matches zero or more strings" )
>>
>>
>>Imaginons ce bout de schema RelaxNG (que l'on retrouve dans le schema
>>RelaxNG de RelaxNG : http://www.relaxng.org/spec-20011203.html#IDA5MCS
>>au niveau du <define name="other"/>)
>>
>><element>
>> ....
>> <zeroOrMore>
>> <choice>
>> <attribute>
>> <anyName/>
>> </attribute>
>> <text/>
>> </choice>
>> </zeroOrMore>
>></element>
>>
>>Ce schema indique que l'élément peut contenir n'importe quel attribut OU
>>un noeud text, et ce en un nombre indéterminé. D'une manière générale,
>>le problème existe avec ce schema :
>>
>><element>
>> ....
>> <zeroOrMore>
>> <choice>
>> <pattern_quelconque />
>> <text/>
>> </choice>
>> </zeroOrMore>
>></element>
>>
>>ou même
>>
>><element>
>> <zeroOrMore>
>> <text/>
>> </zeroOrMore>
>></element>
>>
>>imaginons alors par exemple cette balise :
>><foo />
>>
>>comme il n'y a pas d'attribut le pattern <text /> s'applique, et est
>>finalement positif (puisque valide l'absence de noeud text).
>>Du coup <zeroOrMore> est valide.
>>Bien sûr, puisque "zero ou plus", il faut vérifier une nouvelle fois
>>que les sous-patterns de zeroOrMore ne valident pas encore une fois.
>>D'où, une boucle dans mon implementation.
>>
>>Mais voilà, dans ce cas précis : ça tourne en boucle indéfiniement
>>puisque le pattern <text /> valide toujours.
>>
>>Donc je m'interroge :
>>- un "bug" dans les specs de RelaxNG ?
>>- une mauvaise interpretation de ma part au sujet de <text/> ou de
>><zeroOrMore /> ? (ou même <oneOrMore> puisque le problème existe aussi
>>avec lui)
>>- mon implémentation est-elle incorrecte ? Mais alors, quand arreter
>>cette boucle ? Quand est ce que le pattern <zeroOrMore> ne devrait-il
>>plus "matcher" dans ce cas ?
>>
>>
>>Merci d'avance pour vos idées..
>>
>>
>
>Je pense qu'il faut distinguer deux types de documentations... La
>description que l'on donne d'un langage dans un livre (qui cherche à
>être didactique) et la formalisation d'un langage qui est faite dans sa
>spécification ont des buts très différents et ne sont pas
>interchangeables :-) ...
>
>Dans le cas de RELAX NG, la référence est la norme ISO
>(http://dsdl.org/relaxng-is.pdf) et mon livre doit être vu comme une
>vulgarisation pour les auteurs de schémas RNG qui ne veulent pas rentrer
>dans la description mathématique du langage plus que comme une référence
>pour les implémenteurs.
>
>
Je comprend bien. Seulement je trouve dommage qu'il n'existe pas de
specs qui soient accessibles aux développeurs autre que ceux qui ont un
BAC + 15 et qui savent donc interpreter toutes ces descriptions
mathématiques utilisées dans les specs de RelaxNG (dans la section
semantics surtout :-/ ). Mais bon c'est peut-être moi aussi qui suit
trop rouillé aprés toutes ces années à ne pas avoir fait de math (et
aprés tout, je n'ai qu'un bac C+ 4 :-) ).
Aussi me suis-je rabattu en partie sur des explications un peu plus
verbeuses, tels que votre livre. Même si il n'est pas déstiné aux
développeurs, il est suffisement bien écrit pour qu'on puisse avoir
quelques idées sur ce qu'il faut implementer et comment.
>Pour ceux-ci; James Clark a publié des notes d'implémentation assez
>détaillées (http://www.thaiopensource.com/relaxng/implement.html) qu'ils
>peuvent suivre s'ils le souhaitent ainsi qu'une suite de tests
>(http://thaiopensource.com/relaxng/testSuite.zip) permettant de vérifier
>la conformité de leurs implémentations.
>
>
Je connais ces notes d'implémentation. Le problème est que je n'arrive
pas du tout à me faire au Haskell, et donc à comprendre ce qu'il a
écrit... J'avais donc laissé tomber à l'époque où j'ai commencé mon
validateur.
Pour ce qui est de la testSuite, je comptais bien la passait (j'ai pour
le moment ma propre suite de tests)
>Vous pouvez également vous inspirer de l'implémentation (partielle) que
>j'ai écrit en Python et qui s'inspire très fortement des notes de James
>Clark : http://downloads.xmlschemata.org/python/xvif/
>
>Il n'est pas évident de comparer l'algorithme que vous décrivez
>brièvement et celui de James Clark puisqu'ils semblent prendre le
>problème de la validation de manière diamétralement opposée.
>
>James Clark décrit une méthode dite "par dérivation" adaptée de celles
>qui permettent d'écrire des processeurs d'expressions régulières : en
>gros, on calcul la "dérivée" du schéma par le document en enlevant du
>schéma ce que l'on trouve dans le document et le document est valide si
>l'on n'a détecté aucune erreur pendant la validation et si tout ce qui
>reste dans le schéma à la fin de la validation est optionnel.
>
>
J'aurais du poser la question plutôt : qu'est ce que la méthode par
dérivation ? Vous avez reussi à m'expliquer en quelques mots ce que j'ai
tenté de comprendre dans les nombreuses pages de James Clark pendant
longtemps :-)
Donc oui, effectivement, je n'ai pas utilisé un algorithme par
dérivation comme James Clark. En gros, mon implémentation lit le schema
RelaxNG pour produire une serie de graphe (deterministes). Ensuite,
lorsque j'ai besoin de valider, un automate lit/execute ces graphes.
Chaque noeud du graph teste quelque chose (un noeud DOM, text ou
element, un attribut...), et si le test est ok, le noeud DOM ou
l'attribut est enlevé d'une liste de noeud/attributs à valider. Si à la
fin du parcours du graph, cette liste est non vide, ce n'est pas valide.
Il m'a semblé que c'était une bonne méthode de faire, vis à vis de mes
contraintes (pouvoir faire de la validation quasi temps-réèl, que ce
soit sur des fragments de document ou sur un document entier).
D'ailleurs, jusqu'au stade actuel (c'est à dire, presque terminé), cela
a trés bien fonctionné. Jusqu'à ce que je tombe sur ce "bug"...
>En suivant ce principe, mon écriture de la dérivation d'un pattern
>"oneOrMore" par un noeud est :
>
> def deriv(self, node):
> pderiv = self.p.deriv(node)
> if pderiv == notAllowed:
> if self.p.nullable():
> pderiv = self.savp.deriv(node)
> if pderiv == notAllowed:
> return pderiv
> else:
> self.p = pderiv
> return self
> else:
> return pderiv
> else:
> self.p = pderiv
> return self
>
>C'est à dire que je calcul la dérivée de la valeur actuelle du pattern
>inclus dans le pattern "oneOrMore" par le noeud (pderiv =
>self.p.deriv(node)).
>
>S'il n'y a pas d'erreur, je conserve cette valeur (c'est que l'on est
>toujours dans la même "boucle" pour reprendre votre terminologie).
>Sinon, je regarde s'il n'y avait que des patterns optionnels dans "la
>boucle courante" (self.p.nullable()).
>
>Si ce n'est pas le cas il y a erreur, sinon je pars dans une nouvelle
>boucle en dérivant la valeur initiale du pattern inclus dans le pattern
>oneOrMore (pderiv = self.savp.deriv(node)).
>
>J'espère que vous pourrez adapter tout cela à votre propre
>implémentation!
>
>
Je ne sais pas. Mon validateur étant quasi terminé, implémenter votre
algorithme reviendrait peut être à tout remettre en question :-/ Mais ça
m'est en tout cas instructif, et peut-être que cela va m'aider à trouver
une solution complète (car entre temps trouvée mais seulement en partie).
Merci
---
Laurent Jouanneau
http://www.disruptive-innovations.com
--
Devenez redacteur <XML>fr et contribuez au developpement du
xml francophone (http://xmlfr.org/infos/redacteurs/) !
Liste de diffusion "xml-tech@xmlfr.org" (http://xmlfr.org).
Cette liste est a votre disposition pour discuter en francais de
tout sujet technique lie a XML.
Pour resilier votre abonnement, envoyez un message contenant
la commande "unsubscribe" a xml-tech-request@xmlfr.org
(mailto:xml-tech-request@xmlfr.org?Subject=unsubscribe)
Received on Mon Mar 7 18:18:55 2005
