如何检测两个正则表达式在它们可以匹配的字符串中是否重叠？

Question

我有一组正则表达式，想要分析它们以确定是否存在一个字符串能匹配超过1个正则表达式。除了为此编写自己的正则表达式引擎之外，是否有一种在C++或Python中解决这个问题的简单方法？

- Joseph Garvin

---

为了解决这个问题，了解你所说的“正则表达式”的确切含义可能很重要。你指的是某种编程语言中使用的regexp语法吗？还是指只使用串联、交替和Kleene星号的“真正”的正则表达式呢？ - PeterAllenWebb

我很想知道哪种最强大的正则表达式类型可以实现这一点。 - Joseph Garvin

嗨，约瑟夫，我正在撰写一篇与这个问题相关的博士论文。我想知道你正在开发哪个应用程序，是否可以详细说明一下。如果需要，我们可以通过电子邮件进一步讨论：mwehar在buffalo点edu。 - Michael Wehar

Answer 1

没有简单的方法。

只要你的正则表达式仅使用标准功能（我想Perl允许您嵌入匹配的任意代码），您就可以从每个正则表达式中产生一个非确定性有限状态自动机(NFA)，它紧密地编码了正则表达式匹配的所有字符串。

对于任何一对NFA，都可以确定它们的交集是否为空。如果交集不为空，则某些字符串同时匹配该对RE中的两个RE（反之亦然）。

标准可判定性证明是将它们确定为DFA，然后构造一个新的DFA，其状态是两个DFA状态的组合，并且其最终状态恰好是原始DFA中两个状态均为最终状态的状态。或者，如果您已经展示了如何计算NFA的补集，则可以通过DeMorgan的定律样式得到交集：complement(union(complement(A),complement(B)))。

不幸的是，NFA->DFA涉及潜在的指数级爆炸（因为DFA中的状态是NFA中状态的子集）。来自Wikipedia：

某些正则语言类只能由大小呈指数级增长的确定性有限自动机描述，这里的标准示例是L_k语言，该语言由符号集{a,b}上所有k次最后一次字母等于a的字符串组成。

顺便提一下，你绝对应该使用OpenFST。你可以创建文本文件作为自动机，并在其中进行操作，如最小化、交集等等，以查看它们对您的问题的效率如何。已经存在开源regexp->nfa->dfa编译器（我记得有一个Perl模块）；修改其中一个以输出OpenFST自动机文件并进行操作。

幸运的是，可以避免状态子集爆炸(SOE)问题，直接使用与DFA相同的构造方法交叉两个NFA：

如果在一个NFA中 A ->a B（您可以从状态A到B输出字母'a'），并且在另一个NFA中 X ->a Y，则在交集中(A,X) ->a (B,Y)。

当且仅当C在一个NFA中是最终状态且Z在另一个NFA中是最终状态时，(C,Z)是最终状态。

要开始这个过程，您需要从两个NFA的起始状态对中开始，例如(A,X) - 这是交集-NFA的起始状态。每次访问一个状态时，根据上述规则为每对离开两个状态的弧生成一个弧，然后访问这些弧到达的所有（新）状态。您将存储您扩展状态的弧（例如在哈希表中），并最终探索从起点可以到达的所有状态。

如果允许epsilon转换（不输出字母），那就没问题：

如果在第一个NFA中，A ->epsilon B，则对于每个您到达的状态(A,Y)，添加弧(A,Y) ->epsilon (B,Y)，类似地，在第二个位置的NFA中也是如此。

在将正则表达式转换为NFA时，使用epsilon转换对于取两个NFAs的并集是有用的（但不是必需的）; 每当您有交替 regexp1|regexp2|regexp3 时，都会进行并集操作：一个起始状态具有到代表交替中的每个正则表达式的NFA的epsilon转换的NFA。

决定NFA是否为空很容易：如果您从起始状态开始进行深度优先搜索并到达终止状态，则它不为空。

该NFA交集类似于有限状态转换器组合（转换器是一种输出符号对的NFA，这些符号成对连接以匹配输入和输出字符串，或将给定输入转换为输出）。

- Jonathan Graehl

---

非常好的答案，尽管这正是我希望避免自己编写代码的内容 ;) 不过OpenFST看起来很不错。 - Joseph Garvin

Answer 2

这个使用pyparsing编写的正则表达式反转器只能处理有限的re语法子集（例如不允许使用*或+）- 你可以将两个re反转成两个集合，然后查找集合交集。

- PaulMcG

---

链接已经断开:/ - Joseph Garvin

谢谢，我已经尝试追踪所有这些参考资料，但似乎错过了一些。答案已被编辑以指向新的存储库。 - PaulMcG

Answer 3

从理论上讲，您所描述的问题是不可能的。

在实践中，如果您有一些可管理的正则表达式数量，这些正则表达式使用有限的子集或regexp语法和/或有限的字符串选择来匹配正则表达式容器，那么您可能能够解决它。

假设您不是试图解决抽象的一般情况，那么可能有一些方法可以解决实际应用。也许，如果您提供正则表达式的代表性样本，并描述要匹配的字符串，就可以创建一个启发式算法来解决问题。

- ironchefpython

---

“识别上下文无关或更差语言的正则表达式”会使得无法证明交集中不存在字符串。显然，这些并不是真正的“正则表达式”，而只是受其启发的某些东西。但完整的正则表达式语言可以通过NFA捕获，并且大多数人实际使用的来自“regexp”。 - Jonathan Graehl

我同意正则表达式可以分解为NFA，但我认为原帖作者可能有更具体的用例，例如像“c [aeiou] t”和“d [aeiou] g”这样的正则表达式，并且允许的字符串是英语词典。 - ironchefpython