打开编译原理教材的词法分析一章，你大概率会看到这样一行公式：letter(letter|digit)*。如果你之前写过一点正则表达式，肯定会有种熟悉的亲切感——这不就是正则嘛。但再往下翻，教材开始出现 ε、闭包、子集构造、NFA……数学味突然变重，很多同学就是在这里开始掉队。
这篇文章我把编译原理视角下的正则表达式和正则定义单独拎出来，一次讲透。内容包括它们的递归定义、运算优先级、正则定义的模块化思路、代数化简技巧，以及正则语言的能力边界。写给正在学编译原理、考前突击重新梳理、或者做词法分析实验写到一半发现自己模式写错了的同学。它不会教你把公式背下来，而是帮你在“背公式”和“真正理解”之间找到那条路。
1. 词法分析器的“主菜单”：正则表达式到底描述了什么
1.1 一种描述“语言的集合”的记号系统
在编译原理里学正则表达式，第一步要接受一个和平时写代码完全不同的视角：正则表达式描述的不是“某个字符串长什么样”，而是一个集合——所有能被它匹配出来的串组成的集合。这个集合在编译原理里有个专门的名字，叫语言。
这里面的三个基本概念绕不开。字母表∑是符号的有限集合，比如C语言词法分析用到的就是一个包含ASCII字符的字母表；串是字母表上符号的有限序列，比如abc、123；语言是串的集合，可以是有限的，也可以是无限的。正则表达式本质上就是一种用有限公式描述语言的记号。
举个例子，(0|1)*描述的就是所有由0和1组成的串，包括空串、0、1、01、1010……这是一个无限大的集合，但公式只有短短几个字符。这一点是正则表达式最厉害的地方：用极短的“程序”压缩描述无穷多个串。学这一章的时候，遇到任何表达式，第一反应都应该是“它描述了哪个集合”，而不是“它能匹配哪个字符串”。后者是编程思维，前者才是编译原理思维。
1.2 token、pattern、lexeme，三个词把词法分析串起来
词法分析器做的事，简单说就是拿着这些“语言描述”去扫描源代码，把一段段字符归类成有意义的词法单元。这里涉及三个术语，很多教材喜欢连着写：token、pattern、lexeme。我第一次读教材时，这三个词翻来覆去看不明白，后来用一个例子就全通了。
比如模式id → letter(letter|digit)*，它描述的是“标识符长什么样”；源代码里实际出现的count、x1、myVar，是匹配上这条模式的词素；而“标识符”这个类别，就是词法单元。换句话说，词法单元是抽象类别，模式是这一类别的描述规则，词素是源程序中真实落地的字符串。在教材里，“模式”这个词几乎可以和“正则表达式”互换使用。
搞清楚这三者的关系后，再看词法分析器的工作流程就顺畅多了：读入字符流，按模式判断当前位置能匹配哪个token，切出一个词素，输出一个token，继续往后扫。很多学校的编译原理实验用flex写一个简易词法分析器，本质上就是把这张“模式表”翻译成代码。
1.3 和JavaScript、Python里的正则有什么不一样
有同学会问：编译原理里的正则，和我用JS写表单校验时的正则有什么区别？这个问题问得特别好，也特别容易让人困惑。
教材里的正则被严格限定在三种基本运算以内：选择、连接、克林闭包，再允许用括号改变优先级。而日常编程里的正则还有\d、\w、+、?、{n,m}、捕获组、回溯引用等一大堆功能，这些其实是扩展正则，并不在教材定义的“正则表达式”范畴内。
为什么教材要把自己限制得这么“简陋”？因为只有这三种运算，才能保证每个表达式可以机械地转换成等价的有限自动机，也就是后续章节的NFA/DFA。一旦加入反向引用这类能力，匹配引擎的计算模型就会超出传统有限自动机的范围，没法用于词法分析器的自动生成。理解了这一点，就不会再抱怨教材写得晦涩了——它不是不会写花哨的语法，而是故意只保留最能讲清楚原理的一小块核心。
2. 从空串到闭包：正则表达式的递归定义与运算优先级
2.1 三条规则把整个体系递归起来
翻开任何一本编译原理教材，正则表达式的定义几乎都是递归的。给定字母表∑后，通常这样定义：
- ε是正则表达式，表示语言{ε}；
- 对∑中任意符号a，a是正则表达式，表示语言{a}；
- 如果r和s是正则表达式，那么
r|s、rs、r*、(r)也都是正则表达式，分别表示L(r)∪L(s)、L(r)L(s)、L(r)*、L(r)。
这个定义看起来平淡，信息量其实很大。它从“空串”和“单个符号”这两个原子出发，用三种组合运算拼出所有可能的模式。我学的时候觉得它像乐高：两个基础零件加三种接口，就能拼出无穷多模型。
三种运算各自对应什么语言，整理成一张表方便对照：
| 表达式 | 表示的语言 | 直观理解 |
|---|---|---|
| ε | {ε} | 空串，长度为零的串 |
| a | {a} | 只有单符号a |
| r|s | L(r)∪L(s) | 二者选其一 |
| rs | L(r)L(s) | 先匹配r串，再匹配s串 |
| r* | L(r)* | r的串重复0次或多次 |
注意这里的L(r)L(s)表示连接，也就是把任意一个来自L(r)的串和任意一个来自L(s)的串拼接起来。闭包的定义则约定L(r)* = L(r)⁰ ∪ L(r)¹ ∪ L(r)² ∪ ...，其中任意语言的0次幂都是{ε}。
2.2 连接的“乘法直觉”与闭包的“重复直觉”
如果让我用一个比喻讲这三种运算，我倾向于说：|是加法，连接是乘法，*是任意次幂。|对应集合的并，连接对应串的拼接，闭包对应拼接操作的任意次迭代。
看一个具体例子就清楚了。设 r = a|b，s = c，那么rs = (a|b)c，展开得到{ac, bc}。因为并运算在括号范围内先选一种，然后整体再和c拼接。再看(a|b)*，它能接收空串、单个a或b、以及任意长度的排列组合，比如ab、ba、abba……几乎所有只有a和b组成的串都可以。
特别容易混淆的是(a|b)*和a*b*。前者是a和b任意排列的串；后者必须是先若干a、再若干b，也就是形如a的m次方接b的n次方。拿字符串ba举例：ba属于(a|b)*，但不属于a*b*，因为b出现在了a前面。用具体字符串验证两个表达式是否有差异，是后面判断等价时最好用的方法。
2.3 优先级：闭包最高，连接次之，选择最低
优先级本质上决定了表达式在不加括号时怎么解析。规定是：闭包最高，连接次之，选择最低，和四则运算里“先乘除后加减”是一个道理。
比如a|bc，默认解析为a|(bc)，而不是(a|b)c。再如ab*，是a后面跟任意个b，不是a和b交替重复。所以a、abb都是ab*能匹配的，而abab不属于。作业里经常有“展开表达式”的题，其实就是在考括号归属。
顺带提一下结合性：并和连接都满足结合律，所以a|b|c怎么加括号，结果都一样；rst也一样。但连接不满足交换律，ab和ba是两个不同的语言，这一点到第四章讲化简时会反复用到。
2.4 ε和∅：两个特别容易翻车的小概念
如果说前面还算顺畅，那 ε 和 ∅ 绝对是把一批人绊倒的地方。ε 表示空串，也就是长度为零的串；∅ 表示空语言，是“一个串都不存在”的集合。人话比较：ε 是“手里攥着一个空袋子”，∅ 是“连袋子都没有”。
由此推出一组运算性质，考试超爱考：
- ε是连接的单位元：
εr = rε = r。 - ∅是连接的零元：
∅r = r∅ = ∅。 - 并运算里，∅是单位元：
r|∅ = r。 - 最骗人的一个：
∅* = {ε}。因为闭包允许重复0次，任何语言重复0次得到的都是空串，所以空集也不例外。
我第一次看到∅* = {ε}时觉得像鬼打墙，后来想通了：L* = L⁰ ∪ L¹ ∪ ……，其中L⁰约定就是{ε}，所以即使集合是空的，它“一次都不重复”仍然产生空串。这些细节对后续理解NFA的ε转移特别重要——ε转移表示不消费任何输入就跳转，是整个子集构造法的基础。
3. 正则定义：把复杂模式拆成可复用的零件
3.1 定义语法，以及“只能向前引用”的约束
正则表达式做到一半，问题就来了：真实语言的token模式往往很长，比如C语言无符号数，直接写成一串会非常难看，也不好维护。于是教材引入了正则定义，它本质上是一组带名字的宏定义。
格式是：
d1 → r1 d2 → r2 ... dn → rn其中每个di是一个新名字，ri只能使用字母表上的基础符号，以及前面已经定义过的d1到d(i-1)。不允许引用自己，也不允许引用还没定义的后续名字，否则会出现循环依赖。这个限制保证了每个名字都能被逐步展开成一个只含基础符号的普通正则表达式，不引入新的计算能力，只是让表达式更可读。我当时把这个理解成程序里的模块化：先把最底层的零件定义好，再往上层拼出标识符、数字常量，关系像一张有向无环的依赖图。
3.2 教科书三大经典：标识符、无符号数、实数
直接上最经典的例子。标识符的定义几乎是必考：
letter → A|B|...|Z|a|b|...|z|_ digit → 0|1|...|9 id → letter(letter|digit)*展开之后，id就是先一个letter、再任意个letter或digit交替重复的模式。这个定义唯一要注意的是letter必须先定义，因为id引用了它。
无符号数稍微复杂一点。这是几乎所有编译原理教材都会出现的经典正则定义：
digit → 0|1|...|9 digits → digit digit* optional_fraction → . digits | ε optional_exponent → E(+|-|ε) digits | ε num → digits optional_fraction optional_exponent这个定义好在哪？它把可选项和主结构分离了。读源码时看到3.14E-5，用定义一套就能解释：digits匹配3，optional_fraction匹配.14，optional_exponent匹配E-5。考试如果让写实数或无符号数的定义，背下这个结构基本就稳了，但更关键的是理解每一步为什么这样拆：主体、可选小数、可选指数三层，各管各的。
3.3 flex实验里，其实就在用正则定义
实验课用flex写词法分析器时，你很快会发现它和教材的正则定义惊人地一致。你可以在flex源文件里这样写：
digit [0-9] letter [a-zA-Z_] id {letter}({letter}|{digit})* num {digit}+(\.{digit}+)?([Ee][+-]?{digit}+)?这里的大括号{letter}就是对前面定义名字的引用，语法不同，思想完全一样。我第一次写完跑起来还挺感慨：教材里的理论，居然在工具里是原样落地的。
实验里有两个坑必须提前知道。第一，关键字和标识符的模式会冲突，比如if既能被关键字规则匹配，也能被id模式匹配。解决办法是把关键字的规则写在id规则前面，flex会优先采用先出现的规则。第二，flex默认按最长匹配取词，比如输入ifx，匹配到的是长度更长的ifx，而不是先匹配if再匹配x，这一点和教材描述的词法分析器行为一致。写测试用例时，我会专门准备if、ifx、123abc这种边界输入，避免最后交实验才发现模式优先顺序写错了。
4. 化简与等价：考试和实验中最容易被忽略的代数技巧
4.1 一组可以直接抄的代数恒等式
很多人以为正则只出现在词法分析那一章，结果发现作业、考试里有大量“化简”和“判断等价”题。别慌，正则有自己的一套代数系统，规律很强。
先看基础定律：
| 性质 | 恒等式 |
|---|---|
| 并交换律 | r|s = s|r |
| 并结合律 | r|(s|t) = (r|s)|t |
| 并幂等律 | r|r = r |
| 连接结合律 | r(st) = (rs)t |
| 分配律 | r(s|t) = rs|rt，且(s|t)r = sr|tr |
| 单位元/零元 | εr = rε = r，∅r = r∅ = ∅ |
此外还有一组关于闭包的恒等式，在化简时非常有用：
(ε|r)* = r* r* r* = r* (r*)* = r* (r|s)* = (r*s*)*每个恒等式都可以用语言集合去验证。比如r* r* = r*：左边是两个任意次重复段拼接，但任何有限次重复合并起来，还是一个任意次的重复，所以集合完全一样。考试时不要死背，理解成“两个无限集合覆盖关系相同”就不容易错。
4.2 化简策略：先把正则读回语言
我做化简题的方法是：别急着动笔，先把表达式用自然语言读一遍，找到冗余结构再动手。比如(ε|a)*，读出来是“要么空串、要么a，重复任意次”。空串重复多少次都不影响结果，所以直接化简成a*。
再看(a*|b)*。内层要么吐一堆a，要么吐一个b；外层随便重复。任何由a、b组成的串，里面每一段连续的a都可以由内层的a来提供，因此这个表达式描述的就是“所有a、b组合”，等价于(a|b)*。这里内层带a看起来像是有某种限制，但实际上已经足够自由了。
如果遇到带连接的表达式，比如a(a|ε)，就读成“一个a后面要么跟空串、要么跟a”，展开自然是a|aa。这类题练几道手感就出来了，核心思维永远是把表达式翻译成“它描述了什么串”。
4.3 判断等价的两板斧：反例法和双包含
判断两个正则是否等价，我很少去套一堆记忆中的规则，而是用两个更底层的思路。
第一是反例法：找一个字符串t，使得t被表达式A匹配、却不被B匹配，那两者一定不等价。比如比较(a|b)*和(ab)*，取ba——前者能匹配，后者不能，基本就能断定不等价。反例法适合快速排除不等价的选项。
第二是双包含思路：要证明等价，就往“L(A)包含于L(B)”且“L(B)包含于L(A)”去想。考试不一定要求严格证明，但这个角度能帮你建立直觉，避免想当然。
还要提醒一个高频错误：连接不满足交换律。ab和ba是两个语言，看到“化简rs为sr”的题目先打个问号。之前有同学用(a|b)*去化简a*b*，想当然认为一样，用反例法一测，ba直接打脸，这就是没有把连接看成有方向的拼接。
5. 正则描述能力的边界，以及和前后章节的衔接
5.1 为什么词法分析能用正则，语法分析却不行
这一节想聊一个经常被问的问题：既然正则这么强，为什么不用正则去描述语法结构，比如括号匹配？
因为正则语言无法描述嵌套结构。比如语言 {(ⁿ )ⁿ | n≥1}，左边n个左括号、右边n个右括号，它就不是正则语言。直观原因：识别这种语言需要记录左括号的个数，而这个个数可以无限增长，有限状态的自动机记不住。教材里的泵引理，就是用来严格证明这类语言不是正则的工具。
这也是为什么词法分析用正则，语法分析要换上下文无关文法。表达式这种递归嵌套结构，靠正则写不出来，必须让语法分析器借助栈或者递归去处理。理解这个边界后，整个课程的脉络就通顺了：词法分析负责“线性、局部”的模式，语法分析负责“嵌套、递归”的结构，两者分工明确。
5.2 正则表达式与正则文法的相互转换
还有一个常考的桥梁知识点：正则语言和3型文法（右线性文法）描述的语言，是同一个集合。右线性文法里，产生式形如A → aB或A → a。
举个例子就明白了。表达式a*b对应的文法可以写：
S → aS | bS每产生一个a并继续用S，最后产生b收尾，正好对应a的任意次重复后接一个b。反过来，如果给你文法，也可以通过解方程组写出正则表达式。比如A → aA | b，这个递归定义的非终结符A本质上是a*，最终结果就是a*b。
期末卷子很喜欢出这种互转题，考的本质是“递归产生式等价于闭包运算”这一层理解。学会了之后，再回头看闭包*，会有一种更立体、更工具化的感受——它不只是匹配时的“任意次重复”，它还对应着文法的递归结构。
5.3 应试和实验的一些亲身经验
最后分享几条我踩过的坑和总结的套路。写正则定义时，我习惯先在草稿上列出所有要识别的token，按关键字、标识符、数字、运算符分类，然后再从头开始定义零件。这样不会漏，也不会写一半发现前面少定义了letter。
考试碰到给语言写正则的题，先在心里描述这个语言的特点：“以a开头以b结尾”就写a(a|b)*b；“每个a后面必须跟b”就写(b|ab)*。写完之后再用几个边界字符串反推验证，比如空串、最短匹配串、容易混的串各来一个，能挡掉大部分粗心错误。
实验调试时，flex有一个很实用的习惯：先测正常输入，再故意输一些畸形串。比如数字模式，要专门测1e3、1E-5、1.、.5这种边缘情况，输出可能不对，但你能立刻反向检查是模式优先级的问题，还是正则定义写漏了某种形式。我把ifx、123abc、"1E-5"这几个测试输入常年放在实验文件开头，每次改模式都会重跑一遍。
在这一章里，我最深的体会是：学正则表达式最重要的不是把公式背得多熟，而是早点把“正则表达式描述的是语言集合”这个视角焊在脑子里。带着这个视角回头看闭包、ε、优先级，一切都是语言集合上的运算；再往后学NFA、DFA、文法转换，也会顺畅得多。
