正则表达式与正则定义：词法分析器的核心原理与工程实践

1. 正则表达式与正则定义：词法分析的基石

学编译原理的同学都知道，词法分析是整个编译流程的第一关，而正则表达式就是词法分析器用来“认字”的核心工具。我当年第一次接触这个概念的时候也困惑过：正则表达式不就是用来做字符串匹配的吗？跟编译原理有什么关系？直到自己在手写词法分析器的时候才真正明白，编译器如何从一长串源代码里识别出关键字、标识符、数字常量，靠的正是正则表达式和正则定义这套精密的描述体系。

这篇文章我打算把编译原理视角下的正则表达式和正则定义完完整整地拆一遍——不光是背定义、记符号，更重要的是搞清楚它们背后的设计逻辑，以及怎么把纸面上的正则表达式变成真正能跑的词法分析器。无论你是正在准备编译原理考试的学生，还是想搞懂编译器工作机理的开发者，这篇文章都能给你一个清晰的脉络。我会结合自己手写词法分析器的实际经验，把容易踩坑的地方一并讲透。

2. 为什么词法分析要用正则表达式

2.1 词法分析的本质任务

要理解正则表达式在编译原理中的地位，得先看清楚词法分析器在做什么。编译器的前端通常分为词法分析和语法分析两步，词法分析器读入源代码的字符流，按照一定的规则把字符序列切分成一个个有意义的词法单元（Token）。比如遇到if就识别为关键字，遇到连续的字母数字序列就识别为标识符，遇到数字串就识别为常量。

这个过程看似简单，但难点在于如何给计算机说清楚什么算“标识符”、什么算“数字”。如果你用自然语言去描述——“标识符就是由字母开头、后面可以跟字母数字下划线的字符串”——机器是听不懂的。正则表达式就是用来精确描述这类字符串模式的数学工具，它是把自然语言描述转化成机器可理解规则的中间桥梁。

在学习编译原理第三版教材时，你会发现作者把正则表达式放在词法分析章节的最前面，这个编排是有讲究的。正则表达式对应的自动机理论是整个词法分析的理论根基：正则表达式描述模式，NFA（不确定有限自动机）和DFA（确定有限自动机）则提供识别模式的执行机制。你只有理解了正则表达式，后面的自动机转换、DFA最小化这些内容才有落脚点。

2.2 正则表达式的形式化定义

考试的时候最容易被问到的就是正则表达式的递归定义。我当初备考的时候，山东科技大学编译原理期末卷和燕山大学编译原理的课后题里都出现过这类题目，基本套路就是让你判断某个表达式是不是正则表达式，或者让你给出某个模式的正则表达式。

正则表达式的定义是递归的。基础情况很简单：空串对应的表达式是ε，单个字符a对应的表达式就是a。如果r和s都是正则表达式，那么它们的并集r|s、连接rs、闭包r*也分别是正则表达式。这里需要特别注意的是，这个定义里没有提+（正闭包）和?（可选），在实际应用中我们会把r+看成rr*的简写，把r?看成r|ε的简写。

括号的优先级也必须记清楚，三种运算的优先级从高到低依次是闭包（*）大于连接（相邻表达式）大于并集（|）。我在教学和实际写词法规则的时候见过不少人在这里栽跟头，比如想表达“a或者b开头，后面跟任意个c”，写成a|bc*就完全错了。因为按照优先级，它实际表达的是a | (b(c*))，而不是(a|b)(c*)。这里的教训就是：拿不准优先级的时候，加括号最保险。

2.3 正则表达式描述的语言

正则表达式描述的语言集合用L(r)表示，r是正则表达式。理解这个符号的意义在于建立“表达式”和“语言集合”之间的映射关系。每个正则表达式都对应唯一一个语言集合，但同一个语言集合可以由多个不同的正则表达式描述。比如(a|b)*、(a*b*)*、(b|a)*这三个表达式描述的语言其实是同一个——由a和b组成的任意串的集合。

