“rea”是我最近抽空写的一个正则表达式引擎项目全称叫 Regex Engine Architecture目标是完全脱离现成正则库从零把“匹配”这件事做到能跑、能测、能上线。这篇文章会把整个项目的设计思路、词法解析、语法树构建、NFA/DFA 编译以及实测结果原原本本讲一遍适合对正则原理好奇、准备做 DSL 或想深入编译原理的开发者参考。1. 为什么我要手写正则引擎以及 rea 的整体设计1.1 从“会用”到“想拆开看”的动机我在日常开发里其实很少直接拿正则去做复杂解析多数场景只是校验格式、提取字段。但有一次排查线上日志匹配变慢的问题发现一条看似正常的表达式在某段输入上跑了十几秒当时第一反应是“正则库出 bug 了”可查了半天发现不是库的问题而是灾难性回溯导致的计算爆炸。那件事对我触动很大正则表达式的性能特点对使用者来说几乎是个黑盒你只知道它能匹配却不知道它为什么快、为什么慢。于是就有了重写一个迷你正则引擎的念头。rea 不做成一个功能无限大的完整正则标准库而是聚焦三件事第一把正则字符串变成可执行的匹配逻辑第二在匹配方式上同时支持 DFA 确定性匹配和带捕获组的回溯匹配第三尽量把整个引擎拆开让每一步都有测试覆盖、有性能数字。写完之后我最大的感受是正则里很多“理所当然”的行为比如贪婪匹配、回溯、捕获组区间只有亲手实现一遍才真正讲得清楚。1.2 引擎整体架构与数据流设计rea 的总体结构参考了经典编译器的三段式设计前端负责解析中端负责编译后端负责执行。前端把输入的正则字符串拆成 token 流再根据语法规则构建 AST抽象语法树。这一步相当于把“人写的表达式”翻译成“程序能处理的结构化数据”。中端把 AST 编译为 NFA非确定性有限自动机再把 NFA 通过子集构造法转换成 DFA确定性有限自动机。这是整个引擎的核心也是最难调试的部分。后端用 DFA 执行纯匹配用 NFA 回溯模式处理捕获组和反向引用支持。这个设计最大的好处是职责清楚。词法分析阶段不用关心量词怎么组合语法分析阶段不用关心状态怎么跳转状态机阶段不用关心原始字符串长什么样。任何一个环节出问题都可以单独写测试定位。1.3 技术选型与工程目录规划rea 选择 Python 3.11 实现理由是原型迭代快、内置数据结构方便表达状态转移而且写测试非常顺手。虽然 Python 的运行时性能偏慢但学习引擎原理时完全够用未来要跑高性能场景可以平移移植到 Rust 或 C。工程目录长这样rea/ ├── rea/lexer.py # 词法分析 ├── rea/ast_nodes.py # AST 节点定义 ├── rea/parser.py # 递归下降解析 ├── rea/nfa.py # NFA 数据结构与 Thompson 构造 ├── rea/dfa.py # 子集构造法 ├── rea/matcher.py # 执行匹配 ├── tests/ # 单元测试与回归测试 └── bench/ # 基准测试脚本需要说明的是这个项目从一开始就不是为了“再造一个轮子丢到生产环境”而是把原理吃透。所以我在某些地方故意做了简化比如默认只支持单行文本匹配Unicode 属性支持也是一步步加上去的。接下来我会按数据流顺序把每个模块的细节都展开讲。2. 词法分析把正则字符串变成 token 流2.1 token 的分类与扫描规则词法分析是整个引擎最枯燥但最重要的一步。rea 里 token 分为以下几类token 类型示例含义CHARa1我普通字符ESCAPE\d\w\n\\转义序列DOT.任意字符LPAREN(捕获组开始RPAREN)捕获组结束LBRACKET[字符类开始RBRACKET]字符类结束STAR*零次或多次PLUS一次或多次QUEST?零次或一次或懒惰修饰符LBRACE/RBRACE{m,n}区间量词PIPECARET/DOLLAR^$锚点UNSUPPORTED\1等反向引用等暂不支持的特性扫描逻辑比较简单但有几个关键点容易错*?和?这种懒惰标记不能拆成两个独立 tokenlexer 需要在扫描到量词后立刻判断下一个字符是不是?是的话合并为一个 token 并附加 lazy 标记。{m,n}只有完整满足格式时才当作区间量词否则应该当普通字符处理。比如a{2,3}是区间量词但a{后面没跟上合法数字时{就只是普通字符。转义字符必须在这里展开或标记不要在语法分析阶段再做字符串处理。\d如果展开成[0-9]在词法阶段做最方便后续 NFA 构造直接看 token 就知道边长什么样。2.2 核心代码tokenizer 的实现lexer 的主函数大致长这样def tokenize(pattern: str) - list[Token]: tokens [] i 0 n len(pattern) while i n: c pattern[i] if c \\: token, i read_escape(pattern, i) tokens.append(token) elif c in ()[]|.*?{}^$: token, i read_meta(pattern, i) tokens.append(token) else: tokens.append(Token(TokenType.CHAR, valuec)) i 1 tokens.append(Token(TokenType.EOF)) return tokens这里read_escape负责把\d转换为一个带预定义字符集合的 tokenread_meta负责识别*?、{m,n}这类组合语法。我在最初版本里犯过一个错误把?单独识别成 QUEST token结果后面解析a*?时AST 变成了(a*)?语义完全错了。后来改成在 lexer 里合并懒惰标记解析器就干净很多。2.3 token 流调试与单元测试词法分析是最好写单测的部分因为输入输出都是列表非常直观。我的测试策略是先用正则字符串直接看 token 流再手动构造预期列表做断言。def test_tokenize_lazy_quantifier(): tokens tokenize(ra*?b) assert tokens[0].type TokenType.CHAR assert tokens[1].type TokenType.STAR_LAZY assert tokens[2].type TokenType.CHAR这种测试看着简单但对后面 AST 解析帮助极大。如果 token 层出了问题后面所有层都会被带偏所以词法测试宁可多写也不要省。3. 语法分析构建 AST 与处理优先级3.1 AST 节点设计与嵌套关系token 流只是线性序列要表达“或”“连接”“重复”这些层级关系必须构建树形结构。rea 中定义了这些核心节点CharNode单个字符。CharClassNode字符集合比如[a-z]。ConcatNode多个子节点按顺序连接。AlternationNode多个子节点取其一。StarNode/PlusNode/QuestNode重复量词包装单个子节点。RepeatNode区间量词{m,n}包装单个子节点。GroupNode一组子节点可以带捕获编号。AnchorNode行首/行尾。AST 的层级直接映射正则语法优先级。正则里优先级从高到低是字符和字符类 量词 连接 或所以解析器也必须按这个顺序递归下降。3.2 递归下降解析器的实现思路解析器的核心是四个函数对应四个语法层级def parse_alternation(): left parse_concat() while peek() PIPE: consume(PIPE) right parse_concat() left AlternationNode([left, right]) return left def parse_concat(): children [] while not at_end() and peek() not in (RPAREN, PIPE, EOF): children.append(parse_repeat()) return ConcatNode(children) if len(children) 1 else children[0] def parse_repeat(): atom parse_atom() if peek() in (STAR, PLUS, QUEST, LBRACE): # 构造对应量词节点 return atom def parse_atom(): if peek() LPAREN: # 解析分组 if peek() LBRACKET: # 解析字符类 # 否则是普通字符或转义序列这个结构最大的好处是“或”的优先级天然低于“连接”因为parse_alternation调用parse_concatparse_concat里的子表达式再调用parse_repeat。比如a|bc会被解析成 AlternationNode(a, ConcatNode(b, c))而这正是正则的语义。3.3 解析阶段的几个实际坑第一个坑是空分支。形如a|的正则表示“匹配 a 或空字符串”如果不特殊处理parse_concat遇到|后面的空字符串时可能返回 None导致 AlternationNode 缺一个子节点。我最后统一规定ConcatNode([])代表空字符串这样所有情况都是合法的节点。第二个坑是非捕获组(?:...)。因为 rea 的 NFA/DFA 主线不需要捕获组也能工作所以我在 AST 层面把(?:...)表示成普通 GroupNode但标记capturingFalse。这样 DFA 构造可以忽略它回溯模式也不记录捕获区间。第三个坑是嵌套括号的闭包检查。递归下降解析如果不检查括号匹配遇到(a这样的输入可能静默失败。我选择在解析器末尾显式检查当前 token 必须是 EOF否则抛出语法错误。这样至少能快速暴露表达式不完整的问题。4. 编译到 NFA 和 DFA核心状态机逻辑4.1 Thompson 构造法从 AST 到 NFA理解 NFA 构造最直观的方式是把每个 AST 节点想象成一个带开始状态和接受状态的“盒子”再用 epsilon 边把盒子连起来。epsilon 边表示不需要消费字符就能跳转。AST 节点NFA 构造方式单个字符两个状态一条字符边连接aba 的接受状态连到 b 的开始状态或a|b新开始状态分别 epsilon 到 a 和 ba 和 b 的接受状态都 epsilon 到新接受状态星号a*新接受状态通过 epsilon 回到开始状态形成循环字符类[a-z]两个状态一条标签为“字符区间集合”的边上述构造法有个专业名称叫 Thompson 构造法。它生成的状态和边都很少而且天然支持后续的 DFA 转换。rea 的 NFA 数据结构很简单class NFA: def __init__(self): self.transitions [] # 每个元素是 [(label_or_None, target_state)] self.start 0 self.accept 0每个状态一个列表列表元素是 (边标签, 目标状态)。边标签要么是 None 表示 epsilon要么是一个字符区间集合对象匹配时判断当前字符是否在区间内。4.2 子集构造法从 NFA 到 DFANFA 匹配时可能同时在多个状态停留实际执行要么维护状态集合要么先把 NFA 转成 DFA。rea 选择的是后者。子集构造法分两步计算 epsilon 闭包从一个状态集合出发沿着所有 epsilon 边能到达的状态全收进来。计算 move对某个字符 c从当前闭包里所有状态出发走所有能匹配 c 的边得到目标状态集合再对目标集合求闭包。转换后的 DFA每个状态都是一个集合这个集合对应 NFA 的多个状态。所以 DFA 匹配时每次只需做一次查表速度可预测不会回溯。实际代码里我需要维护一个 map 把每个“集合”映射到新状态编号def to_dfa(nfa: NFA) - DFA: start_set epsilon_closure({nfa.start}) dfa_states [start_set] dfa_transitions [] unprocessed [0] while unprocessed: idx unprocessed.pop() current_set dfa_states[idx] trans {} for label in collect_labels_from(current_set): target_set epsilon_closure(move(current_set, label)) if target_set not in dfa_states: dfa_states.append(target_set) unprocessed.append(len(dfa_states) - 1) trans[label] dfa_states.index(target_set) dfa_transitions.append(trans) accept_states [i for i, s in enumerate(dfa_states) if nfa.accept in s] return DFA(dfa_transitions, 0, accept_states)这里有一个细节正则字符类往往包含多个字符我采取的不是逐个字符生成转移边而是以“区间集合”为转移标签。比如[a-z0-9]在 NFA 里就是一条边标签是 [(97,122),(48,57)]。这样 DFA 状态数不会因为字符集扩大而爆炸。4.3 捕获组与回溯模式的取舍理论上 DFA 只能回答“能否匹配”很难直接给出每个捕获组的起止位置。因为 DFA 合并了历史路径它不知道在某个状态时究竟是从哪个分组进来的。rea 的解决方案是双模式纯匹配模式走 DFA结果是一个布尔值适合做快速校验、过滤、分词。捕获组模式走 NFA 回溯记录每个捕获组的开始和结束位置。回到最开始设计时的目标rea 并不打算完全替代内置正则库所以这种取舍是故意的。用纯匹配模式处理高性能场景用回溯模式处理需要捕获组的场景两者共用同一个 NFA 和 AST代码复用度高行为也一致。5. 测试、性能验证与避坑经验5.1 测试用例设计思路我对 rea 的测试分四类基本匹配abc匹配abca.c匹配abc。空匹配与边界空正则匹配任意位置^a$匹配整行a。贪婪与懒惰a在aaa上匹配整个串a?只匹配第一个a。复杂嵌套(a|b)*c对aabac的匹配结果以及捕获组(a(b)c)的区间是否正确。测试框架我直接用 Python 自带的 unittest没引入额外依赖。关键是要把“预期结果”写得精确双模式都要断言。5.2 与内置正则模块的基准对比在同样条件下我把 rea 的 DFA 模式和 Python 内置正则模块做了对比。测试文本是 10 万字符的模拟日志表达式是ERROR [a-z] \d。实测结果大致如下引擎单次匹配耗时一万次匹配耗时极端回溯样本耗时rea DFA 模式约 0.4 ms约 3.8 ms3.2 ms内置正则模块约 0.2 ms约 2.1 ms无法在正常时间内完成DFA 模式在简单场景下比内置库慢主要是因为 Python 层模拟状态转移开销大但极端回溯样本下内置模块触发了灾难性回溯导致长时间无响应rea 的 DFA 却保持了稳定耗时。这也验证了 DFA 在“最坏情况性能可预测”上的优势。后来我做了个小优化把 DFA 转移表从 dict 换成数组形式的二维表匹配循环里少一层哈希查找整体性能提升了约 20%。如果再把匹配循环用 C 或 Rust 实现性能差距会进一步缩小。5.3 常见问题与排查技巧速查表我在开发过程中整理了这张避坑表基本覆盖了最容易翻车的点现象根本原因解决办法表达式识别错乱量词 token 和普通字符混淆在 lexer 阶段合并*?等组合 tokenAST 嵌套错误优先级处理不对严格按“或 连接 量词 原子”递归下降空分支丢失没处理空字符串分支用空 ConcatNode 表示空串DFA 状态爆炸字符类展开到单个字符用区间集合作为转移标签捕获组位置错NFA 边顺序和 epsilon 闭包计算不一致对比一个简单表达式的全流程输出匹配无限循环星号节点构造缺少新状态检查 Thompson 构造是否引入新的开始状态排查这些问题时我最高效的方法是“断点打印”。写一个dump_nfa(nfa)函数把每个状态的转移边打出来再手动走一遍表达式基本一眼就能看出状态连接哪里不对。最后再分享一个小技巧如果你也想照着 rea 的思路手写一个正则引擎我强烈建议先不要碰捕获组和反向引用。先把字符、连接、或、星号、加号这五种最基础的能力跑通再逐步加括号捕获和字符类。我早期试图一步到位同时支持所有特性结果 NFA 构造和 DFA 转换互相干扰定位问题花的时间比写代码还多很多。一步步来反而更快。