我读http://swtch.com/~rsc/regexp/regexp1.html和它的作者说，为了在regexs反向引用，需要匹配时回溯，这使得最坏情况下的复杂性指数。 但我不明白究竟为什么反向引用引入需要回溯。 有人可以解释为什么，也许提供了一个例子（正则表达式和输入）？
Answer 1:
要直接在你的问题搞定了，你应该做的短期学习乔姆斯基层次 。 这是套日益复杂的组织形式语言的一个古老而又美丽的方式。 层次结构的最底层是正则语言。 您可能已经猜到 - 和你是对的 - 即RL的正是那些可以使用“纯”正则表达式来表示：那些只有拼音，空字符串，并置，交替|和克林星*（看马，没有反向引用）。 克林定理- -形式语言理论的一个经典定理，是的DFA，NFA的（如你所引用的文章中所描述），和正则表达式都具有完全相同的动力表现和识别语言。 在文章中给出汤普森的建设是定理的证明的一部分。
每个RL也是CFL。 但也有无限多的节能灯是不正规。 可在CFL的，这使得它们太复杂，定期存在的特征是平衡对事物：括号，开始 - 结束块等几乎所有的编程语言都是节能灯。 节能灯可以通过什么叫做下推自动机这基本上是一个NFA与粘在堆栈中有效地识别。 堆栈增长是大如需要，所以它不再是一个有限自动机。 真正的编程语言解析器上下推自动机几乎所有的变化。
考虑后向引用正则表达式
^(b*a)\1$
在的话，这表示对于某些n，其中两者的第n个和2n'th字符是长度为2N的字符串a和所有其它字符是b 。 这是AA CFL，这不是普通的一个很好的例子。 你可以用严格的叫抽引理另一个很酷的形式语言工具证明了这一点。
这就是为什么反向引用导致问题！ 他们让“正则表达式”代表不属于正规语言。 因此没有NFA或DFA能够不断识别它们。
别急，它甚至不如我做出来至今如此。 考虑
^(b*a)\1\1$
我们现在有长3N的字符串，其中的第n个，2n'th和3n'th元素是a和所有其他人都b 。 还有就是抽引理的另一种风味，使一个证明，这种语言甚至是太复杂，是一个CFL！ 没有下推自动机可以识别这一个。
返回引用允许这些增压正则表达式来表示三个梯级了乔姆斯基层次的语言：上下文相关的语言。 粗略地说，承认一个CSL的唯一方法是检查所有字符串的长度相等的语言（至少如果P！= NP，但是这对于所有的实际目的和不同的故事完全真实的）。 这样的字符串的数量是在你匹配一个长度指数。
这就是为什么需要搜索正则表达式匹配。 你可以在你设计的搜索方式很聪明。 但是总是会有一些输入驱动其采取指数时间。
所以，我同意你所引用的论文的作者。 这可能与将被有效地识别几乎所有的输入没有回参写完全无辜的看着正则表达式，但其中存在一些输入并导致Perl或Java或Python的正则表达式匹配-因为它是一个回溯搜索-需要数以百万计的年完成了比赛。 这太疯狂了。 你可以有一个脚本这是正确的和多年工作正常，后来有一天，仅仅锁定了，因为它无意中发现的不良输入之一。 假设正则表达式是埋在你骑飞机导航系统的消息解析器...
编辑
按要求，我就勾勒出泵引理如何可以用来证明语言的a^kba^kb是不正规。 这里a^k是一个速记a重复k倍。 的PL说，必须存在一个正整数N，从而在长度的正则语言的每串，对至少N必须形式RST，使得RS-1K-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^kba^kb满足PL。 因为它确实是这样，你必须能够给我N个部分值（见上文）：状态在一个假设的DFA识别L。在这一点上号，我会说：“好吧先生普通的家伙，考虑串b = a^N ba^N b “。 如果L是有规律的，B必须使这个DFA（不管它是什么样子）的前N个字符之内环路，它必须是所有a小号！ 所以循环（串S以上）由所有的a S，也。 有了这个，我可以立刻证明你对L是正规说法是错误的。 我只是选择去各地循环第二次。 这将导致你的这种假设DFA接受一个新的字符串， a^M ba^N b ，其中M> N，因为我加了a s到其上半年。 哎哟! 这个新的字符串不是L，所以PL毕竟是不正确的。 因为我每次都能做到这招不管你提供了什么N，该PL不能保持L，和L不能毕竟正规。
由于它是不是正规，克林定理告诉我们，没有DFA也不FA也不是“纯粹的”正则表达式描述它。
这回裁判证明允许，甚至没有上下文语言具有非常相似的戒指，但需要上我不会给这里下推自动背景。 谷歌将提供。
注：这两个功亏一篑证明，回裁判做出识别NP完全的。 他们只是说，在回裁判增加实际的复杂性纯的正则表达式一个非常严谨的方式。 他们允许不能与具有有限内存的任何机器，也没有任何仅有一个无限大的内存LIFO识别语言。 我将离开NP完全证明给别人。
Answer 2:
NFA和DFA是有限自动机 ，又名有限状态机，其是“抽象机，可以是在有限数目的状态中的一个” [1] 。 注意状态的数量有限 。
链接的文章中讨论的快速NFA / DFA算法， 正则表达式匹配可以是简单和快速 ，速度快，因为他们可以用有限数量的文章中所描述的状态（独立输入的长度）的工作。
引入反向引用使得状态数（几乎）“无限”（在最坏的情况下约为256 n，其中n是输入的长度）。 国家数量的增长，因为每一个反向引用的每一个可能的值成为自动机的状态。
因此，使用一个有限状态机不再装配/可能的，并且回溯算法必须被使用。
Answer 3:
有一个在本教程中一些很好的例子：
http://www.regular-expressions.info/brackets.html
你会有兴趣在“回溯进入捕获组”显示的具体情况-它解释哪有整场比赛可以在最后一节之前给了好几次可以发现，整个正则表达式匹配。 此外，值得注意的是，这可能会导致意想不到的结果。
Answer 4:
非常有趣的文件： 扩展有限自动机，以有效地匹配Perl兼容的正则表达式 ，支持反向引用，并修改NFA高效计算的出现。
文章来源: How do backreferences in regexes make backtracking required?
