如何從零寫一個正規表式引擎？

是的, 首先要確定實作的目標, 有幾個關鍵目標是會影響你的實作的

- 要不要支持完整的正則文法? (如果不支持 "|", 幾十行就能搞定, 如果要支持完整的正則文法, 就需要一個能力超越正則的解析器, 如果要編寫一個高效的 one-pass 正則編譯器, 還是要學不少編譯技術的...)

- 要不要支持 unicode 及 unicode character class? (掃描 UTF-8/16 碼點會比較蛋疼, 容易一點的做法是轉換成 UTF-32 做), 要對 unicode 做完整支持的話, 很多傳統正則引擎瑞奇於字節的匹配方式就不能做了, 一些 DFA 節點的表示方式和壓縮手段也會受限制.

- 要不要支持 back reference? (如果你要實作 back reference 的話, 你不能用

裏描述的 ThompsonVM/PikeVM 的, thread list 占有的記憶體會隨著狀態數指數增長而爆裂) 支持 back reference 的正則基本很多會退回去擴充套件最原始那個 Henry Spencer VM...

- 要做成 NFA based, DFA based, 還是一個字節碼虛擬機器? 對虛擬機器的解決方案, 你要學習字節碼直譯器的基本構造, 可能會用 direct threading 等技術去做最佳化. 字節碼可以看作線性化的 NFA, 相比構造 NFA 節點會減少一些 cache miss 但是相應的就不能使用很多節點壓縮和最佳化的手段了.

- 要不要做一個 JIT 引擎? 這個更令人興奮, 可以參考

)

- 要不要相容 POSIX 標準裏的正則部份? (估摸至少 4000 行程式碼, 自己考慮工作量咯)

- 要不要做 extended 正則?

所謂 extended 正則, 就是還支持補集和交集運算, 正則語言這麽搞完結果還是個正則語言, 就是實作 grep -v 之類的可以簡單一些, 可以嘗試

- 要不要做 Online Parsing?

online parsing 常用於語法高亮和大檔解析中. 其意思是輸入一部份內容就匹配一部份, 有新內容輸入的時候你不該重頭匹配一遍 (每敲一個字元重新著色一遍太慢了), 而是做最低限度的回溯. 如果要做 online parsing, 那麽怎麽暫停你的 VM, 怎麽緩存回溯都是要考慮的問題. 而且正則的語法會有限制.

- 要不要支持超巨大的正規表式?

有些 network filter 例如聯邦的防火墻, 會有幾十萬條規則, 你會發現普通的辦法在 20G 記憶體的機器上都編譯不了這個正則... 不過用小記憶體支持 DFA 千萬節點的方法已經有人研究出來了: D^2FA... 為了編譯出這麽大的 D^2FA, 其編譯期演算法也有人研究過了:

- 要不要支持以下各種正則引擎的 fancy feature?

-- \X 匹配字素

-- 遞迴 named group

-- capture history

-- nested capture

-- atomic group

-- greedy vs reluctant vs possessive

...

每一項都相當有難度... 尤其是 greedy/reluctant/possessive 的區別有可能從根本上顛覆你這個正則引擎的實作, 很多人的正則引擎做完 DFA/NFA 就停下來了, 也是因為搞不動這些 feature.

---

OK, 目標明確了, 開始程式碼之前要先夾溝夾溝哦, 建議: 不要一開始就想把它做得很高效率, 要把問題拆得足夠小足夠簡單的來做, 只要決定好大方向不錯, 就不用推倒重來很多次了...

現在的正則引擎的構造比各種 parser generator 都要復雜, good luck!

推薦書籍: Parsing Techniques - A Practical Guide 2008 (講得比較全了, 就是缺少 coroutine based parser 的構建)

推薦課程:

(為什麽要 beyond CFG 呢? 因為現在正則引擎的能力已經 beyond CFG 啦)

推薦程式碼: Henry Spencer's regexp engine

是很多現代流行的正則引擎的始祖, 直譯器實作, 很多新 feature 能擴充套件得得進去, 也有混合 DFA 的最佳化

Onigmo

是 Ruby 的正則引擎, 特點是 encoding aware 相容多種語法和 feature, 如果要做 unicode character class 可以抄它的...