內(nèi)容可能有些不嚴(yán)謹(jǐn)?shù)牡胤剑Ｍ蠹衣淠_前先拍磚，多謝
?
深入入門正則表達(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)行嘗試”和“跳過嘗試”之間選擇，對(duì)于匹配優(yōu)先量詞來說，引擎會(huì)優(yōu)先選擇“進(jìn)行嘗試”，對(duì)于忽略優(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+( \d \d ) ”，下面是一個(gè)流程 示意圖 ：
匹配過程比較簡單，首先\d+匹配3、4、5、6， 其中綠色的圓圈是\d+的備用位置。
\d+繼續(xù)嘗試匹配，發(fā)現(xiàn)沒有字符了，所以它的匹配結(jié)束，把控制權(quán)交給了 \d ，然而 \d 也無法匹配，所以需要進(jìn)行回溯。
?
正則回到第二個(gè)綠色圓圈那里，然后控制權(quán)交給 \d 。現(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ì)給出能阻塞程序的例子。
（對(duì)于傳統(tǒng)NFA來說，選擇結(jié)構(gòu)是按順序的，并不是匹配優(yōu)先也不是忽略優(yōu)先）
?
固化分組與占有優(yōu)先量詞
(?>...) ? ：固化分組
“?+”、“*+”、“++”、“{m,n}+” ? ：占有優(yōu)先量詞
?
固化分組
對(duì)于 “(?>...)” ?中的內(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)視來模擬固化分組。
對(duì)于 “(?>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”。“\1”再次重新匹配abc。
如果正則改為： “(?=\w+)\1c”
我想讓\w+匹配到“ab”，這樣“\1”就匹配到了“ab”，“c”對(duì)應(yīng)“c”，匹配成功。 但是，結(jié)果并不是這樣的！
和上面的匹配過程一樣：首先\w+會(huì)匹配abc， 匹配完成后放棄其所有備選狀態(tài)， 把控制權(quán)交給“\1”。“\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” ? 對(duì)其中的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)先
作者告訴我們：請(qǐng) 務(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)都被訪問為止。屬于盲目搜索。
?
轉(zhuǎn)貼請(qǐng)保留以下鏈接
本人blog地址
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
