基于 DFA 的正则表达式匹配 - 如何获取所有匹配项？

Question

我有一个代表正则表达式的给定 DFA。
我想要将 DFA 与输入流进行匹配，并获取所有可能的匹配项，而不仅仅是最左边的最长匹配项。

例如：

正则表达式：a*ba|baa

输入：aaaaabaaababbabbbaa

结果：

1. aaaaaba
2. aaba
3. ba
4. baa

Answer 1

假设

根据您的问题和后来的评论，您需要一种通用方法将句子拆分为不重叠的匹配子字符串，并丢弃句子中不匹配的部分。 您似乎还想要最佳的运行时性能。 另外，我假设您已经有一个现有的算法可以将正则表达式转换为 DFA 形式。 我进一步假设您正在通过首先构建 NFA 并通过子集构建将其转换为 DFA 的常用方法来执行此操作，因为我不知道完成此操作的任何其他方法。

在你去追逐阴影之前，请确保你尝试使用正确的工具来完成这项工作。 任何关于正则表达式的讨论几乎总是令人困惑，因为人们使用正则表达式做的事情比他们真正最适合做的事情要多得多。 如果您想获得正则表达式的好处，请确保您使用的是正则表达式，而不是更广泛的表达式。 如果您想要做的事情不能在某种程度上编码到正则表达式本身中，那么您就无法（完全）受益于正则表达式算法的优势。

一个明显的例子是，再多的聪明也不允许使用 FSM 或任何其他 算法。算法，预测未来。 例如，像 (a*b)|(a) 这样的表达式，当与字符串 aaa 匹配时...，其中省略号是表达式中尚未出现的部分已扫描因为用户尚未键入它们，无法为您提供所有可能的正确子组。

有关正则表达式实现的更详细讨论，特别是 Thompson NFA，请查看此链接 ，它描述了一个带有一些巧妙优化的简单 C 实现。

正则语言的局限性

正则表达式算法的 O(n) 和 Space(O(1)) 保证是一个相当狭窄的主张。 具体来说，常规语言是可以在恒定空间中识别的所有语言的集合。 这个区别很重要。 任何比接受或拒绝句子更复杂的算法增强功能都可能适用于比常规语言更大的语言集。 最重要的是，如果您可以证明某些增强功能需要大于恒定空间来实现，那么您也不在性能保证范围内。 话虽这么说，如果我们非常小心地将我们的算法保持在这些狭窄的限制内，我们仍然可以做很多事情。

显然，这消除了我们可能想要用递归回溯做的任何事情。 堆栈没有恒定的空间。 即使维护句子的指针也是被禁止的，因为我们不知道句子可能有多长。 足够长的句子会溢出任何整数指针。 当我们要解决这个问题时，我们无法为自动机创建新的状态。 在将识别器暴露给任何输入之前，所有可能的状态（以及一些不可能的状态）都必须是可预测的，并且该数量必须受某个常数的限制，该常数可能因我们想要匹配的特定语言而异，但不受其他变量的限制。

这仍然为添加额外的行为留出了一些空间。 获得更多里程的常用方法是为处理中发生的某些事件添加一些额外的注释，例如子表达式开始或停止匹配的时间。 由于我们只允许进行恒定空间处理，这限制了我们可以处理的子表达式匹配的数量。 这通常意味着该子表达式的最新实例。 这就是为什么当您请求 (a|)* 匹配的子组时，您总是得到一个空字符串，因为 a 的任何序列都隐含地跟随无限多个空字符串。

另一个常见的增强功能是在状态之间做一些聪明的事情。 例如，在 perl 正则表达式中， \b 匹配空字符串，但前提是前一个字符是单词字符而下一个字符不是，反之亦然。 许多简单的断言都适合这种情况，包括公共行锚运算符 ^ 和 $。 前向断言和后向断言也是可能的，但要困难得多。

在讨论各种常规语言识别器之间的差异时，值得澄清的是我们谈论的是匹配识别还是搜索识别，前者仅当整个句子都在该语言中时才接受，而后者如果句子中存在任何子字符串则接受是在语言中。 它们在某种意义上是等效的，如果搜索方法接受某个表达式 E，则 .*<匹配方法接受strong>(E).*。

这很重要，因为我们可能想弄清楚像 a*b|a 这样的表达式是否接受 aa 。 在搜索方法中，确实如此。 任一标记都将匹配析取的右侧。 但它不匹配，因为您永远无法通过单步执行表达式并从转换生成标记来获得该句子，至少在一次传递中是这样。 因此，我只讨论匹配语义。 显然如果你想要搜索语义，你可以用.*修改表达式。 注意

：由表达式E<定义的语言/strong>|.* 实际上并不是一种非常易于管理的语言，无论 E 的子语言如何，因为它匹配所有可能的句子。 这对正则表达式识别器来说是一个真正的挑战，因为它们实际上只适合识别一种语言或确认一个句子不是使用同一种语言，而不是做任何更具体的工作。

