W3C home > Mailing lists > Public > xmlschema-dev@w3.org > January 2005

Re: Need help with Unique Particle Attribution Rule

From: Burak Emir <Burak.Emir@epfl.ch>
Date: Fri, 07 Jan 2005 15:02:54 +0100
Message-ID: <41DE968E.6000701@epfl.ch>
To: Vinotha Suntharalingam <vinos@carbontwelve.com>
CC: xmlschema-dev@w3.org

Hello Vinotha,

You might know that there are some regular expressions that just cannot 
be rewritten to something "1-unambiguous" (that conforms to UPA).

[I am assuming you know that by regular expression I talk about the 
content model of a complex type, not just character sets]

Yours looks pretty much like such a "inherently ambiguous" regular 
expression. Don't waste time trying to fix it (find a "proof" below).

The simplest one is this chess thing (see Murali Mani 
http://www.cs.wpi.edu/~mmani/publications/extreme2001chess.ppt)

(a,b)*,a?

If possible, I would factor our the complex type of error in to an 
ErrorType, and then rename the two occurrences of error to adminError 
and deviceError.

On the one hand it seems sad that content models need to be 
1-unambiguous (or deterministic). On the other hand, it facilitates 
implementation and avoids some pitfalls in connection with derivation by 
extension. (Assume you define (a,b)* and somebody extends with a? - 
which type should capture the additional child?)

cheers,
Burak

P.S.:
[as good old Don Knuth would say, "non-mathematical readers please skip"]

Here's how to reduce yours to this one (b = 'admin', a = 'error', c = 
'deviceTypeInfo'). The <: is set inclusion. By some mathematical common 
sense it should be clear that if you take things *away* from the 
language (you pass to a subset), and you cannot find an unambiguous 
regular expression, the richer language will be ambiguous, too.

(b,a?)*,c*,b? == your content model

(b,a?)*,b? <: (remove c*)

b,a?,(b,a?)*,b?  <: (unfold (b,a?)* once)

b,(a?,b)*,a?,b? <: (magic)

b,(a,b)*,a?  <:

Justify the "magic" step would lead a bit far, but you can convince 
yourself that c(dc)* is always the same as (cd)*c (for instance by 
induction).

Vinotha Suntharalingam wrote:

> Hi,
>
> I'm trying to parse an xsd with Xerces and I'm running into UPA rule 
> violation problems. Attached below is relevant sections in the xsd 
> where the problem is encountered. I'm finding it difficult to define 
> the 'systemProvider' element in such way it doesn't violate this rule. 
> Could someone please assist me on how it can be done?
>
> (I tried to follow the name, first-name, last-name example to fix the 
> problem, but this particular element definition seems to be a bit more 
> complicated. Any help would be much appreciated.)
>
> <xsd:element name="systemProvider">
>     <xsd:complexType>
>         <xsd:sequence>
>             <xsd:sequence minOccurs="0" maxOccurs="unbounded">
>                 <xsd:element ref="admin"/>
>                 <xsd:element ref="error" minOccurs="0"/>
>             </xsd:sequence>
>             <xsd:element ref="deviceTypeInfo" minOccurs="0" 
> maxOccurs="unbounded"/>
>             <xsd:element ref="error" minOccurs="0"/>
>         </xsd:sequence>
>     </xsd:complexType>
> </xsd:element>
>
> <!-- The following elements are referenced in the above piece of code -->
>
> <xsd:element name="deviceTypeInfo">
>   <xsd:complexType>
>    <xsd:sequence>
>     <xsd:element ref="deviceType"/>
>     <xsd:element ref="category"/>
>     <xsd:element ref="maxPorts"/>
>     <xsd:element ref="protocolSupported" maxOccurs="unbounded"/>
>    </xsd:sequence>
>   </xsd:complexType>
>  </xsd:element>
>  
> <xsd:element name="protocolSupported">
>   <xsd:complexType>
>    <xsd:simpleContent>
>     <xsd:extension base="xsd:string">
>      <xsd:attribute name="default" use="optional">
>       <xsd:simpleType>
>        <xsd:restriction base="xsd:string">
>         <xsd:enumeration value="true"/>
>        </xsd:restriction>
>       </xsd:simpleType>
>      </xsd:attribute>
>     </xsd:extension>
>    </xsd:simpleContent>
>   </xsd:complexType>
>  </xsd:element>
>  
> <xsd:element name="error">
>   <xsd:complexType>
>    <xsd:sequence>
>     <xsd:element ref="id"/>
>     <xsd:element ref="summary"/>
>     <xsd:element ref="detail" minOccurs="0"/>
>    </xsd:sequence>
>   </xsd:complexType>
>  </xsd:element>
> <xsd:element name="admin">
>   <xsd:complexType>
>    <xsd:sequence>
>     <xsd:element ref="userId"/>
>     <xsd:element ref="password" minOccurs="0"/>
>     <xsd:element ref="userName" minOccurs="0"/>
>    </xsd:sequence>
>   </xsd:complexType>
>  </xsd:element>
> <xsd:element name="summary" type="xsd:string"/>
> <xsd:element name="id" type="xsd:string"/>
> <xsd:element name="detail" type="xsd:string"/>
> <xsd:element name="userId" type="xsd:string"/>
> <xsd:element name="password" type="xsd:string"/>
> <xsd:element name="userName" type="xsd:string"/>
> <xsd:element name="deviceType" type="xsd:string"/>
> <xsd:element name="category" type="xsd:string"/>
> <xsd:element name="maxPorts" type="xsd:string"/>
>
>
> Thank you in advance.
> Vino
>


-- 
Burak Emir

http://lamp.epfl.ch/~buraq
Received on Friday, 7 January 2005 14:03:01 GMT

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