來源：正則表達式回溯法原理
作者：老姚（轉載已獲得作者授權）
學習正則表達式，是需要懂點兒匹配原理的屑埋。而研究匹配原理時豪筝，有兩個字出現(xiàn)的頻率比較高：回溯。聽起來挺高大上摘能，確實還有很多人對此不明不白的续崖。因此，本文就簡單扼要地說清楚回溯到底是什么東西团搞。
內容包括：
1 . 沒有回溯的匹配
2 . 有回溯的匹配
3 . 常見的回溯形式
1. 沒有回溯的匹配
假設我們的正則是/ab{1,3}c/严望，其可視化形式是：
而當目標字符串是"abbbc"時，就沒有所謂的“回溯”逻恐。其匹配過程是：
其中子表達式b{1,3}表示“b”字符連續(xù)出現(xiàn)1到3次像吻。
2. 有回溯的匹配
如果目標字符串是"abbc"，中間就有回溯复隆。
圖中第5步有紅顏色拨匆，表示匹配不成功。此時b{1,3}已經匹配到了2個字符“b”挽拂，準備嘗試第三個時惭每，結果發(fā)現(xiàn)接下來的字符是“c”。那么就認為b{1,3}就已經匹配完畢亏栈。然后狀態(tài)又回到之前的狀態(tài)（即第6步台腥，與第4步一樣）宏赘，最后再用子表達式c，去匹配字符“c”黎侈。當然察署，此時整個表達式匹配成功了。
圖中的第6步峻汉，就是“回溯”箕母。
你可能對此沒有感覺，這里我們再舉一個例子俱济。正則是：
標字符串是"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"寒波，是兩個數字乘盼，而不是一個。
3.3 分支結構
我們知道分支也是惰性的俄烁，比如/can|candy/绸栅，去匹配字符串"candy"，得到的結果是"can"页屠，因為分支會一個一個嘗試粹胯，如果前面的滿足了，后面就不會再試驗了辰企。
分支結構风纠，可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時牢贸，仍會繼續(xù)嘗試剩下的分支竹观。這種嘗試也可以看成一種回溯。
比如正則：
目標字符串是"candy"潜索，匹配過程：
上面第5步臭增，雖然沒有回到之前的狀態(tài)，但仍然回到了分支結構竹习，嘗試下一種可能誊抛。所以，可以認為它是一種回溯的整陌。
后記
其實回溯法拗窃，很容易掌握的瞎领。
簡單總結就是，正因為有多種可能随夸，所以要一個一個試九默。直到，要么到某一步時逃魄，整體匹配成功了荤西；要么最后都試完后澜搅，發(fā)現(xiàn)整體匹配不成功伍俘。
- 貪婪量詞“試”的策略是：買衣服砍價。價錢太高了勉躺，便宜點癌瘾，不行，再便宜點饵溅。
- 惰性量詞“試”的策略是：賣東西加價妨退。給少了，再多給點行不蜕企，還有點少啊咬荷，再給點。
- 分支結構“試”的策略是：貨比三家轻掩。這家不行幸乒，換一家吧，還不行唇牧，再換罕扎。
既然有回溯的過程，那么匹配效率肯定低一些丐重。相對誰呢腔召？相對那些DFA引擎。而JS的正則引擎是NFA扮惦，NFA是“非確定型有限自動機”的簡寫臀蛛。大部分語言中的正則都是NFA，為啥它這么流行呢崖蜜？
答：你別看我匹配慢掺栅，但是我編譯快啊，而且我還有趣哦纳猪。
感謝你看到這里氧卧，本文也要結束了。雖然本文大部分都是圖片氏堤，沒多少代碼沙绝，但也要說搏明，此時，我們該想到闪檬，陸游詩人對前端做出的最大貢獻是：
紙上得來終覺淺星著，絕知此事要躬行。
本文完粗悯。
