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

Re: Create XML

• To: "Simon St.Laurent" <simonstl@s...>,"'Xml-Dev'" <xml-dev@l...>
• Subject: Re: Create XML
• From: "Bob Foster" <bob@o...>
• Date: Sat, 14 Jun 2003 19:25:14 -0500
• References: <r01050400-1026-A5DA4B189E6611D7B8650003937A08C2@[192.168.124.11]>

From: "Simon St.Laurent" <simonstl@s...>
> ><!ELEMENT A
> >((B)|(C)|(D)|(B,C)|(B,D)|(C,D)|(C,B)|(D,B)|(D,C)|(B,C,D)|(B,D,C)|(C,B,
> >D)|(C,D,B)|(D,B,C)|(D,C,B)) >
> >
> >That said, this is enough to make order constraints required rather
> >than useful, with 20 children this becomes so tedious the errors are
> >almost guaranteed.
>
> Doesn't that trip over the requirement at:
> http://www.w3.org/TR/REC-xml#sec-element-content
>
> "The content of an element matches a content model if and only if it is
> possible to trace out a path through the content model, obeying the
> sequence, choice, and repetition operators and matching each element in
> the content against an element type in the content model. 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."

(I like little puzzles like this, so please excuse.)

Yes, it does. The expression seems to be trying to solve the problem: at
most one of each term in any order but at least one of some term. You need
to factor this answer to make it unambiguous, e.g.,

(D,((B,C?)|(C,B?))?) | (B,((D,C?)|(C,D?))?) | (C,((D,B?)|(B,D?))?)

Tedium is in the eye of the beholder. One could write a program to generate
this stuff, along the lines of:

e([A]) = A
e(cons(x,y)) = (x,e(y)?)|(e(cons(head(y),cons(x,tail(y))))

But it will still be exponential in the number of elements, so you will not
like the result for 32 elements. ;-}

People often respond that this question is a FAQ, but actually it seems to
be a FWAQ (Frequently Wrongly Answered Question).

> RELAX NG seems to have these kinds of problems under control, at least
> for my purposes.

In RELAX NG, the answer is:

A|B|C|(A?&B?&C?)

RELAX NG validators avoid the exponential expansion vs. backtracking issues
by evaluating only the branch of the tree that matches the input. Superior
technology trumps implementation-motivated restrictions! (Which is what the
next generation will say about RELAX NG. ;-)

Bob Foster

• References:
  • RE: Create XML
    • From: "Simon St.Laurent" <simonstl@s...>

• Prev by Date: Re: modeling, validating and documenting an xml grammar
• Next by Date: Re: modeling, validating and documenting an xml grammar
• Previous by thread: RE: Create XML
• Next by thread: Re: Create XML
• Index(es):
  • Date
  • Thread