企业官网建设流程全解析

自己动手写一个正则引擎，这事我一直觉得是每个写文本处理工具的工程师早晚会踩进去的坑。不是因为网上没有现成库，而是你在实际项目里一旦遇到灾难性回溯、诡异死循环、或者是那个“同一个正则，换一行日志就慢了一个数量级”的问题时，你会非常想搞明白正则背后的执行机制到底是什么样的。我去年在做一个日志清洗工具时就被这个问题折腾得不轻，后来干脆花了两周时间写了一款极简正则引擎，代号就叫 treg，全称是 tiny regex engine，基于 Thompson NFA 构造法和 Pike VM 状态模拟，主打线性时间匹配。这篇文章把这套设计、实现、踩坑过程完整梳理一遍，给那些想了解正则内部机制、或者自己也打算手搓一个解析器的朋友提供一个可以直接参考的样本。

1. 项目整体设计与功能边界

1.1 为什么手写正则引擎：一次日志清洗把我卡死

先交代背景。那是去年第四季度，我在做一个面向云服务器运维场景的日志分析组件，需要从海量访问日志里提取特定模式的请求路径、状态码、响应时间。日志行的样例大概长这样：

2024-11-18 09:12:33 [INFO] GET /api/v2/users/12345/orders?page=1&size=20 200 45ms

我需要按用户传来的自定义正则去过滤和抽取字段。一开始直接使用了某个常见语言自带的正则库，功能很齐全，写起来也顺手。但上了线上数据后发现一个问题：某些用户写的正则包含嵌套量词，比如(.*)*、(a+)+这种，在超长且不匹配的日志行上，匹配耗时会从几毫秒直接飙到几十秒，甚至把容器 CPU 打满。第一次看到监控告警时我还以为是谁在跑什么定时任务，查了半天才发现是正则在回溯。

这件事给我提了个醒：带回溯的正则引擎，最坏情况下会沿着所有可能的路径反复试探，输入长度一涨，耗时呈指数级增长。有些库虽然做了一些保护机制，比如回溯次数上限，但那是“止损”不是“解决”。我想做的 treg 从一开始就把目标定成：不使用回溯，而是把正则表达式编译成非确定有限自动机（NFA），再用状态集合的方式同时推进所有可能的路径，匹配复杂度和输入长度呈线性关系。

从设计理念来说，这更像是在“翻译”正则而不是“枚举”匹配路径。读到这里你大概能理解，我写的不是又一个功能最全的正则库，而是一个面向性能敏感场景、可嵌入、可观测的轻量引擎。它适合三类人：一类是正在被回溯型正则折磨的文本处理开发者，一类是想搞清楚(ab|cd)*这种正则到底怎么被机器执行的初学者，还有一类是准备动手做自己的 DSL 解析器、需要参考编译原理落地案例的工程师。

1.2 功能定界：treg 不打算什么都做

任何个人项目都要做功能减法。treg 第一版只支持常用语法子集，我明确把它写进了 README：

为什么不做反向引用？因为它会把原本的正则语言变成上下文相关文法，NFA 和 DFA 都表达不了，诱导出回溯是必然的。如果你确实需要(a|b)\1这种能力，那应该去用 PCRE 系或支持回溯的库，而不是要求一个线性时间引擎去做它做不到的事。

我还在第一版刻意砍掉了零宽断言、条件组、递归匹配这些高级能力。这不是技术障碍，而是这些功能会让编译器和匹配器的实现复杂度成倍上升，而且一旦引入，线性时间保证就很难维持。treg 的目标是“覆盖八成常见场景，同时让性能最坏情况可控”，而不是“用两万行代码重新实现一遍 Perl”。

1.3 正则语言与 NFA 的直觉

这里用大白话讲一下形式语言基础，不绕弯。所谓正则语言，就是能用有限状态自动机识别的字符串集合。你可以把 NFA 想象成一张有向图，节点是状态，边上的标签是字符或者空串 epsilon。一条路径上的标签连起来如果能覆盖整个输入字符串，说明匹配成功。

那为什么 NFA 模拟能做到线性时间？关键在于“同时维护多个可能状态”。想象你走迷宫找出口，回溯型引擎的做法是：先走左边这条死路，退回来，再走右边那条，如果中间有岔路就再递归试下去。NFA 的模拟则不同，它用一个集合记录当前所有可能到达的位置，每读一个字符，就把集合里每个状态能走的边都走一遍，生成下一个集合。这样无论迷宫里有多少条岔路，每读一个字符我们只处理一遍状态集合，而不是一遍一遍重复走。

