LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 1916|回复: 4

什么是回溯?

[复制链接]
发表于 2004-5-1 01:37:47 | 显示全部楼层 |阅读模式
<<perl技术内幕>>第6章第177页有段话:
带有量词的正则表达式也可能涉及到所谓的回溯过程.为了匹配正则表达式,必须匹配整个表达式,而不是某个部分.如果包含量词的模式开头部分发挥了作用,但使得模式的以后部分失败,则perl将倒退并从开头处重新开始(这就是称之为回溯的原因)

请问:这个回溯是什么意思? :thank
发表于 2004-5-1 10:43:00 | 显示全部楼层
在骆驼书244页上有一个例子很好的说明了什么是回溯:

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


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


打印出:


  1. Matched so far: abcdef
  2. Matched so far: abcde
  3. Matched so far: abcd
  4. Matched so far: abc
  5. Matched so far: ab
  6. Matched so far: a
复制代码

显示出.+先抢占所有字母,然后在引擎回溯的时候一个一个地放弃。
 楼主| 发表于 2004-5-1 11:32:43 | 显示全部楼层
谢谢,:thank,理解起来要比shell的要困难些!我看的是<<perl black book>>
也就是说要用最小匹配模式($&)才能得到正确的结果,对吧?
ps:,这就是传说中的正则表达式(量词)的贪婪性吧~
发表于 2004-5-1 11:36:23 | 显示全部楼层
我试了一下,这个例子在perl 5.6.1-2下可以通过,但在5.8下就只会打印“Matched so far: a”。
很明显,在5.8以后perl对回溯进行了优化,这样匹配时就快多了。
发表于 2004-5-1 11:45:07 | 显示全部楼层
ps:,这就是传说中的正则表达式(量词)的贪婪性吧~

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

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

本版积分规则

快速回复 返回顶部 返回列表