XML and non-deterministic content models
Here are postings from Joe English and James Clark on XML and non-deterministic content models. Answers to a FAQ that goes back to "SGML" before it became ISO 8879:1986. See SGML/XML Notion of Ambiguity (non-deterministic content models)
Date: Sun, 14 Jan 2001 09:58:16 -0800 From: Joe English <email@example.com> To: firstname.lastname@example.org Subject: Re: should all XML parsers reject non-deterministic content models?
TAKAHASHI Hideo wrote:
> I understand that the XML 1.0 spec prohibits non-deterministic (or, > ambiguous) content models (for compatibility, to be precise). > Are all xml 1.0 compliant xml processing software required to reject > DTDs with such content models?
No: a processor can ignore the DTD entirely and still be compliant. And since the prohibition against non-deterministic content models appears in a non-normative appendix, I would presume that conforming DTD-aware processors are not required to detect this condition either. Even in full SGML, ambiguous content models are a "non-reportable markup error", i.e., parser don't need to detect this condition.
> Ambiguous content models doesn't cause any problems when you construct a > DFA via an NFA. I have heard that there is a way to construct DFAs > directly from regexps without making an NFA, but that method can't > handle non-deterministic regular expressions.
There are many, many other ways to validate documents against content models though. Take a look at James Clark's TREX implementation, which has no problem with ambiguity, and also efficiently handles intersection, negation, and interleaving of content models (the first two of which are *very* expensive in a DFA-based approach).
> If you choose that method > to construct your DFA, you will surely benefit from the rule in XML 1.0 > . But if you choose not, detecting non-deterministic content models > become an extra job.
But note that detecting ambiguity in XML content models is considerably simpler than in SGML -- the really difficult part involves '&' groups which aren't present in XML.
Date: Sun, 14 Jan 2001 17:42:16 +0700 From: James Clark <email@example.com> To: Daniel.Veillard@imag.fr Cc: "TAKAHASHI Hideo(BSD-13G)" <firstname.lastname@example.org>, email@example.com, firstname.lastname@example.org Subject: Re: should all XML parsers reject non-deterministic content models?
Daniel Veillard wrote:
> On Sun, Jan 14, 2001 at 04:42:55PM +0900, TAKAHASHI Hideo(BSD-13G) wrote: > > Hello. > > > > I understand that the XML 1.0 spec prohibits non-deterministic (or, > > ambiguous) content models (for compatibility, to be precise). > > Note also that this is stated in a non-normative appendix.
It is also stated normatively in the body of the spec (http://www.w3.org/TR/REC-xml#sec-element-content): "For compatibility, it is an error if an element in the document can match more than one occurrence of an element type in the content model."
> > Are all xml 1.0 compliant xml processing software required to reject > > DTDs with such content models? > > Since it is stated as non-normatively only I don't think this is the > case in theory.
It states normatively that it is an error. However, when the XML Rec says merely that something is an error, a conforming XML processor is not required to report it. If it said "it is a fatal error", then a conforming XML processor would be required to report it.
> In prectice this can be a problem. I recently faced a problem with > a DtD developped at the IETF which was clearly non-determinist. This > also means that this introduce new classes of XML parser among the > validating ones: > - those who detect and report non-determinist content model > - those who validate (correctly) or not using non-determinist > content model
> > Ambiguous content models doesn't cause any problems when you construct a > > DFA via an NFA. I have heard that there is a way to construct DFAs > > directly from regexps without making an NFA, but that method can't > > handle non-deterministic regular expressions. If you choose that method > > to construct your DFA, you will surely benefit from the rule in XML 1.0 > > . But if you choose not, detecting non-deterministic content models > > become an extra job. > > I tried to read the Brüggemann-Klein thesis listed in reference and > found it a bit frightening, though very informative. The beginning > of the Part I on Document Grammar for example makes clear that SGML > view of unambiguity of the content model is really a 1 token lookahead > determinism. > In practice this is a very good rule because it allows to simplify > the validation of a content model a lot.
Complicating things for the user to make things simpler for the parser writer seems in general a bad trade-off to me. Also this decreases interoperability (as you've observed). The only justification is compatibility with SGML.
In fact, there is a very simple algorithm available that handles non-determinism just fine (it doesn't require you to construct a NFA and then do the subset construction). See http://www.flightlab.com/~joe/sgml/validate.html (TREX uses a variation on this).
> Problem is that grammars > need to be rewritten to conform to it (the thesis proves it's always > possible at lest).
The thesis proves the opposite: that there are some regular expressions that do not denote 1-unambiguous languages (see p52). She gives the example of
Prepared by Robin Cover for The XML Cover Pages archive.