深入入门正则表达式（java） - 匹配原理 - 2 - 回溯

内容可能有些不严谨的地方，希望大家落脚前先拍砖，多谢

 

深入入门正则表达式（java） - 引言

深入入门正则表达式（java） - 1 - 入门基础 
深入入门正则表达式（java） - 2 - 基本实例

深入入门正则表达式（java） - 3 - 正则在java中的使用

深入入门正则表达式（java） - 匹配原理 - 1 - 引擎分类与普适原则

深入入门正则表达式（java） - 匹配原理 - 2 - 回溯

 

回溯（backtracking）

NFA引擎最重要的性质是：它会一次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，它会选择其一，同时记住其他结果，以备后续需要

需要做出选择的情形包括 量词（决定是否尝试另一次匹配）和多选结构（决定选择哪个多选分支）

两个要点：

1.如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词来说，引擎会优先选择“进行尝试”，对于忽略优先量词来说，会选择“跳过尝试”

2.距离当前最近存储的选项就是当本地失败强制回溯返回的。使用的原则是LIFO（last in first out，后进先出）。

 

实际上，NFA搜索的过程算法就是深度优先（关于深度优先介绍见文章末尾，内容来自中文维机百科），只不过并不一定完全遍历，完成匹配之后就停止搜索了。下面我举几个简单的例子，画图来描述一下。

例，假如我们要匹配一串数字中的最后两位，目标字符串“3456”，正则“\d+(\d\d)”，下面是一个流程示意图：

匹配过程比较简单，首先\d+匹配3、4、5、6，其中绿色的圆圈是\d+的备用位置。

\d+继续尝试匹配，发现没有字符了，所以它的匹配结束，把控制权交给了\d，然而\d也无法匹配，所以需要进行回溯。

 

正则回到第二个绿色圆圈那里，然后控制权交给\d。现在\d可以匹配到数字6了，匹配结束，控制权交给\d，发现没有字符留给它，所以还需要回溯。

正则回到第一个绿色圆圈那里，然后控制权交给\d。现在\d可以匹配到数字5了，匹配结束，控制权交给\d，匹配到了数字6，匹配结束，至此整个表达式完成了匹配。

（这里红色的圆圈表示交换控制权，这样方便理解。只有在绿色圆圈处才可能产生新的分支，其余地方，如果匹配失败，只需要原路返回到绿色圆圈处即可，然后尝试量词和多选结构的备用状态）

 

环视中的回溯

如果环视结构的匹配尝试结束，那么它就不会留下任何备用状态。如果匹配成功，它会放弃剩余的备用状态；如果匹配失败，则继续尝试匹配，直到所有备用状态用光，所以也不会留下备用状态。

环视中，是有可能放弃备用状态的，下面要介绍的固化分组和占有优先量词也会具有这样的性质。

 

 

下面有一条显而易见，但是又容易让大家忽略的事实。

无论是匹配优先还是忽略优先，只要引擎报告匹配失败，它就必然尝试了所有可能。

所以，如果有太多的回溯的可能，那么可能会使得你的程序阻塞，在android里面会产生ANR。之后会给出能阻塞程序的例子。

（对于传统NFA来说，选择结构是按顺序的，并不是匹配优先也不是忽略优先）

 

固化分组与占有优先量词

(?>...) ：固化分组

“?+”、“*+”、“++”、“{m,n}+” ：占有优先量词

 

固化分组

对于“(?>...)” 中的内容部分（省略号省略的部分）来说，与之前将过的匹配规则一致，没有什么区别，但是，当此部分表达式匹配完毕，开始匹配括号外面的部分时，括号内的所有备用状态都会被放弃，也就是说，如果之后的匹配失败，也不会回退固化分组之前记录的状态（因为出了固化分组后，它就忘了之前的状态了，这哥们记性不是很好）。

 

固化分组和环视都有放弃备用状态的特点，我们可以考虑使用肯定环视来模拟固化分组。

对于“(?>regex)” ，我们希望匹配了regex之后就放弃其备用状态，我们知道“(?=regex)”匹配结束之后会放弃其备选状态，那么可以使用“(?=(?:regex))\1”，这样会比真正的固化分组慢一些，因为还要重新匹配“\1”。

 

下面给出一个简单的例子：目标字符串“abc”，正则“(?=\w+)\1”

首先\w+会匹配abc，匹配完成后放弃其所有备选状态，把控制权交给“\1”。“\1”再次重新匹配abc。

如果正则改为：“(?=\w+)\1c”

我想让\w+匹配到“ab”，这样“\1”就匹配到了“ab”，“c”对应“c”，匹配成功。但是，结果并不是这样的！

和上面的匹配过程一样：首先\w+会匹配abc，匹配完成后放弃其所有备选状态，把控制权交给“\1”。“\1”再次重新匹配abc。然后把控制权交给“c”，发现匹配失败，没有备用状态，整体匹配就失败了。有的同学可能会想，如果我让正则回溯到环视之前呢？其实也是一样的，当把控制权交给环视的时候，“\w+”依然直接匹配“abc”，后面大家都知道了，然后再次回溯……

所以当“c”无法匹配字符时，没有必要进行回溯，可以直接宣告匹配失败。

 

下面看看这个正则表达式：“(?>.*?)”

如果上面的内容理解了，那么这个正则也不难了，它永远也匹配不到任何字符。

 

 

占有优先量词

占有优先量词与匹配优先量词（贪婪匹配）很像，区别在于：占有优先量词不会交还字符，而匹配优先在需要的时候会交还字符。

下面给大家一个例子：

字符串：aaaaa

正则1：“\w+a”

正则2：“\w++a”

正则1：首先“\w+a” 的\w+部分会匹配所有字符，它会占有5个a，然后“\w+a” 对其中的a进行匹配，发现已经没有字符留给它了，这时候\w会交还之前占有的字符，每次交还一个。交还一个后，\w拥有“aaaa”，这时候“\w+a” 的a发现，它能匹配\w交还的字符，于是匹配成功，匹配结束。

 

正则2：同样，“\w++a” 的\w++部分会匹配所有字符，然后发现“\w++a” 的a部分无法匹配，但是\w++不会交还之前匹配到的字符，于是，匹配宣告失败！

 

 

区分固化分组与占有优先

作者告诉我们：请务必区分 下面两个表达式

表达式1：“(?>M)+”

表达式2：“(?>M+)”

表达式1放弃了M的备用状态，但是M并没有创造状态，所以这样做没有什么意义

表达式2放弃了M+的备用状态，这样显然有意义。

表达式3：“M++”

与表达式2一样，占有优先量词可以用固化分组来实现。

 

下面是一个稍微复杂点的占有优先表达式，如何将它转化为固化分组呢？

(\\"|[^"])*+

其实我觉得，如果理解了上面的文字，那么转化还是挺简单的，结果如下

(?>(\\"|[^"])*)

可作者觉得，可能会有很多人写成下面错误 的形式

(?>\\"|[^"])*

所以作者特意总结了一下：去掉表示占有优先的加号，用固化分组把余下的部分包括起来。

 

 

深度优先算法（Depth-First-Search）

类别：	搜索算法
数据结构：	图
时间复杂度：
空间复杂度：
最佳解：	否
完全性：	是
其他：	b-分支系数 m-图的最大深度

搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

 

转贴请保留以下链接

本人blog地址

http://su1216.iteye.com/

http://blog.csdn.net/su1216/

评论

2 楼 gtandsn 2014-04-14  

感觉看不懂

1 楼 cjp1989 2012-12-21  

楼主的正则讲的太详细了，顶下了！