28

我有一个正则表达式容器。我想分析它们以确定是否有可能生成一个匹配超过 1 个的字符串。没有考虑到这个用例编写我自己的正则表达式引擎，C++ 或 Python 中有没有简单的方法来解决这个问题？

4

3 回答 3

37

没有简单的方法。

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

给定任意一对 NFA，可以判断它们的交集是否为空。如果交集不为空，则某些字符串与该对中的两个 RE 匹配（反之亦然）。

标准的可判定性证明是首先将它们确定为DFA，然后构造一个新的 DFA，其状态是两个 DFA 的状态的对，其最终状态恰好是对中的两个状态在其原始 DFA 中都是最终的状态. 或者，如果您已经展示了如何计算 NFA 的补码，那么您可以（德摩根定律风格）通过 获得交集complement(union(complement(A),complement(B)))。

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

某些类型的正则语言只能由确定性有限自动机来描述，其大小随着最短等价正则表达式的大小呈指数增长。这里的标准示例是由字母表 {a,b} 上的所有字符串组成的语言 L_k，其中第 k 个最后一个字母等于 a。

顺便说一句，您绝对应该使用OpenFST。您可以将自动机创建为文本文件并尝试最小化、交叉等操作，以了解它们对您的问题的效率。已经存在开源 regexp->nfa->dfa 编译器（我记得一个 Perl 模块）；修改一个以输出 OpenFST 自动机文件并播放。

幸运的是，可以避免状态子集爆炸，并使用与 DFA 相同的结构直接与两个 NFA 相交：

如果A ->a B （在一个 NFA 中，您可以从状态 A 转到 B 输出字母“a”）

和X ->a Y（在另一个 NFA 中）

然后(A,X) ->a (B,Y)在路口

(C,Z)是最终的，当且仅当 C 在一个 NFA 中是最终的并且 Z 在另一个 NFA 中是最终的。

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

如果您允许 epsilon 转换（不输出字母），那很好：

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

在将正则表达式转换为 NFA 时，Epsilon 转换在合并两个 NFA 时很有用（但不是必需的）；每当你有 alternation 时regexp1|regexp2|regexp3，你都会接受 union: 一个 NFA，它的起始状态有一个 epsilon 转换到每个 NFA，代表了交替中的正则表达式。

确定 NFA 的空性很容易：如果您从开始状态进行深度优先搜索时达到了最终状态，那么它就不是空的。

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

于 2009-12-04T20:34:03.910 回答
2

这个正则表达式逆变器（使用 pyparsing 编写）适用于 re 语法的有限子集（例如，不允许 * 或 +） - 您可以将两个 re 反转为两组，然后寻找一个集合交集。

于 2009-12-04T21:38:43.390 回答
-1

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

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

假设您不尝试解决抽象的一般情况，您可能可以采取一些措施来解决实际应用程序。也许如果您提供了一个有代表性的正则表达式样本，并描述了您要匹配的字符串，则可以创建一个启发式来解决问题。

于 2009-12-04T20:58:18.300 回答