正则语言识别器的实现

通常有三种方法来处理正则表达式。 这三者的起点相同，都是将表达式转换为 NFA。 此过程为原始表达式中的每个产生规则生成一个或两个状态。 规则极其简单。 这是一些粗略的 ascii 艺术：请注意，a 是语言字母表中的任何单个文字字符，E1 和 E2 是任何正则表达式。 Epsilon(ε) 是一种具有输入和输出的状态，但忽略字符流，也不消耗任何输入。

a     ::=  > a ->

E1 E2 ::=   >- E1 ->- E2 ->

               /---->
E1*   ::= > --ε <-\
               \  /
                E1

             /-E1 ->
E1|E2 ::= > ε
             \-E2 ->

就是这样！ E+、E?、[abc] 等常见用法分别相当于 EE*、(E|)、(a|b|c)。 另请注意，我们为每个产生式规则添加了极少量的新状态。 事实上，每个规则添加零个或一个状态（在本演示中）。 字符、量词和脱节都只添加一种状态，而串联不会添加任何状态。 其他一切都是通过将片段的结束指针更新为其他状态或片段的开始指针来完成的。

epsilon 过渡态很重要，因为它们是不明确的。 当遇到这种情况时，机器是否应该将状态更改为以下状态或其他状态？ 它应该改变状态还是保持不变？ 这就是为什么这些自动机被称为不确定性的原因。 解决方案是让自动机转换到正确状态，以能够匹配最佳状态为准。 因此，棘手的部分是弄清楚如何做到这一点。

基本上有两种方法可以做到这一点。 第一种方法是尝试每一种方法。 遵循第一个选择，如果不起作用，请尝试下一个。 这是递归回溯，出现在一些（并且值得注意的）实现中。 对于精心设计的正则表达式，此实现几乎不需要做任何额外工作。 如果表达式有点复杂，递归回溯就非常非常糟糕，O(2^n)。

另一种方法是并行尝试这两个选项。 在每次 epsilon 转换时，将 epsilon 转换建议的两个状态添加到当前状态集合中。 由于您使用的是集合，因此您可以多次出现相同的状态，但您只需要跟踪它一次，无论您是否处于该状态。 如果您发现某个特定状态无法遵循，请忽略它，因为该路径不匹配。 如果没有更多状态，则整个表达式不匹配。 一旦任何状态达到最终状态，您就完成了。

仅从这个解释来看，我们要做的工作量就增加了一些。 我们已经从必须跟踪单个状态变为必须跟踪多个状态。 在每次迭代中，我们可能必须更新 m 个状态指针的顺序，包括检查重复项之类的事情。 此外，我们所需的存储量也增加了，因为现在它不再是指向 NFA 中一种可能状态的单个指针，而是一整套状态。

然而，这并不像听起来那么糟糕。 首先，状态的数量受到原始正则表达式中产生式数量的限制。 从现在开始，我们将调用该值 m，以区别于输入中的符号数量，即 n 。 如果两个状态指针最终转换到相同的新状态，您可以丢弃其中一个，因为无论发生什么情况，它们都将遵循相同的路径。 这意味着您需要的状态指针的数量受状态数量的限制，因此 to 为 m。

与回溯相比，在最坏的情况下，这是一个更大的胜利。 从输入中消耗每个字符后，您将创建、重命名或销毁最多 m 个状态指针。 没有办法制作一个正则表达式，它会导致您执行更多的指令（​​乘以一些常数因子，具体取决于您的具体实现），或者会导致您在堆栈或堆上分配更多空间。

该 NFA 同时处于其 m 状态的某个子集中，可以被视为某种其他状态机，其状态代表其建模的 NFA 可能处于的一组状态。该 FSM 的每个状态代表来自NFA 各州的幂集。 这正是用于匹配正则表达式的 DFA 实现。

使用这种替代表示的一个优点是，您不必更新 m 个状态指针，而只需更新一个。 它也有一个缺点，因为它对 m 状态的幂集进行建模，所以实际上最多有 2^m 状态。 这是一个上限，因为您不会对不可能发生的状态进行建模，例如表达式 a|b 在读取第一个字符后有两种可能的状态，要么是看到 >a，或者看到b。 无论您给它什么输入，它都不能同时处于这两种状态，因此状态集不会出现在 DFA 中。 事实上，因为您正在消除 epsilon 转换的冗余，所以许多简单的 DFA 实际上比它们所代表的 NFA 更小，但根本没有办法保证这一点。

为了防止状态爆炸变得太大，该算法的几个版本中使用的解决方案是仅生成您实际需要的 DFA 状态，如果生成太多，则丢弃最近未使用的状态。 您始终可以再次生成它们。

