Le lundi 07 mars 2005 à 18:20 +0100, Laurent Jouanneau a écrit :
...
> >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.
C'est plus clair :-) ...
D'après ce que je comprend, vous avez utilisé la méthode "classique"
pour implémenter un processeur de schéma qui repose sur un automate à
états finis.
Pour pouvoir être utilisable facilement tout en donnant des temps de
réponse linéaires, cette méthode impose un certain nombre de contraintes
sur le langage de schéma (notamment que les schémas soient
"déterministes"). W3C XML Schema a accepté ces contraintes mais RELAX
les a rejeté ce qui le rend plus difficile à implémenter avec cette
méthode et je me demande si vous ne tombez pas sur un de ces problèmes.
Ceci dit, Murata Makoto a réussi à écrire une implémentation reposant
sur des automates à états finis mais il a fait peu de communications sur
ce point (à part une démonstration où il a montré que cette
implémentation était suffisamment peu gourmande en mémoire pour tourner
sur son téléphone portable).
Il me semble que Daniel Veillard a également utilisé ce type
d'algorithme pour libxml et vous pourriez regarder de ce côté.
> 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"...
C'est une méthode qui semble en effet plus naturelle que celle de James
Clark mais celui-ci a montré avec le mode NXML pour Emacs que sa méthode
pouvait être adaptée pour une validation partielle en temps réel... Si
LISP vous inspire plus que Haskell, vous pouvez également regarder
cela :-) ...
> >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).
Tenez-nous au courant!
Merci,
Eric van der Vlist
--
Weblog:
http://eric.van-der-vlist.com/blog?t=category&a=English
------------------------------------------------------------------------
Eric van der Vlist http://xmlfr.org http://dyomedea.com
(ISO) RELAX NG ISBN:0-596-00421-4 http://oreilly.com/catalog/relax
(W3C) XML Schema ISBN:0-596-00252-1 http://oreilly.com/catalog/xmlschema
------------------------------------------------------------------------
--
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:46:30 2005
