正则表达式

注册表单里检查邮箱格式的那行校验、IDE 里按下 Ctrl+Shift+F 的全局搜索、运维在几十 GB 日志里捞出某个错误码的那条 grep——它们背后是同一个工具：正则表达式。

正则表达式是一种用紧凑的符号描述"一类字符串"的语言。比如 \d{4}-\d{2}-\d{2} 描述所有"四位数字-两位数字-两位数字"形状的字符串。它可能是编程世界里投入产出比最高的一项技术：学会几十个符号，就拥有了一把处理文本的瑞士军刀。

但很少有人意识到，这个日常工具直接连接着计算理论最深的一层地基，而且你平时用的那个"正则"，和教科书里的"正则"已经不是一回事了。

破除误解：你用的"正则"大多不是正则#

两个流传最广的误解，恰好方向相反。

误解一：正则表达式就是正则语言。 名字确实来自形式语言理论——正则表达式描述的恰好是正则语言，即能被有限自动机识别的字符串集合（详见 自动机与形式语言）。但 Perl 一系的引擎陆续加入了反向引用、环视等特性，表达力早已超出正则语言，甚至超出上下文无关语言。今天的"正则"是一个历史名称，不是能力描述。

误解二：正则匹配天然很慢。 理论上恰恰相反——用有限自动机做正则匹配，每个输入字符只需常数到线性的工作量，整个匹配是 $O(mn)$（m 为正则长度，n 为文本长度），不存在"坏输入"。慢的是另一类实现策略：回溯。主流语言之所以普遍偏慢，是因为它们选择了回溯，而选择回溯又是因为要支持误解一里那些超正则的特性。

这两个误解解开之后，正则表达式的全部故事——历史、实现、性能灾难、现代救药——就都有了一条清晰的线索：表达力与匹配效率之间长达半个世纪的权衡。

从神经网到 grep：理论与工程的接力#

克莱尼：为神经元写的记号（1951–1956）#

正则表达式的数学起源不在文本处理，而在神经科学模型。1951 年，逻辑学家斯蒂芬·克莱尼（Stephen C. Kleene）在兰德公司的一份研究备忘录中，试图精确刻画麦卡洛克-皮茨神经元网络（一种早期神经网络模型）能表示哪些"事件"。他设计了一套代数记号：从单个符号出发，只用三种运算——连接（先 a 后 b）、选择（a 或 b）、重复（a 重复任意次，即后来以他命名的克莱尼星号 *）——构造出的所有字符串集合，他称之为正则事件。

这篇工作正式发表于 1956 年，收录在香农（Claude Shannon）和麦卡锡（John McCarthy）主编的论文集《自动机研究》（Automata Studies）中。克莱尼在文中证明的核心结果后来被称为克莱尼定理：正则事件恰好就是有限自动机能识别的语言。记号系统与计算模型完全等价——你写的每个正则表达式，都对应一台具体的、状态有限的机器。这个等价是整个正则工程的理论基石。

汤普森：把定理变成编辑器功能（1968）#

理论在论文集里躺了十几年，直到肯·汤普森（Ken Thompson）把它变成程序。汤普森先是在 CTSS 分时系统的 QED 编辑器里加入了基于正则表达式的搜索；1968 年 6 月，他在 Communications of the ACM 上发表了四页论文《正则表达式搜索算法》（Regular Expression Search Algorithm，CACM 11(6): 419–422），给出了完整的实现——用 IBM 7094 汇编写的。

这篇论文的方法后来被称为汤普森构造：把正则表达式编译成一台非确定性有限自动机（NFA），然后模拟这台 NFA 去扫描文本。每个正则算子对应一小块标准的自动机"零件"，像乐高一样拼接，零件数与正则长度成正比。它与回溯完全不同的模拟方式，是本文后半部分的全部戏肉。

grep：一夜写成的工具（1973）#

1973 年，贝尔实验室的道格·麦基尔罗伊（Doug McIlroy）正在做一个语音合成项目，需要在词典文本里查找满足特定模式的词。他后来回忆：一天下午他问汤普森能不能把编辑器里的正则识别器抽出来做成一个独立程序，汤普森答应了；第二天早上，他的信箱里就多了一个叫 grep 的新程序。

这个奇怪的名字来自行编辑器 ed 的命令 g/re/p——global（全局）匹配一个 regular expression（正则表达式）并 print（打印）。grep 随第四版 Unix 面世，很快成为 Unix 工具哲学的样板：做一件事，做好，不对输入格式做多余假设。此后阿尔·阿霍（Alfred Aho）在贝尔实验室写的 egrep 走了另一条实现路线（惰性 DFA，下文详述），正则工具链在 Unix 生态里站稳了脚跟。

