Comment réécrire ce schéma XML non déterministe en déterministe?

Question

Pourquoi cela n'est pas déterministe et comment y remédier?

<xs:element name="activeyears"> 
     <xs:complexType> 
      <xs:sequence minOccurs="0" maxOccurs="1"> 
       <xs:sequence minOccurs="0" maxOccurs="unbounded"> 
        <xs:element ref="from" minOccurs="1" maxOccurs="1"/> 
        <xs:element ref="till" minOccurs="1" maxOccurs="1"/> 
       </xs:sequence> 
       <xs:element ref="from" minOccurs="0" maxOccurs="1"/> 
      </xs:sequence> 
     </xs:complexType> 
    </xs:element> 

Il est censé signifier que <activeyears> est vide ou contient une séquence de <from><till> qui commence par <from> mais peut se terminer par.

Answer 1

Un schéma est non déterministe quand il y a deux branches qui commencent par le même élément - de sorte que vous ne pouvez pas dire quelle branche à prendre sans regarder en avant après cet élément. Un exemple simple est ab|ac - lorsque vous voyez un a, vous ne savez pas quelle branche prendre. Pour les boucles, la "branche" consiste à répéter la boucle ou à continuer après. Un exemple de ceci est a*a - une fois que vous êtes dans la boucle, et vous lisez un a, vous ne savez pas s'il faut répéter la boucle, ou continuer.

En regardant votre exemple de schéma, imaginez qu'il vient d'analyser un <till>, et qu'il doit maintenant analyser un <from>. Vous pouvez l'analyser avec la boucle <from><till>ou avec la version finale <from>. Vous ne pouvez pas dire quelle branche utiliser, juste en regardant cela <from>. Vous pouvez seulement dire avec plus de perspicacité.

---

Mauvaises nouvelles: Je pense que votre exemple de schéma est très rare, qu'il est impossible d'exprimer de manière déterministe!

Voici les documents XML que vous voulez accepter (j'utilise une seule lettre pour chaque élément, où a = <from>...</from> et b = <to>...</to>.

*empty* 
a 
ab 
aba 
abab 
ababa 
ababab 
... 

... vous avez l'idée Le problème est que toute lettre peut être la lettre finale dans la séquence ou il peut faire partie de la boucle.Il est impossible de dire ce qu'il sera, sauf en regardant en avant à la lettre suivante. que vous ne faites pas ce lookahead (par définition), la langue que vous voulez ne peut pas être exprimée de façon déterministeSimplifiant votre schéma, il tente une approche similaire à (ab)*a? - mais les deux branches commencent par a. Une autre approche est a(ba)*b? - maintenant les deux branches commencent par b. Nous ne pouvons pas gagner!

Techniquement, l'ensemble de tous les documents acceptés par un schéma est appelé . S'il n'existe pas de schéma déterministe pouvant exprimer un langage, le langage est appelé "un ambigu".

Pour une discussion théorique, voir la série de documents par Brüggemann-Klein (par exemple Deterministic Regular Languages et One-Unambiguous Regular Languages). Elle inclut un test formel pour les langues non ambiguës.

Answer 2

Ceci est une simple modification de votre code; Je ne l'ai pas essayé:

<xs:element name="activeyears"> 
     <xs:complexType> 
      <xs:sequence minOccurs="0" maxOccurs="1"> 
       <xs:element ref="from" minOccurs="1" maxOccurs="1"/> 
       <xs:sequence minOccurs="0" maxOccurs="unbounded"> 
        <xs:element ref="till" minOccurs="1" maxOccurs="1"/> 
        <xs:element ref="from" minOccurs="0" maxOccurs="1"/> 
       </xs:sequence> 
      </xs:sequence> 
     </xs:complexType> 
    </xs:element> 

Certains arrière-plan: schéma XML est une grammaire très simple, et le processeur de schéma est un analyseur qui tente d'appliquer les règles de cette grammaire dans le fichier d'entrée. Contrairement aux analyseurs syntaxiques utilisés par les compilateurs traditionnels, cependant, le schéma XML n'a pas de lookahead. Vous ne pouvez donc pas avoir deux règles partageant le même ensemble initial de jetons (noms d'éléments).

Ainsi, les changements spécifiques que j'ai fait:

• Je reste inchangé votre sequence extérieur; il contrôle l'exigence "vide ou a un contenu spécifique".
• S'il y a du contenu, il doit commencer par "from"; donc j'ai fait que le premier element dans la séquence, avec le compte d'occurrence explicite
• Puisque j'ai utilisé "de" comme un élément explicite, j'ai dû inverser l'ordre de la sous-séquence.
• Et à moins que vous ne vouliez spécifier que chaque "till" doit être suivi d'un "from", vous devez assouplir minOccurs dans la sous-séquence. La sous-séquence traite également le cas d'un seul de/till - comme un commentateur l'a noté, ma seconde édition avec le minOccurs='0' a permis une séquence de terminaison de deux «till».