作為前端大佬的你平斩，想必對(duì)于 JavaScript 的正則表達(dá)式非常熟悉了夫椭，甚至隨手就能利用正則表達(dá)式寫出一些驚世駭俗的代碼劣欢。只是不知道你是否有和我一樣的疑惑：正則表達(dá)式是怎么執(zhí)行的呢盛垦？
我們寫下這樣的正則表達(dá)式 (a+|b)c湿弦，然后用它來(lái)匹配字符串 aacde、abcde腾夯，這是怎樣的一個(gè)過(guò)程呢颊埃？
前段時(shí)間，我試著去查找蝶俱、學(xué)習(xí)相關(guān)的資料班利，然后知道了以下的內(nèi)容：
- 目前正則表達(dá)式引擎主要有兩種：NFA 和 DFA
- JavaScript 采用的是 NFA 引擎
那么 NFA 又是啥，跟 DFA 有什么不同榨呆？NFA 又是怎么實(shí)現(xiàn)正則表達(dá)式匹配的呢罗标？
接下來(lái)，我試著用我自己的方式來(lái)介紹积蜻，希望也能幫助對(duì)此感興趣的你闯割。
NFA
NFA 是指 Nondeterministic Finite Automaton，非確定有限狀態(tài)自動(dòng)機(jī)竿拆。
有點(diǎn)深?yuàn)W宙拉，我剛看到的時(shí)候也很懵，咱們慢慢來(lái)丙笋。
先說(shuō)有限狀態(tài)機(jī)（Automation）谢澈，來(lái)個(gè)示例圖看下：
狀態(tài)機(jī)中有這樣一些要素煌贴，對(duì)照上圖分別說(shuō)下：
- 開始狀態(tài)：圓圈表示狀態(tài)，被一個(gè)“沒(méi)有起點(diǎn)的箭頭”指向的狀態(tài)澳化，是開始狀態(tài)崔步，上例中是 S1
- 最終狀態(tài)：也叫接受狀態(tài)，圖中用雙圓圈表示缎谷，這個(gè)例子中也是 S1
- 輸入：在一個(gè)狀態(tài)下井濒，向狀態(tài)機(jī)輸入的符號(hào)/信號(hào)，不同輸入導(dǎo)致?tīng)顟B(tài)機(jī)產(chǎn)生不同的狀態(tài)改變
- 轉(zhuǎn)換：在一個(gè)狀態(tài)下列林，根據(jù)特定輸入瑞你，改變到特定狀態(tài)的過(guò)程，就是轉(zhuǎn)換
所以有限狀態(tài)機(jī)的工作過(guò)程希痴，就是從開始狀態(tài)者甲，根據(jù)不同的輸入，自動(dòng)進(jìn)行狀態(tài)轉(zhuǎn)換的過(guò)程砌创。
上圖中的狀態(tài)機(jī)的功能虏缸，是檢測(cè)二進(jìn)制數(shù)是否含有偶數(shù)個(gè) 0。從圖上可以看出嫩实，輸入只有 1 和 0 兩種刽辙。從 S1 狀態(tài)開始，只有輸入 0 才會(huì)轉(zhuǎn)換到 S2 狀態(tài)甲献，同樣 S2 狀態(tài)下只有輸入 0 才會(huì)轉(zhuǎn)換到 S1宰缤。所以，二進(jìn)制數(shù)輸入完畢晃洒，如果滿足最終狀態(tài)慨灭，也就是最后停在 S1 狀態(tài)，那么輸入的二進(jìn)制數(shù)就含有偶數(shù)個(gè) 0球及。
還是有點(diǎn)暈氧骤，這個(gè)和正則表達(dá)式有什么關(guān)系呢？
正則表達(dá)式吃引，可以認(rèn)為是對(duì)一組字符串集合的描述筹陵。例如 (a+|b)c 對(duì)應(yīng)的字符串集合是：
ac
bc
aac
aaac
aaaac
...
有限狀態(tài)機(jī)也可以用來(lái)描述字符串集合，同樣是正則表達(dá)式所描述的集合际歼，用有限狀態(tài)機(jī)來(lái)表示，可以是這樣的：
這里的 NFA 狀態(tài)圖是我用自己寫的頁(yè)面繪制出來(lái)的姑蓝，比較簡(jiǎn)陋鹅心，不過(guò)我相信你可以看懂。
你可以在這里（luobotang/nfa）自己試試看纺荧，只支持簡(jiǎn)單的正則表達(dá)式旭愧。
并且颅筋，有限狀態(tài)機(jī)是可以“執(zhí)行”的，給出如上的狀態(tài)機(jī)之后输枯，就可以用來(lái)對(duì)輸入的字符串進(jìn)行檢測(cè)议泵。如果最終匹配，也就意味著輸入的字符串和正則表達(dá)式 (a+|b)c 匹配桃熄。
所以先口，編程語(yǔ)言中的正則表達(dá)式，一般是通過(guò)有限狀態(tài)機(jī)來(lái)實(shí)現(xiàn)瞳收。正則表達(dá)式匹配字符串的過(guò)程碉京，可以分解為：
- 正則表達(dá)式轉(zhuǎn)換為等價(jià)的有限狀態(tài)機(jī)
- 有限狀態(tài)機(jī)輸入字符串執(zhí)行
到這里，我想你大概知道有限狀態(tài)機(jī)在正則表達(dá)式中的作用了螟深，當(dāng)然谐宙，只是具體實(shí)現(xiàn)還不清楚。
這里再講一下 NFA 和 DFA 的區(qū)別界弧。DFA 是 Deterministic Finite Automaton凡蜻，確定有限狀態(tài)機(jī)。DFA 可以認(rèn)為是一種特殊的 NFA垢箕，它最大的特點(diǎn)划栓，就是確定性。它的確定性在于舰讹，在一個(gè)狀態(tài)下茅姜，輸入一個(gè)符號(hào)，一定是轉(zhuǎn)換到確定的狀態(tài)月匣，沒(méi)有其他的可能性钻洒。
舉個(gè)例子，對(duì)于正則表達(dá)式 ab|ac锄开，對(duì)應(yīng) NFA 可以是這樣的：
可以看到素标，在狀態(tài) 1 這里，如果輸入 a萍悴，其實(shí)有兩種可能头遭，如果后面的符號(hào)是 b，那么可以匹配成功癣诱，后面符號(hào)是 c 也能匹配成功计维。所以狀態(tài)機(jī)在執(zhí)行過(guò)程中，可能要嘗試所有的可能性撕予。在嘗試一種可能路徑匹配失敗后鲫惶，還要回到之前的狀態(tài)再嘗試其他的路徑，這就是“回溯”实抡。
但是 DFA 消除了這種不確定性欠母，所以可以想見(jiàn)欢策，其執(zhí)行性能應(yīng)該要比 NFA 更好，因?yàn)椴恍枰厮荨?/p>
NFA 是可以轉(zhuǎn)換為等價(jià)的 DFA 的赏淌，也就是說(shuō)踩寇，理論上講，正則表達(dá)式可以用 DFA 來(lái)實(shí)現(xiàn)六水，從而獲得優(yōu)于 NFA 的執(zhí)行性能俺孙。但是 NFA 轉(zhuǎn)換 DFA 的過(guò)程，會(huì)消耗更多資源缩擂，甚至最終得到的 DFA 要占用大量存儲(chǔ)空間（據(jù)有的資料的說(shuō)法鼠冕，可能會(huì)產(chǎn)生指數(shù)級(jí)增長(zhǎng)）。而且胯盯，DFA 相比 NFA懈费，在實(shí)現(xiàn)一些正則表達(dá)式的特性時(shí)會(huì)更復(fù)雜，成本更高博脑。所以當(dāng)前的許多編程語(yǔ)言憎乙，其正則表達(dá)式引擎為 NFA 模式。
可以用如下的正則表達(dá)式測(cè)試當(dāng)前編程語(yǔ)言采用的引擎是否 NFA：
nfa|nfa not
用上面的正則表達(dá)式來(lái)測(cè)試字符串 nfa not叉趣，NFA 引擎在檢測(cè)滿足 nfa 就返回匹配成功的結(jié)果了泞边，而 DFA 則會(huì)嘗試?yán)^續(xù)查找汁汗，也就是說(shuō)會(huì)得到“最長(zhǎng)的匹配結(jié)果”膀捷。
從正則表達(dá)式到 NFA
了解了 NFA 在正則表達(dá)式中的應(yīng)用，接下來(lái)要介紹的是如何將正則表達(dá)式轉(zhuǎn)換得到對(duì)應(yīng)的 NFA严卖。這一部分會(huì)稍微有些枯燥烟具，不過(guò)對(duì)于深入理解正則表達(dá)式和 NFA 還是挺有幫助的梢什。
Thompson 算法
Thompson 算法用于轉(zhuǎn)換正則表達(dá)式為NFA，它并非最高效的算法朝聋，但是實(shí)用嗡午，易于理解。
Thompson 算法中使用最基本的兩種轉(zhuǎn)換：
普通轉(zhuǎn)換就是在一個(gè)狀態(tài)下冀痕，輸入字符a后轉(zhuǎn)換至另一個(gè)狀態(tài)荔睹；epsilon轉(zhuǎn)換則不需要有輸入，就從一個(gè)狀態(tài)轉(zhuǎn)換至另一個(gè)狀態(tài)言蛇。
正則表達(dá)式中的各種運(yùn)算僻他，可以通過(guò)組合上述兩種轉(zhuǎn)換實(shí)現(xiàn)：
- 組合運(yùn)算
RS：
-
替換運(yùn)算
R|S：R|S -
重復(fù)運(yùn)算
R*：R*
上面圖中的 R、S 是有開始狀態(tài)和結(jié)束狀態(tài)的 NFA腊尚。
以正則表達(dá)式 ab|c 為例吨拗，包括兩個(gè)運(yùn)算：
-
ab組合 -
ab的結(jié)果，與c替換
這樣我們把正則表達(dá)式視為一系列輸入和運(yùn)算，進(jìn)行分解丢胚、組合，就可以得到最終的 NFA受扳。
首先携龟，我們要把正則表達(dá)式轉(zhuǎn)換為方便記錄輸入、運(yùn)算的方式勘高。
正則表達(dá)式 -> 后綴表達(dá)式
后綴表達(dá)式是一種方便記錄輸入峡蟋、運(yùn)算的表達(dá)式，本身已包含了運(yùn)算符的優(yōu)先級(jí)华望，也稱為 逆波蘭表示法（Reverse Polish Notation蕊蝗，簡(jiǎn)寫為 RPN）。
為方便記錄運(yùn)算赖舟，我們?yōu)檎齽t表達(dá)式中的組合運(yùn)算也創(chuàng)建一個(gè)運(yùn)算符“.”（本文只涉及最簡(jiǎn)單的正則表達(dá)式形式蓬戚，這里的“.”不是用于匹配任意字符的特殊符號(hào)）。
正則表達(dá)式ab|c對(duì)應(yīng)的后綴表達(dá)式為 ab.c|宾抓。
這樣子漩，通過(guò)逐個(gè)掃描后綴表達(dá)式，并識(shí)別其中的運(yùn)算符來(lái)執(zhí)行石洗，就可以對(duì)后綴表達(dá)式進(jìn)行求解幢泼。對(duì)于正則表達(dá)式來(lái)說(shuō)，則是在將其變?yōu)楹缶Y表達(dá)式后讲衫，通過(guò)“求值”的過(guò)程來(lái)進(jìn)一步構(gòu)建并得到最終的 NFA缕棵。
用于創(chuàng)建后綴表達(dá)式的是 調(diào)度場(chǎng)算法。
對(duì)于這里的正則表達(dá)式處理的場(chǎng)景涉兽，算法的大致描述如下：
代碼在：regex2post() | nfa.js#L14 - luobotang/nfa
- 創(chuàng)建輸出隊(duì)列 output 和運(yùn)算符棧 ops
- 依次讀取輸入字符串中每一個(gè)字符 ch
- 如果 ch 是普通字符招驴，追加到 output
- 如果 ch 是運(yùn)算符，只要 ops 棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)不低于 ch花椭，依次出棧并追加到 output忽匈，最后將 ch 入棧 ops
- 如果 ch 是“(”，入棧 ops
- 如果 ch 是“)”矿辽，只要 ops 棧頂不是“(”丹允，依次出棧并追加到 output
- 將 ops 中運(yùn)算符依次出棧追加到 output
- 返回 output
具體處理過(guò)程中，由于原始正則表達(dá)式中并沒(méi)有組合運(yùn)算符袋倔，所以需要自行判斷合理的插入位置雕蔽。
運(yùn)算符優(yōu)先級(jí)如下（由高到低）：
- * ? +
- .
- |
- (
后綴表達(dá)式 -> NFA
基于后綴表達(dá)式創(chuàng)建 NFA，是一個(gè)由簡(jiǎn)單的 NFA 進(jìn)行不斷組合得到復(fù)雜 NFA 的過(guò)程宾娜。
用于表示狀態(tài) State 的數(shù)據(jù)結(jié)構(gòu)為：
// State
{
id: String,
type: String, // 'n' - normal, 'e' - epsilon, 'end'
symbol: String, // 普通狀態(tài)對(duì)應(yīng)的輸入字符
out: State, // 允許的下一個(gè)狀態(tài)
out1: State // 允許的下一個(gè)狀態(tài)
}
每個(gè)狀態(tài)可以對(duì)應(yīng)最多兩個(gè) out 狀態(tài)批狐，像 a|b|c 的表達(dá)式，會(huì)被分解為 (a|b)|c，每次運(yùn)算符“|”都只處理兩個(gè)（子）表達(dá)式嚣艇。
在構(gòu)造最終 NFA 過(guò)程中承冰，每次會(huì)創(chuàng)建 NFA 的片段 Fragment：
// Fragment
{
start: State,
out: State
}
不管 NFA 片段內(nèi)部是怎樣復(fù)雜，它都只有一個(gè)入口（開始狀態(tài)）食零，一個(gè)出口（最終狀態(tài)）困乒。
這一部分代碼在：post2nfa() | nfa.js#L90 - luobotang/nfa
處理的過(guò)程大致為：
- 創(chuàng)建用于記錄 NFA 片段的棧 stack
- 依次讀取輸入的后綴表達(dá)式的每個(gè)字符 ch
- 如果 ch 是運(yùn)算符，從 stack 出棧所需數(shù)目的 NFA 片段贰谣，構(gòu)建新的 NFA 片段后入棧 stack
- 如果 ch 是普通字符娜搂，創(chuàng)建新的狀態(tài)，并構(gòu)建只包含此狀態(tài)的 NFA 片段入棧 stack
- 返回 stack 棧頂?shù)?NFA 片段吱抚，即最終結(jié)果
以對(duì)組合運(yùn)算的處理為例：
const e2 = stack.pop()
const e1 = stack.pop()
e1.out.out = e2.start
stack.push(new Fragment(e1.start, e2.out))
從 stack 出棧兩個(gè) NFA 片段百宇，然后將其首尾相連后構(gòu)建新的 NFA 片段再入棧。
其他處理過(guò)程就不詳細(xì)介紹了秘豹，感興趣可以看下代碼携御。
NFA 的執(zhí)行
NFA 的執(zhí)行過(guò)程就是用當(dāng)前狀態(tài)來(lái)比對(duì)字符串的當(dāng)前字符，如果匹配就繼續(xù)比對(duì)下一個(gè)狀態(tài)和下一個(gè)字符既绕，否則匹配失敗因痛。
不過(guò)由于 NFA 的不確定性，所以可能會(huì)同時(shí)有多個(gè)匹配的狀態(tài)岸更。
我這里就簡(jiǎn)單粗暴了鸵膏，直接讓當(dāng)前所有的狀態(tài)都進(jìn)行比對(duì)，仍然滿足條件的下一個(gè)狀態(tài)再繼續(xù)參與下一輪比對(duì)怎炊。一次只跟蹤一條路徑谭企，匹配失敗后再回溯肯定也是可以的，不過(guò)就要復(fù)雜很多了评肆。
代碼在：simulator.js - luobotang/nfa
總結(jié)
綜上债查，正則表達(dá)式的執(zhí)行，可以通過(guò)構(gòu)建等價(jià)的 NFA瓜挽，然后執(zhí)行 NFA 來(lái)匹配輸入的字符串盹廷。真實(shí)的 JavaScript 中的正則表達(dá)式擁有更多的特性，其正則表達(dá)式引擎也更加復(fù)雜久橙。
希望通過(guò)我的介紹俄占，能夠讓你對(duì)正則表達(dá)式有了更多的了解。當(dāng)然淆衷，水平有限缸榄，講得不當(dāng)?shù)牡胤皆谒y免，歡迎指正祝拯。
最后甚带，感謝閱讀！