这块知识在课程中的设计思路是循序渐进的，先讲表达式本身，再讲表达式对应的语言，最后过渡到语言对应的自动机。从我的实践经验来看，考试中经常出现两类题型：第一类是给你自然语言描述，让你写正则表达式；第二类是给你正则表达式，让你描述它表示什么样的字符串集合。这两类题目正好对应了“模式→表达式”和“表达式→语言”两种方向的能力，缺一不可。

2.4 正则文法与正则表达式的等价关系

编译原理里最具迷惑性的概念之一就是正则文法和正则表达式的关系。教材中会提到，正则文法（3型文法）产生的语言恰好是正则表达式描述的语言。这个等价定理看起来很抽象，但从实践角度理解非常简单：正则文法用产生式来描述语言，比如标识符 → 字母 字母串，这种一步步重写的过程本质上和正则表达式的递归结构一一对应。

我在复习三版教材的课后习题时发现，有一类题目专门考察这个等价关系，让你将正则文法转换成等价的正则表达式，或者反向转换。转换的规则并不复杂，核心思路是建立方程组然后解方程。比如文法S → aS | b，可以写成S = aS | b的形式，利用X = aX | b的解是a*b，就能得到S = a*b。这其实就是正则表达式闭包运算在文法层面的体现。

3. 正则定义：工程实践中的真实武器

3.1 正则定义的结构解析

如果说正则表达式是理论工具，那么正则定义就是编译器中实际使用的工程工具。正则定义本质上是一个命名规则的序列，每个定义给一个名字并赋一个正则表达式，后面的定义可以使用前面定义的名字。

这种设计很像编程语言里的变量定义——先定义基础模块，再层层组合成复杂模块。比如定义标识符的时候，我们可以先定义数字字符集合digit → 0|1|...|9，然后定义数字串digits → digit+，再定义可选符号的整数optional_fraction → .digits | ε，最后组合成完整的数字常量模式。这样做的最大好处是可读性强，像 JavaScript 学习手册里推荐的正则表达式编写技巧也强调这一点——先用变量拆解，再组合成最终模式。

3.2 一个完整的正则定义实例

我以一个典型的 C 语言风格词法分析器为例，展示如何用正则定义来构建完整的词法模式。这个例子我建议收藏下来，考试和实际项目中都用得上。

第一步定义基础字符分类。字母集合letter → A|B|...|Z|a|b|...|z，数字集合digit → 0|1|...|9。这一步没什么技术含量，但是是整个定义的根基。

第二步定义标识符和数字常量。标识符的模式是字母开头，后面跟零个或多个字母数字字符：id → letter(letter|digit)*。数字常量要处理整数和浮点数，整数部分integer → digit+，小数部分fraction → .digit+，浮点数常量float → digit+ . digit+ | digit+ | . digit+。

第三步定义运算符和关键字。运算符可以直接列出来：relop → < | <= | = | <> | > | >=。关键字本质上就是特定的标识符，比如if → if、while → while，但由于关键字是保留字，词法分析器通常先把所有标识符都识别出来，再查表确认是否为关键字，这种处理方式更高效。

3.3 正则定义在词法分析器生成器中的价值

如果你用过 Lex 或 Flex 这类词法分析器生成工具，你会发现它们的输入文件格式本质上就是一个正则定义的集合。每条规则由“正则表达式 + 对应的动作代码”组成，生成器会把整个规则集转换成一个确定有限自动机，在扫描输入的时候同时进行模式匹配，找出最长的、优先级最高的匹配结果。

这里就引出一个重要的工程细节：多条正则规则之间存在歧义时怎么处理。比如输入是if，它既匹配关键字if的规则，也匹配标识符id的规则，词法分析器应该听谁的？主流生成器的策略是两条原则：一是最长匹配原则，匹配最长的输入前缀；二是先出现的规则优先。实际项目中通常把关键字的规则写在标识符规则前面，配合最长匹配，就能正确处理if和iffy这类情况。

3.4 正则定义与上下文无关文法的边界

说句实话，很多初学者把正则定义和能力更强的上下文无关文法搞混。正则定义描述的语言有个重要限制：它无法描述嵌套结构。比如括号配对( ( ) )这样的语言，正则表达式是描述不了的，因为正则表达式对应的自动机没有堆栈，记不住嵌套的深度。

