regex - 正则表达式中的反向引用如何使回溯成为必需的？

Question

我阅读了http://swtch.com/~rsc/regexp/regexp1.html并且作者在其中说，为了在正则表达式中有反向引用，匹配时需要回溯，这使得最坏情况的复杂性呈指数级增长。但我不明白为什么反向引用引入了回溯的需要。有人可以解释为什么，也许可以提供一个例子（正则表达式和输入）？

Answer 1

要直接解决您的问题，您应该对Chomsky Hierarchy做一个简短的研究。这是一种以越来越复杂的方式组织形式语言的古老而美丽的方式。层次结构的最低级别是常规语言。你可能会猜到——而且你是对的——RL 正是那些可以用“纯”正则表达式表示的：那些只有字母表、空字符串、连接、交替 | 和 Kleene 星 *（看 Ma，没有反向引用）。形式语言理论的一个经典定理 - Kleene 定理 - 是 DFA、NFA（如您引用的文章中所述）和正则表达式都具有表示和识别语言的相同能力。文章中给出的 Thompson 构造是该定理证明的一部分。

每个 RL 也是一个 CFL。但是有无数个不规则的 CFL。CFL 中可能存在的一个使它们过于复杂而无法成为规则的特性是平衡的事物对：括号、开始-结束块等。几乎所有的编程语言都是 CFL。CFL 可以被所谓的下推自动机有效识别，这本质上是一个带有堆栈 的 NFA 。堆栈增长到所需的大小，因此它不再是有限自动机。真实编程语言的解析器几乎都是下推自动机的变体。

考虑带有反向引用的正则表达式

^(b*a)\1$

换句话说，这表示一些 n 的长度为 2n 的字符串，其中第 n 个和第 2n 个字符都是a，所有其他字符都是b。这是一个不规则的 CFL 的完美示例。您可以使用另一种很酷的形式语言工具（称为抽水引理）来严格证明这一点。

这正是反向引用导致问题的原因！它们允许表示非正则语言的“正则表达式”。因此，没有 NFA 或 DFA 可以识别它们。

但是等等，它比我到目前为止所做的还要糟糕。考虑

^(b*a)\1\1$

我们现在有一个长度为 3n 的字符串，其中第 n 个、第 2n 个和第 3n 个元素是a，所有其他元素都是b。抽水引理还有另一种风格，它可以证明这种语言甚至过于复杂而不能成为 CFL！没有下推自动机可以识别这个。

反向引用允许这些增压的正则表达式代表乔姆斯基层次结构中的三个梯级的语言：上下文敏感语言。粗略地说，识别 CSL 的唯一方法是检查长度相等的语言中的所有字符串（至少如果 P!=NP，但对于所有实际目的和完全不同的故事都是如此）。此类字符串的数量与您匹配的字符串的长度呈指数关系。

这就是需要搜索正则表达式匹配器的原因。您可以非常聪明地设计搜索。但是总会有一些输入导致它花费指数级的时间。

所以我同意你引用的论文的作者。可以编写看起来完全无辜的正则表达式，没有反向引用，几乎所有输入都可以有效识别，但是存在一些输入会导致 Perl 或 Java 或 Python 正则表达式匹配器 - 因为它是回溯搜索 - 需要数百万年才能完成比赛。这太疯狂了。您可以拥有一个正确且可以正常运行多年的脚本，然后仅仅因为偶然发现其中一个错误输入而锁定了一天。假设正则表达式隐藏在您乘坐的飞机的导航系统的消息解析器中......

编辑

根据要求，我将概述如何使用 Pumping 引理来证明语言a^k b a^k b不规则。这a^k是a重复k次数的简写。PL 说必须存在一个正整数 N，使得长度至少为 N 的常规语言中的每个字符串必须是 RST 形式，使得 RS^k T 也适用于所有自然 k 的语言。这里R, S,T是字符串，S不能为空。

PL 的证明取决于每个常规语言对应于某个 DFA 的事实。此 DFA 接受的输入长于其状态数（等于引理中的 L）必须使其“循环：”以重复一个状态。将此状态称为 X。机器消耗一些字符串 R 从开始到 X，然后 S 循环回到 X，然后 T 进入接受状态。好吧，在输入中添加额外的 S 副本（或删除 S）仅对应于从 X 回到 X 的不同数量的“循环”。因此，带有额外（或删除）S 副本的新字符串也将被接受.

由于每个RL 都必须满足 PL，因此通过证明它与 PL 相矛盾来证明一种语言不是正则的。对于我们的语言来说，这并不难。假设您试图让我相信语言 L =a^k b a^k b满足 PL。因为它这样做了，所以你必须能够给我一些 N 的值（见上文）：假设 DFA 中识别 L 的状态数。在这一点上，我会说，“好吧，普通人先生，考虑字符串 B= a^N b a^N b。” 如果 L 是正则的，则 B 必须使这个 DFA（不管它看起来像什么）在前 N 个字符内循环，这必须全a是 s！所以循环（上面的字符串 S）由所有as，也。有了这个，我可以立即证明你关于 L 是常规的说法是错误的。我只是选择第二次绕过循环。这将导致您的这个假设的 DFA 接受一个新的 string a^M b a^N b，其中 M>N 因为我将as 添加到它的前半部分。哎哟! 这个新字符串不在 L 中，所以 PL 毕竟不是真的。因为无论你提供什么 N，我每次都可以做这个技巧，所以 PL 不能适用于 L，而且 L 也不能是正则的。

由于它不是正则的，Kleene 定理告诉我们没有 DFA 或 FA 或“纯”正则表达式来描述它。

back refs 允许甚至不是上下文无关的语言的证明有一个非常相似的环，但需要关于下推自动机的背景，我不会在这里给出。谷歌会提供。

注意：这两个都不足以证明后备裁判使识别 NP 完成。他们只是以非常严格的方式说后向引用为纯正则表达式增加了真正的复杂性。它们允许任何具有有限内存的机器都无法识别的语言，或者任何只有无限大的 LIFO 内存的机器都无法识别的语言。我会将NP完整性证明留给其他人。

Answer 2

NFA 和 DFA 是有限自动机，也称为有限状态机，它们是“可以处于有限数量状态之一的抽象机器” [1]。注意有限数量的状态。

链接文章“正则表达式匹配可以简单且快速”中讨论的快速 NFA/DFA 算法速度很快，因为它们可以处理有限数量的状态（与输入长度无关），如文章中所述。

引入反向引用使状态的数量（几乎）“无限”（在最坏的情况下约为 256 ⁿ，其中n是输入的长度）。状态的数量增加了，因为每个反向引用的每个可能值都变成了自动机的状态。

因此，使用有限状态机不再合适/不可能，而必须使用回溯算法。

Answer 3

本教程中有一些很好的例子：
http ://www.regular-expressions.info/brackets.html

您将感兴趣的特定情况显示在“回溯到捕获组”中- 它解释了如何在找到与整个正则表达式匹配的最后一个匹配之前多次放弃整个匹配。此外，值得注意的是，这可能会导致意外匹配。

Answer 4

非常有趣的文档：Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions，支持反向引用并使用修改后的 NFA 有效地计算出现次数。