W3C home > Mailing lists > Public > xmlschema-dev@w3.org > February 2006

RE: Ignore Order while validating XSD

From: Ralf Lammel <Ralf.Lammel@microsoft.com>
Date: Sun, 19 Feb 2006 02:45:05 -0800
Message-ID: <1152E22EE8996742A7E36BBBA7768FEE08B1282B@RED-MSG-50.redmond.corp.microsoft.com>
To: "Mukul Gandhi" <gandhi.mukul@gmail.com>, "Ramkumar Menon" <ramkumar.menon@gmail.com>
Cc: <xmlschema-dev@w3.org>

> I am curious, is the validation happening correctly(for the case a, b,
> c), or is this bug in the validator?

You would need to use left factorization if the approach for exhaustive
enumeration of permutations is meant to cope with UPA.

Here is the concise EBNF demo.
Suppose you want all permutations of A, B+, C.
In EBNF with permutation phrases (say "||") you would write:

S -> A||B+||C

(S being the start symbol.)

In EBNF without "||" and with the goal to use LL(1), you would write:

S -> A ( B+ C | C B+ ) | B+ ( A C | C A) | C ( A B+ | B+ A)

I am not commenting on the scalability of this approach. :-)

HTH
Ralf Laemmel
Microsoft, Webdata/XML
http://www.cwi.nl/~ralf


> -----Original Message-----
> From: xmlschema-dev-request@w3.org
[mailto:xmlschema-dev-request@w3.org]
> On Behalf Of Mukul Gandhi
> Sent: Saturday, February 18, 2006 11:39 PM
> To: Ramkumar Menon
> Cc: xmlschema-dev@w3.org
> Subject: Re: Ignore Order while validating XSD
> 
> 
> You can try something like this. i.e. use xs:choice to select one
> among all the permutations.
> 
> <xs:element name="x">
>   <xs:complexType>
>      <xs:choice>
>        <xs:sequence>
>            <xs:element name="a" type="xs:string"/>
>            <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>        </xs:sequence>
>        <xs:sequence>
>            <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>            <xs:element name="a" type="xs:string"/>
>        </xs:sequence>
>      </xs:choice>
> </xs:complexType>
> 
> This works for this simple case. But once I make it slightly more
> complex as shown below (by introducing another element c), the XSD
> validator(XMLSpy 2006) reports that schema is not valid. It says
> "content model is non-deterministic. Possible causes: name equality,
> overlapping occurence or substitution groups".
> 
> <xs:element name="x">
>    <xs:complexType>
>       <xs:choice>
>          <xs:sequence>
>              <xs:element name="a" type="xs:string"/>
>              <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>              <xs:element name="c" type="xs:string"/>
>          </xs:sequence>
>          <xs:sequence>
>             <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>             <xs:element name="a" type="xs:string"/>
>             <xs:element name="c" type="xs:string"/>
>          </xs:sequence>
>          <xs:sequence>
>             <xs:element name="a" type="xs:string"/>
>             <xs:element name="c" type="xs:string"/>
>             <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>          </xs:sequence>
>          <xs:sequence>
>             <xs:element name="c" type="xs:string"/>
>             <xs:element name="a" type="xs:string"/>
>             <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>          </xs:sequence>
>          <xs:sequence>
>             <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>             <xs:element name="c" type="xs:string"/>
>             <xs:element name="a" type="xs:string"/>
>          </xs:sequence>
>          <xs:sequence>
>             <xs:element name="c" type="xs:string"/>
>             <xs:element name="b" type="xs:string"
maxOccurs="unbounded"/>
>             <xs:element name="a" type="xs:string"/>
>           </xs:sequence>
>        </xs:choice>
>   </xs:complexType>
> </xs:element>
> 
> I am curious, is the validation happening correctly(for the case a, b,
> c), or is this bug in the validator?
> 
> Regards,
> Mukul
> 
> 
> On 2/18/06, Ramkumar Menon <ramkumar.menon@gmail.com> wrote:
> > Hi,
> >
> > is it possible to ignore the document order while using schema
validator
> to
> > validate an XSD ?
> > If not, is there an alternative to the following issue ?
> > I have an element that has a set of elements witihn it, one of them
> being
> > maxOccurs="unbounded". Since I wanted to use the "xsd:all" group so
that
> I
> > can assume unordered child nodes, the node with
maxOccurs="unbounded"
> > prevents me from making such a definition.
> >
> > Any help will be appreciated.
> > pls reply direcly to my email id, since I am not on this mailing
list.
> >
> > rgds,
> > Ram
> >
> > --
> > Shift to the left, shift to the right!
> > Pop up, push down, byte, byte, byte!
> >
> > -Ramkumar Menon
> > A typical Macroprocessor
> 
Received on Sunday, 19 February 2006 10:54:46 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:14:53 GMT