深入入門正則表達式（java） - 匹配原理 - 2 - 回溯

內(nèi)容可能有些不嚴(yán)謹(jǐn)?shù)牡胤剑Ｍ蠹衣淠_前先拍磚，多謝

?

深入入門正則表達式（java） - 引言

深入入門正則表達式（java） - 1 - 入門基礎(chǔ)?
深入入門正則表達式（java） - 2 - 基本實例

深入入門正則表達式（java） - 3 - 正則在java中的使用

深入入門正則表達式（java） - 匹配原理 - 1 - 引擎分類與普適原則

深入入門正則表達式（java） - 匹配原理 - 2 - 回溯

?

回溯（backtracking）

NFA引擎最重要的性質(zhì)是：它會一次處理各個子表達式或組成元素，遇到需要在兩個可能成功的可能中進行選擇的時候，它會選擇其一，同時記住其他結(jié)果，以備后續(xù)需要

需要做出選擇的情形包括?量詞（決定是否嘗試另一次匹配）和多選結(jié)構(gòu)（決定選擇哪個多選分支）

兩個要點：

1.如果需要在“進行嘗試”和“跳過嘗試”之間選擇，對于匹配優(yōu)先量詞來說，引擎會優(yōu)先選擇“進行嘗試”，對于忽略優(yōu)先量詞來說，會選擇“跳過嘗試”

2.距離當(dāng)前最近存儲的選項就是當(dāng)本地失敗強制回溯返回的。使用的原則是LIFO（last in first out，后進先出）。

?

實際上，NFA搜索的過程算法就是深度優(yōu)先（關(guān)于深度優(yōu)先介紹見文章末尾，內(nèi)容來自中文維機百科），只不過并不一定完全遍歷，完成匹配之后就停止搜索了。下面我舉幾個簡單的例子，畫圖來描述一下。

例，假如我們要匹配一串?dāng)?shù)字中的最后兩位，目標(biāo)字符串“3456”，正則“d+(dd)”，下面是一個流程示意圖：

匹配過程比較簡單，首先d+匹配3、4、5、6，其中綠色的圓圈是d+的備用位置。

d+繼續(xù)嘗試匹配，發(fā)現(xiàn)沒有字符了，所以它的匹配結(jié)束，把控制權(quán)交給了d，然而d也無法匹配，所以需要進行回溯。

?

正則回到第二個綠色圓圈那里，然后控制權(quán)交給d?，F(xiàn)在d可以匹配到數(shù)字6了，匹配結(jié)束，控制權(quán)交給d，發(fā)現(xiàn)沒有字符留給它，所以還需要回溯。

正則回到第一個綠色圓圈那里，然后控制權(quán)交給d?，F(xiàn)在d可以匹配到數(shù)字5了，匹配結(jié)束，控制權(quán)交給d，匹配到了數(shù)字6，匹配結(jié)束，至此整個表達式完成了匹配。

（這里紅色的圓圈表示交換控制權(quán)，這樣方便理解。只有在綠色圓圈處才可能產(chǎn)生新的分支，其余地方，如果匹配失敗，只需要原路返回到綠色圓圈處即可，然后嘗試量詞和多選結(jié)構(gòu)的備用狀態(tài)）

?

環(huán)視中的回溯

如果環(huán)視結(jié)構(gòu)的匹配嘗試結(jié)束，那么它就不會留下任何備用狀態(tài)。如果匹配成功，它會放棄剩余的備用狀態(tài)；如果匹配失敗，則繼續(xù)嘗試匹配，直到所有備用狀態(tài)用光，所以也不會留下備用狀態(tài)。

環(huán)視中，是有可能放棄備用狀態(tài)的，下面要介紹的固化分組和占有優(yōu)先量詞也會具有這樣的性質(zhì)。

?

?

下面有一條顯而易見，但是又容易讓大家忽略的事實。

無論是匹配優(yōu)先還是忽略優(yōu)先，只要引擎報告匹配失敗，它就必然嘗試了所有可能。

所以，如果有太多的回溯的可能，那么可能會使得你的程序阻塞，在android里面會產(chǎn)生ANR。之后會給出能阻塞程序的例子。

（對于傳統(tǒng)NFA來說，選擇結(jié)構(gòu)是按順序的，并不是匹配優(yōu)先也不是忽略優(yōu)先）

?

固化分組與占有優(yōu)先量詞

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

“?+”、“*+”、“++”、“{m,n}+”?：占有優(yōu)先量詞

?

固化分組

