什么是回溯?

KornLee

<<perl技术内幕>>第6章第177页有段话:

带有量词的正则表达式也可能涉及到所谓的回溯过程.为了匹配正则表达式,必须匹配整个表达式,而不是某个部分.如果包含量词的模式开头部分发挥了作用,但使得模式的以后部分失败,则perl将倒退并从开头处重新开始(这就是称之为回溯的原因)

请问:这个回溯是什么意思? :thank

BBDD

在骆驼书244页上有一个例子很好的说明了什么是回溯：

……
一个更原始的调试解决方法是，使用(?{ CODE })子模打印出在匹配过程中的某时刻已经匹配了什么东西：

1. 
   
2. "abcdef" =~ / .+ (?{print "Matched so far: $&\n"}) bcdef $/x;
   

复制代码

打印出：

1. 
   
2. Matched so far: abcdef
   
3. Matched so far: abcde
   
4. Matched so far: abcd
   
5. Matched so far: abc
   
6. Matched so far: ab
   
7. Matched so far: a
   

复制代码

显示出.+先抢占所有字母，然后在引擎回溯的时候一个一个地放弃。

KornLee

谢谢,:thank,理解起来要比shell的要困难些!我看的是<<perl black book>>
也就是说要用最小匹配模式($&)才能得到正确的结果,对吧?
ps:,这就是传说中的正则表达式(量词)的贪婪性吧~

BBDD

我试了一下，这个例子在perl 5.6.1-2下可以通过，但在5.8下就只会打印“Matched so far: a”。
很明显，在5.8以后perl对回溯进行了优化，这样匹配时就快多了。

BBDD

ps:,这就是传说中的正则表达式(量词)的贪婪性吧~

不错。
但要明白这个例子首先要明白(?{CODE})的作用。
关于这一点，骆驼书是这么说的：

“更灵活的是，你可以用(?{CODE})扩展在模式中的任何位置插入一段代码。而那段代码在引擎回溯时杂乱的快四慢三的舞步中，每次只要碰到它，就会执行。”