OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [xml-dev] interleave algorithm?

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


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


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

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
> to implement the "interleave" pattern.  Are there any published
algorigthms or
> open-source implementations of a similar nature that I could access and
> (for free!)
> I have a _very_ rough idea how one might attempt it in Ruby (using
> and Python (generators) but the language I am working in (Xbase++) has
> 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>