對于“(?>...)”?中的內(nèi)容部分（省略號省略的部分）來說，與之前將過的匹配規(guī)則一致，沒有什么區(qū)別，但是，當(dāng)此部分表達式匹配完畢，開始匹配括號外面的部分時，括號內(nèi)的所有備用狀態(tài)都會被放棄，也就是說，如果之后的匹配失敗，也不會回退固化分組之前記錄的狀態(tài)（因為出了固化分組后，它就忘了之前的狀態(tài)了，這哥們記性不是很好）。

?

固化分組和環(huán)視都有放棄備用狀態(tài)的特點，我們可以考慮使用肯定環(huán)視來模擬固化分組。

對于“(?>regex)”?，我們希望匹配了regex之后就放棄其備用狀態(tài)，我們知道“(?=regex)”匹配結(jié)束之后會放棄其備選狀態(tài)，那么可以使用“(?=(?:regex))1”，這樣會比真正的固化分組慢一些，因為還要重新匹配“1”。

?

下面給出一個簡單的例子：目標(biāo)字符串“abc”，正則“(?=w+)1”

首先w+會匹配abc，匹配完成后放棄其所有備選狀態(tài)，把控制權(quán)交給“1”?！?”再次重新匹配abc。

如果正則改為：“(?=w+)1c”

我想讓w+匹配到“ab”，這樣“1”就匹配到了“ab”，“c”對應(yīng)“c”，匹配成功。但是，結(jié)果并不是這樣的！

和上面的匹配過程一樣：首先w+會匹配abc，匹配完成后放棄其所有備選狀態(tài)，把控制權(quán)交給“1”?！?”再次重新匹配abc。然后把控制權(quán)交給“c”，發(fā)現(xiàn)匹配失敗，沒有備用狀態(tài)，整體匹配就失敗了。有的同學(xué)可能會想，如果我讓正則回溯到環(huán)視之前呢？其實也是一樣的，當(dāng)把控制權(quán)交給環(huán)視的時候，“w+”依然直接匹配“abc”，后面大家都知道了，然后再次回溯……

所以當(dāng)“c”無法匹配字符時，沒有必要進行回溯，可以直接宣告匹配失敗。

?

下面看看這個正則表達式：“(?>.*?)”

如果上面的內(nèi)容理解了，那么這個正則也不難了，它永遠也匹配不到任何字符。

?

?

占有優(yōu)先量詞

占有優(yōu)先量詞與匹配優(yōu)先量詞（貪婪匹配）很像，區(qū)別在于：占有優(yōu)先量詞不會交還字符，而匹配優(yōu)先在需要的時候會交還字符。

下面給大家一個例子：

字符串：aaaaa

正則1：“w+a”

正則2：“w++a”

正則1：首先“w+a”?的w+部分會匹配所有字符，它會占有5個a，然后“w+a”?對其中的a進行匹配，發(fā)現(xiàn)已經(jīng)沒有字符留給它了，這時候w會交還之前占有的字符，每次交還一個。交還一個后，w擁有“aaaa”，這時候“w+a”?的a發(fā)現(xiàn)，它能匹配w交還的字符，于是匹配成功，匹配結(jié)束。

?

正則2：同樣，“w++a”?的w++部分會匹配所有字符，然后發(fā)現(xiàn)“w++a”?的a部分無法匹配，但是w++不會交還之前匹配到的字符，于是，匹配宣告失?。?/p>

?

?

區(qū)分固化分組與占有優(yōu)先

作者告訴我們：請務(wù)必區(qū)分?下面兩個表達式

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

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

表達式1放棄了M的備用狀態(tài)，但是M并沒有創(chuàng)造狀態(tài)，所以這樣做沒有什么意義

表達式2放棄了M+的備用狀態(tài)，這樣顯然有意義。

表達式3：“M++”

與表達式2一樣，占有優(yōu)先量詞可以用固化分組來實現(xiàn)。

?

下面是一個稍微復(fù)雜點的占有優(yōu)先表達式，如何將它轉(zhuǎn)化為固化分組呢？

(\"|[^"])*+

其實我覺得，如果理解了上面的文字，那么轉(zhuǎn)化還是挺簡單的，結(jié)果如下

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

可作者覺得，可能會有很多人寫成下面錯誤?的形式

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

所以作者特意總結(jié)了一下：去掉表示占有優(yōu)先的加號，用固化分組把余下的部分包括起來。

?

?

深度優(yōu)先算法（Depth-First-Search）

類別： 搜索算法 數(shù)據(jù)結(jié)構(gòu)： 圖 時間復(fù)雜度：空間復(fù)雜度：最佳解： 否 完全性： 是 其他：

b-分支系數(shù)

m-圖的最大深度

搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當(dāng)節(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有節(jié)點都被訪問為止。屬于盲目搜索。