473,703 Members | 2,448 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

A DTD problem: "Content model is not determinist"

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.dt d">
<section>
<text>Filler 1</text>
<list>
<item><text>Fil ler 2a</text></item>
<item><text>Fil ler 2b</text></item>
</list>
<text>Filler 3</text>
<list>
<item><text>Fil ler 4a</text></item>
<item><text>Fil ler 4b</text></item>
</list>
</section>

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

Aug 18 '05 #1
10 7172
In article <11************ **********@z14g 2000cwz.googleg roups.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
Aug 18 '05 #2
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

Aug 19 '05 #3
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.
Aug 19 '05 #4
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)>

?
Aug 19 '05 #5
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

Aug 20 '05 #6
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

Aug 20 '05 #7
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

Aug 21 '05 #8
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
Aug 21 '05 #9
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
Aug 21 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
5385
by: Pete Mahoney | last post by:
Ok I use a textarea to store data input by the user, and then upon them clicking the submit button I store this data to a database. The problem is once the user inputs too much data (about 3 paragraphs or 2020 characters) when they click on the submit button nothing happens. When I say nothing happens I mean just that, nothing at all happens the page just sits there as if nothing at all happened. If I remove one line for the textarea,...
205
10641
by: Jeremy Siek | last post by:
CALL FOR PAPERS/PARTICIPATION C++, Boost, and the Future of C++ Libraries Workshop at OOPSLA October 24-28, 2004 Vancouver, British Columbia, Canada http://tinyurl.com/4n5pf Submissions
3
2706
by: Arpi Jakab | last post by:
I have a main project that depends on projects A and B. The main project's additional include directories list is: ...\ProjectA\Dist\Include ...\ProjectB\Dist\Include Each of the include directories contain a file named "cppfile1.h". In my main project I #include "cppfile1.h". I rely on the order of paths in additional include directories list to get file cppfile1.h from ProjectA and
50
6062
by: Shadow Lynx | last post by:
Consider this simple HTML: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 STRICT//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" > <head> <title>Strict kills my widths!</title> </head> <body> <table style="width:400px; table-layout:fixed;">
5
7164
by: Damiano ALBANI | last post by:
Hello, I'd like to write a single XML Schema for both these documents : <Items> <Item xml:id="id1"> <Name>ABC</Name> ... </Item> <Item xml:id="id2">
4
29385
by: john | last post by:
Hi to All, I am new to html authoring, so sorry if my terminology is not correct or exact. I would like to position a footer div to the bottom of the browser window. As I research in the web shows this could be done a containing element with "min-height: 100%;" and an absolute positioned element (div) inside, aligned to bottom ("position: absolute; bottom:0px")
94
30313
by: Samuel R. Neff | last post by:
When is it appropriate to use "volatile" keyword? The docs simply state: " The volatile modifier is usually used for a field that is accessed by multiple threads without using the lock Statement (C# Reference) statement to serialize access. " But when is it better to use "volatile" instead of "lock" ?
0
8674
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8971
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7878
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6598
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5923
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4435
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4690
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3127
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2463
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.