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

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的regexp试用了Ragel。Ragel可以从生成的状态机为graphviz生成一个“点”文件，这非常棒。OP的regexp的交集在Ragel语法中如下所示：

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

并具有以下状态机：

而空交叉口：

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

看起来像这样：

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

Answer 2

这个问题可以重述为“两种或两种以上规则描述的语言 表达式有一个非空的交集“？

如果你把问题局限于纯正则表达式（没有反向引用，向前看， lookbehind或其他允许识别上下文无关或更复杂的功能 语言），这个问题至少是可以决定的。常规语言在 交集，并且有一个算法接受这两个正则表达式 作为输入，在有限时间内产生一种识别交集的数据流分析。

每个正则表达式都可以转换成一个不确定的有限自动机， 然后是一个确定性的有限自动机。可以转换一对DFA 到识别交叉点的DFA。如果有一条路从 开始状态到该最终DFA的任何接受状态，交叉点为非空 （用你的术语来说是“冲突”）。

不幸的是，在转换初始NFA时可能会出现指数放大 对于DFA，问题很快在实践中变得不可行，因为 输入表达式会增长。

如果允许对纯正则表达式进行扩展，则所有匹配都将关闭-- 这样的语言在交集下不再是封闭的，所以这个构造不会 工作。

Answer 3

是的，我认为这是可以解决的：不要把正则表达式看作匹配字符串，还可以把它们看作生成字符串。也就是说，所有匹配的字符串。

设[R]为正则表达式R生成的字符串集，然后给正则表达式R和T，我们可以尝试将T与[R]匹配。也就是说，如果[R]中有一个字符串与T相匹配

应该可以将其发展为一种算法，在这种算法中，R可以根据需要懒洋洋地构造：在这种情况下，正则表达式匹配将尝试匹配输入字符串中的下一个字符，然后前进到字符串中的下一个字符，修改后的算法将检查与输入正则表达式对应的FSM是否能够在其当前状态下生成匹配字符，然后同时前进到“所有下一个状态”。