代价也很明显：NFA 状态数量往往大于 DFA，所以单个字符的处理是“批量推进”而不是“单步确定”。但在工程上，一个几百个状态的 NFA 处理一行几 KB 的日志完全不是问题，换来的却是可预期的耗时曲线。这个取舍非常值。

2. 核心实现：从正则文本到可执行指令

2.1 递归下降解析：优先级是怎么处理的

写正则引擎的第一个关卡是解析器。正则表达式虽然短，但它有明确的优先级规则：|最低，连接次之，量词最高。我采用了最简单也最好调试的递归下降解析法，把语法分成三层：

alt -> concat ('|' concat)* concat -> repeat* repeat -> primary ('*' | '+' | '?' | '{' m ',' n '}')? primary -> char | '.' | '[' class ']' | '(' alt ')' | escape

这里有个经验：千万不要把所有逻辑堆到一个函数里。我第一版图省事，用一个parse_atom()硬扛了所有情况，结果量词嵌套和|分支的组合一多，树结构就乱了，后来重构成了三个函数才稳定下来。

核心节点长这样（C 实现）：

typedef enum { NODE_CHAR, NODE_DOT, NODE_CLASS, NODE_CONCAT, NODE_ALT, NODE_STAR, NODE_PLUS, NODE_QUEST, NODE_REPEAT, NODE_GROUP } NodeType; typedef struct Node { NodeType type; int c; // NODE_CHAR / NODE_CLASS 使用 int neg_class; // 是否取反 unsigned char class_bits[32]; // 128 字符位图 struct Node *left; struct Node *right; int m, n; // NODE_REPEAT 的 {m,n} } Node;

递归函数也不复杂，关键是parse_alt循环折叠出左结合的效果：

Node *parse_alt(Parser *p) { Node *node = parse_concat(p); while (peek(p) == '|') { advance(p); Node *rhs = parse_concat(p); Node *alt = new_node(NODE_ALT); alt->left = node; alt->right = rhs; node = alt; } return node; }

这个阶段很容易犯的一个错是忘记处理空分支。当用户写a|或(|b)时，解析器看到|后接右括号或结尾，应该生成一个匹配空串的节点，而不是报错。我一开始直接报“语法错误”，后来发现不少用户习惯性写(a|)表示“a 或空”，所以补上了 EPSILON 节点。

2.2 编译成 NFA 指令：把 AST 变成状态图

解析器产出 AST 之后，下一步是把它编译成一组顺序指令。我没有用传统的“状态对象 + 指针”表示 NFA，而是采用了类似 Pike VM 的指令数组方案。这样做的好处是内存紧凑、cache 友好，而且调试时可以像看汇编一样一条条核对。

指令类型定义：

typedef enum { INST_CHAR, // 匹配单个字符，前进一个 char INST_SPLIT, // 分叉：同时把两个目标地址加入当前状态集 INST_JMP, // 无条件跳转 INST_SAVE, // 记录字符串下标到槽位，用于捕获组 INST_MATCH // 匹配成功 } InstType; typedef struct { InstType type; int c; // INST_CHAR 的字符 int x, y; // 分支目标的指令下标 int slot; // INST_SAVE 槽位 } Inst;

Thompson 构造法有几个核心模式，我记得非常清楚：

• 单字符a：生成INST_CHAR('a')，后面紧跟父节点拼接的后续指令。
• 连接e1 e2：先编译e1，再紧接着编译e2，中间不需要额外跳转。
• 分支e1|e2：生成INST_SPLIT，两条分支分别指向e1和e2的入口，分支结束之后回到同一个汇合点。
• 星号e*：生成INST_SPLIT，一条路径跳过整个e直接到汇合点，另一条路径进入e，e结束之后用INST_JMP跳回INST_SPLIT。

这些模式的实现代码不长，但有个细节值得注意：星号循环的跳转回边在拼接时容易产生悬空前向引用。我的解决方案是先记录占位下标，等编译完整个单元后再 backpatch。你写的时候不妨也这么做，别试图在编译过程中动态“修正”指令序列，那样容易越改越乱。

2.3 Pike VM 匹配循环：为什么它是线性的

指令编排好了，匹配器就很简单了。传统回溯是递归地尝试一条路径，失败后回退。Pike VM 则维护两个状态列表：当前状态集cur和下一状态集next。每读入输入字符串的一个字符，就把cur中所有指令逐个执行一遍，把所有可能到达的下一个指令位置放进next，然后交换两个列表。

伪代码如下：

static void add_state(List *l, int pc, Programs *p, int *visited) { if (visited[pc]) return; visited[pc] = 1; Inst *ins = &p->code[pc]; switch (ins->type) { case INST_SPLIT: add_state(l, ins->x, p, visited); add_state(l, ins->y, p, visited); break; case INST_JMP: add_state(l, ins->x, p, visited); break; default: append(l, pc); break; } } int vm_match(Programs *p, const char *s) { List *cur = new_list(), *next = new_list(); add_state(cur, 0, p, init_visited(p)); for (int i = 0; s[i] != '\0'; i++) { for (int j = 0; j < cur->len; j++) { Inst *ins = &p->code[cur->items[j]]; if (ins->type == INST_CHAR && ins->c == (unsigned char)s[i]) { add_state(next, cur->items[j] + 1, p, visited); } } swap(cur, next); clear(next); reset_visited(p); } int matched = 0; for (int j = 0; j < cur->len; j++) { if (p->code[cur->items[j]].type == INST_MATCH) matched = 1; } return matched; }

加visited数组是关键中的关键。如果没有它，a*这种带 epsilon 回边的指令会让同一个状态无穷无尽地加入列表，导致死循环。有了 visited 数组，每个指令在每个输入字符位置至多进入状态集一次，整个匹配循环的复杂度就是O(字符串长度 * 指令总数)，完全可控。

贪婪和懒惰量词在这里也有一个很优雅的实现方式：INST_SPLIT的两个分支谁先被add_state谁就有“优先权”。比如a*的 split 先加“回边进入a再循环”的分支，就会自动倾向于贪婪；反过来先加“跳过整个循环”的分支，就会倾向于懒惰。不用额外写任何特殊逻辑，排序即语义。

3. 实操过程与性能优化记录

3.1 跑通第一个用例的完整过程

treg 的编码过程我用了 C11，没有依赖第三方库，编译器用的 GCC 和 Clang 各测过一遍。项目结构保持得很简单，只有四个文件：

src/ parser.c // 递归下降解析，产出 AST compile.c // AST -> 指令数组 vm.c // Pike VM 匹配 treg.h // 对外 API

第一个用例我印象很深，就是匹配(ab|cd)*ef在字符串abcdabef上的结果。一开始编译出来的指令顺序经常错乱，尤其是分支汇合点，总是少一个JMP或者多一个JMP。我写了调试辅助函数，把指令数组逐条打印出来：

$ ./treg --dump '(ab|cd)*ef' 0: split 1, 3 1: char 'a' 2: jmp 5 3: char 'c' 4: jmp 5 5: split 6, 0 6: char 'e' 7: char 'f' 8: match

看到这份 dump 我立刻明白了问题：星号的回边指向0，但split 6, 0的分支顺序反了，导致先进入ef后回溯再尝试ab|cd，虽然最终结果没错，但优先级语义不对。后来我定了一条规律：在所有 Thompson 模式里，INST_SPLIT的x分支永远是对应“贪婪/继续循环”的那一侧，y永远对应“跳过/退出”的那一侧，这样写不会乱。

3.2 对比实测：同一批日志、两种引擎

功能跑通之后，我做的第一件正经事就是拿真实数据做回归对比。测试环境是一台普通的 4 核虚拟机，Ubuntu 22.04，输入是 10 万行模拟日志，总大小约 40MB。

测试用两组正则，一组是常规但略带回溯压力的模式，另一组是典型的嵌套量词：

第一组结果说明，普通场景下两种引擎差距不明显。第二组和第三组的差距才是重点：回溯引擎彻底被嵌套量词的指数爆炸拖垮，而 treg 因为压根不回溯，耗时就只是线性扫描。数据测出来那一刻，我基本确定这个方向是值得做下去的。

3.3 性能优化的三个关键点

做完第一版之后，我顺手做了三轮优化，每一轮都有可量化的收益。

第一轮是给add_state加 visited 数组并在每次字符循环前重置。这个不做功能也能跑，但状态集里会出现大量重复项，a*这种模式直接导致状态集膨胀十几倍。加上之后，匹配开销从“每个字符处理数百项”降到“每个字符处理十几项”，耗时大约是原来的五分之一。

第二轮是字符类预计算。一开始每遇到一个INST_CHAR就调用一次is_in_class()函数，里面再做区间判断。后来我把字符类预先展开成一张 128 字节的位图，char 指令直接查表：

if (ins->type == INST_CHAR && ins->char_mask[(unsigned char)s[i]]) { add_state(next, pc + 1); }

实测整体性能提升了 15%-20%。这个优化意义不大，但代码干净了不少。

第三轮是编译结果缓存。treg 的 API 设计成“编译一次，匹配多次”，把treg_compile()的结果存到结构体里重复使用，避免每次匹配都重新解析和构建 NFA。这个优化对数据库过滤、路由匹配这种“同一正则跑海量文本”的场景收益最明显，直接省掉了整个编译阶段的时间。

4. 常见问题与避坑实录

4.1 捕获组实现细节：后悔没一开始就做

我一开始为了追求“核心能跑”，把捕获组砍掉了，只保留(?:...)不捕获分组的解析。后来要用treg_capture()提取users/(\d+)里的 ID 时，才发现要补这个功能得动匹配器。

最终方案是在指令里加INST_SAVE，用在捕获组开始和结束时记录当前字符串指针位置。匹配完成后，槽位里就是捕获子串的起止下标。实现起来不复杂，但有一个明显代价：SAVE是带副作用的指令，同一个指令在同一位置只能写一次槽位，而 NFA 模拟过程中可能会有多个路径同时到达同一个SAVE，导致槽位被后写覆盖，拿到的捕获值不一定对应最终成功的路径。

解决思路是给每个INST_SAVE追加一个“路径标识”判断，只有同一条路径的写入才覆盖。这个方案虽不完美，但对大多数使用场景足够了。我的建议是，如果你的项目一开始就需要捕获组，别拖，第一版就把它设计进去。后补的代价是在状态模拟逻辑里到处加条件判断，远比一开始就让SAVE成为一等公民麻烦。

4.2 解析器的优先级与空匹配陷阱

递归下降解析器虽然直观，但有两个坑我记忆犹新。

第一个坑是parse_concat的终止条件。正则表达式里连接是隐式的，没有显式运算符，所以很容易写出无限吞字符的解析器。我的经验是：每个函数只消费自己职责范围内的 token，遇到)、|或字符串结尾就立即返回，不要越俎代庖。

第二个坑是空匹配死循环。在 NFA 模拟中，像a*这样的模式完全可能在某个输入位置匹配空串。如果正则整体是(a*)*且输入字符串里有一段连续的a被消耗完之后，外层循环还能再次进入空匹配，当前输入位置不前进，就会反复应用同一组状态。我在匹配循环里做了一个检测：如果某一轮只有 epsilon 类指令在推进，而没有任何INST_CHAR消费输入字符，就强制结束这一轮，避免原地打转。这在理论上不是最优解，但实际使用中能挡住绝大多数因用户写了诡异正则而导致的死循环。

4.3 常见问题速查表

4.4 用 fuzz 测试补课

代码写到后期，我意识到光是手写的单元测试覆盖不了所有组合情况，于是上了简单的 fuzz 测试：随机生成一批长度为 1 到 8 的字符串，再随机生成由abc|*+?()[]构成的表达式，把 treg 的匹配结果与一个参考实现（我用了系统中已有的另一套库）做对比。这个 fuzz 跑了两百万次，找出了十几个边界 bug，其中最有价值的是一个字符类取反逻辑错误：[^a]在第一版里居然还能匹配 EOF 空串，原因是我给字符类补了默认匹配项。这也是为什么我推荐任何想自研正则引擎的人都搞一遍 fuzz 测试，靠人脑穷举是不可能的。

5. 写在后面：我的一些体会

代码写到这里，treg 已经能完成我的日志清洗需求了：编译一次，反复在百万行日志里做字段提取，最坏情况耗时可控，线上再没出现过正则拖垮进程的告警。回看整个项目，我最深的体会是：写正则引擎最难的不是算法，而是边界。普通匹配、量词、字符类、分支，每块功能单独拿出来都很简单，但一旦组合起来，空串、惰性量词、嵌套分组、取反字符类这些边缘情况都会伺机而出。建议你动手做之前先定好“支持什么、明确定性报错不支持什么”，再配一个能自动构造上万条用例的 fuzz 工具，比什么都管用。如果你也想做类似项目，我把推荐路线总结成一句话：先用 Pike VM 跑通核心循环，再去碰捕获组和高级断言。顺序反了，你会被无穷无尽的边缘 case 淹没。