來源：正則表達(dá)式回溯法原理
作者：老姚（轉(zhuǎn)載已獲得作者授權(quán)）
學(xué)習(xí)正則表達(dá)式，是需要懂點(diǎn)兒匹配原理的。而研究匹配原理時(shí)，有兩個(gè)字出現(xiàn)的頻率比較高：回溯。聽起來挺高大上，確實(shí)還有很多人對此不明不白的。因此，本文就簡單扼要地說清楚回溯到底是什么東西。
內(nèi)容包括：
1 . 沒有回溯的匹配
2 . 有回溯的匹配
3 . 常見的回溯形式
1. 沒有回溯的匹配
假設(shè)我們的正則是/ab{1,3}c/，其可視化形式是：
而當(dāng)目標(biāo)字符串是"abbbc"時(shí)，就沒有所謂的“回溯”。其匹配過程是：
其中子表達(dá)式b{1,3}表示“b”字符連續(xù)出現(xiàn)1到3次。
2. 有回溯的匹配
如果目標(biāo)字符串是"abbc"，中間就有回溯。
圖中第5步有紅顏色，表示匹配不成功。此時(shí)b{1,3}已經(jīng)匹配到了2個(gè)字符“b”，準(zhǔn)備嘗試第三個(gè)時(shí)，結(jié)果發(fā)現(xiàn)接下來的字符是“c”。那么就認(rèn)為b{1,3}就已經(jīng)匹配完畢。然后狀態(tài)又回到之前的狀態(tài)（即第6步，與第4步一樣），最后再用子表達(dá)式c，去匹配字符“c”。當(dāng)然，此時(shí)整個(gè)表達(dá)式匹配成功了。
圖中的第6步，就是“回溯”。
你可能對此沒有感覺，這里我們再舉一個(gè)例子。正則是：
標(biāo)字符串是"abbbc"，匹配過程是：
其中第7步和第10步是回溯。第7步與第4步一樣，此時(shí)b{1,3}匹配了兩個(gè)"b"，而第10步與第3步一樣，此時(shí)b{1,3}只匹配了一個(gè)"b"，這也是b{1,3}的最終匹配結(jié)果。
這里再看一個(gè)清晰的回溯，正則是：
目標(biāo)字符串是："acd"ef，匹配過程是：
圖中省略了嘗試匹配雙引號失敗的過程?？梢钥闯觥?*”是非常影響效率的。
為了減少一些不必要的回溯，可以把正則修改為/"[^"]*"/。
3. 常見的回溯形式
正則表達(dá)式匹配字符串的這種方式，有個(gè)學(xué)名，叫回溯法。
回溯法也稱試探法，它的基本思想是：從問題的某一種狀態(tài)（初始狀態(tài)）出發(fā)，搜索從這種狀態(tài)出發(fā)所能達(dá)到的所有“狀態(tài)”，當(dāng)一條路走到“盡頭”的時(shí)候（不能再前進(jìn)），再后退一步或若干步，從另一種可能“狀態(tài)”出發(fā)，繼續(xù)搜索，直到所有的“路徑”（狀態(tài)）都試探過。這種不斷“前進(jìn)”、不斷“回溯”尋找解的方法，就稱作“回溯法”。（copy于百度百科）。
本質(zhì)上就是深度優(yōu)先搜索算法。其中退到之前的某一步這一過程，我們稱為“回溯”。從上面的描述過程中，可以看出，路走不通時(shí)，就會(huì)發(fā)生“回溯”。即，嘗試匹配失敗時(shí)，接下來的一步通常就是回溯。
道理，我們是懂了。那么JS中正則表達(dá)式會(huì)產(chǎn)生回溯的地方都有哪些呢？
3.1 貪婪量詞
之前的例子都是貪婪量詞相關(guān)的。比如b{1,3}，因?yàn)槠涫秦澙返?，嘗試可能的順序是從多往少的方向去嘗試。首先會(huì)嘗試"bbb"，然后再看整個(gè)正則是否能匹配。不能匹配時(shí)，吐出一個(gè)"b"，即在"bb"的基礎(chǔ)上，再繼續(xù)嘗試。如果還不行，再吐出一個(gè)，再試。如果還不行呢？只能說明匹配失敗了。
雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？
此時(shí)我們不禁會(huì)問，如果當(dāng)多個(gè)貪婪量詞挨著存在，并相互有沖突時(shí)，此時(shí)會(huì)是怎樣？
答案是，先下手為強(qiáng)！因?yàn)樯疃葍?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 惰性量詞
惰性量詞就是在貪婪量詞后面加個(gè)問號。表示盡可能少的匹配，比如：
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}?只匹配到一個(gè)字符"1"，而后面的\d{1,3}匹配了"234"。
雖然惰性量詞不貪，但也會(huì)有回溯的現(xiàn)象。比如正則是：
目標(biāo)字符串是"12345"，匹配過程是：
知道你不貪、很知足，但是為了整體匹配成，沒辦法，也只能給你多塞點(diǎn)了。因此最后\d{1,3}?匹配的字符是"12"，是兩個(gè)數(shù)字，而不是一個(gè)。
3.3 分支結(jié)構(gòu)
我們知道分支也是惰性的，比如/can|candy/，去匹配字符串"candy"，得到的結(jié)果是"can"，因?yàn)榉种?huì)一個(gè)一個(gè)嘗試，如果前面的滿足了，后面就不會(huì)再試驗(yàn)了。
分支結(jié)構(gòu)，可能前面的子模式會(huì)形成了局部匹配，如果接下來表達(dá)式整體不匹配時(shí)，仍會(huì)繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯。
比如正則：
目標(biāo)字符串是"candy"，匹配過程：
上面第5步，雖然沒有回到之前的狀態(tài)，但仍然回到了分支結(jié)構(gòu)，嘗試下一種可能。所以，可以認(rèn)為它是一種回溯的。
后記
其實(shí)回溯法，很容易掌握的。
簡單總結(jié)就是，正因?yàn)橛卸喾N可能，所以要一個(gè)一個(gè)試。直到，要么到某一步時(shí)，整體匹配成功了；要么最后都試完后，發(fā)現(xiàn)整體匹配不成功。
- 貪婪量詞“試”的策略是：買衣服砍價(jià)。價(jià)錢太高了，便宜點(diǎn)，不行，再便宜點(diǎn)。
- 惰性量詞“試”的策略是：賣東西加價(jià)。給少了，再多給點(diǎn)行不，還有點(diǎn)少啊，再給點(diǎn)。
- 分支結(jié)構(gòu)“試”的策略是：貨比三家。這家不行，換一家吧，還不行，再換。
既然有回溯的過程，那么匹配效率肯定低一些。相對誰呢？相對那些DFA引擎。而JS的正則引擎是NFA，NFA是“非確定型有限自動(dòng)機(jī)”的簡寫。大部分語言中的正則都是NFA，為啥它這么流行呢？
答：你別看我匹配慢，但是我編譯快啊，而且我還有趣哦。
感謝你看到這里，本文也要結(jié)束了。雖然本文大部分都是圖片，沒多少代碼，但也要說，此時(shí)，我們該想到，陸游詩人對前端做出的最大貢獻(xiàn)是：
紙上得來終覺淺，絕知此事要躬行。
本文完。
