• From: "Koorn, Wilco" <Wilco@B...>
• To: 'Joe English' <jenglish@f...>, xml-dev@l...
• Date: Thu, 14 Jun 2001 19:22:20 +0200

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@f...]
Sent: 14 June 2001 18:30
To: xml-dev@l...
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@f...

------------------------------------------------------------------
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...

• Prev by Date: Re: How are you using XML?
• Next by Date: Re: How are you using XML?
• Previous by thread: Re: Non-deterministic content model
• Next by thread: RE: Non-deterministic content model
• Index(es):
  • Date
  • Thread