正則表達式和 NFA

1 人贊了文章

作為前端大佬的你，想必對於 JavaScript 的正則表達式非常熟悉了，甚至隨手就能利用正則表達式寫出一些驚世駭俗的代碼。只是不知道你是否有和我一樣的疑惑：正則表達式是怎麼執行的呢？

我們寫下這樣的正則表達式 (a+|b)c，然後用它來匹配字元串 aacde、abcde，這是怎樣的一個過程呢？

前段時間，我試著去查找、學習相關的資料，然後知道了以下的內容：

• 目前正則表達式引擎主要有兩種：NFA 和 DFA
• JavaScript 採用的是 NFA 引擎

那麼 NFA 又是啥，跟 DFA 有什麼不同？NFA 又是怎麼實現正則表達式匹配的呢？

接下來，我試著用我自己的方式來介紹，希望也能幫助對此感興趣的你。

NFA

NFA 是指 Nondeterministic Finite Automaton，非確定有限狀態自動機。

有點深奧，我剛看到的時候也很懵，咱們慢慢來。

先說有限狀態機（Automation），來個示例圖看下：

狀態機中有這樣一些要素，對照上圖分別說下：

• 開始狀態：圓圈表示狀態，被一個「沒有起點的箭頭」指向的狀態，是開始狀態，上例中是 S1
• 最終狀態：也叫接受狀態，圖中用雙圓圈表示，這個例子中也是 S1
• 輸入：在一個狀態下，向狀態機輸入的符號/信號，不同輸入導致狀態機產生不同的狀態改變
• 轉換：在一個狀態下，根據特定輸入，改變到特定狀態的過程，就是轉換

所以有限狀態機的工作過程，就是從開始狀態，根據不同的輸入，自動進行狀態轉換的過程。

上圖中的狀態機的功能，是檢測二進位數是否含有偶數個 0。從圖上可以看出，輸入只有 1 和 0 兩種。從 S1 狀態開始，只有輸入 0 才會轉換到 S2 狀態，同樣 S2 狀態下只有輸入 0 才會轉換到 S1。所以，二進位數輸入完畢，如果滿足最終狀態，也就是最後停在 S1 狀態，那麼輸入的二進位數就含有偶數個 0。

還是有點暈，這個和正則表達式有什麼關係呢？

正則表達式，可以認為是對一組字元串集合的描述。例如 (a+|b)c 對應的字元串集合是：

acbcaacaaacaaaac...

有限狀態機也可以用來描述字元串集合，同樣是正則表達式所描述的集合，用有限狀態機來表示，可以是這樣的：

這裡的 NFA 狀態圖是我用自己寫的頁面繪製出來的，比較簡陋，不過我相信你可以看懂。

你可以在這裡（luobotang/nfa）自己試試看，只支持簡單的正則表達式。

並且，有限狀態機是可以「執行」的，給出如上的狀態機之後，就可以用來對輸入的字元串進行檢測。如果最終匹配，也就意味著輸入的字元串和正則表達式 (a+|b)c 匹配。

所以，編程語言中的正則表達式，一般是通過有限狀態機來實現。正則表達式匹配字元串的過程，可以分解為：

• 正則表達式轉換為等價的有限狀態機
• 有限狀態機輸入字元串執行

到這裡，我想你大概知道有限狀態機在正則表達式中的作用了，當然，只是具體實現還不清楚。

這裡再講一下 NFA 和 DFA 的區別。DFA 是 Deterministic Finite Automaton，確定有限狀態機。DFA 可以認為是一種特殊的 NFA，它最大的特點，就是確定性。它的確定性在於，在一個狀態下，輸入一個符號，一定是轉換到確定的狀態，沒有其他的可能性。

舉個例子，對於正則表達式 ab|ac，對應 NFA 可以是這樣的：

可以看到，在狀態 1 這裡，如果輸入 a，其實有兩種可能，如果後面的符號是 b，那麼可以匹配成功，後面符號是 c 也能匹配成功。所以狀態機在執行過程中，可能要嘗試所有的可能性。在嘗試一種可能路徑匹配失敗後，還要回到之前的狀態再嘗試其他的路徑，這就是「回溯」。

但是 DFA 消除了這種不確定性，所以可以想見，其執行性能應該要比 NFA 更好，因為不需要回溯。

NFA 是可以轉換為等價的 DFA 的，也就是說，理論上講，正則表達式可以用 DFA 來實現，從而獲得優於 NFA 的執行性能。但是 NFA 轉換 DFA 的過程，會消耗更多資源，甚至最終得到的 DFA 要佔用大量存儲空間（據有的資料的說法，可能會產生指數級增長）。而且，DFA 相比 NFA，在實現一些正則表達式的特性時會更複雜，成本更高。所以當前的許多編程語言，其正則表達式引擎為 NFA 模式。

可以用如下的正則表達式測試當前編程語言採用的引擎是否 NFA：

nfa|nfa not

用上面的正則表達式來測試字元串 nfa not，NFA 引擎在檢測滿足 nfa 就返回匹配成功的結果了，而 DFA 則會嘗試繼續查找，也就是說會得到「最長的匹配結果」。

從正則表達式到 NFA

了解了 NFA 在正則表達式中的應用，接下來要介紹的是如何將正則表達式轉換得到對應的 NFA。這一部分會稍微有些枯燥，不過對於深入理解正則表達式和 NFA 還是挺有幫助的。

Thompson 演算法

Thompson 演算法用於轉換正則表達式為NFA，它並非最高效的演算法，但是實用，易於理解。

