Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > XML > A DTD problem: "Content model is not determinist"

Reply
Thread Tools

A DTD problem: "Content model is not determinist"

 
 
Michael Strorm
Guest
Posts: n/a
 
      08-18-2005
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>

 
Reply With Quote
 
 
 
 
Richard Tobin
Guest
Posts: n/a
 
      08-18-2005
In article <(E-Mail Removed) .com>,
Michael Strorm <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Michael Strorm
Guest
Posts: n/a
 
      08-19-2005
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

 
Reply With Quote
 
Steve Jorgensen
Guest
Posts: n/a
 
      08-19-2005
On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <(E-Mail Removed)> 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.
 
Reply With Quote
 
C. M. Sperberg-McQueen
Guest
Posts: n/a
 
      08-19-2005
Steve Jorgensen <(E-Mail Removed)> writes:

> On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <(E-Mail Removed)> 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)>

?


 
Reply With Quote
 
Michael Strorm
Guest
Posts: n/a
 
      08-20-2005
C. M. Sperberg-McQueen wrote:
> Steve Jorgensen <(E-Mail Removed)> 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

 
Reply With Quote
 
Michael Strorm
Guest
Posts: n/a
 
      08-20-2005
Steve Jorgensen wrote:
> On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <(E-Mail Removed)> 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

 
Reply With Quote
 
Peter Flynn
Guest
Posts: n/a
 
      08-21-2005
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

 
Reply With Quote
 
Peter Flynn
Guest
Posts: n/a
 
      08-21-2005
C. M. Sperberg-McQueen wrote:

> Steve Jorgensen <(E-Mail Removed)> writes:
>
>> On 18 Aug 2005 17:47:43 -0700, "Michael Strorm" <(E-Mail Removed)>
>> 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


 
Reply With Quote
 
Alain Frisch
Guest
Posts: n/a
 
      08-21-2005
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Convert Java Model to Java Model without XML erinbot@gmail.com Java 1 10-06-2006 09:00 PM
XML file from one DTD to another DTD test Java 2 07-28-2006 08:48 PM
How to specify DTD to DTD.getDTD for DocumentParser? Ronald Fischer Java 4 03-17-2005 09:37 AM
Removing the dtd name when using print(...) on the dtd generated class Joseph Tilian Java 0 12-21-2004 02:58 PM
Including a dtd into another dtd... possible? Asfand Yar Qazi XML 1 09-19-2003 12:10 PM



Advertisments