A DTD problem: "Content model is not determinist"

Discussion in 'XML' started by Michael Strorm, Aug 19, 2005.

  1. Hi!

    I've been having problems with a DTD. Having had the Sun XML validator
    reject a document, I put it through 'xmllint' for more information.

    'Xmllint' noted a problem with the DTD itself;
    "validity error : Content model of section is not determinist: (text ,
    (list , text)* , list?)"

    Here's a very simplified version of the DTD demonstrating the problem:-
    <?xml version="1.0" encoding="iso-8859-1"?>
    <!ELEMENT section (text, (list, text)*, list?)>
    <!ELEMENT list (item+)>
    <!ELEMENT item (text)>
    <!ELEMENT text (#PCDATA)*>

    The section element is the problem line; it should permit *any*
    sequence of alternating <text> and <list> elements that start with a
    <text> element.

    My guess... either I've broken a specific rule of XML, or (as I suspect
    from the use of the word 'determinist') there's a fundamental ambiguity
    of logic in there. I *don't* think the problem is a bug in xmllint, as
    Sun's XML validator had previously given unexpected results (hence my
    use of xmllint for more info).

    (Sample documents are at the end of this post, if that's any help).

    Any feedback would be appreciated. Thank you!

    - MS

    ==================================





    <?xml version="1.0" encoding="iso-8859-1"?>
    <!DOCTYPE section SYSTEM "problem.dtd">
    <section>
    <text>Filler 1</text>
    <list>
    <item><text>Filler 2a</text></item>
    <item><text>Filler 2b</text></item>
    </list>
    <text>Filler 3</text>
    <list>
    <item><text>Filler 4a</text></item>
    <item><text>Filler 4b</text></item>
    </list>
    </section>



    <?xml version="1.0" encoding="iso-8859-1"?>
    <!DOCTYPE section SYSTEM "problem.dtd">
    <section>
    <text>Filler 1</text>
    <list>
    <item><text>Filler 2a</text></item>
    <item><text>Filler 2b</text></item>
    </list>
    <text>Filler 3</text>
    <list>
    <item><text>Filler 4a</text></item>
    <item><text>Filler 4b</text></item>
    </list>
    <text>Filler 5</text>
    </section>
     
    Michael Strorm, Aug 19, 2005
    #1
    1. Advertising

  2. In article <>,
    Michael Strorm <> wrote:
    >"validity error : Content model of section is not determinist: (text ,
    >(list , text)* , list?)"


    A content model has to be deterministic in the sense that at every point,
    there must only be one label in the content model that matches the next
    element. In your content model, when there is a <list> after a <text>,
    there are two possibilities: the text in the starred group, and the
    one at the end.

    Usually it is possible to rewrite your content model so that it is
    deterministic, but unfortunately not in this case. Yours is an example
    of the simplest non-determinizable content model. (It's the same as
    the chess game model where black and white must alternate.)

    You'll just have to make do with a less precise content model that won't
    check the alternation, such as (text|list)*

    -- Richard
     
    Richard Tobin, Aug 19, 2005
    #2
    1. Advertising

  3. I appreciate your help, and I see what you are saying.

    I'll understand if you don't want to get in a longwinded discussion
    about this, but..... why should this be a problem? Is it to do with
    keeping the XML parsers reasonably simple?

    Put another way; once the whole <section> element has been read, there
    is no ambiguity. If the <list> that was ambiguous is the final element,
    it corresponds to the final 'list?'. If it is followed by another
    <text>, it must be the other list, in the '(list | text)*'.

    Out of interest, is this a limitation of DTDs or with XML in general?
    (Having used DTDs a bit, I can understand why they wanted to replace
    them with the likes of XML Schema and Relax NG...)

    Anyway, thanks!

    - MS
     
    Michael Strorm, Aug 19, 2005
    #3
  4. On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <> wrote:

    >I appreciate your help, and I see what you are saying.
    >
    >I'll understand if you don't want to get in a longwinded discussion
    >about this, but..... why should this be a problem? Is it to do with
    >keeping the XML parsers reasonably simple?


    It's more like keeping them from being completely intractible. There's a fine
    line between a set of rules that guarantees to reject all non-deterministic
    models, but also rejects many that are theoretically deterministic, and a set
    of rule for which code cannot be written that can determine the determinism of
    a model and be guaranteed to finish making the determination in finite time.

    Now, add to that the fact that if you make one parser smarter than another by
    handling just a few more cases than the conservative spec., that parser will
    successfully process a model that a 3rd party's parser might not, so you'll
    blithely use yours to create a model that can't be used to communicate with
    some 3rd parties.

    >Put another way; once the whole <section> element has been read, there
    >is no ambiguity. If the <list> that was ambiguous is the final element,
    >it corresponds to the final 'list?'. If it is followed by another
    ><text>, it must be the other list, in the '(list | text)*'.
    >
    >Out of interest, is this a limitation of DTDs or with XML in general?
    >(Having used DTDs a bit, I can understand why they wanted to replace
    >them with the likes of XML Schema and Relax NG...)


    XML Schema does not help in this case. I don't know about RELAX NG.
     
    Steve Jorgensen, Aug 19, 2005
    #4
  5. Steve Jorgensen <> writes:

    > On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <> wrote:


    > >Out of interest, is this a limitation of DTDs or with XML in general?
    > >(Having used DTDs a bit, I can understand why they wanted to replace
    > >them with the likes of XML Schema and Relax NG...)


    > XML Schema does not help in this case. I don't know about RELAX NG.


    Relax NG does not require content models to be
    deterministic.

    -C. M. Sperberg-McQueen
    World Wide Web Consortium

    p.s. By the way, is there a strong reason to require 'text'
    elements between lists, instead of just writing

    <!ELEMENT section (#PCDATA | list)*)>
    <!ELEMENT list (item+)>
    <!ELEMENT item (#PCDATA)>

    ?
     
    C. M. Sperberg-McQueen, Aug 19, 2005
    #5
  6. C. M. Sperberg-McQueen wrote:
    > Steve Jorgensen <> writes:
    > p.s. By the way, is there a strong reason to require 'text'
    > elements between lists, instead of just writing
    >
    > <!ELEMENT section (#PCDATA | list)*)>
    > <!ELEMENT list (item+)>
    > <!ELEMENT item (#PCDATA)>


    I wrote it that way because it made processing the document with XSLT
    (which I didn't know previously) simpler. There may be ways of getting
    the same end-result with a document structured as you mention above,
    and if I have time, I'll try it.

    However, I'm taking a "breadth-first" approach with this project (in an
    attempt to curb my overly "depth-first" tendencies where I concentrate
    on perfecting one thing before I do the next), and so I'm leaving it
    the old way just now; if I was in that position now, I might write it
    differently.

    - MS
     
    Michael Strorm, Aug 20, 2005
    #6
  7. Steve Jorgensen wrote:
    > On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <> wrote:
    > >I'll understand if you don't want to get in a longwinded discussion
    > >about this, but..... why should this be a problem? Is it to do with
    > >keeping the XML parsers reasonably simple?

    >
    > It's more like keeping them from being completely intractible. There's a fine
    > line between a set of rules that guarantees to reject all non-deterministic
    > models, but also rejects many that are theoretically deterministic, and a set
    > of rule for which code cannot be written that can determine the determinism of
    > a model and be guaranteed to finish making the determination in finite time.


    Very Computer Science-y...

    So, what you're saying is that XML is being hobbled by the need to
    support all those plebs out there who're still running computers based
    on old-fashioned Turing-machine architectures? (^_^)

    (In all seriousness, do these proofs assume that the architecture is
    basically a Turing-machine? I have to admit that although I find this
    stuff interesting, I'm no computer scientist...)

    - MS
     
    Michael Strorm, Aug 20, 2005
    #7
  8. Michael Strorm

    Peter Flynn Guest

    Michael Strorm wrote:

    > I appreciate your help, and I see what you are saying.
    >
    > I'll understand if you don't want to get in a longwinded discussion
    > about this, but..... why should this be a problem? Is it to do with
    > keeping the XML parsers reasonably simple?
    >
    > Put another way; once the whole <section> element has been read,


    Parsers aren't allowed to do this kind of backtracking to see "what might
    have happened if..."

    > there
    > is no ambiguity. If the <list> that was ambiguous is the final element,
    > it corresponds to the final 'list?'. If it is followed by another
    > <text>, it must be the other list, in the '(list | text)*'.


    It's too late by then,

    > Out of interest, is this a limitation of DTDs or with XML in general?


    It's a limitation built into SGML, which XML inherited.

    > (Having used DTDs a bit, I can understand why they wanted to replace
    > them with the likes of XML Schema and Relax NG...)


    That won't help any, I'm afraid. They are just alternative (and richer)
    syntaxes for saying the same thing.

    If you really need a content model this loose, don't use a DTD or Schema
    at all, just make sure the file is well-formed.

    ///Peter
     
    Peter Flynn, Aug 21, 2005
    #8
  9. Michael Strorm

    Peter Flynn Guest

    C. M. Sperberg-McQueen wrote:

    > Steve Jorgensen <> writes:
    >
    >> On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <>
    >> wrote:

    >
    >> >Out of interest, is this a limitation of DTDs or with XML in general?
    >> >(Having used DTDs a bit, I can understand why they wanted to replace
    >> >them with the likes of XML Schema and Relax NG...)

    >
    >> XML Schema does not help in this case. I don't know about RELAX NG.

    >
    > Relax NG does not require content models to be
    > deterministic.


    I haven't used it much, so I didn't realise that, thanks.

    But what does it do if you try to export a non-deterministic model as a DTD
    or W3C Schema?

    ///Peter
     
    Peter Flynn, Aug 21, 2005
    #9
  10. Michael Strorm

    Alain Frisch Guest

    Peter Flynn , dans le message (comp.text.xml:69570), a écrit :
    > But what does it do if you try to export a non-deterministic model as a DTD
    > or W3C Schema?


    What do you mean? XML-Schema and Relax-NG just have different expressive
    power. Some schemas in one system simply cannot be "exported" to the
    other; any converter has to be partial (either failling for some inputs or
    computing an approximation).


    -- Alain
     
    Alain Frisch, Aug 21, 2005
    #10
  11. Michael Strorm

    Peter Flynn Guest

    Alain Frisch wrote:

    > Peter Flynn , dans le message (comp.text.xml:69570), a écrit :
    >> But what does it do if you try to export a non-deterministic model as a
    >> DTD or W3C Schema?

    >
    > What do you mean? XML-Schema and Relax-NG just have different expressive
    > power. Some schemas in one system simply cannot be "exported" to the
    > other; any converter has to be partial (either failling for some inputs or
    > computing an approximation).


    Quite so...what I meant was what kind of error message do you get (if any)?

    ///Peter
     
    Peter Flynn, Aug 21, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Bjoern Wolter

    Problem with external DTD and JAXP

    Bjoern Wolter, Feb 11, 2004, in forum: Java
    Replies:
    0
    Views:
    426
    Bjoern Wolter
    Feb 11, 2004
  2. Joseph Tilian
    Replies:
    0
    Views:
    377
    Joseph Tilian
    Dec 21, 2004
  3. Ronald Fischer
    Replies:
    4
    Views:
    1,806
    Ronald Fischer
    Mar 17, 2005
  4. test
    Replies:
    2
    Views:
    2,175
    Oliver Wong
    Jul 28, 2006
  5. Damiano ALBANI
    Replies:
    5
    Views:
    836
    Soren Kuula
    Aug 27, 2006
Loading...

Share This Page