Computing derivatives of Regular Expressions for Relax NG

[Verwijderd]

N.B. Het gaat hier niet om POSIX of PCRE regular expressions. Een Relax NG document of DTD is namelijk ook een regular expression.

Ik ben bezig met het maken van een wysiwyg editor en zit er over na te denken om Relax NG te implementeren. James Clark en Kohsuke Kawaguchi zijn in 2001 begonnen aan Jing; een Java implementatie voor het valideren van XML documenten tegen een Relax NG.
Jing is ondertussen uitgegroeid tot een grote parser die meer kan valideren dan Relax NG alleen. Van documenteren heeft Clark nooit gehoord. In een mail die ik kreeg van Kohsuke stond; "It is just the way het writes code".
Op internet heb ik een tweetal waardevolle documenten gevonden:

http://www.kohsuke.org/relaxng/implbook/
http://www.thaiopensource.com/relaxng/derivative.html

Ik heb ze aandachtig gelezen, maar ik kan niet bevatten wat ze nou precies doen. Het basis idee voor het valideren is het maken van een Derivative van een Regular Expression. Voor mijn editor wil ik dus van een gegeven node de Derivative berekenen. De Derivative geeft namelijk aan wat er op die plaats nog ingevoegd mag worden zodat je document nog steeds geldig is. Op die manier kan je een editor maken die gegarandeerd correcte xhtml uitpoept en valideert.

Ik vroeg mij dus af of er hier mensen ervaring hebben met het schrijven van een Relax NG parser en of ze nog boeken danwel andere informatie hebben over het schrijven van zo'n parser. Kortom; kan iemand mij vertellen hoe je precies de afgeleide van een regular expression berekent? De concepten zijn mij namelijk nog niet geheel duidelijk.

offtopic:
NMe

[ Voor 6% gewijzigd door Verwijderd op 25-06-2005 12:58 ]

[Verwijderd]

*kick*
Ik kan me niet voorstellen dat op een forum als tweakers er helemaal niemand is die zich met deze materie bezighoudt...

[Alex]

Mag ik vragen waarom je het wilt gaan implementeren als je niet exact snapt wat het idee erachter is?

[Verwijderd]

Dit lijkt mij nogal een vreemde vraag. Ik zie wat je met een Relax NG parser kan bereiken, ik weet alleen niet hoe je het moet maken. Ik weet welk middel ik moet gebruiken om mijn doel te bereiken, maar ik weet nog niet hoe het werkt.
Relax NG parser wil ik gebruiken om realtime te kunnen bepalen welke elementen ik op die positie in mag voegen. Hoe het precies werkt weet ik niet, daar probeer ik achter te komen.

[MSalters]

Simpel uitgelegd: een regex beschrijft een Finite State Machine. Een derivative is niets meer of minder dan de "valide" transities uit een bestaande state; andere input leidt tot een van de "error" states.

[Verwijderd]

De afgeleide van een PCRE regex snap ik wel; "blurp+ op blurp" is natuurlijk "blurp*", "(a?,b*,c)|(b?,a?,b) op b" is "(b*,c)|(a?,b)|empty_sequence".

Dus het concept afgeleide snap ik wel globaal, maar ik heb geen flauw idee hoe je dit van een Relax NG document bepaalt voor een gegeven node P in je document.

[joopst]

Ik snap niet zo goed wat je niet snapt

die twee documenten heb ik gelezen .. en ze vertellen je toch best uitgebreid wat ze doen ?

je begint met 3 dingen
1. een document dat je hebt getypt
2. een setje nodes die je mag gebruiken in je document
3. regels welke nodes op welke plek mogen

dan ga je het document recursief doorlopen en op elke plek kijken welke van je setje nodes(2) je mag toevoegen. Dit valideer je met de regels van 3.

--
Om nu extra stoer te zijn ga je dat valideren doen met regexen :-)
en om nog stoerder te doen maak je je eigen xml document met een bepaald format zodat je daaruit de gegevens van 2 en 3 kan lezen.

en deze laatste twee 'verstoerders' maken het ingewikkeld.

je kan om toch gemotiveerd te blijven best een paar iteraties doen. Bijv eerst een maken die e.e.a. hardcoded heet en steeds meer dingen stoerder en dynamisch programmeren.