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

Question

我想知道两个已知的正则表达式之间是否会发生冲突，以允许用户构建一个互斥正则表达式的列表。

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

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

是否可以使用计算机算法确定两个正则表达式是否会发生这种冲突？如何？

Answer 1

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

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

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

然后是RAGEL

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 计算交集并通过比较生成的“点”文件来检查它是否输出空状态机。