[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: interleave algorithm?
Hi Joe (and James), Many thanks for your replies. I think I should just 'fess up and admit to being _way_ out of my depth here. I think I might be living proof of the dictum "a little knowledge is a dangerous thing" - in which case I might be seen to be _extremely_ dangerous, due to my having _very_ little knowledge! <g> I managed to cobble together a validating XML parser ( in Xbase++ ) without much difficulty by modelling classes for each of the different types of content models, and compiling the DTD into a list of instances of these classes . Roughly, content-model classes have validate methods that accept as their single parameter the dom element to be validated. An element validates itself by first validating all its child elements, and then calling its content model's validate method. I assume (but am not entirely sure) that in fact I have constructed a sort of finite automaton, but I had no theoretical conception in this regard whilst programming it. When, later on, I tried to get the thing to determine whether the DTD was deterministic or not, I crapped out completely, as I had no theoretical basis from which to proceed. (I managed to detect _some_ non-determinism, but I couldn't see any structural method for catching all cases). Naively, I thought RelaxNG was going to be a similar stroll-in-the-park ;-( , but, of course, I hadn't (and still haven't) understood some of the more thorny details lurking beneath its seductively simple exterior! Sigh.., 46 years old and still a mere babe-in-arms programming wise. My only defense (slim though it be) is that I started late, and am entirely self taught. (Nobody wants to employ a forty-plus year old "junior programmer" ( . Sh*t, I've only got forty or so years left to get on top of this caper - I'd better get a move on! ) thanks again, gary ----- Original Message ----- From: "Joe English" <jenglish@f...> To: <xml-dev@l...> Sent: Wednesday, October 17, 2001 12:39 AM Subject: Re: interleave algorithm? > > Gary Stephenson wrote: > > > > I am trying to implement Relax NG, but am having a hard time > > figuring out how to implement the "interleave" pattern. > > The implementation depends on how you're implementing > the *rest* of Relax-NG. 'Interleave' is probably easiest > to implement if you're using an algebraic approach. > The reduction rule is: > > (e1 ^ e2) \ sym = ((e1 \ sym) ^ e2) | (e1 ^ (e2 \ sym)) > > (where '^' = interleave, | = union, and \ is the transition operator). > > The following simplification rules also hold: > > (e ^ 0) = (0 ^ e) = 0 > (e ^ 1) = (1 ^ e) = e > > > You need to take some care if you're using a finite automaton > based algorithm, since expressions involving '^' can generate > extremely large numbers of states. One approach is to represent > states in M(e1 ^ e2) as _pairs_ of states drawn from M(e1) x M(e2). > > > Are there any published algorigthms or open-source implementations > > of a similar nature that I could access and study? (for free!) > > James Clark's TREX might be a good place to start. > > > --Joe English > > jenglish@f... > > ----------------------------------------------------------------- > The xml-dev list is sponsored by XML.org <http://www.xml.org>, an > initiative of OASIS <http://www.oasis-open.org> > > The list archives are at http://lists.xml.org/archives/xml-dev/ > > To subscribe or unsubscribe from this elist use the subscription > manager: <http://lists.xml.org/ob/adm.pl> >
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|