写代码的人几乎没有不碰正则的。一段 /ab*c/，或者更花哨的邮箱、手机号校验，往代码里一贴，好像就解决了字符串匹配问题。但绝大多数人对正则的理解，停留在"一种神奇的模式语法"——它从哪来、按下回车后引擎到底做了什么、为什么同样的写法有时候飞快、有时候却把 CPU 直接打满，很少有人追究。
Computerphile 频道里 Prof. Brailsford 那期《Regular Expressions》之所以值得看，恰恰在于它把正则从"工具语法"拉回了它的本源：一门有 70 年历史的形式语言。顺着这条线往下挖，你会发现一个被很多教程跳过的关键事实——正则不是被"逐字符扫描"匹配的，它先被编译成一台状态机。而正是这台状态机"怎么跑"，决定了你的正则是秒回，还是把整台服务器拖进指数级的深渊。2019 年 Cloudflare 那场波及半个互联网、持续约 27 分钟的全球级宕机，肇事的就是一行完全合法、谁也看不出毛病的正则。这篇文章就借这期视频，把正则引擎从"编译"到"爆炸"的完整链路拆给你看。
| 项目 | 内容 |
|---|---|
| 视频标题 | Regular Expressions（正则表达式） |
| 频道 | Computerphile（诺丁汉大学出品的计算机科学频道，订阅数百万） |
| 主讲 | Prof. David Brailsford（形式语言与文档检索方向学者） |
| 时长 | 约 14 分钟 |
| 播放量 | 约 27 万（截至检索时） |
| 核心主题 | 正则表达式的语法起源，以及它和形式语言、有限自动机的内在联系 |
很多人以为正则是程序员为了方便发明的"模式字符串"，其实它是一门正儿八经的数学语言。1956 年，美国数学家 Stephen Cole Kleene 发表论文《Representation of Events in Nerve Nets and Finite Automata》，用"正则集合（regular sets）"来描述有限自动机能够识别的事件类。你现在天天敲的那个 *（匹配零次或多次），名字就叫 Kleene star，正是以他命名。
所以在数学上，你写的每一行正则，本质上都是在描述一个正则语言（regular language）——一类能被有限状态机识别的字符串集合。在 Chomsky 文法层级里，它处于最底层的 Type-3，表达能力最弱，但也正因为弱，它才有"线性时间可判定"这种珍贵性质。Computerphile 这期视频最有价值的点，就是 Brailsford 没有把正则当成一组需要背诵的符号，而是从这条理论根基讲起，让你明白：正则不是魔法，而是一套被严格定义的语言。这一节是视频原话层面的核心立意。
理解了正则是一门语言，下一个关键认知就水到渠成：当你写 /ab*c/，引擎不是用肉眼去字符串里逐个字符找。它在匹配开始之前，会先做一次"编译"——把你写的文本模式，翻译成一台有限自动机（finite automaton），也就是一组状态和带条件的转移边。
这个"编译"思想的源头同样赫赫有名。1968 年，Unix 共同发明人、图灵奖得主、后来又设计了 Go 语言的 Ken Thompson，在《Communications of the ACM》上发表了正则搜索算法，给出第一套把正则高效编译成 NFA（非确定性有限自动机）并在文本里搜索的方案。这就是所谓的 Thompson 构造法（Thompson construction），他当时把它用进了 QED 文本编辑器——后来的 grep、sed、vi 里的正则，全是这条血脉的后代。
这一条延伸出一个非常实用的工程结论：正则存在"编译成本"。当你在一个循环里反复使用同一段正则时，应该预编译它——Python 的
re.compile()、Java 的Pattern.compile()都是这个道理。（本段为延伸分析，非视频原话）
编译出来的 NFA 有个特点：它在某个时刻可能"同时"处在好几个状态里（非确定性）。要在一段文本上真正跑起来，工程上有两条都能保证基本线性的路：
Russ Cox 在 2007 年那篇被奉为经典的《Regular Expression Matching Can Be Simple And Fast》里，实测对比了 Thompson NFA 引擎和当时主流的回溯引擎：前者面对再复杂的模式、再长的文本，耗时曲线都是一条平缓的直线；后者却画出一条陡峭得吓人的指数曲线。这恰恰是问题的分水岭——正则本来是可以很快的。
既然线性时间这么好，为什么不是所有引擎都用自动机？因为另一条路——回溯（backtracking）——实现起来简单得多，而且能做线性自动机做不到的事：反向引用（backreferences，如 \1）、前后查找（lookahead / lookbehind）、捕获组这些高级特性。
回溯的工作方式像走迷宫：遇到一个有多条岔路的状态，先走一条，走不通就退回来换另一条试。在简单的模式上，它和自动机几乎一样快。但麻烦出在嵌套量词上。当你写出 (a+)+、(a*)* 这类结构，再喂给它一长串 aaaaaa...（结尾恰好缺少该有的字符），引擎会去尝试 2ⁿ 种"这些 a 到底怎么分配给内外两层量词"的组合，而几乎所有组合最终都会失败。
于是本该瞬间完成的匹配，退化成了指数级的计算。这就是"灾难性回溯（catastrophic backtracking）"，业界更广为人知的名字叫 ReDoS——Regular expression Denial of Service（正则表达式拒绝服务）。注意，这条雷不是你写错了模式，模式本身完全合法、完全"正确"。
这不是教科书里的思想实验。2019 年 7 月 2 日，Cloudflare 用于 WAF（Web 应用防火墙）的一段正则表达式触发了灾难性回溯，导致全球大量网站——其中包括 Discord、Stripe 等知名服务——集体不可用约 27 分钟。肇事模式形如 (?:(?:\"|'|\]|\}|\\|\d|...)+)+，内层一堆"或"选项外面又套了一层 + 量词，在特定输入下完美踩中指数回溯，把 CPU 瞬间打满。
更要命的是，这段正则部署在每一个 HTTP 请求的关键路径上，于是单条规则的崩溃被瞬间放大成全网级事故。Cloudflare 事后专门发布技术复盘，并很快上线了自动检测危险正则的工具。除此之外，Stack Exchange 等大型平台历史上也踩过同类坑，CVE 漏洞数据库里登记的 ReDoS 条目数量可观，OWASP 已经把 ReDoS 正式列入需要关注的攻击面。
一句话点破这件事的荒诞：攻击者甚至不需要构造复杂 payload，只要发一段精心选择的普通文本，就能让你那行"用来防御的正则"反过来打死你自己。
这是个很自然的疑问。答案是：因为回溯引擎能做的事，线性自动机做不了。反向引用——也就是"把前面匹配到的内容，后面再拿出来用"——在数学上会让这门语言超出正则语言的范畴，纯 DFA 根本表达不了。为了这些丰富特性，PCRE、Perl、Python re、Java、JavaScript、.NET 这些主流引擎，普遍选择了回溯（或带各种优化的回溯）。
反过来，Google 的 RE2、Rust 的 regex、Go 的 regexp 则故意把反向引用这类特性砍掉，换回线性时间的硬保证——它们基于 Thompson NFA / DFA，从设计上就不会 ReDoS。这是一条被刻意做出的工程取舍：功能 vs 安全。Rust 的 regex 文档里甚至明文写着自己拒绝支持反向引用，原因正是 ReDoS。（本段为延伸分析）
知道原理，防御就有了章法。几条可以落地的实践：
google-re2；JavaScript 有 RE2 的绑定。这是釜底抽薪。(x+)+、(x*)*、(.*a){n} 都是高危信号，code review 时应当重点关注。a++（possessive，占有量词）和 (?>...)（atomic group，原子分组），它们明确告诉引擎"这条岔路不回头"，能直接掐断指数级回溯。可惜 JavaScript 原生正则目前还不支持，PCRE / Java / .NET 支持。java.util.regex 支持带超时的匹配，RE2 系天然可控；把正则放在可中断的沙箱里跑，是最后一道闸。regex101 的 debugger、JS 生态的 safe-regex 等静态工具，能在部署前就识别出潜在的危险模式。flowchart TD
A["正则表达式 pattern"] -->|"编译"| B["NFA 有限自动机\nThompson 1968"]
B --> C{"执行引擎怎么跑"}
C -->|"路线A 自动机"| D["Thompson NFA / 子集构造 DFA"]
D --> E["匹配时间 O(n) 线性"]
E --> F["代表：RE2 / rust-regex / Go"]
C -->|"路线B 回溯"| G["递归回溯匹配"]
G --> H["最坏 O(2^n) 指数"]
H --> I["代表：PCRE / Python / Java / JS / Perl"]
I --> J["危险：ReDoS 灾难性回溯"]
J --> K["真实事故：Cloudflare 2019\n宕机约27分钟"]
L["工程防御"] --> M["换用 RE2 / rust-regex"]
L --> N["设超时 / 锚定 / 原子分组"]
L --> O["静态体检 safe-regex 等"]
J -.->|"靠这些消除"| L
看完这期视频再结合引擎原理，最该升级的一个认知是：写正则的时候，脑子里要装一台状态机。 你遇到的绝大多数正则性能问题，根子都不在"模式写得长不长"，而在"你对引擎工作模型的假设是错的"。
落到工程实践上，我建议团队做三件事。第一，把正则纳入 code review 的正式检查项，尤其是那些部署在请求热路径、处理用户输入的正则——它们和 SQL 语句一样，是会被攻击面利用的"代码"，必须可测试、可超时、可替换。第二，建立简单的选型决策树：只需要普通匹配（绝大多数场景）→ 一律上 RE2 系引擎；确实需要反向引用、复杂查找 → 用回溯引擎，但务必设超时并对输入长度做限制。第三，把"正则也会爆炸"写进新人文档，附上 (a+)+ 这类最经典的反面案例和一个本地复现脚本，让人亲眼看到一行"正确的正则"把进程卡死。
更深一层，这件事其实揭示了一个普遍的工程教训："能跑通"和"安全"是两回事。一个合法的正则、一段正确的 SQL、一个没报错的递归，都可能在边界输入下露出指数级的獠牙。养成"想一想最坏情况复杂度"的反射，比背再多语法都值。
正则不是魔法字符串，而是一台被编译出来的状态机；选错了引擎，一行"完全正确"的模式，就足以把整台服务器拖进指数级的泥潭。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
knowledge-card-pro 或 content-to-video 技能把"灾难性回溯的指数曲线"做成短视频卡片。[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。