Perl 与 PCRE：表达力的胜利（1987–1997）#

1987 年 12 月，拉里·沃尔（Larry Wall）发布了 Perl 1.0。Perl 把正则表达式做成语言的一等公民，并在汤普森的纯正则核心之上不断添加新特性：反向引用（\1 引用前面捕获的内容）、环视（(?=...) 前瞻断言）、非贪婪量词等。这些特性极其实用，但它们大多数无法用有限自动机实现——Perl 选择了回溯式引擎，也就埋下了性能隐患。

1997 年，菲利普·黑兹尔（Philip Hazel）发布 PCRE（Perl Compatible Regular Expressions），把 Perl 的正则方言封装成一个 C 库。PHP、Apache 以及无数其他软件随后接入，"Perl 风格"就此成为事实标准。今天大多数程序员学的就是这门口径统一的方言——连同它的回溯基因。

理论内核：三个算子如何长成一台机器#

正则表达式的表达力全部来自三个构造算子。给定两个正则表达式 $R$、$S$：

• 连接 $RS$：先匹配 $R$，再匹配 $S$
• 选择 $R|S$：匹配 $R$ 或匹配 $S$
• 星号 $R^*$：$R$ 重复零次或任意多次

加上单个字符和空串作为底座，反复嵌套这三个算子，就得到所有正则表达式。\d{4} 只是 \d\d\d\d 的语法糖，\d+ 是 \d\d* 的语法糖。

汤普森构造的巧妙在于：每个算子都对应一个标准的 NFA 拼装手法。单字符是一条边；连接是把前一台自动机的出口接到后一台的入口；选择是加一个新的分叉起点，两条 ε 边（不消耗字符的转移）分别通向两台子自动机；星号是一个允许绕圈的回环。因为每个算子只增加常数个状态，长度为 m 的正则编译出的 NFA 只有 $O(m)$ 个状态——自动机的大小与模式成正比，与文本无关。

克莱尼定理保证：这台 NFA 识别的语言，与正则表达式描述的语言分毫不差。理论侧的完整证明与正则语言的代数性质（泵引理、闭包性质），见 自动机与形式语言，本文不再重复，只取工程需要的那一块。

两种实现，一道性能鸿沟#

同样是"拿 NFA 去匹配文本"，两条路线的行为天差地别。

路线一：自动机并发模拟（汤普森式）#

NFA 的"非确定性"意味着同一时刻它可能处于多个状态。模拟的办法不是猜测，而是全部跟踪：维护一个"当前活跃状态集合"，每读入一个字符，把集合里每个状态沿对应字符的边推进一步，取并集得到新集合。文本读完时，集合里若有接受状态，则匹配成功。

关键分析：NFA 只有 $O(m)$ 个状态，所以每读一个字符最多处理 $O(m)$ 次转移，整个匹配是 $O(mn)$ 时间、$O(m)$ 空间。这个上界对任何输入都成立——不存在能让它变慢的"坏文本"，因为它从不试探、从不回头。

更快的变体是先把 NFA 确定化成 DFA：匹配时每读一个字符只做一次查表，$O(1)$。代价是子集构造在最坏情况下会产生多达 $2^m$ 个 DFA 状态。阿霍在 egrep 里用了折中方案——惰性 DFA：DFA 状态不预先全部展开，而是匹配中用到哪个才算哪个，并缓存复用。实践中出现的 DFA 状态远少于理论上限，于是既有接近 DFA 的速度，又躲开了指数爆炸的内存。

路线二：回溯（Perl/PCRE 式）#

回溯引擎像走迷宫：遇到分支就先走一条，在岔路口放一根"记忆线"；走不通就退回最近的岔路口，换一条再试。实现上就是深度优先搜索加选择点栈。

这个策略本身不算坏，且它能直接支持反向引用这类超正则特性——\1 要求记住之前捕获的子串，这超出了有限自动机的记忆能力，但对"边走边记"的回溯来说很自然。这正是 Perl 当年选择回溯的根本原因：先有特性，后选实现。

