A DTD problem: "Content model is not determinist"

[Michael Strorm]

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>

[Richard Tobin]

In article <11**********************@z14g2000cwz.googlegroups .com>,
Michael Strorm <ms*****@yahoo.co.uk> 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

[Michael Strorm]

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

[Steve Jorgensen]

On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <ms*****@yahoo.co.uk> 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.

[C. M. Sperberg-McQueen]

Steve Jorgensen <no****@nospam.nospam> writes:

On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <ms*****@yahoo.co.uk> 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)>

?

[Michael Strorm]

C. M. Sperberg-McQueen wrote:

Steve Jorgensen <no****@nospam.nospam> 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]

Steve Jorgensen wrote:

On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <ms*****@yahoo.co.uk> 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

[Peter Flynn]

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]

C. M. Sperberg-McQueen wrote:

Steve Jorgensen <no****@nospam.nospam> writes:

On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <ms*****@yahoo.co.uk>
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

[Alain Frisch]

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

[Peter Flynn]

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