正则表达式入门与提高

正则表达式入门与提高

达式的所有分支,那么它是怎样来实现这一点的呢?即真正的表因是什么?

我们再来分析它的匹配过程: 当引擎处于文本开始这个位置时(其它位置也一样),它面临两种选择:一是用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