如何从零写一个正则表达式引擎？

是的, 首先要确定实现的目标, 有几个关键目标是会影响你的实现的

- 要不要支持完整的正则文法? (如果不支持 "|", 几十行就能搞定, 如果要支持完整的正则文法, 就需要一个能力超越正则的解析器, 如果要编写一个高效的 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 可以抄它的...

写了个80行的C++模板版。注意啊，regex的定义包括了concatenation，alternation（“|”），Kleene closure（“*”），还得有一个ε字符（可近似认为“?”），expression还要能嵌套（“(”“)”）。有些例子里缺了alternation和嵌套那就不该叫regex了。

之所以这么短是因为压根没有parsing，parsing多无聊啊。直接构造regex的AST，根本不去打NFA的主意。想加什么功能就直接加type就行了。

这个是compile time regex，所以跑起来是raw speed，很快。你要是要运行时的regex，把那几个模板特化改为一个树状variant结构，在树上走就行了，算法（包括那个continuation的trick）都是一样的。

建NFA那套做法是Ken Thompson推出来的“标准”算法，但是就玩玩而已应该从更简单的学起。学一下CPS变换又不会死。

另外把程序写短小紧凑的诀窍就是写成FP style。我的80行中所有函数都只有一个return语句。