Re: is XML Schema context free or context sensitive or something entirely different

XML Schema Formal Description [1] is a work-in-progress (not much
progress lately :-( and should not be considered normative.  The
inference rules it's talking about are not the constraints on schemas
from the REC in any case.

Considered as a grammar for a language over preterminal element
names, W3C XML Schema part 1 is certainly not directly isomorphic to
traditional context-free phrase-structure _grammars_, because

 a) It allows regular expressions on the 'right-hand side';
 b) It allows type definitions to be associated with element names in
    a context-sensitive way.

However, per the Peters and Ritchie result (try google) I suspect that
none-the-less it defines only context-free _languages_, because it
uses an analogue of the node-admissability interpretation (as opposed
to the string-rewriting interpretation) of its rules.

Once you take IDs and key/unique/keyref in to account, we probably get
out of the context-free languages -- how far is not at all obvious.
Not clear we even get to the indexed languages, although I _think_ I
can do a{n}b{n}c{n} as follows (warning, serious key hacking follows):

<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
 <xs:element name="root">
  <xs:complexType>
   <xs:sequence>
    <xs:element ref="a" minOccurs="0" maxOccurs="unbounded"/>
    <xs:element ref="b" minOccurs="0" maxOccurs="unbounded"/>
    <xs:element ref="c" minOccurs="0" maxOccurs="unbounded"/>
   </xs:sequence>
  </xs:complexType>

  <xs:key name="a">
   <xs:selector xpath="a"/>
   <xs:field xpath="@a"/>
  </xs:key>
  <xs:keyref name="ar" refer="b">
   <xs:selector xpath="a"/>
   <xs:field xpath="@a"/>
  </xs:keyref>

  <xs:key name="b">
   <xs:selector xpath="b"/>
   <xs:field xpath="@b"/>
  </xs:key>
  <xs:keyref name="br" refer="c">
   <xs:selector xpath="b"/>
   <xs:field xpath="@b"/>
  </xs:keyref>

  <xs:key name="c">
   <xs:selector xpath="c"/>
   <xs:field xpath="@c"/>
  </xs:key>
  <xs:keyref name="cr" refer="a">
   <xs:selector xpath="c"/>
   <xs:field xpath="@c"/>
  </xs:keyref>

 </xs:element>

 <xs:element name="a">
  <xs:complexType>
   <xs:attribute name="a" type="xs:integer" use="required"/>
  </xs:complexType>
 </xs:element>

 <xs:element name="b">
  <xs:complexType>
   <xs:attribute name="b" type="xs:integer" use="required"/>
  </xs:complexType>
 </xs:element>
 
 <xs:element name="c">
  <xs:complexType>
   <xs:attribute name="c" type="xs:integer" use="required"/>
  </xs:complexType>
 </xs:element>
</xs:schema>


ht

[1] http://www.w3.org/TR/2001/WD-xmlschema-formal-20010320/
-- 
 Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                     Half-time member of W3C Team
    2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
            Fax: (44) 131 650-4587, e-mail: ht@inf.ed.ac.uk
                   URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]

Received on Tuesday, 10 May 2005 08:56:45 UTC