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

Re: should all XML parsers reject non-deterministic content models?

• From: Daniel Veillard <Daniel.Veillard@i...>
• To: James Clark <jjc@j...>
• Date: Sun, 14 Jan 2001 12:39:02 +0100

On Sun, Jan 14, 2001 at 05:42:16PM +0700, James Clark wrote:
> 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."

  Oops, right, I missed this sentence, sorry.

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

  I'm more convinced by the agument that some content models may
not be expressable in an 1-unambiguous languages. But I'm still
a bit worried that either way interoperability will be a concern.
In this case compatibility with SGML generates risk of interoperability
problems between XML tools, "results are undefined" doesn't sound good
(http://www.w3.org/TR/REC-xml#dt-error).

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

  Thanks for the pointer !
  
> 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
> 
>   (a|b)*,a,(a|b)

  Hum, right, this makes sense and is also stated in Appendix E.

    thanks a lot,

Daniel

-- 
Daniel Veillard      | Red Hat Network http://redhat.com/products/network/
daniel@v...  | libxml Gnome XML toolkit  http://xmlsoft.org/
http://veillard.com/ | Rpmfind RPM search engine http://rpmfind.net/

• Follow-Ups:
  • Re: should all XML parsers reject non-deterministic content models?
    • From: "TAKAHASHI Hideo(BSD-13G)" <hideo-t@b...>

• References:
  • should all XML parsers reject non-deterministic content models?
    • From: "TAKAHASHI Hideo(BSD-13G)" <hideo-t@b...>
  • Re: should all XML parsers reject non-deterministic content models?
    • From: Daniel Veillard <Daniel.Veillard@i...>
  • Re: should all XML parsers reject non-deterministic content models?
    • From: James Clark <jjc@j...>

• Prev by Date: Re: Place under sun (was: XPointer and Sun patent)
• Next by Date: RDDL draft 20010114
• Previous by thread: Re: should all XML parsers reject non-deterministic content models?
• Next by thread: Re: should all XML parsers reject non-deterministic content models?
• Index(es):
  • Date
  • Thread