Thompson 演算法中使用最基本的兩種轉換：

普通轉換就是在一個狀態下，輸入字元a後轉換至另一個狀態；epsilon轉換則不需要有輸入，就從一個狀態轉換至另一個狀態。

正則表達式中的各種運算，可以通過組合上述兩種轉換實現：

• 組合運算 RS：

• 替換運算 R|S：

• 重複運算 R*：

上面圖中的 R、S 是有開始狀態和結束狀態的 NFA。

以正則表達式 ab|c 為例，包括兩個運算：

• ab 組合
• ab 的結果，與 c 替換

這樣我們把正則表達式視為一系列輸入和運算，進行分解、組合，就可以得到最終的 NFA。

首先，我們要把正則表達式轉換為方便記錄輸入、運算的方式。

正則表達式 -> 後綴表達式

後綴表達式是一種方便記錄輸入、運算的表達式，本身已包含了運算符的優先順序，也稱為 逆波蘭表示法（Reverse Polish Notation，簡寫為 RPN）。

為方便記錄運算，我們為正則表達式中的組合運算也創建一個運算符「.」（本文只涉及最簡單的正則表達式形式，這裡的「.」不是用於匹配任意字元的特殊符號）。

正則表達式ab|c對應的後綴表達式為 ab.c|。

這樣，通過逐個掃描後綴表達式，並識別其中的運算符來執行，就可以對後綴表達式進行求解。對於正則表達式來說，則是在將其變為後綴表達式後，通過「求值」的過程來進一步構建並得到最終的 NFA。

用於創建後綴表達式的是 調度場演算法。

對於這裡的正則表達式處理的場景，演算法的大致描述如下：

代碼在：regex2post() | nfa.js#L14 - luobotang/nfa

- 創建輸出隊列 output 和運算符棧 ops- 依次讀取輸入字元串中每一個字元 ch - 如果 ch 是普通字元，追加到 output - 如果 ch 是運算符，只要 ops 棧頂的運算符優先順序不低於 ch，依次出棧並追加到 output，最後將 ch 入棧 ops - 如果 ch 是「(」，入棧 ops - 如果 ch 是「)」，只要 ops 棧頂不是「(」，依次出棧並追加到 output- 將 ops 中運算符依次出棧追加到 output- 返回 output

具體處理過程中，由於原始正則表達式中並沒有組合運算符，所以需要自行判斷合理的插入位置。

運算符優先順序如下（由高到低）：

• * ? +
• .
• |
• (

後綴表達式 -> NFA

基於後綴表達式創建 NFA，是一個由簡單的 NFA 進行不斷組合得到複雜 NFA 的過程。

用於表示狀態 State 的數據結構為：

// State{ id: String, type: String, // n - normal, e - epsilon, end symbol: String, // 普通狀態對應的輸入字元 out: State, // 允許的下一個狀態 out1: State // 允許的下一個狀態}

每個狀態可以對應最多兩個 out 狀態，像 a|b|c 的表達式，會被分解為 (a|b)|c，每次運算符「|」都只處理兩個（子）表達式。

在構造最終 NFA 過程中，每次會創建 NFA 的片段 Fragment：

// Fragment{ start: State, out: State}

不管 NFA 片段內部是怎樣複雜，它都只有一個入口（開始狀態），一個出口（最終狀態）。

這一部分代碼在：post2nfa() | nfa.js#L90 - luobotang/nfa

處理的過程大致為：

- 創建用於記錄 NFA 片段的棧 stack- 依次讀取輸入的後綴表達式的每個字元 ch - 如果 ch 是運算符，從 stack 出棧所需數目的 NFA 片段，構建新的 NFA 片段後入棧 stack - 如果 ch 是普通字元，創建新的狀態，並構建只包含此狀態的 NFA 片段入棧 stack- 返回 stack 棧頂的 NFA 片段，即最終結果

以對組合運算的處理為例：

const e2 = stack.pop()const e1 = stack.pop()e1.out.out = e2.startstack.push(new Fragment(e1.start, e2.out))

從 stack 出棧兩個 NFA 片段，然後將其首尾相連後構建新的 NFA 片段再入棧。

其他處理過程就不詳細介紹了，感興趣可以看下代碼。

NFA 的執行

NFA 的執行過程就是用當前狀態來比對字元串的當前字元，如果匹配就繼續比對下一個狀態和下一個字元，否則匹配失敗。

不過由於 NFA 的不確定性，所以可能會同時有多個匹配的狀態。

我這裡就簡單粗暴了，直接讓當前所有的狀態都進行比對，仍然滿足條件的下一個狀態再繼續參與下一輪比對。一次只跟蹤一條路徑，匹配失敗後再回溯肯定也是可以的，不過就要複雜很多了。

代碼在：simulator.js - luobotang/nfa

總結

綜上，正則表達式的執行，可以通過構建等價的 NFA，然後執行 NFA 來匹配輸入的字元串。真實的 JavaScript 中的正則表達式擁有更多的特性，其正則表達式引擎也更加複雜。

希望通過我的介紹，能夠讓你對正則表達式有了更多的了解。當然，水平有限，講得不當的地方在所難免，歡迎指正。

最後，感謝閱讀！

參考資料

• Writing own regular expression parser - Amer Gerzic
• Regular Expression Matching Can Be Simple And Fast - Russ Cox
• Automata theory - wikipedia
• Nondeterministic finite automaton - wikipedia
• file-infix-to-postfix-regexp-js - gist.github.com
• Shunting-yard algorithm - wikipedia.com

推薦閱讀：