本文章是在學習程序猿DD的JS正則表達式完整教程的基礎上，將js正則的例子用java實現(xiàn)（其實大體差不多，只是細節(jié)的變化）。目的是自己過一遍，加深理解。如果侵權，請聯(lián)系刪除。
學習正則表達式，是需要懂點兒匹配原理的。
內容包括：
- 沒有回溯的匹配
- 有回溯的匹配
- 常見的回溯形式
1.沒有回溯的匹配
假設我們的正則是/ab{1,3}c/，其可視化形式是：
而當目標字符串是”abbbc”時，就沒有所謂的“回溯”。其匹配過程是：
2.有回溯的匹配
如果目標字符串是”abbc”，中間就有回溯。
圖中第5步有紅顏色，表示匹配不成功。此時
b{1,3}已經(jīng)匹配到了2個字符“b”，準備嘗試第三個時，結果發(fā)現(xiàn)接下來的字符是“c”。那么就認為b{1,3}就已經(jīng)匹配完畢。然后狀態(tài)又回到之前的狀態(tài)（即第6步，與第4步一樣），最后再用子表達式c，去匹配字符“c”。當然，此時整個表達式匹配成功了。
你可能對此沒有感覺，這里我們再舉一個例子。正則是：
目標字符串是”abbbc”，匹配過程是：
其中第7步和第10步是回溯。第7步與第4步一樣，此時b{1,3}匹配了兩個”b”，而第10步與第3步一樣，此時b{1,3}只匹配了一個”b”，這也是b{1,3}的最終匹配結果。
這里再看一個清晰的回溯，正則是：
目標字符串是：”acd”ef，匹配過程是：
圖中省略了嘗試匹配雙引號失敗的過程?？梢钥闯?是非常影響效率的。
為了減少一些不必要的回溯，可以把正則修改為/"[^"]"/。
3. 常見的回溯形式
正則表達式匹配字符串的這種方式，有個學名，叫回溯法。
回溯法也稱試探法，它的基本思想是：從問題的某一種狀態(tài)（初始狀態(tài)）出發(fā)，搜索從這種狀態(tài)出發(fā)所能達到的所有“狀態(tài)”，當一條路走到“盡頭”的時候（不能再前進），再后退一步或若干步，從另一種可能“狀態(tài)”出發(fā)，繼續(xù)搜索，直到所有的“路徑”（狀態(tài)）都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法，就稱作“回溯法”。（copy于百度百科）。
本質上就是深度優(yōu)先搜索算法。其中退到之前的某一步這一過程，我們稱為“回溯”。從上面的描述過程中，可以看出，路走不通時，就會發(fā)生“回溯”。即，嘗試匹配失敗時，接下來的一步通常就是回溯。
道理，我們是懂了。那么JS中正則表達式會產生回溯的地方都有哪些呢？
3.1 貪婪量詞
之前的例子都是貪婪量詞相關的。比如b{1,3}，因為其是貪婪的，嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試”bbb”，然后再看整個正則是否能匹配。不能匹配時，吐出一個”b”，即在”bb”的基礎上，再繼續(xù)嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了。
雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？
此時我們不禁會問，如果當多個貪婪量詞挨著存在，并相互有沖突時，此時會是怎樣？
答案是，先下手為強！因為深度優(yōu)先搜索。測試如下：
var string = "12345";
var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );
// => ["12345", "123", "45", index: 0, input: "12345"]
其中，前面的\d{1,3}匹配的是”123”，后面的\d{1,3}匹配的是”45”。
3.2 惰性量詞
惰性量詞就是在貪婪量詞后面加個問號。表示盡可能少的匹配，比如：
var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]
其中\(zhòng)d{1,3}?只匹配到一個字符”1”，而后面的\d{1,3}匹配了”234”。
雖然惰性量詞不貪，但也會有回溯的現(xiàn)象。比如正則是：
目標字符串是”12345”，匹配過程是：
知道你不貪、很知足，但是為了整體匹配成，沒辦法，也只能給你多塞點了。因此最后
\d{1,3}?匹配的字符是”12”，是兩個數(shù)字，而不是一個。
3.3 分支結構
我們知道分支也是惰性的，比如/can|candy/，去匹配字符串”candy”，得到的結果是”can”，因為分支會一個一個嘗試，如果前面的滿足了，后面就不會再試驗了。
分支結構，可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯。
比如正則：
目標字符串是”candy”，匹配過程：
上面第5步，雖然沒有回到之前的狀態(tài)，但仍然回到了分支結構，嘗試下一種可能。所以，可以認為它是一種回溯的。
小結
其實回溯法，很容易掌握的。
簡單總結就是，正因為有多種可能，所以要一個一個試。直到，要么到某一步時，整體匹配成功了；要么最后都試完后，發(fā)現(xiàn)整體匹配不成功。
- 1.貪婪量詞“試”的策略是：買衣服砍價。價錢太高了，便宜點，不行，再便宜點。
- 2.惰性量詞“試”的策略是：賣東西加價。給少了，再多給點行不，還有點少啊，再給點。
- 3.分支結構“試”的策略是：貨比三家。這家不行，換一家吧，還不行，再換。
既然有回溯的過程，那么匹配效率肯定低一些。相對誰呢？相對那些DFA引擎。
而JS的正則引擎是NFA，NFA是“非確定型有限自動機”的簡寫。
大部分語言中的正則都是NFA，為啥它這么流行呢？
答：你別看我匹配慢，但是我編譯快啊，而且我還有趣哦。
注：DFA和NFA的區(qū)別
正則表達式引擎分成兩類，一類稱為DFA（確定性有窮自動機），另一類稱為NFA（非確定性有窮自動機）。兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手里，一個吃下去。DFA捏著文本串去比較正則式，看到一個子正則式，就把可能的匹配串全標注出來，然后再看正則式的下一個部分，根據(jù)新的匹配結果更新標注。而NFA是捏著正則式去比文本，吃掉一個字符，就把它跟正則式比較，匹配就記下來：“某年某月某日在某處匹配上了！”，然后接著往下干。一旦不匹配，就把剛吃的這個字符吐出來，一個個的吐，直到回到上一次匹配的地方。
DFA與NFA機制上的不同帶來5個影響：
- DFA對于文本串里的每一個字符只需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字符、吐字符，速度慢，但是特性豐富，所以反而應用廣泛，當今主要的正則表達式引擎，如Perl、Ruby、Python的re模塊、Java和.NET的regex庫，都是NFA的。
- 只有NFA才支持lazy和backreference等特性；
- NFA急于邀功請賞，所以最左子正則式優(yōu)先匹配成功，因此偶爾會錯過最佳匹配結果；DFA則是“最長的左子正則式優(yōu)先匹配成功”。
- NFA缺省采用greedy量詞（見item 4）；
- NFA可能會陷入遞歸調用的陷阱而表現(xiàn)得性能極差。
例如用正則式/perl|perlman/來匹配文本 ‘perlman book’。如果是NFA，則以正則式為導向，手里捏著正則式，眼睛看著文本，一個字符一個字符的吃，吃完 ‘perl’ 以后，跟第一個子正則式/perl/已經(jīng)匹配上了，于是記錄在案，往下再看，吃進一個 ‘m’，這下糟了，跟子式/perl/不匹配了，于是把m吐出來，向上匯報說成功匹配 ‘perl’，不再關心其他，也不嘗試后面那個子正則式/perlman/，自然也就看不到那個更好的答案了。
如果是DFA，它是以文本為導向，手里捏著文本，眼睛看著正則式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一個鉤，記上一筆，說這個字符已經(jīng)匹配上了，然后往下吃。當看到 /perl/ 之后，DFA不會停，會嘗試再吃一口。這時候，第一個子正則式已經(jīng)山窮水盡了，沒得吃了，于是就甩掉它，去吃第二個子正則式的/m/。這一吃好了，因為又匹配上了，于是接著往下吃。直到把正則式吃完，心滿意足往上報告說成功匹配了 ‘perlman’。
由此可知，要讓NFA正確工作，應該使用 /perlman|perl/ 模式。