那为什么词法分析不用上下文无关文法呢？因为词法层面的模式基本都是“平铺”的，不需要处理嵌套。一旦遇到需要嵌套的语言结构，比如表达式里的括号匹配，那就进入语法分析的范畴了。这个边界在考试中经常以判断题或简答题出现，比如让你判断某个语言是否是正则语言。我的经验是：如果这种语言要求记录任意深度的嵌套信息，那基本可以断定它不是正则语言。

4. 从正则表达式到词法分析器：实操全流程

4.1 手写词法分析器的思路

理解了正则定义之后，真正动手写词法分析器有两种路线。第一种是使用生成工具，第二种是手写。虽然现在大部分人都会用工具，但我强烈建议你至少手写过一次，因为手写的过程能让你把教科书上的理论真正串起来。

手写词法分析器的核心思路是模拟 DFA（确定有限自动机）。比如识别标识符时，DFA 有三种状态：初始状态、标识符中间状态、结束状态。在初始状态若读到字母，进入中间状态；在中间状态若读到字母或数字，停留在中间状态；读到其他字符则结束识别。用代码实现就是用 switch 或状态变量管理当前状态，配合一个循环不断读取输入字符。

我在给海南大学编译原理实验课做辅导的时候发现，很多学生卡在“什么时候结束一个 Token 的识别”这个问题上。正确的做法是使用超前扫描一步的策略：一直读到不符合当前模式规则的字符为止，然后把那个字符“退还”给输入流，因为它可能是下一个 Token 的开头。这里还需要注意，如果当前识别出的是空白字符或注释，就直接丢弃并继续识别下一个 Token。

下面我给出一个简化版的识别标识符和数字的 Python 实现，这个代码风格参考了经典编译原理教材的实现思路，基本框架可以直接套用到 C 语言版本上：

def lexer(input_text): # 定义运算符、分隔符和关键字集合 operators = {'+', '-', '*', '/', '=', '<', '>'} separators = {'(', ')', '{', '}', ';', ','} keywords = {'if', 'else', 'while', 'return', 'int'} tokens = [] index = 0 length = len(input_text) while index < length: current = input_text[index] # 跳过空白字符 if current.isspace(): index += 1 continue # 识别标识符和关键字：首字符是字母或下划线 if current.isalpha() or current == '_': start = index while index < length and (input_text[index].isalnum() or input_text[index] == '_'): index += 1 token = input_text[start:index] token_type = '关键字' if token in keywords else '标识符' tokens.append((token_type, token)) continue # 识别数字常量 if current.isdigit(): start = index is_float = False while index < length and (input_text[index].isdigit() or (input_text[index] == '.' and not is_float)): if input_text[index] == '.': is_float = True index += 1 token = input_text[start:index] tokens.append(('数字常量', token)) continue # 识别运算符，这里简化了多字符运算符的处理 if current in operators: start = index two_char = input_text[index:index+2] if index + 1 < length else '' if two_char in {'==', '<=', '>=', '!='}: index += 2 else: index += 1 tokens.append(('运算符', input_text[start:index])) continue # 识别分隔符 if current in separators: tokens.append(('分隔符', current)) index += 1 continue # 无法识别的字符，报错并跳过 print(f'第 {index} 个字符无法识别: {current}') index += 1 return tokens if __name__ == '__main__': source_code = ''' int sum = 0; for (int i = 0; i < 10; i++) { sum = sum + i * 2; } if (sum > 10) { return sum; } ''' for token in lexer(source_code): print(token)

4.2 长度优先匹配与回退策略

在上面的代码里，多字符运算符==、<=的处理就体现了回退策略。当读到=的时候，我们不能立刻断定它是赋值运算符，需要再读一个字符看看，如果是等号就构成==，否则就要把后面那个字符退回输入流。

这个“向前再看一个字符”的做法是有讲究的，有些极端的语法甚至需要提前看三个字符才能确定 Token 的边界，比如 C 语言里的>>=就存在与>>和>的歧义问题。处理这类问题有两种常用方法：一是不管后续字符，先按最长匹配识别完当前运算符；二是引入状态机级别的歧义消解规则。实际编译器中往往还需要结合语法分析阶段来最终消解歧义，因为单靠词法层面无法完全判断a>>=b到底该断成(a>>)=b还是a>>(=b)。

