正则表达式:确定两个正则表达式是否可以匹配相同的输入？

Question

我想查明两个已知正则表达式之间是否存在冲突，以便允许用户构建互斥正则表达式列表。

例如，我们知道下面的正则表达式有很大不同，但它们都匹配 xy50:

'^xy1\d'
'[^\d]\d2$'

是否可以使用计算机算法来确定两个正则表达式是否存在这样的冲突？怎么办？

Answer 1

这里不涉及停止问题。您所需要做的就是计算 ^xy1\d 和 [^\d]\d2$ 的交集是否非空。

我不能在这里给你一个算法，但这里有两个关于无需构建 DFA 即可生成交集的方法的讨论:

• http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

然后是拉格尔

• http://www.complang.org/ragel/

它也可以计算正则表达式的交集。

更新:我刚刚使用 OP 的正则表达式尝试了 Ragel。 Ragel 可以从生成的状态机中为 graphviz 生成一个“点”文件，这非常棒。 OP 正则表达式的交集在 Ragel 语法中看起来像这样:

('xy1' digit any*) & (any* ^digit digit '2') 

并具有以下状态机:

而空交集:

('xy1' digit any*) & ('q' any* ^digit digit '2')

看起来像这样:

因此，如果所有其他方法都失败了，那么您仍然可以让 Ragel 计算交集，并通过比较生成的“点”文件来检查它是否输出空状态机。