[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: 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 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@i...> To: <xml-dev@l...> Sent: Tuesday, October 16, 2001 11:10 AM Subject: 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> > > >
|
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
|