我阅读了http://swtch.com/~rsc/regexp/regexp1.html，作者在其中提到为了在正则表达式中使用反向引用，需要在匹配时进行回溯，这使得最坏情况下的复杂度呈指数级增长。但我不清楚为什么反向引用会导致需要回溯。能否有人解释一下原因，并可能提供一个示例（正则表达式和输入）？
正则表达式中的反向引用如何导致需要回溯？
22
- oskarkv
1
1这篇文章有点回答了那个问题，正则表达式带反向引用并不是根据其正式定义来说的一个普通正则表达式。虽然这并没有回答为什么不能为带有反向引用的正则表达式制作如此快速的算法。 - Qtax
4个回答
24
为了回答你的问题，你应该简要研究一下乔姆斯基层次结构。这是一种古老而美丽的方式，将形式语言组织成逐渐增加复杂性的集合。层次结构的最低层是正则语言。你可能会猜到 - 你会发现 - RL恰好可以用“纯”正则表达式表示：只有字母表、空字符串、连接、交替|和Kleene星号*（看，没有反向引用）。形式语言理论的一个经典定理 - Kleene定理 - 是DFA、NFA（如你所引用的文章中所描述的）和正则表达式都具有完全相同的能力来表示和识别语言。文章中给出的Thompson构造是定理证明的一部分。
每个RL也是CFL。但是有无限多个CFL不是正则的。使它们过于复杂而无法成为正则的CFL的一个特征是平衡的一对东西：括号、开始-结束块等等。几乎所有编程语言都是CFL。CFL可以通过称为下推自动机的东西有效地识别。这本质上是一个带有堆栈的NFA。堆栈会增长到需要的大小，因此它不再是有限自动机。真正的编程语言解析器几乎都是下推自动机的变体。
考虑具有反向引用的正则表达式。
我们现在有一个长度为3n的字符串，其中第n个、第2n个和第3n个元素是
反向引用使得这些超级正则表达式能够表示三级上的Chomsky层次结构：上下文有关语言。粗略地说，识别CSL的唯一方法是检查相等长度的语言中的所有字符串（至少如果P!=NP，但这对于所有实际目的来说都是真实的，是一个完全不同的故事）。这样的字符串数量是指数级的，与您匹配的字符串长度成正比。
这就是为什么需要搜索正则表达式匹配器的原因。你可以设计非常聪明的搜索方式。但总会有一些输入会导致它花费指数时间。
所以我同意您引用的论文的作者。可以编写看起来非常无辜的正则表达式，没有反向引用，几乎可以有效地识别所有输入，但存在某些输入，导致Perl或Java或Python正则表达式匹配器 - 因为它是回溯搜索 - 需要数百万年才能完成匹配。这很疯狂。您可以编写一个脚本，它在多年内都是正确的，并且运行良好，然后有一天会因为偶然遇到了其中一个坏输入而锁定。假设正则表达式嵌入在你所乘坐的飞机的导航系统的消息解析器中...
根据请求，我将概述如何使用泵引理证明语言
PL的证明依赖于一个事实，即每种正则语言都对应着某个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（见上文）：识别 L 的理论 DFA 中状态的数量。此时，我会说，“好吧，普通先生，考虑字符串 B = 'a^N b a^N b'”。如果 L 是正则的，则 B 必须导致该 DFA 在前 N 个字符内循环，这些字符必须全部是 'a'！因此，循环（上面的字符串 S）也包含所有的 'a'。有了这个，我就可以立即证明您关于 L 是正则的说法是错误的。我选择再绕一圈。这将导致您的理论 DFA 接受一个新字符串 'a^M b a^N b'，其中 M > N，因为我在其前半部分添加了 'a'。哎呀！这个新字符串不在 L 中，因此 PL 并不成立。由于我每次都可以使用这个技巧，无论您提供了什么 N，PL 都不能适用于 L，因此 L 最终不能是正则的。
由于它不是正则的，Kleene 定理告诉我们没有 DFA、FA 或“纯”正则表达式可以描述它。
证明反向引用允许甚至不是上下文无关的语言具有非常相似的结构，但需要关于下推自动机的背景知识，我在这里不会给出。Google 可以提供。
注：这两个证明都不足以证明反向引用使识别成为 NP 完全问题。它们只是以非常严谨的方式表明反向引用将实际复杂性添加到纯正则表达式中。它们允许使用任何具有有限内存的机器或仅具有无限大 LIFO 内存的机器无法识别的语言。我将把 NP 完全性证明留给其他人。
每个RL也是CFL。但是有无限多个CFL不是正则的。使它们过于复杂而无法成为正则的CFL的一个特征是平衡的一对东西：括号、开始-结束块等等。几乎所有编程语言都是CFL。CFL可以通过称为下推自动机的东西有效地识别。这本质上是一个带有堆栈的NFA。堆栈会增长到需要的大小，因此它不再是有限自动机。真正的编程语言解析器几乎都是下推自动机的变体。
考虑具有反向引用的正则表达式。
^(b*a)\1$
简而言之，这代表长度为2n的字符串（其中n是任意正整数），第n个和第2n个字符都是a，其余字符都是b。这是一个典型的不规则CFL例子。可以使用另一个称为泵引理的形式语言工具来严格证明这一点。
这也是为什么反向引用会导致问题的原因！它们允许表示不规则语言的“正则表达式”。因此，无论如何都没有NFA或DFA能够识别它们。
但是，请注意，情况比我迄今为止所描述的更糟糕。考虑以下内容：
^(b*a)\1\1$
我们现在有一个长度为3n的字符串，其中第n个、第2n个和第3n个元素是
a，而其他所有元素都是b。还有另一种泵引理的变体，它允许证明这种语言甚至太复杂，无法成为上下文无关语言！没有下推自动机可以识别它。反向引用使得这些超级正则表达式能够表示三级上的Chomsky层次结构：上下文有关语言。粗略地说，识别CSL的唯一方法是检查相等长度的语言中的所有字符串（至少如果P!=NP，但这对于所有实际目的来说都是真实的，是一个完全不同的故事）。这样的字符串数量是指数级的，与您匹配的字符串长度成正比。
这就是为什么需要搜索正则表达式匹配器的原因。你可以设计非常聪明的搜索方式。但总会有一些输入会导致它花费指数时间。
所以我同意您引用的论文的作者。可以编写看起来非常无辜的正则表达式，没有反向引用，几乎可以有效地识别所有输入，但存在某些输入，导致Perl或Java或Python正则表达式匹配器 - 因为它是回溯搜索 - 需要数百万年才能完成匹配。这很疯狂。您可以编写一个脚本，它在多年内都是正确的，并且运行良好，然后有一天会因为偶然遇到了其中一个坏输入而锁定。假设正则表达式嵌入在你所乘坐的飞机的导航系统的消息解析器中...
根据请求，我将概述如何使用泵引理证明语言
a^k b a^k b不是正则的。这里a^k是a重复k次的缩写。PL表示必须存在一个正整数N，使得长度至少为N的正则语言中的每个字符串必须采用R S T的形式，以便R S^k T也适用于所有自然数k。这里R，S，T是字符串，S可能不为空。PL的证明依赖于一个事实，即每种正则语言都对应着某个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（见上文）：识别 L 的理论 DFA 中状态的数量。此时，我会说，“好吧，普通先生，考虑字符串 B = 'a^N b a^N b'”。如果 L 是正则的，则 B 必须导致该 DFA 在前 N 个字符内循环，这些字符必须全部是 'a'！因此，循环（上面的字符串 S）也包含所有的 'a'。有了这个，我就可以立即证明您关于 L 是正则的说法是错误的。我选择再绕一圈。这将导致您的理论 DFA 接受一个新字符串 'a^M b a^N b'，其中 M > N，因为我在其前半部分添加了 'a'。哎呀！这个新字符串不在 L 中，因此 PL 并不成立。由于我每次都可以使用这个技巧，无论您提供了什么 N，PL 都不能适用于 L，因此 L 最终不能是正则的。
由于它不是正则的，Kleene 定理告诉我们没有 DFA、FA 或“纯”正则表达式可以描述它。
证明反向引用允许甚至不是上下文无关的语言具有非常相似的结构，但需要关于下推自动机的背景知识，我在这里不会给出。Google 可以提供。
注：这两个证明都不足以证明反向引用使识别成为 NP 完全问题。它们只是以非常严谨的方式表明反向引用将实际复杂性添加到纯正则表达式中。它们允许使用任何具有有限内存的机器或仅具有无限大 LIFO 内存的机器无法识别的语言。我将把 NP 完全性证明留给其他人。
- Gene
1
因此，对于问题“为什么？”的答案是“因为它不是一个正则表达式”，这本身并没有多大意义。证明为什么这样的表达式不再代表正则语言将具有价值。 - Qtax
10
NFA和DFA是有限自动机，也称为有限状态机，它们是“可以处于有限数量状态之一”的抽象机器[1]。请注意状态数量是有限的。
链接文章中讨论的快速NFA/DFA算法之所以快速，是因为它们可以使用有限数量的状态（与输入长度无关），正如所述的那样正则表达式匹配可以简单而快速。
引入回溯引用使状态数量（在最坏情况下约为256 n，其中n 是输入的长度）变得（几乎）“无限”。状态的数量增加是因为每个回溯引用的每个可能值都成为自动机的状态。
因此，使用有限状态机不再适合/可能，必须改用回溯算法。
链接文章中讨论的快速NFA/DFA算法之所以快速，是因为它们可以使用有限数量的状态（与输入长度无关），正如所述的那样正则表达式匹配可以简单而快速。
引入回溯引用使状态数量（在最坏情况下约为256 n，其中n 是输入的长度）变得（几乎）“无限”。状态的数量增加是因为每个回溯引用的每个可能值都成为自动机的状态。
因此，使用有限状态机不再适合/可能，必须改用回溯算法。
- Qtax
10
我只能补充一点，使用DFA可以构建一个正则表达式引擎，该引擎可能允许反向引用...如果该引擎在面对这样的任务时切换到NFA。)至少Jeffrey Friedl在他的精彩著作中谈到了两个使用这种方法的例子 - POSIX grep和Tcl正则表达式解析器。 - raina77ow
请注意，如果 backref 的值的数量是有限的，您可以构建一个 NFA 并使用非回溯算法。例如，
([ab])[ab]+\1+ 可以与 NFA 匹配。但是，对于 ([ab]+)[ab]+\1+，您无法构建 NFA，因为捕获组存在无限可能的值（因此状态）。 - Qtax好的，我刚刚用JavaScript做到了：我说过
var rex = /([ab]+)[ab]+\1+/，然后rex.test('aabaa')，它很好（实际上是true，但是good更好）。所以在这里确实很重要，我想。 - raina77ow@raina，这与什么相关呢？JS 无论如何都使用回溯算法，因此您可以使用任何类型的后向引用。 - Qtax
@Qtax：你是什么意思？你粘贴的正则表达式永远不会匹配任何内容，这才是实际正确的行为。第一个 [ab] 循环匹配所有的 "ab"，第二个循环因为第一个循环消耗了所有 "ab" 而未能匹配成功，并不奇怪。我们可以通过分析正则表达式来轻松地确定哪些是自动逻辑的，也就是我们已经知道它们永远不会匹配的表达式。"[^a]+[^a]a" 是另一个永远不会匹配的正则表达式。要知道我们应该匹配“除了最后一个应该由其他 'ab' 匹配之外的所有 'ab'”需要一种上下文感知的语言，因为我们说了“最后一个”。 - Hannes Landeholm
显示剩余5条评论
4
在这个教程中有一些很好的例子：
http://www.regular-expressions.info/brackets.html 你可能会感兴趣的特殊情况在“回溯到捕获组”中显示，它解释了在找到与整个正则表达式匹配的最终结果之前，整个匹配可能会多次放弃。此外，值得注意的是，这可能导致意想不到的匹配。
http://www.regular-expressions.info/brackets.html 你可能会感兴趣的特殊情况在“回溯到捕获组”中显示，它解释了在找到与整个正则表达式匹配的最终结果之前，整个匹配可能会多次放弃。此外，值得注意的是，这可能导致意想不到的匹配。
- Joanna Derks
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接