我自己在调试词法分析器时就被这种隐形坑折磨过。记得有一次用 C 语言写模板式的表达式，模板里的>>和嵌套模板的>>混在一起，词法分析器无论如何都会把它切错。最后发现，真正可靠的方案是把词法分析和语法分析结合起来处理，而不是一味在词法层面兜圈子。这也是为什么我们学编译原理总是强调各个阶段要协同工作。

4.3 用 DFA 模拟实现词法规则

上面提到的 Python 实现是基于状态判断的，但真正的词法分析器生成器会把所有正则表达式合并成一个巨大的 DFA，然后在这个 DFA 上做状态跳转。手工模拟时，如果你的词法规则较复杂，建议先画出每个 Token 的 NFA，再用书上的子集构造法（Subset Construction）转换成 DFA。

我举个例子，标识符letter(letter|digit)*的 NFA 画法是这样的：从初始状态出发，读入一个 letter 进入中间状态，中间状态有一条指向自身的回环边，标签是 letter 和 digit。这个 NFA 转换成 DFA 后有两个状态——初始状态和接受状态。代码里只需要用一个布尔变量就能区分。但是当你同时处理几十种 Token 时，状态数会叠加，手写代码就容易出错，这时用变量表记录状态、用循环驱动跳转是更稳妥的做法。

另外，我在 SDU T 编译原理课程实验和山东理工大学编译原理实验里都见过要求学生手动构造某 Token 的 NFA 和 DFA 的题目。做这类题的关键是先理清楚语言的组成结构，比如带符号的整数常量，它由三部分组成：可选符号位、数字串、可选的小数部分。每一部分对应一段子自动机，再把它们串起来。这种模块化构建方式与正则定义的思路完全一致。

4.4 工具链推荐：Flex 使用要点

如果你不想完全手写词法分析器，Flex 是最常用的工具。我之前读书时在学校机房手动装过 Flex 和 Bison，用起来其实很简单——写一个.l文件，在里面定义正则表达式和对应的动作，然后命令生成 C 代码，最后用 gcc 编译。

一个最基础的 Flex 文件长这样：

