[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Must DTDs constrain order?

• From: Rick JELLIFFE <ricko@g...>
• To: xml-dev@l...
• Date: Sat, 28 Oct 2000 05:02:53 +0800

Michael Rossi wrote:
 
>         In an SGML DTD you would do this with the "&" operator.
> Unfortunately, XML has dropped the "&" in the interest of simplicity (that
> is, simplicity of parser implementation). Maybe now that we're all
> sophisticated enough to handle XML Schemas, we should bring back the "&" in
> DTDs. :-) But I digress.

The Schema WG took a decision that, for XML Schemas 1.0, we wanted it to
be able to be implemented using a (deeterministic) Finite State Machine,
if possible. 

This has two ramifications. First that the content models do not require
lookahead or backtracking: so unambiguous content models are not
allowed.

Second, that the SGML "&" operator could easily cause combinatorial
explosions 
that were not expected by the user, especially if nested within
repeating groups of various sorts.  This could, in fact, be used as a
kind of virus. 

Rather than completely banning them, the WG has allowed an <any> group
at the top-level only. Of course, this is also subject to combinatorial
explosions, but not at nearly the same rate, and probably not of the
same order (anyone who can spare the time working out the order, please
post it to this list: I guess that an any group is O(n!) but it is not
my game.)

Of course, it can be solved simply by implementing an any group as an
array rather than a FSM.  

If it can be shown that there is no need to worry, and that allowing
FSMs implementations does not simplify implementations, then it is not
impossible that some future version of XML Schemas could relax these
rules.  But they are not arbitrary.

Rick Jelliffe

• References:
  • RE: Must DTDs constrain order?
    • From: Michael Rossi <mrossi@c...>

• Prev by Date: Re: foo:space instead of xml:space?
• Next by Date: Re: Global attributes (was Mapping XHTML to XLink via ArchitecturalForms)
• Previous by thread: Re: Must DTDs constrain order?
• Next by thread: Re: Must DTDs constrain order?
• Index(es):
  • Date
  • Thread