如何将这种不确定的XML Schema重写为确定性？

Question

为什么这是非确定性的以及如何解决它？

 <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>

它应该意味着它<activeyears>是空的或包含序列<from><till>开头<from>但可以以任何一个结束.

Answer 1

当有两个以相同元素开头的分支时,模式是非确定性的 - 这样,如果不在该元素之后向前看,就无法分辨哪个分支.一个简单的例子是ab|ac- 当你看到一个时a,你不知道要采取哪个分支.对于循环,"分支"是重复循环,还是继续循环.一个例子是a*a- 一旦你在循环中,并且你读了一个a,你不知道是重复循环,还是继续.

看看你的示例模式,想象它刚刚解析了一个<till>,现在它需要解析一个<from>.您可以使用<from><till>循环或最终解析它<from>.你只能通过查看它来判断使用哪个分支<from>.你只能进一步展望未来.

坏消息:我认为你的示例模式非常罕见,不可能确定性地表达!

以下是您要接受的XML文档(我为每个元素使用单个字母,其中a= <from>...</from>和b= <to>...</to>:

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

......你明白了.问题是任何字母都可以是序列中的最后一个字母,或者它可以是循环的一部分.没有办法告诉它会是什么,除非通过查看以下信件.由于"确定性"意味着您不执行此前瞻(根据定义),因此无法确定性地表达您所需的语言.

简化您的架构,它尝试类似的方法(ab)*a?- 但两个分支开始a.另一种方法是a(ba)*b?- 现在两个分支都以b.我们不能赢!

从技术上讲,架构将接受的所有文档集称为架构的语言.如果不存在可以表达语言的确定性模式,则该语言被称为"一个模糊的".

有关理论讨论,请参阅Bruggemann-Klein的系列论文(例如确定性常规语言和单一明确的常规语言).她包括对一种明确的语言的正式测试.