正则表达式入门与提高
达式的所有分支,那么它是怎样来实现这一点的呢?即真正的表因是什么?
我们再来分析它的匹配过程: 当引擎处于文本开始这个位置时(其它位置也一样),它面临两种选择:一是用cat去尝试,二是用car去尝试.我们知道多选结构是首先用前面的cat去尝试,.如果用cat尝试成功了,那么引擎宣布匹配结束;这个例子的实际匹配情况怎样的呢?在开始位置0处”c”匹配成功,由于子表达式还没有匹配完,所以引擎移动到下一位置1,也匹配成功,继续移动到位置2,”t”不能匹配”r”,匹配失败.于是第一个分支在文本的位置0处匹配失败.
到这里我们知道引擎将从位置2回退到位置0处尝试下一个分支car.事实上,要做到这一点,引擎必须在尝试第一个分支cat之前,记住还有一个子表达式可以备用. 也就是说:在位置0处引擎遭遇多选结构时,它将在该处存储所有的可能途径,称为”备用状态”,以准备当前一个子表达式匹配失败,而能尝试下一个子表达式, 并能够确定回退的位置;在这同时正则表达式中也保存了一个”备用状态”,即第一个子表达式尝试失败后,该从正则表达式的哪个位置开始进行第二轮尝试.
我们把上面多选结构第一次尝试失败后,回退的过程叫”回溯”.
(2)量词”?”的回溯
例: 用正则表达式 ab?c
分别匹配目标文本 abc 或 ac
首先看匹配ac的情况:在ac位置0处匹配成功,引擎移动到位置1处,在这里,正则子表达式”b?”有两种选择,一是匹配0次b(即不匹配b),二是尝试一次. 所以,引擎将分别在文本和正则的位置1处留下”备用状态”;而”?”是优先匹配的,所以它将首先尝试匹配一次b,结果正则中的b不能匹配文本中的c, 于是引擎回溯尝试第二个选择,即不匹配b;回溯的位置是”备用状态”中存储的位置1. 显然不匹配始终是成功的.于是在位置1处,用正则中的下一个元素”c”来尝试,结果匹配成功.引擎停止,整个匹配报告成功.
再看匹配abc的情况.前面的情况与上面一样的,直到首先尝试匹配一次b时,结果匹配成功;引擎后移,匹配字符”c”,匹配成功.由于正则表达式的所有元素都得到成功匹配,这时将抛弃备用状态,引擎报告整个匹配成功.
在这个例中,只有存储备用状态过程,没有”回溯”过程;所以,“回溯”是当有多个选择,并且前面选择导致整体匹配失败时发生的.
思考:
1.如果改用忽略优先量词,即用正则表达式 ab??c
47
VBA平台的正则学习参考资料
分别匹配abc 或 ac,情况是怎样的?请自己分析. 2.如果目标文本是abx,请分析匹配过程.
(3)量词”*”的回溯
下面图片展示正则表达式 “.*” 匹配目标文本: ”ab””c”
请分析用上面的正则表达式匹配文本: ”a”bcdefghijk
从这个例子中你得到什么启示?你能调较这个正则表达式,提高它的匹配效率吗? 思考:
如果改用忽略优先量词的正则表达式 ”.*?”
匹配文本”ab””cd” ,结果是什么?请自己分析.
五. 回溯的总结
在匹配的过程中NFA引擎会依次处理正则各个子表达式或组成元素.当遇到量词或多选结构时,它将面临两种或多种尝试选择.这时它会存储备用状态.即选择其一,同时记住其它可能的路径.
不论选择那一种途径,如果它能匹配成功,而且正则表达式的余下部分也成功了,整个匹配即告完成.如
48
正则表达式入门与提高
果正则表达式余下的部分匹配失败,引擎就会回溯到备用状态所指示的位置,选择其他的备用分支继续尝试.这样引擎最终可能尝试表达式所有可能的途径,直到余下部分匹配成功,或所有途径尝试完毕都失败,而停下来.
回溯的几个要点:
(1) 如果需要在”进行尝试”和”跳过尝试”之间选择,对于匹配优先量词,引擎会优先选择”进行尝试”,而对于忽略优先量词”,会选择”跳过尝试”.
(2) 对于多选结构,引擎从正则表达式的开始依次尝试各子表达.
(3) 如果正则表达式中有多个量词或多选结构,就意谓着有多个”备用状态”.至于引擎回溯时使用哪个”备用状态”,原则是:距离当前最近存储的选项就是”当本地失败时”强制回溯时返回的.
(4) 使用匹配优先还是忽略优先量词,有时会得到不同的匹配结果.如分别用<.*>或<.*?> 去匹配文本aaa. 但如果只有一条可能的路径,那么无论使用匹配优先还是忽略量词,其最终匹配结果都一样,不一样的只是引擎在达到最终匹配之前需要尝试的次数.如:分别用<.*>或<.*?>去匹配文本
(5) 在环视的内部,其子表达式也有可能包含量词或多选结构,它们的回溯原理与上面所讨论的完全一样.但要提醒一点的是当引擎退出环视时,它将抛弃内部的所有”备用状态”.
六. 回溯与效率
NFA中的回溯是一个好东西，可以为正则表达式带来更多的功能，它也是很多正则引擎选择NFA的原因。但从上面的介绍中，我们也明显感觉到，回溯也可能带来效率的问题。所以，在我们编制正则表达式时，如果涉及量词或多选结构，就必须关注正则表达式的形式，尽可能减少回溯次数。
例：下面三个正则表达式在效果上是等价的 Jeffrey|Jeffery Jeff(rey|ery) Jeff(re|er)y
这三个表达式在某些情况下,效率是不一样的.其中效率最高的是第三个表达式. 为了说明这个问题,我们假设用它们来匹配下列目标文本:
Jeffery and Jeffrey
分析:用第一个表达式匹配,在位置0处留下”备用状态”,它的第一个分支在位置4处”r”不能匹配文本中的”e”,于是回溯选择第二个分支重新从位置0处开始尝试,最后匹配成功.找到文本的成功匹配: Jeffery
如果用第三个表达式匹配,当匹配到位置4时,留下”备用状态”. 用第一分支”er”尝试失败,这时回
49
VBA平台的正则学习参考资料
溯,用第二分支”er”尝试匹配成功.可以看出它的回溯与第一个表达式不同:不需要重新回退到位置0处. 从而减少了找到匹配的尝试次数.
在使用量词时,也要关注回溯导致的效率问题,如果可能尽量用替代方法. 前面多次遇到的一个例子: 提取目标文本中引号的内容:
本帖”正则表达式入门与提高”对你有用吗? 下面三个正则表达式都能实现目标: “”.*”” “”.*?”” “”[^””]+”” 分析:
第一个表达式是通过回溯来实现目标的.即需要回退6步.
第二个表达式在匹配引号内的字符时,每个位置都需要回溯一次,所以,共有10次回溯. 比较第一/二个表达式的效率高低,与具体文本中,引号内字符数与右引号后字符数多少有关. 而第三个表达式,只有一次回溯,它发生在字符匹配右双引号失败时,回退一步.
七.灾难回溯
有时不小心使用量词,则可能带来灾难性的后果. 现在我们用下面正则表达式 \\d+
匹配目标文本 123456X
显然,引擎最后将报告整个匹配失败.那么 正则表达式必须计算多少个路径才能得出此结论呢？ 它会在此字符串开头处开始计算，发现字符 1 是一个有效的数字字符，与此正则表达式匹配。然后它会移动到字符 2，该字符也匹配。因此，在此时，此正则表达式与字符串 12 匹配。接下来，它会尝试 3（匹配123），依次类推，直到到达 X，该字符不匹配。
但是，由于我们的引擎是回溯 NFA 引擎，它不会在此点上停止。而是从其当前的匹配 (123456) 返回到其上一个已知的匹配 (12345)，然后从那里再次尝试匹配。由于 5 后面的下一个字符不是此字符串的结尾，因此，此正则表达式不是匹配项，它会返回到其上一个已知的匹配 (1234)，然后再次尝试匹配。按这种方
50