4

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

例如：

正则表达式：a*ba|baa

输入：aaaaabaaababbabbbaa

结果：

  1. 啊啊啊啊
  2. 阿巴
  3. 巴
  4. 咩
4

1 回答 1

16

假设

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

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

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

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

常规语言的限制

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

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

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

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

在讨论各种常规语言识别器之间的差异时，有必要澄清一下我们是在讨论匹配识别还是搜索识别，前者仅在整个句子都在该语言中时才接受，而后者仅在句子中有子字符串时才接受是在语言中。这些在某种意义上是等价的，如果某个表达式E被搜索方法接受，那么在匹配方法中被接受。 .*(E).*

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

注意：由表达式定义的语言实际上并不是一种非常易于管理的语言，不管它的子语言是什么，因为它匹配所有可能的句子。这对正则表达式识别器来说是一个真正的挑战，因为它们实际上只适合识别一种语言或确认一个句子不是同一种语言，而不是做任何更具体的工作。 E|.*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个状态的 powerset ，它实际上有多达 2 m个状态。这是一个上限，因为您不会对不可能发生的状态进行建模，例如，表达式a|b在读取第一个字符后有两种可能的状态，一种是a看到 a ，一种是看到 ab. 无论您给它什么输入，它都不能同时处于这两种状态，因此状态集不会出现在 DFA 中。事实上，因为您正在消除 epsilon 转换的冗余，许多简单的 DFA 实际上比它们所代表的 NFA 更小，但根本无法保证这一点。

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

从理论到实践

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

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

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

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

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

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

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

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

于 2009-08-01T19:13:45.320 回答