如何将这个非确定性 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>

它应该意味着 为空或包含以 < 开头的 序列/code> 但可以以任一结尾。

Answer 1

当有两个以同一元素开头的分支时，模式是非确定性的 - 因此，如果不向前查看该元素，您就无法判断要采用哪个分支。一个简单的例子是 ab|ac - 当您看到 a 时，您不知道该选择哪个分支。对于循环，“分支”是是否重复循环，或者在循环之后继续。一个例子是a*a - 一旦你进入循环，并且你读取了a，你不知道是否要重复循环，或者继续。

查看您的示例架构，假设它刚刚解析了 ，现在需要解析 。您可以使用 循环或以及最终的来解析它。仅通过查看 无法判断要使用哪个分支。你只能进一步展望未来才能判断。

---

坏消息：我认为您的示例模式非常罕见，它不可能确定性地表达！

以下是您想要接受的 XML 文档（我对每个元素使用一个字母，其中 a = ...和 b = ...:

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

... 你明白了，问题是任何字母都可以是最后一个字母。序列或它可以是循环的一部分，除非提前查看以下字母，否则无法确定它是什么。因为“确定性”意味着您不这样做。这种前瞻（根据定义），您想要的语言无法确定性地表达。

为了简化您的架构，它尝试了类似于 (ab)*a? 的方法 - 但两个分支都以 a 开头。。另一种方法是 a(ba)*b? - 现在两个分支都以 b 开头，从技术上讲，我们无法赢得

所有文档的集合 ！模式将接受的称为该模式的语言。如果不存在可以表达语言的确定性模式，则该语言称为“单歧义”。

有关理论讨论，请参阅 Bruggemann-Klein 的系列论文（例如 确定性正则语言 和单一明确的正则语言）。
她包括对单一明确语言的正式测试。

Answer 2

这是对代码的简单编辑；我还没有尝试过：

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

一些背景：XML 模式是一种非常简单的语法，模式处理器是一个解析器，尝试将此语法的规则应用于输入文件。然而，与传统编译器使用的解析器不同，XML 模式没有前瞻功能。因此，两个规则不能共享相同的初始标记集（元素名称）。

因此，我所做的具体更改是：

• 我保持外部序列不变；它控制“空或有特定内容”的要求。
• 如果有内容，必须以“from”开头；所以我制作了序列中的第一个 element ，并具有显式的出现次数。
• 由于我使用“from”作为显式元素，因此我必须反转子序列的顺序。
• 除非您想指定每个“till”后面必须跟一个“from”，否则您需要放宽子序列中的 minOccurs。
• 子序列还处理单个 from/till 的情况 - 正如评论者指出的那样，我使用 minOccurs='0' 进行的第二次编辑允许使用两个“till”的终止序列。