[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Non-deterministic content model
You are correct that the rewritten version is deterministic. It is provable that _every_ non-deterministic content model can be converted to a deterministic content model. The trick is basically to manually 'unroll' the content model. A non-deterministic content model is non-deterministic _because_ a direct conversion of the content model to a state diagram produces a state diagram with a single state and multiple outgoing edges for the same match. To make it determinisitic, collapse the paths together. (A formal discussion of this exists in almost any computation theory book, and in the book "Compilers, Principles, Techniques, and Tools" by Aho, Sethi, and Ullman) MSXML allows non-deterministic content models in DTDs, partially for that reason, but IBM's parser throws an error, so you shuld avoid them for strict parser compatibility. Derek Denny-Brown > -----Original Message----- > From: Steve Rosenberry > [mailto:Steve.Rosenberry@E...] > Sent: Wednesday, June 13, 2001 10:55 AM > To: xml-dev@l... > Subject: Re: Non-deterministic content model > > > > > Marcus Carr wrote: > > > > It would be non-deterministic if it the processor was faced > > with element x in two contexts (for example), such as: > > > > <!ELEMENT a ((x, y) | (x, x))?> > > > > > Ok, now that I think I understand deterministic vs. non-deterministic > that leads to a couple of other questions: > > 1) Would rewriting the above as <!ELEMENT a (x,(x|y))?> convert the > original content model to a deterministic one? As I now > understand the > rules, I believe the rewritten content model to be deterministic. At > 'a' I can either have 'x' or nothing. If I have 'x', it must then be > followed by a single 'x' or 'y'. > > 2) If the rewritten form in (1) is indeed deterministic, will > parsers do > the boolean algebra for me to get from the original content > model to the > rewritten one, or is this going to be a point of > incompatibility between > parsers? XML-Spy seems very happy to validate using either form. > > > > -- > Steve Rosenberry > Sr. Partner > > Electronic Solutions Company -- For the Home of Integration > http://ElectronicSolutionsCo.com > > http://BetterGoBids.com -- The Premier GoTo Bid Management Tool > > (610) 670-1710 > > ------------------------------------------------------------------ > The xml-dev list is sponsored by XML.org, an initiative of OASIS > <http://www.oasis-open.org> > > The list archives are at http://lists.xml.org/archives/xml-dev/ > > To unsubscribe from this elist send a message with the single word > "unsubscribe" in the body to: xml-dev-request@l... >
|
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
|