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: Non-deterministic content model

Title: RE: Non-deterministic content model

Here's another interesting one:
<!ELEMENT X (A, Y, B)>

This is like "matching parenthesis" in mathematics. Or am I cheating now because I use two elements?

Note that any recognizer will need a stack to "remember" all a's seen and then pop an 'a' for each 'b'. This is typical for non finite state automaton (deterministic or not) based recognizers.


-----Original Message-----
From: Joe English [mailto:jenglish@flightlab.com]
Sent: 14 June 2001 18:30
To: xml-dev@lists.xml.org
Subject: Re: Non-deterministic content model

Arthur Rother wrote:

> I came across this one in my first lessons on learning DTD's, where I tried
> to write a DTD for a game of chess:
>          ((whitemove, blackmove)*, whitemove?)

That's a neat example.  It's well-known that ((a,b)*,a?)
is hopelessly ambiguous (i.e., there's no way to write
it as deterministic content model), but I've never
seen a real-world example where that construct was
useful before now.

> If this is the only endless case, one could hardcode this in the parser.

It's not -- there's an infinite number of "hopelessly ambiguous"
regular languages.

> How do [XML Spy and XMetal] deal with it?

There are plenty of algorithms for regular expression
matching besides the one prescribed for SGML.
You can convert to a DFA (lex), backtrack (Perl),
use derivatives (TREX), or simulate an NDFA,
to name a few.

The only real problem with nondeterministic
content models in SGML has to do with start-tag
inference (and even that can be worked around).
Since XML doesn't support this feature, it's
not as big of a problem for implementations.

--Joe English


The xml-dev list is sponsored by XML.org, an initiative of OASIS

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@lists.xml.org