问题在于，回溯的运行时间取决于它要试探多少条路径，而路径数可以对输入长度呈指数增长。经典例子：用 ^(a+)+$ 去匹配字符串 "aaaa...aaaaX"（n 个 a 跟一个 X）。外层 + 的每一轮可以把连续的 a 任意切成若干段分给内层 a+——n 个 a 有 $2^{n-1}$ 种切法，回溯引擎在最终失败前会把它们几乎全部试一遍。n = 30 时是约 5 亿条路径，n = 60 时已经超过了可等待的宇宙尺度。

这就是灾难性回溯（catastrophic backtracking）。攻击者只要向使用回溯引擎的服务提交一个精心构造的输入，就能让 CPU 在一条正则上烧掉——这类攻击叫 ReDoS（Regular Expression Denial of Service，正则表达式拒绝服务）。它不是纸上谈兵：2019 年 7 月，Cloudflare 因一条 WAF 规则中的正则触发灾难性回溯，CPU 被打满，全球服务中断了约 27 分钟；2018 年 ESEC/FSE 会议上，James Davis 等人的大规模生态研究表明，ReDoS 漏洞在主流包生态中广泛存在且影响真实。

对比一览#

现代工程的回答：RE2 与线性时间保证#

2007 年，谷歌工程师拉斯·考克斯（Russ Cox）发表了一篇影响深远的文章《正则表达式匹配可以既简单又快速》（Regular Expression Matching Can Be Simple And Fast），副标题毫不客气："但在 Java、Perl、PHP、Python、Ruby 里都很慢"。他把汤普森 1968 年的方法重新讲了一遍，并用基准测试证明：四十年前的教科书方法比所有主流语言的引擎都快几个数量级，且没有最坏情况。

2010 年，考克斯主导的开源库 RE2 随这篇文章的第三篇发布。它的设计决策是一条清晰的原则：凡是自动机模型表达不了的特性，一概不支持。反向引用、环视全部被排除，换来的是硬保证——任何正则、任何输入，匹配时间都是 $O(mn)$，内存有界。RE2 被用于谷歌代码搜索等对不可信输入做匹配的场景，Go 语言的 regexp 包也采用了同样的设计与语法。网安领域的高性能匹配库 Hyperscan（英特尔，NSDI 2019）则把同一思路推向多模式：用 SIMD 指令同时对数万个模式做自动机匹配。

代价是真实的：写惯了 Perl 方言的人会发现有些"正则"在 RE2 里根本编译不过。但这正是这笔交易的意义——把表达力降回正则语言，买回可证明的性能。而经验表明，反向引用在实际正则中的使用频率远比直觉低，绝大多数用途并不需要它。

Unicode 时代：`\w` 到底是什么#

ASCII 时代一切简单：\w 就是 [A-Za-z0-9_]，62 个字符，一张小表。Unicode 时代，同一个 \w 变成了对字符属性数据库的查询——它要涵盖全世界上百种文字的字母与数字。Unicode 联盟的技术标准 UTS #18《Unicode Regular Expressions》专门规定了正则引擎的 Unicode 支持，分三个一致性级别：从基本的字符属性（\p{Greek} 匹配希腊字母），到字形簇与默认大小写折叠，再到本地化排序与上下文匹配。

复杂性藏在"字符"的定义里：

• 码点不等于用户眼中的字符。字母 é 可以是单个码点 U+00E9，也可以是 e（U+0065）加组合尖音符（U+0301）两个码点。. 匹配一个码点，于是 ^.+$ 眼里的长度和用户看到的字符数可能对不上。
• 规范化是前置步骤。同一文本存在多种等价编码（NFC/NFD），匹配前不做规范化，字节级相等的判断会把"相同的字符串"判成不同。
• 大小写不是一对一。希腊字母 σ 在词尾写成 ς，两个码点；大小写折叠规则随语言而异，德语 ß 的大写是 SS——一个字符变两个。

这些不是边角料，而是多语言文本处理的日常。今天的正则引擎本质上运行在 Unicode 数据库之上，"查表"的开销与正确性要求都比 ASCII 时代高了一个量级。

什么时候不该用正则#

2009 年，Stack Overflow 上有人问"如何用正则匹配 XHTML 标签"，用户 bobince 的回答成了编程圈最著名的咆哮体模因："你不能用正则解析 HTML"——混沌降临、灵魂污染那段。笑声背后是一个精确的技术陈述，值得拆开说清。

准确的那一半：正则语言无法匹配任意深度的嵌套结构。直觉来自泵引理：有限自动机只有有限个状态，记不住"已经开了几层 <div>"——计数需要无界记忆（一个栈），那已经是上下文无关语言（2 型）的地盘。HTML、JSON、算术表达式都是嵌套结构，用纯正则去"解析"它们，总会在某个深度上失败。

