Re: [xml-dev] interleave algorithm?

[Gary Stephenson <garys@ihug.com.au>]

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@flightlab.com>
To: <xml-dev@lists.xml.org>
Sent: Wednesday, October 17, 2001 12:39 AM
Subject: Re: [xml-dev] 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@flightlab.com
>
> -----------------------------------------------------------------
> 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>
>