%{ #include <stdio.h> %} letter [a-zA-Z] digit [0-9] id {letter}({letter}|{digit})* number {digit}+ %% {id} { printf("标识符: %s\n", yytext); } {number} { printf("数字: %s\n", yytext); } [ \t\n]+ { /* 跳过空白 */ } . { printf("其他: %s\n", yytext); } %% int main(void) { yylex(); return 0; }

注意 Flex 中yytext指向当前匹配的文本，yyleng是匹配长度，动作代码里的内容就是你在 C 程序中想要执行的部分。用 Flex 写词法分析器最大的好处是，你不需要关心底层的 DFA 构建和状态跳转，Flex 已经帮你把正则表达式转换成了高效的确定性有限自动机。

不过也不要以为用了 Flex 就万事大吉。前面提到的规则优先级问题在 Flex 里依然存在，它的处理策略是“选择最长的匹配”，如果长度相同则选先定义的规则。因此，关键字规则必须定义在标识符规则之前，否则if会被识别成标识符——这是我当年踩过的最经典的坑之一。另外，如果你定义了错误的字符类范围，比如[a-Z]，Flex 会直接报错，因为正则表达式不允许这种跨 ASCII 码范围的写法。

5. 正则表达式在语言与框架中的实战：从 C 到 JavaScript

5.1 不同语言中正则表达式的语法差异

编译原理中学到的正则表达式是理论概念，但在 Java、Python、JavaScript 等实际语言里，正则表达式的语法产生了很多扩展。比如在 Python 的re模块中，\d代表数字，\w代表单词字符，这些简写在理论正则表达式里并不存在。但是这并不影响理论的正则表达能力，因为\d完全可以等价地写成0|1|...|9，\w可以写成letter|digit|_。

我在辅导 C# 正则表达式提取数据的时候发现，很多人喜欢用\d+这类简写，比如从表单里提取出中间的数字及#符号后的字符串时，会写\d+(?:#\w+)?这样的模式。这些在实际开发中效率很高，但要注意的是，多数语言的正则引擎支持回溯（backtracking），这跟理论上的 DFA 匹配速度完全不同。理论正则表达式在 DFA 上是线性时间匹配的，而带回溯的引擎在某些模式下可能指数级退化。

5.2 20 个常用正则表达式的实战参考

网上流传的“20 个常用正则表达式”清单，我建议你当成速查表，不要死记硬背。我自己动手整理过一份，把最常用的几种放在项目里随用随抄：

• 邮箱验证：^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$
• IPv4 地址：^((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)\.){3}(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)$
• 中国手机号：^1[3-9]\d{9}$
• URL 提取：https?://[^\s]+
• 数字格式化：\B(?=(\d{3})+(?!\d))（用于千分位分隔）

在使用这些表达式时，一定要注意字符转义和边界锚点^、$的区别。忘了加^和$会导致部分匹配而不是完全匹配，比如邮箱验证时可能允许"abc@def.comxyz"这种非法输入通过。这种细节在实战中经常被忽略，却是非常影响结果正确性的问题。

5.3 JavaScript 学习手册中的正则进阶技巧

JavaScript 中的正则表达式和编译原理中的理论还有一个显著不同的地方：JavaScript 的正则引擎自带捕获组、非贪婪匹配、前瞻断言等高级特性。比如(?<=#)\w+表示匹配#后面的单词字符但不包括#本身，这种能力远超理论正则表达式。

但从编译原理的角度去理解 JavaScript 正则，仍然有意义。你写正则表达式时，本质上就是在描述一个模式，让引擎判断一个字符串是否属于这个模式描述的语言。理解了词法分析器的工作原理，你就能理解为什么某些正则表达式写法会导致性能灾难，比如嵌套量词(a+)+在回溯引擎中会引发指数级匹配时间——这在处理用户提交的大文本时是相当大的隐患。我自己做表单校验的时候吃过这个亏，后来强制要求自己写正则之前先在脑子里面过一遍是否可能退化成灾难性回溯模式。

6. 常见问题与高频考点排查

6.1 考试中的高频失分点

考试里最常出现的错误集中在三个方面。第一是优先级搞混，a|bc*和(a|b)c*表达的语言差之千里，前者匹配a或bc开头后面跟任意个c的串，后者是a或b开头后面跟任意个c的串。很多同学把初级错误犯在这里，非常可惜。

第二是闭包运算的边界理解。ε是任意语言闭包中的元素吗？是的，r*一定包含空串ε，因为零次重复就是空串。这个性质在构造 NFA 时特别重要，因为空串转移正是 NFA 和 DFA 的重要差异。第三是+与*的关系，不少同学的答案是“+要求至少出现一次，*允许零次”。这个理解对，但考试题往往还要你写出r+与rr*的等价关系，并说明r* = r+ | ε，这才是真正的考点。

还有一类经典题型是给定语言描述求正则表达式。比如“所有以 a 开头以 b 结尾的字符串”，不少同学的答案写成a(a|b)*b，这个实际上是对的，但它还漏掉了字符串长度为 2 时的情况——表达式本身已经覆盖了ab。注意，它没有覆盖空串和仅有一个字符的情况。如果题目要求“所有以 a 开头以 b 结尾的非空字符串”，这个表达式就完全正确。关键是审题时要确定边界条件是否包含空串。

6.2 实际开发中词法分析器的性能调优

在实际项目中，词法分析器的性能往往卡在输入流的读取方式和状态跳转的实现上。如果直接逐字节调用 I/O 操作读取文件，性能会非常差，正确做法是使用缓冲区批量读取，一次读入一大块字符，再在内存中做状态跳转。

Flex 生成的分析器内部就使用了固定大小的缓冲区配合指针扫描，这比逐字符读取提升了至少一个数量级。我在做一个简单的脚本语言解释器时，最初用 Python 逐字符处理，后来改成一次性读入整个源码字符串并配合索引指针扫描，性能提升非常明显——这就是教科书里所说的大缓冲输入优化。

状态跳转本身也能做优化。最简单的做法是二维数组state[当前状态][输入字符] → 下一状态，查表法实现直接且高效。如果状态和字符种类很多，这个表会很大，这时可以用转移矩阵压缩、跳转表分组或基于哈希的映射结构来优化。但大部分教学场景和中小型工程的词法分析器，二维数组查表已经完全够用。

6.3 正则表达式无法匹配的情况

正则表达式的能力边界我前面已经提到了嵌套结构。除了嵌套括号以外，HTML 标签的“正确嵌套”也是经典的反例——很多初学者尝试用正则解析 HTML，最终都会被嵌套标签折磨得死去活来。原因很简单，HTML 嵌套需要记录层级深度，这超出了有限自动机的能力范围。业界有句名言：“凡是想用正则解析 HTML 的人都会后悔”，这句话的真实含义不是正则太弱，而是用错了工具。

还有一个实际项目里常犯的错误：想用正则表达式验证一个字符串是否为合法的 C 语言标识符，但遇到关键字时正则表达式无法区分“合法的标识符”和“保留字”，因为保留字集合需要查表判断。我的建议是正则只负责模式匹配，语义层面的区分交给代码逻辑。词法分析器里就是把所有letter(letter|digit)*都识别成标识符，再在后续步骤中通过查关键字表决定其真实类型。

6.4 常见问题速查表

我把学习过程中遇到的高频问题和解决方案整理成了一个速查表，考前一分钟翻一遍比重新啃教材高效得多：

7. 设计正则定义时的工程规范与经验心得

最后再分享一些我们在实际项目中总结出来的规范。这些内容教科书上不太会明说，但对一个真正可维护的词法分析器来说极其重要。

第一，正则定义的命名要有清晰的分层。我见过太多人把所有正则规则堆在一张大列表里，看起来能跑，一改就崩。正确的做法是像编写代码一样组织正则定义：常量优先定义（如字符集合、分隔符集合），简单结构次之（如数字、标识符），复杂结构最后组合（如带符号的数、带转义符的字符串）。每一层的定义尽量只依赖更低的层，形成可读的依赖树。这样改一处定义时，你能清楚判断它影响哪些上层规则。

第二，Token 的优先级与顺序必须有文档记录。规则并非越多越好。如果你定义了[0-9]+又定义了[0-9]+.[0-9]*，那么123.456会被拆成123和.456两个 Token，除非你设置了最长匹配策略。如果你用 Flex，这个问题可以通过调整规则顺序解决；但如果你维护的是手写词法分析器，就要在代码注释里写清楚每种 Token 的优先级说明，否则后面接手的人一定会踩坑。

第三，正则表达式本身要注重可读性。不要让一条正则表达式超过一屏，用正则定义把复杂模式拆成子表达式并命名。比如解析配置文件的键值对格式时，我通常会先定义key → [a-zA-Z_]\w*，再定义value → "[^"]*"，最后才是pair → key\s*:\s*value。这种分层写法在排查问题时能快速定位到具体哪一位符号出了问题。

从个人经验上说，编译原理里正则表达式和正则定义的学习真的不能只靠背书。我现在带学生做实验，都会布置一个“手写简易词法分析器”的作业，不强求用工具，要在两周内从零开始实现。经历过那一关的学生，后面学 NFA 转 DFA、学 LL 分析、学自底向上语法分析，都明显轻松得多。因为词法分析是整个编译课程里最直观、最容易验证的一块，你把这一块亲手打通了，对“形式化描述语言”的感觉就会完全不一样。

最后补一个小技巧：如果你在写词法分析器时发现规则冲突特别多，不妨先把所有 Token 的样例输入和预期输出列成表格，用一小段测试代码先跑通样例，再对样例做扩展。这种“用例先行”的做法在词法分析器开发中极其有效，既能保证规则之间的优先级安排合理，又能显著减少后期调试的挫败感。希望这篇内容对你理解正则表达式与正则定义有所帮助。