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

內(nèi)容可能有些不嚴(yán)謹(jǐn)?shù)牡胤?，希望大家落腳前先拍磚，多謝

?

深入入門正則表達(dá)式（java） - 引言

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

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

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

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

?

回溯（backtracking）

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

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

兩個(gè)要點(diǎn)：

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

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

?

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

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

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

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

?

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

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

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

?

環(huán)視中的回溯

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

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

?

?

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

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

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

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

?

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

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

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

?

固化分組

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

?

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

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

?

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

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

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

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

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

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

?

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

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

?

?

占有優(yōu)先量詞

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

下面給大家一個(gè)例子：

字符串：aaaaa

正則1：“w+a”

正則2：“w++a”

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

?

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

?

?

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

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

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

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

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

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

表達(dá)式3：“M++”

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

?

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

(\"|[^"])*+

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

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

可作者覺得，可能會(huì)有很多人寫成下面錯(cuò)誤?的形式

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

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

?

?

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

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

b-分支系數(shù)

m-圖的最大深度

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