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

Question

我阅读了http://swtch.com/~rsc/regexp/regexp1.html,其中作者说,为了在正则表达式中进行反向引用,在匹配时需要回溯,这使得最坏情况的复杂度呈指数级增长.但我并不确切地知道为什么反向引用会引入回溯的必要性.有人可以解释为什么,也许提供一个例子(正则表达式和输入)？

Answer 1

要直接回答您的问题,您应该对Chomsky Hierarchy进行简短的研究.这是一种古老而美丽的方式,以越来越复杂的方式组织形式语言.层次结构的最低行是常规语言.你可能会猜测 - 而且你是对的 - RL正是可以用"纯"正则表达式表示的那些:只有字母,空字符串,连接,交替|和Kleene星*的那些(看看Ma,没有后援参考).形式语言理论的经典定理--Kleene定理 - 是DFA,NFA(如您引用的文章中所述)和正则表达式都具有完全相同的能力来表示和识别语言.文章中给出的汤普森结构是定理证明的一部分.

每个RL也是CFL.但是有无数的CFL不常规.CFL中存在的一个特性使得它们太复杂而不规则是平衡的事物对:括号,开始结束块等.几乎所有的编程语言都是CFL.CFL可以通过所谓的下推自动机进行有效识别. 这实际上是一个粘贴有堆栈的NFA .堆栈增长到所需的大小,因此它不再是有限的自动机.真正的编程语言的解析器几乎都是下推自动机的变种.

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

^(b*a)\1$

换言之,这表示某些n的长度为2n的字符串,其中第n个和第2个字符都是,a而所有其他字符都是b.这是一个非常规的CFL的完美例子.你可以用另一个很酷的形式语言工具 - 泵浦引理来严格证明这一点.

这正是后引用导致问题的原因!它们允许表示非常规语言的"正则表达式".因此,没有NFA或DFA可以识别它们.

但是等等,这比我到目前为止做得还要糟糕.考虑

^(b*a)\1\1$

我们现在有一个长度为3n的字符串,其中第n个,第2个和第3个元素是,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的状态数.在那一点上,我会说,"好的Mr. Regular Guy,考虑一下字符串B = a^N b a^N b." 如果L是常规的,B必须使这个DFA(无论它看起来如何)在前N个字符内循环,这些字符必须全部为as!所以循环(上面的字符串S)也包括所有as.有了这个,我可以立即证明你对L是正常的说法是错误的.我只是选择第二次绕圈.这将导致你的这个假想DFA接受一个新的字符串a^M b a^N b,其中M> N,因为我a在上半部分添加了s.哎哟! 这个新字符串不在L中,所以PL毕竟不是真的.因为无论你提供什么N,我每次都可以做这个技巧,PL不能保持L,毕竟L不能是常规的.

由于它不规则,Kleene定理告诉我们没有DFA也没有FA,也没有描述它的"纯"正则表达式.

反向引用的证据允许甚至没有上下文的语言有一个非常相似的环,但需要在下推自动机上有背景,我不打算在这里给出.谷歌将提供.

注意:这两个都不能证明后面的参考使得识别NP完整.他们只是以非常严格的方式说,后面的引用为纯正则表达式增加了真正的复杂性.它们允许任何具有有限内存的机器无法识别的语言,也不允许任何只有无限大LIFO内存的语言.我会把NP完整性证明留给别人.

Answer 2

NFA和DFA是有限自动机,又名有限状态机,它是"抽象机器,可以处于有限数量的状态之一" [1].注意有限数量的状态.

链接文章中讨论的快速NFA/DFA算法,正则表达式匹配可以简单快速,因为它们可以使用有限数量的状态(与输入长度无关),如本文所述.

引入反向引用使状态数(几乎)"无限"(在最坏的情况下约为256 ⁿ,其中n是输入的长度).状态数量增加是因为每个反向引用的每个可能值都成为自动机的状态.

因此,使用有限状态机不再适合/可能,并且必须使用回溯算法.

Answer 3

本教程中有一些出色的示例：
http://www.regular-expressions.info/brackets.html

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