Re: Non-deterministic content model

[Joe English <jenglish@flightlab.com>]

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