同样是上面的例子“文本主导”在扫描字符串时,会记录当前有效的所有匹配可。当引擎移动到t时,它会在当前处理的匹配可能中添加一个潜在的可能:
字符串中的位置 | 正则表达中的位置 |
……doing tonight | 可能的匹配位置:/t↑o(nite|knight|nigth)/ |
接下来扫描的每个字符,都会更新当前的可能匹配序列。继续扫描两个字符以后的情况是:
字符串中的位置 | 正则表达中的位置 |
……doing tonight | 可能的匹配位置:/to(ni↑te|knight|ni↑gth)/ |
有效的可能匹配变为两个(knight被淘汰出局)。扫描到g时,就只剩下一个可能匹配了。当h和t匹配完成后,引擎发现匹配已经完成,报告成功。“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制。
如果想要弄明白“表达式主导”是如何工作的,那就要看一下我们今天的主题“回溯(backtracking)”。回溯就像是在走岔路口,当遇到岔路的时候就先在每个路口做一个标记。如果走了死路,就可以照原路返回,直到遇见之前所做过的标记,标记着还未尝试过的道路。如果那条路也走不能,可以继续返回,找到下一个标记,如此重复,直到找到出路,或者直到完成所有没有尝试过的路。
在许多情况下,正则引擎必须在两个(或更多)选项中做出选择。当遇到/……x?……/时,引擎必须是否尝试匹配X。对于/……X+……/的情况,毫无疑问,X至少尝试匹配一次——因为加号要求必须匹配至少一次。第一个X匹配之后,此要求已经满足,需要决定是否尝试下一个X。如果决定进行,还要决定是否匹配第三个X,第四个X,如此继续。每次选择,其实就是做一个标记,用于提示此处还有另一个可能的选择,保留起来以备用。在回溯的过程中要考虑两个要点:哪个分支应当首先选择?回溯的时候使用的是哪个(或者是哪些个)之前保存的分支?
第一个问题是按下面这条重要原则来选择的:
如果需要在“进行尝试”和“路过尝试”之间选择,对于匹配优先量词,引擎会优先选择“进行尝试”,而对于忽略优先量词,会选择“路过尝试”。
第二个问题是按以下这条原则:
距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO(last in first out,后进先出)。
我们先来看几个在道路中做标记的例子:
1、未进行回溯的匹配
用[ab?c]来匹配“abc”。[a]匹配之后,匹配的当前状态如下:
“a↑bc” | a↑b?c |
现在轮到[b?]了,正则引擎需要决定:是需要尝试[b]呢,还是跳过?因为[?]是匹配优先的,它会尝试匹配。但是,为了确保在这个尝试最终失败之后能够恢复,引擎会把:
“a↑bc” | ab?↑c |
“ab↑c” | ab?↑c |
最终的[c]也能成功匹配,所以整个匹配完成。备用状态不再需要了,所以不再保存它们。
2、进行了回溯的匹配
下面要匹配的文本是“ac”,在尝试[b]之前,一切都与之前的过程相同。显然,这次[b]无法匹配。也就是说,对[……?]进行尝试的路走不通了。因为有一个备用状态,这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯,也就是说,把“当前状态”切换为最近保存的状态。
“a↑c” | ab?↑c |
在[b]尝试之前保存的尚未尝试的选项。这时候,[c]可以匹配c,所以整个匹配宣告完成。
3、不成功的匹配
现在要匹配的文本是“abx”。在尝试[b]以前,因为存在问号,保存了这个备用状态:
“a↑bx” | ab?↑c |
[b]能够匹配,但这条路往下却走不通了,因为[c]无法匹配x。于是引擎会回溯到之前的状态,“交还”b给[c]来匹配。显然,这次测试也失败了。如果还有其他保存的状态,回溯会继续进行,但是此时不存在其他状态,在字符串中当前位置开始的整个匹配也就宣告失败。
目前对正则表达式的回溯只能理解这么多,以后我再慢慢补充吧!
php语言是一种脚本语言,它能够做很多事情比如说它可以用来与数据库交互开发web...
准备学习VS2015环境下的数据库编程,在网上找了个实例,链接如下: VS2017调用My...
今天又双叒叕是个心痛的日子。 近日打样一款新产品PCB微控制器选用国产MCUHC32L1...
Mysql基础架构 MySql主要分为 Server层 和 存储引擎层 server层主要包括连接器、...
一、问题描述 ajax 异步请求成功后需要新开窗口打开 url,使用的是 window.open(...
关于数字图像处理中的几种滤波算法 // An highlighted block # - * - coding : u...
从这节开始,将会给大家介绍几个ASP中的三大通用类,它贯穿于我所设计的三层架构中...
【51CTO.com快译】Windows 10是一款出色的操作系统,微软安装累积更新不断改进它...
1月份GitHub上最热门的开源项目排行已经出炉啦,这个月Java相关的开源项目上榜有...
在这之前,民工哥也给大家介绍过一款开源的SQL管理工具:自动补全、回滚!介绍一...