从理论到实践

正则表达式的许多实际用途都涉及跟踪输入的位置。 这在技术上是作弊，因为输入可以是任意长的。 即使您使用 64 位指针，输入也可能是 2⁶⁴+1 个符号长，并且您会失败。 您的位置指针必须随着输入的长度而增长，现在您的算法现在需要的不仅仅是恒定的空间来执行。 实际上，这并不相关，因为如果您的正则表达式最终确实通过了这么多输入，您可能不会注意到它会失败，因为您会在那之前很久就终止它。

当然，我们想要做的不仅仅是接受或拒绝整个输入。 最有用的变体是提取子匹配，以发现输入的哪一部分与原始表达式的特定部分匹配。 实现此目的的简单方法是为表达式中的每个左大括号和右大括号添加 epsilon 转换。 当 FSM 模拟器遇到这些状态之一时，它会用有关遇到特定转换时输入中的位置的信息来注释状态指针。 如果同一指针第二次返回到该转换，则旧注释将被丢弃并替换为新输入位置的新注释。 如果两个具有不同注释的状态指针折叠到相同状态，则稍后输入位置的注释将再次获胜。

如果您坚持使用 Thompson NFA 或 DFA 实现，那么实际上并没有任何贪婪或非贪婪匹配的概念。 回溯算法需要得到提示，表明它是否应该从尝试尽可能多的匹配并递归地尝试更少的内容开始，或者在第一次尝试失败时尝试尽可能少的匹配并递归地尝试更多的内容。 Thompson NFA 方法同时尝试所有可能的数量。 另一方面，您可能仍然希望使用一些贪婪/非贪婪暗示。 该信息将用于确定是否应首选较新或较旧的子匹配注释，以便捕获输入的正确部分。

另一种实用的增强是断言，产生式不消耗输入，而是根据输入位置的某些方面进行匹配或拒绝。 例如，在 perl 正则表达式中， \b 表示输入必须在该位置包含单词边界，这样刚刚匹配的符号必须是单词字符，但下一个字符不能是，或者反之亦然。 同样，我们通过向模拟器添加带有特殊指令的 epsilon 转换来管理此问题。 如果断言通过，则状态指针继续，否则被丢弃。

前瞻和后瞻断言可以通过更多的工作来实现。 典型的后向断言 r0(?<=r1)r2 转换为两个单独的表达式，.*r1 和 r0 >εr2。 两个表达式都应用于输入。 请注意，我们在断言表达式中添加了 .*，因为我们实际上并不关心它从哪里开始。 当模拟器在第二个生成的片段中遇到 epsilon 时，它会检查第一个片段的状态。 如果该片段处于可以接受的状态，则断言通过，状态指针流入 r2，但否则，它失败，两个片段都继续，第二个片段在 epsilon 转换时丢弃状态指针。

Lookahead 还可以通过为断言使用额外的正则表达式片段来工作，但稍微复杂一些，因为当我们到达输入中断言必须成功的点时，没有遇到任何相应的字符（在lookbehind 情况下，它们都遇到过）。 相反，当模拟器到达断言时，它会在断言子表达式的开始状态中启动一个指针，并在模拟的主要部分中注释状态指针，以便它知道它依赖于子表达式指针。 在每个步骤中，模拟必须检查它所依赖的状态指针是否仍然匹配。 如果找不到，那么无论它在哪里都会失败。 与主要部分相比，您不必保留更多的断言子表达式状态指针副本，如果断言中的两个状态指针位于同一状态，则它们每个所依赖的状态指针将共享相同的状态指针命运，并且可以重新注释以指向您保留的单个指针。

当我们向 epsilon 转换添加特殊指令时，建议一条指令让模拟器偶尔暂停以让用户看到发生了什么，这并不是一个糟糕的主意。 每当模拟器遇到这样的转换时，它都会将其当前状态包装在某种包中，该包可以返回给调用者、检查或更改，然后从中断处恢复。 这可以用于交互式地匹配输入，因此如果用户仅键入部分匹配，则模拟器可以要求更多输入，但如果用户键入无效的内容，则模拟器为空，并且可以向用户抱怨。 另一种可能性是每次匹配子表达式时都会产生，从而允许您查看输入中的每个子匹配。 但这不能用于排除某些子匹配。 例如，如果您尝试将 ((a)*b) 与 aaa 进行匹配，您可能会看到 a 的三个子匹配，即使整个表达式最终失败，因为不存在 b，并且没有对应 b 的子匹配

最后，可能有一种方法可以修改它以使用反向引用。 即使它很优雅，它也肯定是低效的，具体来说，正则表达式加上反向引用是 NP-Complete 的，所以我什至不会尝试想办法做到这一点，因为我们只对（渐近地）感兴趣）有效的可能性。