3

本质上，我想知道是否可以用正则表达式替换特定的 XSD 架构。我知道 XML Schema 语言可以生成 XSD，其有效 XML 实例集可以是任何类型的语言（甚至是上下文相关的）。我想识别那些“正则表达式等效”的模式。在解决了以下问题后，我提出了这个问题：

我需要解析特定的文本格式，我首先尝试了正则表达式，我发现 regexp 足以解析它。然后我想为我收到的这种格式的消息制作一个 XML 表示，所以我用 XML 元素映射了正则表达式组。然后，我根据正则表达式的结构手动创建了一个 XSD 模式。最后，我有一个可以替换我的正则表达式的模式，从某种意义上说，原始的正则表达式可以从模式中构造出来。我还设法做相反的事情：从正则表达式自动创建模式。因此，我可以将消息转换为 XML 并同时对其进行验证。我的问题是：

  1. 每个正则表达式都可以用 XSD 模式表示吗？（我的意思是，给定一个能够生成 XSD 模式的正则表达式）

  2. 给定一个任意 XSD 模式，有没有办法确定是否存在一个表示给定模式的正则表达式？

    编辑：可能第一个问题的答案是肯定的，因为我用我的正则表达式做的，不依赖于特定的正则表达式（这不是每个正则表达式的证明）。

4

1 回答 1

1

XML Schema 语言是常规语言的超集，但显然仅限于 XML 文档领域。

对于#1：加上正则表达式匹配格式良好的 XML 文档的附加条件，没有别的，是的。

对于＃2：是的，这是检查常规语言中允许的 XSD 的任何功能的问题。找到正则表达式将是更多的工作。

常规语言有一个相当简单的定义，非正式地：

  • 空集/字符串
  • 文字（一种“单一语言”），例如“x”
  • 对于正则语言 A，A* 也是正则语言
  • 对于正则语言 A 和 B，A|B（联合）和 AB（连接）是正则的。

基本上，所有连接和交替都很好，但递归是不可能的，并且没有反向引用或“内存”。choice//任何元素类型都不能包含引用自身all或element父类型的元素，并且您不能利用在解析过程中早先找到的任何信息。

递归的限制延伸到any元素，这是被禁止的。根据定义，它接受任何元素，包括带有子元素的元素。由于你不知道这个未知元素的嵌套深度，你需要一个递归模式来匹配它，而你不能在常规语言中做到这一点。

对反向引用的限制意味着您不能执行诸如“一定数量的 'A' 后跟相同数量的 'B'”（A{n}B{n}）之类的事情。我认为这在 XSD 中是不可能的，但是，至少我想不出你会怎么做。

限制数值（例如，minInclusive）在正则表达式中是不可能的。

该all元素将是有问题的，因为它必须接受子元素的所有可能排序，这将使正则表达式呈指数扩展（二项式系数，(n/k)^k <= n!/k!(nk)! < = (ne/k)^k) 与子元素的数量，并且匹配正则表达式在该长度上是超线性的。识别属性会遇到同样的问题，因为元素内属性的排序不受模式的限制。当然，如果你只关心一个正则表达式是否存在而不关心找到它，那也没关系。

于 2011-03-28T23:33:19.510 回答