regex - 是否存在一种算法来确定关于特定XSD架构的所有有效XML实例的集合是否为常规语言？

Question

本质上，我想知道是否可以用正则表达式替换特定的XSD架构。我知道XML Schema语言可以生成XSD，其有效XML实例集可以是任何类型的语言(甚至是上下文相关的)。我想确定那些“正则表达式等效”的模式。解决以下问题后，我想到了这个问题:
我需要解析一种特定的文本格式，并且首先尝试使用正则表达式，然后看到regexp足以解析它。然后，我想对以这种格式接收的消息进行XML表示，因此我将正则表达式组映射为XML元素。然后，我根据正则表达式的结构手动创建了XSD架构。最后，在某种意义上说，我可以替换我的正则表达式，因为可以从该模式构造原始正则表达式。我还设法做相反的事情:从正则表达式自动创建模式。因此，我可以将消息转换为XML并同时进行验证。我的问题是:

每个正则表达式都可以由XSD模式表示吗？ (我的意思是，给定正则表达式以能够产生XSD模式)

给定一个任意的XSD模式，是否有办法确定是否存在以给定模式表示的正则表达式？
编辑:可能第一个问题的答案是肯定的，因为我以不依赖于特定正则表达式的方式对它进行了正则表达式处理(这并不是每个正则表达式的证明)。

Answer 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)和子元素的数量，并且匹配正则表达式在该长度上是超线性的。识别属性会遇到相同的问题，因为元素在属性内的顺序不受架构的约束。当然，如果您只在乎正则表达式是否存在，而不在乎是否找到它，那么这无关紧要。