學(xué)習(xí)正則表達(dá)式，是需要懂點(diǎn)兒匹配原理的。

而研究匹配原理時(shí)，有兩個(gè)字出現(xiàn)的頻率比較高：“回溯”。

聽(tīng)起來(lái)挺高大上，確實(shí)還有很多人對(duì)此不明不白的。

因此，本章就簡(jiǎn)單扼要地說(shuō)清楚回溯到底是什么東西。

內(nèi)容包括：

1. 沒(méi)有回溯的匹配
2. 有回溯的匹配
3. 常見(jiàn)的回溯形式

#1. 沒(méi)有回溯的匹配

假設(shè)我們的正則是/ab{1,3}c/，其可視化形式是：

而當(dāng)目標(biāo)字符串是"abbbc"時(shí)，就沒(méi)有所謂的“回溯”。其匹配過(guò)程是：

其中子表達(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)接下來(lái)的字符是“c”。那么就認(rèn)為b{1,3}就已經(jīng)匹配完畢。然后狀態(tài)又回到之前的狀態(tài)（即第6步，與第4步一樣），最后再用子表達(dá)式c，去匹配字符“c”。當(dāng)然，此時(shí)整個(gè)表達(dá)式匹配成功了。

圖中的第6步，就是“回溯”。

你可能對(duì)此沒(méi)有感覺(jué)，這里我們?cè)倥e一個(gè)例子。正則是：

目標(biāo)字符串是"abbbc"，匹配過(guò)程是：

其中第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，匹配過(guò)程是：

圖中省略了嘗試匹配雙引號(hào)失敗的過(guò)程?？梢钥闯?span style="background-color: rgba(127, 127, 127, 0.12);">.*是非常影響效率的。

為了減少一些不必要的回溯，可以把正則修改為/"[^"]*"/。

#3. 常見(jiàn)的回溯形式

正則表達(dá)式匹配字符串的這種方式，有個(gè)學(xué)名，叫回溯法。

回溯法也稱試探法，它的基本思想是：從問(wèn)題的某一種狀態(tài)（初始狀態(tài)）出發(fā)，搜索從這種狀態(tài)出發(fā)所能達(dá)到的所有“狀態(tài)”，當(dāng)一條路走到“盡頭”的時(shí)候（不能再前進(jìn)），再后退一步或若干步，從另一種可能“狀態(tài)”出發(fā)，繼續(xù)搜索，直到所有的“路徑”（狀態(tài)）都試探過(guò)。這種不斷“前進(jìn)”、不斷“回溯”尋找解的方法，就稱作“回溯法”。（copy于百度百科）。

本質(zhì)上就是深度優(yōu)先搜索算法。**其中退到之前的某一步這一過(guò)程，我們稱為“回溯”。**從上面的描述過(guò)程中，可以看出，路走不通時(shí)，就會(huì)發(fā)生“回溯”。即，嘗試匹配失敗時(shí)，接下來(lái)的一步通常就是回溯。

道理，我們是懂了。那么JS中正則表達(dá)式會(huì)產(chǎn)生回溯的地方都有哪些呢？

3.1 貪婪量詞

之前的例子都是貪婪量詞相關(guān)的。比如b{1,3}，因?yàn)槠涫秦澙返模瑖L試可能的順序是從多往少的方向去嘗試。首先會(huì)嘗試"bbb"，然后再看整個(gè)正則是否能匹配。不能匹配時(shí)，吐出一個(gè)"b"，即在"bb"的基礎(chǔ)上，再繼續(xù)嘗試。如果還不行，再吐出一個(gè)，再試。如果還不行呢？只能說(shuō)明匹配失敗了。

雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？

此時(shí)我們不禁會(huì)問(wèn)，如果當(dāng)多個(gè)貪婪量詞挨著存在，并相互有沖突時(shí)，此時(shí)會(huì)是怎樣？

答案是，先下手為強(qiáng)！因?yàn)樯疃葍?yōu)先搜索。測(cè)試如下：

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è)問(wèn)號(hào)。表示盡可能少的匹配，比如：

var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]

其中\d{1,3}?只匹配到一個(gè)字符"1"，而后面的\d{1,3}匹配了"234"。

雖然惰性量詞不貪，但也會(huì)有回溯的現(xiàn)象。比如正則是：

目標(biāo)字符串是"12345"，匹配過(guò)程是：

知道你不貪、很知足，但是為了整體匹配成，沒(méi)辦法，也只能給你多塞點(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ì)形成了局部匹配，如果接下來(lái)表達(dá)式整體不匹配時(shí)，仍會(huì)繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯。

比如正則：

目標(biāo)字符串是"candy"，匹配過(guò)程：

上面第5步，雖然沒(méi)有回到之前的狀態(tài)，但仍然回到了分支結(jié)構(gòu)，嘗試下一種可能。所以，可以認(rèn)為它是一種回溯的。