常被忽略的那一半：很多人反驳"现代正则明明能匹配嵌套"——他们也对。Perl/PCRE 的递归模式、反向引用早已超出正则语言：反向引用能识别 $a^n b a^n b a^n$ 这样的语言，它甚至不是上下文无关的。模因争论的双方常常在谈论两种不同的"正则"——理论的正则与工程的正则。

真正实用的分工是这样：提取用正则，解析用解析器。在杂乱的半结构化文本里捞一次性模式（日志、一次性数据清洗、简单的输入校验），正则是最佳工具；一旦输入是有严格语法的结构（HTML、JSON、源代码），就该用对应的解析器——它们为嵌套而生，报错信息也可读。如果只是找固定字符串，杀鸡不用宰牛刀：字符串匹配里的 KMP、Boyer-Moore 更快更简单。最后一条经验法则：永远不要手写邮箱校验正则去严格实现 RFC 5322——真实的邮件地址语法远比直觉复杂，那是一份需要专门文法才能覆盖的规范，弱校验加确认邮件才是正解。

跨域连接#

• 自动机与形式语言：正则表达式与有限自动机的等价正是克莱尼定理的内容，本文讲的是同一事实的工程一面。把模式编译成自动机，匹配代价就只随文本长度线性增长；一旦引擎为反向引用放弃自动机模型，这个保证也随之失去——理论层与实现层的这道裂缝，是正则全部性能争议的根源。
• 字符串匹配：固定字符串匹配是正则的退化情形——没有分支与重复，自动机退化成一条链。KMP 的失败函数本质上就是把单一模式编译成自动机，让文本指针永不回退；把"为每个模式造一台机器"推广到"为一整个模式族造一台机器"，就得到了通用正则引擎。
• 形式文法与乔姆斯基谱系：能否匹配任意深度的嵌套，正是 3 型与 2 型语言的分界线。有限自动机没有栈，记不住未闭合的层数；给匹配器加上记忆，它就爬上了谱系，同时失去有限状态带来的线性时间保证。"能否用正则解析 HTML"的争论，本质是这条分界线的通俗版本。
• Unicode 与数字书写：字符类在 Unicode 时代从一张小表变成对字符属性数据库的查询。规范化形式不同而视觉相同的字符串，会让码点级匹配漏掉"相同"的文本——于是先做规范化、再做匹配，成为多语言文本处理不可省略的前置步骤。
• 防火墙与网络安全：WAF 与入侵检测常用正则描述攻击特征，但回溯引擎让检测器自身成为攻击面。精心构造的输入可以触发指数级回溯，把过滤设备拖垮成拒绝服务，这正是 ReDoS 的攻击机制——线性时间引擎在安全场景被优先采用，原因不在速度而在最坏情况可证明。

参考文献#

• Kleene, S. C. Representation of Events in Nerve Nets and Finite Automata. 收录于 Shannon & McCarthy 编 Automata Studies（Annals of Mathematics Studies 34），Princeton University Press, 1956, pp. 3–41.（正则表达式的数学起源与克莱尼定理）
• Thompson, K. Programming Techniques: Regular Expression Search Algorithm. Communications of the ACM 11(6): 419–422, 1968. DOI: 10.1145/363347.363387.（汤普森构造的原始论文）
• Cox, R. Regular Expression Matching Can Be Simple And Fast. swtch.com, 2007.（自动机路线与回溯路线的现代对比，RE2 的设计纲领）
• Davis, J. C., Coghlan, C. A., Servant, F. & Lee, D. The Impact of Regular Expression Denial of Service (ReDoS) in Practice: an Empirical Study at the Ecosystem Scale. ESEC/FSE 2018.（ReDoS 的大规模实证研究）
• Unicode Consortium. UTS #18: Unicode Regular Expressions.（Unicode 正则的一致性标准）
• McIlroy, M. D. A Research Unix Reader. AT&T Bell Laboratories Computing Science Technical Report 139, 1987.（grep 起源的当事人回忆）

延伸阅读#

• Friedl, J. E. F. Mastering Regular Expressions（3rd ed.）. O'Reilly, 2006.（回溯引擎行为最详尽的实操指南）
• Hopcroft, J. E., Motwani, R. & Ullman, J. D. Introduction to Automata Theory, Languages, and Computation（3rd ed.）. Pearson, 2007.（正则语言与自动机理论的标准教材）