regex - 正则表达式中的反向引用如何要求回溯？

Question

我读了http://swtch.com/~rsc/regexp/regexp1.html，作者在其中表示，为了在正则表达式中具有反向引用，匹配时需要反向跟踪，这使得最坏情况下的复杂度呈指数级增长。但是我不明白为什么反向引用会引入回溯的必要性。有人可以解释原因，并提供示例(正则表达式和输入)吗？

Answer 1

为了直接回答您的问题，您应该对Chomsky Hierarchy进行简短的研究。这是一种以越来越复杂的形式组织形式语言的古老而优美的方法。层次结构中最低的梯级是常规语言。您可能会猜到-而且您是对的-RL正是可以用“纯”正则表达式表示的RL:只有字母，空字符串，串联，交替|和Kleene星号*(看起来像Ma，无回溯引用)。形式语言理论的一个经典定理-Kleene定理-DFA，NFA(如您所引用的文章中所述)和正则表达式都具有完全相同的表示和识别语言的能力。文章中给出的汤普森构造是该定理证明的一部分。

每个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!下推式自动机无法识别这一点。

反向引用允许这些增压的正则表达式表示在Chomsky层次结构中是三个梯级的语言:上下文相关语言。粗略地说，识别CSL的唯一方法是以相同长度的语言检查所有字符串(至少如果P!= NP，但这对于所有实际目的和完全不同的情况都是正确的)。此类字符串的数量在您要匹配的字符串的长度上是指数的。

这就是为什么需要搜索正则表达式匹配器的原因。您在设计搜索时可能会非常聪明。但是总会有一些输入驱动它花费指数时间。

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

编辑

根据要求，我将概述如何使用Pumping引理证明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的事实。对该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的状态数。到那时，我会说:“好的，Regular Guy先生，考虑一下字符串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毕竟不是true。由于无论您提供什么N，我都可以每次都执行此操作，因此PL无法容纳L，并且L毕竟不能是正则。

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

反向引用允许甚至不是上下文无关的语言的证明也非常相似，但是需要下推自动机的背景知识，我在这里不做介绍。 Google将提供。

注意:这两个都缺乏证明反向引用使识别NP完整的证据。他们只是以非常严格的方式说回引用为纯正则表达式增加了真正的复杂性。它们允许的语言不能被任何具有有限内存的机器识别，也不能被只有无限大的LIFO存储器识别的语言。我会将NP完整性证明留给他人。