Re: [xml-dev] interleave algorithm?

[James Clark <jjc@jclark.com>]

The easiest way is to use the idea of regular expression derivatives. The
original article is

J. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM,
Volume 11, Issue 4 (October 1964).

There's brief description by Joe English online at

http://www.flightlab.com/~joe/sgml/validate.html

You can get the source code for Jing, which is based on this algoritm, from:

http://www.thaiopensource.com/relaxng/jing.html

The derivative of a regular expression e wrt a string s is a regular
expression that matches any string that when appended to s will match e.
Let's write s\e to denote the derivative of e wrt s.  Then, for example, we
have

foo\foobar = bar
a\a* = a*

Informally, s\e is the regex for what's left of e after matching s.

You match a string against a regular expression by successively computing
the derivative wrt to each character. If the resulting regular expression is
nullable (matches the empty string), then the string as a whole matches.

This works for interleave because for any regular expressions X, Y and any
single character c

c\(X&Y) = ((c\X)&Y)|(X&(c\Y)))

(where | denotes choice and & denotes interleave).

This also handles the element/attribute content models of RELAX NG
straightforwardly.  The idea is that group behaves like interleave when you
take the derivative with respect to an attribute, but behaves like sequence
when you take the derivative with respect to a element or a string.

----- Original Message -----
From: "Gary Stephenson" <garys@ihug.com.au>
To: <xml-dev@lists.xml.org>
Sent: Tuesday, October 16, 2001 11:10 AM
Subject: [xml-dev] interleave algorithm?


> Hi all,
>
> I am trying to implement Relax NG, but am having a hard time figuring out
how
> to implement the "interleave" pattern.  Are there any published
algorigthms or
> open-source implementations of a similar nature that I could access and
study?
> (for free!)
>
> I have a _very_ rough idea how one might attempt it in Ruby (using
codeBlocks)
> and Python (generators) but the language I am working in (Xbase++) has
neither
> of these (er.. well, it does have codeblocks - but not with the nice
> co-routine like capability of those in Ruby).
>
> Many tias,
>
> gary
>
>
> -----------------------------------------------------------------
> 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>
>
>
>