编译原理中的正则表达式与正则定义：词法分析核心解析

打开编译原理教材的词法分析一章你大概率会看到这样一行公式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 三条规则把整个体系递归起来翻开任何一本编译原理教材正则表达式的定义几乎都是递归的。给定字母表∑后通常这样定义ε是正则表达式表示语言{ε}对∑中任意符号aa是正则表达式表示语言{a}如果r和s是正则表达式那么r|s、rs、r*、(r)也都是正则表达式分别表示L(r)∪L(s)、L(r)L(s)、L(r)*、L(r)。这个定义看起来平淡信息量其实很大。它从“空串”和“单个符号”这两个原子出发用三种组合运算拼出所有可能的模式。我学的时候觉得它像乐高两个基础零件加三种接口就能拼出无穷多模型。三种运算各自对应什么语言整理成一张表方便对照表达式表示的语言直观理解ε{ε}空串长度为零的串a{a}只有单符号ar|sL(r)∪L(s)二者选其一rsL(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|bs 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匹配3optional_fraction匹配.14optional_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、文法转换也会顺畅得多。