如何检测两个正则表达式是否在能匹配的字符串上重叠？
我有一组正则表达式，我想分析这些表达式，看看是否可以生成一个字符串，使得这个字符串能同时匹配多个表达式。在不想自己写一个正则表达式引擎的情况下，有没有简单的方法可以用C++或Python来解决这个问题呢？
3 个回答
理论上，你说的问题是无法解决的。
但在实际操作中，如果你有数量适中的正则表达式，并且这些表达式使用的语法比较简单，或者你要匹配的字符串种类不多，那么你可能还是能找到解决办法。
假设你不是在试图解决一个抽象的普遍问题，实际上可能有一些方法可以帮助你解决具体的应用场景。也许如果你提供一些典型的正则表达式，并描述一下你想要匹配的字符串，可能就能找到一个有效的解决方案。
这个正则表达式反转器（用pyparsing写的）只能处理一些简单的正则表达式语法，比如不允许使用*或+这些符号。你可以把两个正则表达式反转成两个集合，然后再找出这两个集合的交集。
这件事没有简单的方法。
只要你的正则表达式使用的都是标准功能（我想Perl允许你在匹配中嵌入任意代码），你就可以从每个正则表达式生成一个叫做非确定性有限自动机（NFA）的东西，它可以紧凑地编码所有与这个正则表达式匹配的字符串。
对于任何一对NFA，我们可以判断它们的交集是否为空。如果交集不为空，那么就说明有某个字符串同时匹配这对正则表达式（反之亦然）。
标准的判断方法是先把它们转化为确定性有限自动机（DFA），然后构造一个新的DFA，它的状态是这两个DFA状态的组合，最终状态正好是这对状态在各自的DFA中都是最终状态的那些状态。或者，如果你已经知道如何计算NFA的补集，那么你可以用complement(union(complement(A),complement(B)))的方式来得到交集。
不幸的是，从NFA转到DFA可能会导致状态数量急剧增加（因为DFA的状态是NFA状态的子集）。根据维基百科：
某些类的正则语言只能用确定性有限自动机来描述，而这些自动机的大小会随着最短等价正则表达式的大小呈指数增长。标准的例子是语言L_k，它由字母表{a,b}中所有字符串组成，这些字符串的倒数第k个字母等于a。
顺便说一下，你一定要使用OpenFST。你可以将自动机创建为文本文件，并尝试进行最小化、交集等操作，以查看它们在你的问题中有多有效。已经存在开源的正则表达式到NFA再到DFA的编译器（我记得有一个Perl模块）；你可以修改一个，使其输出OpenFST的自动机文件，然后进行实验。
幸运的是，可以避免状态子集数量激增，直接使用与DFA相同的构造来交集两个NFA：
如果A ->a B（在一个NFA中，你可以从状态A通过输出字母'a'到达状态B）
并且X ->a Y（在另一个NFA中）
那么在交集中(A,X) ->a (B,Y)
(C,Z)是最终状态，当且仅当C在一个NFA中是最终状态，而Z在另一个NFA中是最终状态。
为了开始这个过程，你从两个NFA的起始状态对开始，例如(A,X)——这是交集NFA的起始状态。每次你第一次访问一个状态时，根据上述规则为离开这两个状态的每对弧生成一个弧，然后访问这些弧所到达的所有（新）状态。你可以存储你扩展了某个状态的弧的信息（例如在哈希表中），最终探索从起始状态可达的所有状态。
如果你允许ε转换（不输出字母的转换），那也没问题：
如果在第一个NFA中A ->epsilon B，那么对于你到达的每个状态(A,Y)，添加弧(A,Y) ->epsilon (B,Y)，同样适用于第二个NFA中的ε。
ε转换在将正则表达式转换为NFA时是有用的（但不是必要的），当你有选择结构regexp1|regexp2|regexp3时，你可以取并集：一个NFA的起始状态有一个ε转换到每个表示选择中正则表达式的NFA。
判断一个NFA是否为空很简单：如果你在从起始状态进行深度优先搜索时，能到达一个最终状态，那么它就不是空的。
这个NFA交集的过程类似于有限状态转换器的组合（转换器是一种输出符号对的NFA，这些符号对被成对连接以匹配输入和输出字符串，或者将给定的输入转换为输出）。