背景
? ? ? ?最近公司規(guī)范出來后，關于字符串不提倡用 “ + ” ?進行拼接，于是自己寫了個function，利用正則表達式來進行匹配。對于正則表達式，之前不了解原理，每次要用的時候查一下，很浪費時間。
內(nèi)容
基礎知識；
正則表達式引擎；
貪婪與非貪婪模式；
DFA與NFA引擎；
回溯機制及常見的回溯形式
基礎知識
1. 占有字符：正則表達式匹配過程中，如果子表達式匹配到東西，而并非是一個位置，并最終保存到匹配的結(jié)果當中
2. 零寬度：只匹配一個位置，或者是匹配的內(nèi)容并不保存到匹配結(jié)果中
一個字符，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配
3.控制權(quán)：正則表達式由左到右依次進行匹配，通常情況下是由一個表達式取得控制權(quán)，從字符串的的某個位置進行匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結(jié)束位置開始的（例如：（表達式一）（表達式二）意思就是表達式一匹配完成后才能匹配表達式二，而匹配表達式二的位置是從表達式一的位置匹配結(jié)束后的位置開始）。如果表達式一是零寬度，那表達式一匹配完成后，表達式二匹配的位置還是原來表達式以匹配的位置。也就是說它匹配開始和結(jié)束的位置是同一個
4. 元字符?
5. 反義元字符
6. 轉(zhuǎn)義字符：\? 使元字符失去它的意義，僅代表其輸入中字符的意義
需要轉(zhuǎn)義的字符列表\ * + ? | { [ ( ) ^ $ . # 和 空白
7. 重復限定符：匹配優(yōu)先量詞，忽略優(yōu)先量詞，即：貪婪與非貪婪
{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*'
8. 字符類：[ ]，區(qū)分大小寫
9. 分支條件： |
10. 分組 ：（）指定子表達式，可限制多選項的范圍、將若干字符組合為一個單元、受問號或星號之類的量詞作用，例：(\d{1,3}){3}\d{3}
斷言；(?
11. 括號及反向引用：（子表達式一）（子表達式二）\1? ? ? 此時括號作用為分組，它具有記憶的功能，即在正則表達式內(nèi)部仍然能回憶上次匹配到的是什么；\1、\2、\n 是用在正則表達式的匹配環(huán)節(jié)。在正則表達式的替換環(huán)節(jié)，則要使用像 $1、$2、$n 這樣的語法
12. 平衡組參考
正則表達式引擎
有兩個主要特點：
1. 默認貪婪匹配；（貪婪匹配與非貪婪匹配）
2. 返回最先匹配到的結(jié)果
針對簡單的正則匹配進行分析，例：
? ? ? ? 當把cat應用到“He captured a catfish for his cat”，引擎先比較c和“H”，結(jié)果失敗了。于是引擎再比較c和“e”，也失敗了。直到第四個字符，c匹配了“c”。a匹配了第五個字符。到第六個字符t沒能匹配“p”，也失敗了。引擎再繼續(xù)從第五個字符重新檢查匹配性。直到第十五個字符開始，cat匹配上了“catfish”中的“cat”，正則表達式引擎急切的返回第一個匹配的結(jié)果，而不會再繼續(xù)查找是否有其他更好的匹配
Rubular: 基于 Web 的 Ruby 正則表達式編輯器
貪婪與非貪婪（又稱惰性、懶惰等）模式
兩者影響的是被量詞修飾的子表達式的行為。
貪婪模式在整個表達式匹配成功的前提下，盡可能多的匹配；而非貪婪模式（只被部分NFA引擎支持）在整個表達式匹配成功的前提下，盡可能少的匹配。
匹配優(yōu)先量詞（屬于貪婪模式的量詞）：
“{m,n}”、“{m,}”、“?”、“*”和“+”。
忽略優(yōu)先量詞（匹配優(yōu)先量詞后加上“?”：非貪婪模式的量詞）：
“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”
例：
源字符串：aa
正則表達式一：
正則表達式二：
DFA與NFA引擎（JS的正則引擎是NFA：非確定型有限自動機）
參考：正則表達式引擎及其分類
DFA引擎：在線性時狀態(tài)下執(zhí)行，不要求回溯（因此永遠不測試相同的字符兩次）；確保匹配最長的可能的字符串；因為只包含有限的狀態(tài)（？），所以它不能匹配具有反向引用的模式；并且因為它不構(gòu)造顯示擴展，所以它不可以捕獲子表達式
傳統(tǒng)的NFA引擎：運行匹配回溯算法——以指定順序測試正則表達式的所有可能的擴展并接受第一個匹配項。因為傳統(tǒng)的 NFA 構(gòu)造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但傳統(tǒng) NFA的 回溯使它可以訪問完全相同的狀態(tài)多次（如果通過不同的路徑到達該狀態(tài)）。因此，在最壞情況下，它的執(zhí)行速度可能非常慢。因為傳統(tǒng)的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發(fā)現(xiàn)
POSIX NFA 引擎：與傳統(tǒng) NFA 引擎類似，不同點：在可以確保已找到了可能的最長的匹配之前，它們將繼續(xù)回溯（更慢）；并且在使用 POSIX NFA 時，您恐怕不會愿意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索
例：
字符串：this is yansen’s dog
正則表達式：/ya(msen|nsen|nsem)/
NFA工作方式：先在字符串中查找y，然后匹配其后是否為a；?如果是a則繼續(xù)查找其后是否為m；如果不是則匹配其后是否為n(此時淘汰msen支分支)； 然后繼續(xù)看其后是否依次為s,e；接著測試是否為n，是n則匹配成功，不是則測試是否為m。為什么是 m ？因為 NFA 工作方式是以正則表達式為標準，反復測試字符串，這樣同樣一個字符串有可能被反復測試了很多次！
DFA：從this中t開始依次查找y，定位到y，已知其后為a，則查看表達式是否有a，此處正好有a；然后字符串a后為n，DFA依次測試表達式，此時msen不符合要求淘汰。nsen和nsem符合要求，然后DFA依次檢查字符串，檢測到sen中的n時只有nsen分支符合，則匹配成功！
由此兩種引擎是完全不同的工作方式：NFA以表達式為主導，更容易操縱；DFA以文本為主導（搜索更快）
回溯機制
引擎是如何來處理那些模糊的條件匹配？
從問題的某一種狀態(tài)（初始狀態(tài)）出發(fā)，搜索從這種狀態(tài)出發(fā)所能達到的所有“狀態(tài)”，當一條路走到“盡頭”的時候（不能再前進），再后退一步或若干步，從另一種可能“狀態(tài)”出發(fā)，繼續(xù)搜索，直到所有的“路徑”（狀態(tài)）都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法，就稱作“回溯法”
--來自百度百科
本質(zhì)上就是深度優(yōu)先搜索算法：嘗試匹配失敗時的下一步通常就是回溯
JS中正則表達式會產(chǎn)生回溯的地方都有哪些呢？
常見的回溯形式
1.貪婪量詞
例：正則：/ab{1,3}c/
可視化形式
1. 沒有回溯的匹配：當目標字符串是"abbbc"時
匹配過程
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步，就是“回溯”
即：嘗試可能的順序是“從多往少”的方向去嘗試：首先會嘗試"bbb"，然后再看整個正則是否能匹配。不能匹配時，吐出一個"b"，即在"bb"的基礎上，再繼續(xù)嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了
另一個清晰的回溯：
正則：/".*"/
目標字符串："acd"ef
省略了嘗試匹配雙引號失敗的匹配過程
其實“.*”最簡單但也是非常影響效率的
2.惰性量詞
雖然惰性量詞不貪，但也會有回溯的現(xiàn)象（為了整體匹配成）
正則表達式
目標字符串："12345"
匹配過程
3.分支結(jié)構(gòu)
分支也是惰性的，比如/Java|JavaScript/，去匹配字符串"JavaScript"，得到的結(jié)果是"Java"，因為分支會一個一個嘗試，如果前面的滿足了，后面就不會再試驗了。
分支結(jié)構(gòu)中可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯：
正則表達式
匹配過程
雖然第五步?jīng)]有回到之前的狀態(tài)，但仍然回到了分支結(jié)構(gòu)，嘗試下一種可能
總結(jié)：有回溯的過程，那么匹配效率肯定比DFA相對低一些；別看匹配慢，但是編譯快而且還挺有趣
參考：正則表達式的回溯機制
