但是,在其他情况下,零或多和一个或多个修饰符确实需要回溯.例如,采用以下正则表达式：
(aa|aaa)+
这个表达式应该能够贪婪地匹配七个a的字符串：有几种方法可以将2和3加起来得到7.但要实现这一点,重新考虑早期的迭代是必要的.例如,如果表达式第一次匹配三个a并且第二次匹配三个a,则只剩下一个a,这是无法匹配的.然后回溯最后三个a并匹配两个a,然而,匹配五个a.然后最后两个a也可以匹配(即3 2 2 = 7).
幸运的是,正则表达式在匹配字符串后退出搜索.但是EBNF解析器怎么样？如果语法不明确,解析器将使用回溯来查找所有可能的语法树！如果我们有生产
( "aa" | "aaa" )*
一个七个字母的字符串,一个完全回溯的解析器将返回所有可能的方式来表达7的2和3.这只是七个a：匹配一个稍长的字符串,N-ary树的可能性增长另一个级别.考虑N = 6：
S : ( T )* ; T : A | B | C | D | E | F ;
一个可怕的组合爆炸！
但是真的可以这样吗？ EBNF中的零或多和一个或多个修饰符没有限制吗？如上所述实现它们比PEG解析器的简单while()循环要多得多,所以我不得不怀疑……
解决方法
但并非所有解析算法都会回溯.正则表达式的许多实现都这样做,但并不总是必要的.事实上,对于一个“简单”的正则表达式(一个实际上仅限于常规语法),它可以在没有回溯的情况下进行匹配 – 从某种意义上说,诀窍是并行运行.
有两种(等效的)方法 – 通过“编译”正则表达式(如果并行工作是显式的那样计算表达式),或者通过在运行时处理并行匹配.编译方法将正则表达式转换为DFA(确定性有限自动机).更确切地说,NFA(非确定性的……)模糊地类似于正则表达式的图形版本,并且可能是您想象正则表达式的工作方式;与NFA匹配确实需要回溯,但您可以将NFA转换为DFA而不是.
但是,在运行时执行此操作更容易理解(并且在实践中往往更有用),并在三篇很棒的文章中进行了解释,如果您想要更好地理解这一点,您应该真正阅读这些文章：http://swtch.com/~rsc/regexp/regexp3.html以及开头的链接.
我不能强调这一点 – 你需要阅读这些文章……
ps模糊相关 – 您可以通过缓存稍后可能需要的结果(当您最终通过不同的路径到达相同的文本和表达式时)来使回溯更有效.这被称为“packrat解析”,当应用于递归正常解析时(虽然说实话它不值得一个单独的名称 – 它实际上只是使用缓存).缓存避免了指数运行时 – 诺维格(谷歌的那个人,但这是之前写的方式)某处有一篇论文解释了：http://acl.ldc.upenn.edu/J/J91/J91-1004.pdf
