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:index2] 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 语言里的就存在与和的歧义问题。处理这类问题有两种常用方法一是不管后续字符先按最长匹配识别完当前运算符二是引入状态机级别的歧义消解规则。实际编译器中往往还需要结合语法分析阶段来最终消解歧义因为单靠词法层面无法完全判断ab到底该断成(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 到 JavaScript5.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))用于千分位分隔在使用这些表达式时一定要注意字符转义和边界锚点^、$的区别。忘了加^和$会导致部分匹配而不是完全匹配比如邮箱验证时可能允许abcdef.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 常见问题速查表我把学习过程中遇到的高频问题和解决方案整理成了一个速查表考前一分钟翻一遍比重新啃教材高效得多问题类型典型表现解决办法表达式优先级混淆abc*被误读为(a闭包包含空串忘记r*包含空串记住零次重复的定义构造 NFA 时预留空串转移与*混淆把r写成r*导致长度丢失r等价于rr*至少出现一次匹配空串问题表达式意外匹配空串检查是否包含ε分支根据题目要求删减状态机状态数过多手写识别器分支混乱先画 NFA/DFA 再编码不要跳步骤最长匹配与优先级冲突关键字被识别为标识符规则顺序调整或使用工具的最高优先级原则忽略空白与注释词法分析器把空白当非法字符在词法规则中加入空白跳过动作多字符运算符误判与无法区分向前多看一个字符并实现回退机制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 的样例输入和预期输出列成表格用一小段测试代码先跑通样例再对样例做扩展。这种“用例先行”的做法在词法分析器开发中极其有效既能保证规则之间的优先级安排合理又能显著减少后期调试的挫败感。希望这篇内容对你理解正则表达式与正则定义有所帮助。 正则表达式与正则定义：词法分析器的核心原理与工程实践
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:index2] 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 语言里的就存在与和的歧义问题。处理这类问题有两种常用方法一是不管后续字符先按最长匹配识别完当前运算符二是引入状态机级别的歧义消解规则。实际编译器中往往还需要结合语法分析阶段来最终消解歧义因为单靠词法层面无法完全判断ab到底该断成(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 到 JavaScript5.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))用于千分位分隔在使用这些表达式时一定要注意字符转义和边界锚点^、$的区别。忘了加^和$会导致部分匹配而不是完全匹配比如邮箱验证时可能允许abcdef.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 常见问题速查表我把学习过程中遇到的高频问题和解决方案整理成了一个速查表考前一分钟翻一遍比重新啃教材高效得多问题类型典型表现解决办法表达式优先级混淆abc*被误读为(a闭包包含空串忘记r*包含空串记住零次重复的定义构造 NFA 时预留空串转移与*混淆把r写成r*导致长度丢失r等价于rr*至少出现一次匹配空串问题表达式意外匹配空串检查是否包含ε分支根据题目要求删减状态机状态数过多手写识别器分支混乱先画 NFA/DFA 再编码不要跳步骤最长匹配与优先级冲突关键字被识别为标识符规则顺序调整或使用工具的最高优先级原则忽略空白与注释词法分析器把空白当非法字符在词法规则中加入空白跳过动作多字符运算符误判与无法区分向前多看一个字符并实现回退机制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 的样例输入和预期输出列成表格用一小段测试代码先跑通样例再对样例做扩展。这种“用例先行”的做法在词法分析器开发中极其有效既能保证规则之间的优先级安排合理又能显著减少后期调试的挫败感。希望这篇内容对你理解正则表达式与正则定义有所帮助。