很多同学学编译原理时最容易在词法分析这一块卡住尤其是看到正则表达式和正则定义满屏字母套着字母、括号叠着括号总觉得这是数学课而不是计算机课。但说句实话正则表达式恰恰是整个编译原理里最能“落地”的内容之一平时写代码用到的字符串校验、日志提取、编辑器里的查找替换底层原理都挂在这棵树上。这篇总结会把正则表达式在编译原理中的位置、基本运算、正则定义的组织方式以及如何一步步把它变成词法分析器从头到尾捋一遍适合正在准备期末考试、做实验课设计或考研复习的你对照着看也适合学过一遍但总感觉知识点是散落的同学用来串线。1. 为什么词法分析绕不开正则表达式1.1 正则表达式在编译流程里的位置很多人一上来就被“正则表达式”这个词吓住觉得它是某种需要花一整周去背规则的“代码咒语”。真实情况完全不是这样。编译原理教正则表达式不是为了让你背规则而是为了回答一个很朴素的问题怎么用一套简洁的、确定的规则告诉计算机“什么样的字符串是一个合法的标识符、关键字、数字”。词法分析器就是每天在执行这个判断的岗位而正则表达式就是它的岗位说明书。咱们对照一段C语言代码来看。int a 10;这一行里int是关键字a是标识符10是无符号数是运算符;是界符。编译器要做的第一件事就是把这一行拆成这一个个“单词”也就是词法单元。怎么拆不能靠肉眼也不能靠写一堆if-else去比较而是需要一种形式化的描述告诉程序满足什么模式才算某种单词。这个描述工具就是正则表达式。所以它在编译流程里的位置极其靠前属于词法分析阶段的核心模型而词法分析又是语法分析的前提——这一步分析错了后面解析树再漂亮也没用。1.2 正则表达式与正规文法的等价关系再深一层看正则表达式之所以能承担这个任务不只是因为“好用”而是它和正则文法也叫3型文法在表达能力上是等价的。这句话很多教材用一句话带过但它是理解整块知识的定心丸。意思是凡是能用正则文法描述的语言一定能写成对应的正则表达式反过来凡是有正则表达式也一定能构造出接受它的有限自动机。这里有个特别重要的认知要纠正正则表达式并不是“一种查找替换的小技巧”它是形式语言理论的一部分描述的是正则语言。编译原理课上让你做的那些看上去很抽象的题什么(a|b)*abb、letter(letter|digit)*背后对应的是实实在在的语言集合。理解这一点之后你看待正则表达式的视角会完全不一样——它不是在“背符号”而是在“描述字符串集合的结构”。这套等价关系还带来一个实用的思考方式当你拿到一个问题比如“设计一个能识别浮点数的词法规则”你可以先在脑子里用“正则文法”的方式描述它再去套正则表达式的写法。正则文法是偏向生成式的思维正则表达式是偏向模式式的思维两者来回切换很多复杂的规则一下子就有了解法。2. 正则表达式基础三个运算吃遍所有模式2.1 选择、连接、闭包三种基本运算正则表达式的核心运算其实只有三样别被那些花里胡哨的扩展语法带跑偏。第一是选择运算用竖线|表示含义是“或者”。比如a|b表示匹配一个字符这个字符要么是a要么是b它对应的是两个语言的并集。第二是连接运算通常直接并排写比如ab表示先匹配a紧接着匹配b对应语言的连接。第三是闭包运算用星号*表示含义是“零次或多次重复”比如a*表示由零个或多个a组成的串对应语言的Kleene闭包。这三个运算合起来加上括号和空串ε、空集符号就能表达几乎所有的正则语言。为什么强调“只有三个”因为很多同学做题时不知道该用还是*还是?意识里全是各种简写反而忘了最基本的组合能力。其实就是a(a*)的简写表示至少一次?表示零次或一次是ε|a的简写。考试如果要求严格按定义写你完全可以用最基础的三运算符去展开展开的过程反而能检验你对语言集合的理解。这里要特别提一个常见误区a*不是“若干个a”这么简单它包含了“零个a”这种情况也就是空串。很多人判断“字符串能否被识别”时会把空串漏掉。比如让你判断ε是否属于(a|b)*描述的语言答案当然是属于因为*允许零次重复。这种细节在做自动机构造和写程序判定时特别容易出错。2.2 运算符优先级和括号的作用正则表达式里运算符优先级是固定的星号*最高连接运算次之选择运算|最低。这个顺序决定了你怎么读一个复杂表达式。看这个例子ab|c*因为*的优先级高于连接高于|所以它实际表示的是(ab)|(c*)也就是“要么是ab这个串要么是若干c组成的串”绝不是a(b|c)*也绝不是(ab|c)*。这个优先级规则和算术里的“先乘除后加减”是一个意思但很多同学栽跟头不是因为记不住顺序而是因为“看着应该对”就跳过了思考。我当年复习时最喜欢拿身边的同学做实验问他们abc*匹配什么。不少人脱口而出是“abc重复任意次”正确解释其实是“ab后面跟任意个c”。因为*只作用于它紧贴着的c除非用括号把abc括起来。所以括号的作用就非常重要它可以把默认的优先级打破显式地改变运算范围。这种地方往往也是考试爱出的点给你一个正则表达式问你它描述的语言集合或者反过来给你一个语言描述让你写出等价的正则表达式。做题时没有捷径必须有意识地先找优先级最高的部分用括号在心里标记好再逐层读懂。遇到特别长的表达式我建议先把它拆开写在草稿纸上比如(a|b)*和a*|b*看上去差不多实际完全不一样前者是所有由a和b组成的任意串后者只有全是a或全是b这两种串。这个坑每年都有同学踩。为了加深理解我整理了一张速查表把常见的写法区别放在一起对照着看。表达式实际含义容易误认为的含义ab|cd匹配ab或cd匹配a、bc或dabc*ab后跟任意个cabc整体重复任意次(abc)*abc这个串整体重复任意次仅c重复a*|b*全是a或全是b的串由a和b自由混合的串(a|b)*由a、b自由混合的任意串只有a或只有b这张表建议抄在自己的笔记里。每次做题之前扫一眼能少丢很多冤枉分。3. 正则定义把复杂模式拆成能看的零件3.1 正则定义到底是什么如果只学基础的正则表达式你很快会发现一个问题一个稍微复杂的词法规则比如C语言里的标识符、带符号的浮点数、字符串常量直接写成一个“一长条”正则表达式写出来没人能看懂自己也维护不了。正则定义就是为解决这个问题出现的组织方式它在概念上很像编程里的“变量定义”先给某个子模式起个名字再在更大的模式里引用它。严格一点说正则定义是一组命名规则形式是d1 - r1、d2 - r2……其中每个di都像一个名字ri是已经在前面定义好的名字或基础字符组合成的正则表达式。注意这里的“前面”是关键的约束在标准定义里新名字只能引用已经定义过的名字不能回头引用更不能递归地定义自己。这一点放在考试里就是判断“某个定义是否合法”的题眼。举个例子说明。很多教材都有一个经典正则定义序列digit - 0|1|2|...|9letter - A|...|Z|a|...|zid - letter(letter|digit)*这里先定义数字和字母最后用它们组合出标识符的定义。id表示的就是“以字母开头后面跟任意个字母或数字”的串也就是绝大多数高级语言的标识符规则。如果没有正则定义你会直接面对一个由几十个字符拼成的超长表达式光看都要看半天。3.2 构造正则定义的步骤和原则构造正则定义的过程其实就是在练习“自顶向下拆解问题”。第一步先列出所有需要定义的基础字符集比如数字、字母、空白符第二步把语言描述中重复出现的结构抽象成中间层名字比如数字序列、可选符号、指数部分第三步用这些名字拼出最终目标模式。这里最大的原则是“从底往上逐层构建每一层只依赖已经出现过的定义”。我们以带符号整数的词法规则为例完整走一遍这个过程。首先定义digit - 0|1|...|9接着定义digits - digit digit*也就是“至少一位数字的序列”它引用了digit然后还需要正负号定义sign - |-这里的-需要转义或用引号包裹最后定义整体signed_integer - sign? digits。其中?表示可选的符号。你把四层定义写出来之后再用普通正则表达式的写法把它整体展开会发现又臭又长但通过正则定义去读它每一层都很清晰。这也是为什么教材在讲词法分析器实现时几乎所有语言都用正则定义来组织词法规则而不是甩出一条巨型正则表达式。工程意义上的可读性在这门课里同样重要。我还是要强调一下正则定义和正则表达式不是并列的两个东西。正则定义是“用命名方式组织正则表达式”的手段最终展开之后还是一个正则表达式。考试时如果问你“给出标识符的正则定义”一定要写成分层定义的格式不要只写一个最终的表达式。反过来如果题目要求你“直接用正则表达式表示”那就别啰嗦地写好几层定义直接给一个扁平写法。看清楚题目的要求是这节内容最实在的得分技巧。4. 从正则定义到可运行的词法分析器4.1 状态转换图把表达式翻译成图正则表达式和正则定义回答的是“规则长什么样”但词法分析器是程序程序需要的是“怎么一步步判断”。这里关键的桥梁是状态转换图。状态转换图由一个初始状态、若干中间状态和接收状态组成每条边上的标号表示“读入这个字符之后从当前状态转移到下一个状态”。比如识别a*的转换图只有两个状态初始状态接收a后进入自身这个初始状态同时是接收状态因为空串也属于a*。手动从正则表达式画状态转换图教材里给了非常机械化的规则就像拼乐高。对应选择运算r|s就新建一个初始状态分出两条ε边分别进入r和s的子图对应连接运算rs就把r的接收状态和s的初始状态用ε边串起来对应闭包运算r*则新建初始和接收状态用ε边让它可以跳过整个r也可以反复循环进入r的子图。这套规则不需要灵感照着套就行。这里想多说一句关于ε边。ε边指的是不需要读入任何字符就能跳转的边它看上去像“作弊”但实际上它是构造NFA时用来拼装子图的万能胶。考试作图时很多同学不习惯画ε边总想着能不能省掉结果拼出来的图各种别扭。我的建议是前期完全按规则画ε边该画就画不要自作主张优化。等你真正理解后再去消除ε边也不迟那是算法层面的事情不是手工作图阶段该考虑的。4.2 从NFA到DFA让程序真正做决定状态转换图画出来之后得到的通常是带ε边的NFA非确定有限自动机。它的问题是在某个状态读入一个字符可能有好几个后继状态可以选择程序真跑起来不知道该走哪条路。所以实际构造词法分析器时还要用子集构造法把它转换成DFA确定有限自动机让每个状态读入每个字符都只有一个确定的去向。子集构造法的核心是“把NFA状态的集合变成DFA的一个状态”。具体做法是先求初始状态经过若干ε边能到达的所有状态的集合作为DFA的初始状态然后对集合中的每个状态、每个输入符号求出能转移到的所有状态再做一次ε闭包得到一个新的状态集合。重复这个过程直到没有新集合出现为止。这个过程在手工课上很繁琐但逻辑非常固定属于那种“只要耐心就能做对”的题。为什么非要把NFA转成DFA不能直接用NFA做程序吗无非是效率和确定性。DFA每个状态读入每个字符只有一个出路词法分析器就能做最长匹配配合缓冲区读入逐字符推进一旦无法继续转移就停机并返回当前识别的词法单元。这是工程实现的要求。而理解这整套转换过程反过来也能帮你更深刻地理解正则表达式、NFA、DFA三者为什么是等价的描述。等到实验课要写真正的词法分析器时流程基本就是这几步先用正则定义写下每种词法单元的规则再画出合并后的状态转换图不同规则合并成一个NFA然后转DFA并最小化最后根据DFA写程序。你别看虎头蛇尾只写了不到五行字这一步一步都是教材里花了大篇幅在讲的内容也是期末题里最容易出“综合大题”的部分。5. 考场高频陷阱这些坑我当年全踩过5.1 闭包、空串和特殊字符的细节坑期末做这套题最经典的一个坑就是分不清*和。a*包含空串a不包含空串。这句话看起来平平无奇一放到题目里就会出问题。比如要求“字母开头的标识符”你写letter*就是错的因为这样允许了空串作为开头还有可能识别出空标识符。正确写法必须是letter(letter|digit)*用这个letter打头就保证至少有一个字母。类似地在描述“一个或多个数字”时优先用digit digit*而不是digit*。第二个高频坑是对特殊字符的处理。正则表达式里的|、*、(、)、?这些符号本身有特殊含义如果要匹配它们自身就必须转义或用引号标起来。教材里常出现的一个例子是匹配符号本身时乘号要写成*的前面带反斜杠管道符要写成\|。一些初学者做题目时只顾着结构忘了把运算符和普通字符区分开结果把a*当成“匹配字符a和字符*”实际含义完全跑偏了。第三个坑是关于语言描述的语义判断。最典型的问题是(a|b)*和a*|b*前文已经提过前者是自由组合后者是纯a或纯b。这种题在选择题和判断题中反复出现核心考察点就是“闭包作用在谁身上”。做题的时候我习惯先给每个*或?找它的“管辖范围”也就是紧邻的最小单元。如果紧邻着的是括号那闭包就作用于整个括号内的表达式如果紧邻着的是单个字符就只作用于这个字符。把管辖范围标清楚语义判断基本就不会错。5.2 解题时的展开与等价性判断还有一种常见题型是判断两个正则表达式是否等价。这里最可靠的方式不是“看着像不像”而是把它们描述的语言集合做对比。你可以把每个表达式先展开成“能匹配哪些串”的视角。比如(a|b)*和(a*|b*)*是否等价从表面看后者复杂很多但仔细想*本身允许反复任意次而外层再套一层*并不会扩大“由a和b组成的任意串”这个范围所以它们是等价的。遇到这种题试着列举前几个长度的串长度为0、1、2时各自能生成什么列到第3个长度时规律就清楚了。还有一种情况题目要求你把某个正则定义展开成整个正则表达式。这时最容易出错的地方是括号数量不对。因为展开时要一层层代入每一层定义的引用都可能引入新的括号和运算一旦漏了括号结构就全变了。我的技巧是代入时把被代入的地方先整体加括号再放到目标位置去。这样做虽然最后看起来括号有点多但优先级不会乱逻辑也更容易检查。再补充一个做题顺序上的建议遇到综合题先判断题目要你输出“正则定义”还是“正则表达式”再判断语言描述里最关键的模式特征是什么比如是开头固定还是结尾固定是必须出现一次还是可以出现零次。把这两点想清楚再动笔正确率远高于看到题目就急于套模板。很多人考完对答案发现思路错了不是因为不会而是因为一开始就没看清题。6. 实操建议和练习方向说了这么多最后给你一些真正能落地的练习方法和实验课上的建议。第一件事把教材里那套“表达式转NFA”的规则亲手画五遍以上。不要只是在纸上抄要闭着眼睛能回忆出选择、连接、闭包三种构造分别怎么画。画熟练之后你会发现词法分析后面的内容突然变得顺了因为自动机是这一章的通用底层工具。画图的顺序也很重要先分别给子表达式画图再按规则拼装每一步都标注清楚当前处理的是哪个运算符。第二件事正则定义要自己动手“造轮子”。不要只看教材里的例子自己去设计一套词法规则。比如试着设计一个能识别C语言浮点数的正则定义要求支持12.3、0.5、3.、.5、1e-3这些形式。你会在设计过程中真正体会到为什么要分层定义、为什么需要可选的符号、为什么要单独抽出一个digit的底层定义。这种练习比背十道题都有用。第三件事如果要做实验课的词法分析器建议从最小的语言开始。先支持关键字和标识符再逐步添加数字、运算符和空白符处理。每次添加一类规则就重新走一遍“写正则定义、构造NFA、转DFA”的流程。我在实际做这个实验时最大感受是最容易出bug的不是状态转换逻辑本身而是识别失败后的“回溯”处理也就是到底要不要回退读入的字符。处理好这个你的词法分析器才算真正能跑。练习时的样例也很有讲究。不要只用合法输入测试一定要准备一组非法输入比如以数字开头的标识符、包含非法字符的串、只有符号没有操作数的表达式。词法分析器的健壮性恰恰体现在这些边界情况下。很多课程设计容易卡在这一步因为大家只想着怎么识别合法的没想着怎么优雅地拒绝非法的。最后再分享一个小技巧。复习这块内容时可以把正则表达式、正则定义、NFA、DFA四者的关系画在一张纸上自己给自己讲一遍“从一条规则到一个可运行程序”的完整链路。能讲得明白就说明知识点真正串起来了讲不清楚的地方就是需要重新看书的薄弱点。考试前能把这个链路讲通比刷多少题都实在。
