學(xué)習(xí)正則表達式,是需要懂點兒匹配原理的。
而研究匹配原理時,有兩個字出現(xiàn)的頻率比較高:“回溯”。
聽起來挺高大上,確實還有很多人對此不明不白的。
因此,本章就簡單扼要地說清楚回溯到底是什么東西。
內(nèi)容包括:
- 沒有回溯的匹配
- 有回溯的匹配
- 常見的回溯形式
#1. 沒有回溯的匹配
假設(shè)我們的正則是/ab{1,3}c/
,其可視化形式是:
而當目標字符串是"abbbc"時,就沒有所謂的“回溯”。其匹配過程是:
其中子表達式b{1,3}
表示“b”字符連續(xù)出現(xiàn)1到3次。
#2. 有回溯的匹配
如果目標字符串是"abbc",中間就有回溯。
圖中第5步有紅顏色,表示匹配不成功。此時b{1,3}
已經(jīng)匹配到了2個字符“b”,準備嘗試第三個時,結(jié)果發(fā)現(xiàn)接下來的字符是“c”。那么就認為b{1,3}
就已經(jīng)匹配完畢。然后狀態(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}
的最終匹配結(jié)果。
這里再看一個清晰的回溯,正則是:
目標字符串是:"acd"ef,匹配過程是:
圖中省略了嘗試匹配雙引號失敗的過程。可以看出.*
是非常影響效率的。
為了減少一些不必要的回溯,可以把正則修改為/"[^"]*"/
。
#3. 常見的回溯形式
正則表達式匹配字符串的這種方式,有個學(xué)名,叫回溯法。
回溯法也稱試探法,它的基本思想是:從問題的某一種狀態(tài)(初始狀態(tài))出發(fā),搜索從這種狀態(tài)出發(fā)所能達到的所有“狀態(tài)”,當一條路走到“盡頭”的時候(不能再前進),再后退一步或若干步,從另一種可能“狀態(tài)”出發(fā),繼續(xù)搜索,直到所有的“路徑”(狀態(tài))都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法,就稱作“回溯法”。(copy于百度百科)。
本質(zhì)上就是深度優(yōu)先搜索算法。**其中退到之前的某一步這一過程,我們稱為“回溯”。**從上面的描述過程中,可以看出,路走不通時,就會發(fā)生“回溯”。即,嘗試匹配失敗時,接下來的一步通常就是回溯。
道理,我們是懂了。那么JS中正則表達式會產(chǎn)生回溯的地方都有哪些呢?
3.1 貪婪量詞
之前的例子都是貪婪量詞相關(guān)的。比如b{1,3}
,因為其是貪婪的,嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試"bbb",然后再看整個正則是否能匹配。不能匹配時,吐出一個"b",即在"bb"的基礎(chǔ)上,再繼續(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"]
其中\d{1,3}?
只匹配到一個字符"1",而后面的\d{1,3}
匹配了"234"。
雖然惰性量詞不貪,但也會有回溯的現(xiàn)象。比如正則是:
目標字符串是"12345",匹配過程是:
知道你不貪、很知足,但是為了整體匹配成,沒辦法,也只能給你多塞點了。因此最后\d{1,3}?
匹配的字符是"12",是兩個數(shù)字,而不是一個。
3.3 分支結(jié)構(gòu)
我們知道分支也是惰性的,比如/can|candy/
,去匹配字符串"candy",得到的結(jié)果是"can",因為分支會一個一個嘗試,如果前面的滿足了,后面就不會再試驗了。
分支結(jié)構(gòu),可能前面的子模式會形成了局部匹配,如果接下來表達式整體不匹配時,仍會繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯。
比如正則:
目標字符串是"candy",匹配過程:
上面第5步,雖然沒有回到之前的狀態(tài),但仍然回到了分支結(jié)構(gòu),嘗試下一種可能。所以,可以認為它是一種回溯的。