內容可能有些不嚴謹的地方，希望大家落腳前先拍磚，多謝
?
深入入門正則表達式（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一樣， 占有優先量詞可以用固化分組來實現。
?
下面是一個稍微復雜點的占有優先表達式，如何將它轉化為固化分組呢？
(\\"|[^"])*+
其實我覺得，如果理解了上面的文字，那么轉化還是挺簡單的，結果如下
(?>(\\"|[^"])*)
可作者覺得，可能會有很多人寫成下面 錯誤 ? 的形式
(?>\\"|[^"])*
所以作者特意總結了一下：去掉表示占有優先的加號，用固化分組把余下的部分包括起來。
?
?
| 類別： | 搜索算法 |
| 數據結構： | 圖 |
| 時間復雜度： |
|
| 空間復雜度： |
|
| 最佳解： | 否 |
| 完全性： | 是 |
| 其他： |
b-分支系數 m-圖的最大深度 |
搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬于盲目搜索。
?
轉貼請保留以下鏈接
本人blog地址
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
