Here's another interesting one:
<!ELEMENT X (A, Y, B)>
<!ELEMENT Y (X)?>
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.
Wilco.
-----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
jenglish@flightlab.com
------------------------------------------------------------------
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@lists.xml.org