编译原理期末复习攻略：从正规式到LR分析的手算全流程

又到了期末周桌面堆着老师上课的PPT、打印的作业题还有自己抄了三遍的笔记。编译原理这门课知识点多且连贯最怕的就是学到中间断裂——第三章的词法分析还没搞透第四章的LL(1)分析表又来了等到第六章几百行LR项目集规范族砸过来整个人都是懵的。吉林大学软件学院《编译原理与实现》的习题三恰好就把这门课最难啃、也是最核心的一段拎了出来从正规式到DFA的手算推演从First/Follow到预测分析表从LR项目集到语法制导翻译再到中间代码生成与运行时环境。这套题不是简单考记忆它考的是能不能顺着编译器的脉络把一个源程序从字符流一路变成中间表示。我前前后后刷了两遍第一遍好多地方看答案勉强看懂第二遍合上答案自己手推才真正把几个容易混淆的点打通。这篇文章就按习题三的出题模块把复习思路、手算流程和踩过的坑整理出来希望能帮正在头疼的学弟学妹们少走点弯路。1. 先从整体摸清习题三的“考点地图”这门课复习的底层逻辑1.1 为什么习题三的位置这么关键《编译原理与实现》这门课在软件学院本科课程里属于“又硬又连贯”的那一类。硬是因为它集合了自动机理论、形式语言、树和图算法、甚至一点点软件工程思想连贯是因为前后章节不是在讲并列知识而是在讲一条完整的流水线词法分析把字符流切成单词流语法分析把单词流组织成语法树语义分析和中间代码生成把语法树变成机器无关的中间表示再到代码优化和目标代码生成。习题三出在语法分析和语义分析这段正好卡在“编译器前中端”的交界处可以说是整套课程承上启下的命门。我在刷题的时候明显感受到习题三跟前两套题最大的区别是它不再只是孤立地考“某个状态转换图怎么画”“某个单词怎么识别”而是开始要求你把“推导过程”完整地写出来。比如给定一个文法让你求First集合和Follow集合再判断是不是LL(1)文法紧接着构造预测分析表再比如给出一串LR(0)项目让你求出项目集规范族、构造ACTION和GOTO表最后分析一个输入串的整个移进规约过程。这种题考的不是“知不知道”而是“练没练过”。所以复习习题三第一件事不是翻书背定义而是把教材里第五章到第八章按常见编译原理教材章节划分的知识点串成一条“推导链”。我自己画了一张图表贴在书桌前每个节点都标上“输入是什么”“输出是什么”“用什么算法”复习时只扫这张图就能回忆起整条主线。1.2 吉林大学软院备考的“常规武器”教材、PPT、旧题提到吉大软院的编译原理很多同学第一反应是“教材好厚PPT信息量太大”。我自己的体会是这门课核心教材和配套PPT重点覆盖了词法分析、语法分析、语法制导翻译、中间代码生成、运行时环境、代码优化几大块习题三的题目基本都在这些范围内。关键不是你读了哪本书而是你能不能把老师PPT上那些“看似理所当然”的推导过程自己在纸上完整走一遍。我推荐的复习顺序是先看PPT和教材里的例题再做习题三里对应的题目最后回到教材看概念细节。千万不要反过来——先做题再翻书那你连题目里的符号都认不全。比如求First集合的题题目给你一个含ε的产生式集合如果你没把“何时加入ε”“何时消除ε”的规则吃透很容易在边界条件上出错。这种细节只有手算一遍才能发现。1.3 习题三覆盖的核心模块清单结合出题风格和课程大纲我把习题三可能涉及的考点整理成了一张清单复习时对着它逐个打勾模块核心考点常出题型词法分析正规式与语言描述、NFA、DFA、最小化构造NFA/DFA、化简状态图语法分析First/Follow、LL(1)条件、预测分析表手算集合、构造表、判断文法LR分析LR(0)/SLR(1)/LR(1)项目集、ACTION/GOTO表构造规范族、填表、分析句子语法制导翻译属性文法、综合/继承属性、SDD/SDT语义动作、翻译模式中间代码三地址码、四元式、三元式翻译表达式、生成中间代码运行时环境活动记录、栈式分配、作用域描述内存布局、过程调用过程代码优化基本块、DAG、循环优化划分基本块、优化局部这张表看起来内容多但其实有清晰的主线前四块是“分析阶段”后三块是“综合阶段”。复习的时候我建议前四块投入七成精力因为期末笔试的大题几乎都集中在这里而且每道题都有固定套路练熟了就是送分题。2. 词法分析大题怎么拿分正规式、NFA转DFA和最小化手算流程2.1 先分清题目到底要你做什么词法分析相关的题目在期末试卷里通常以三种面目出现一是给一个语言的正规式要求画出对应的NFA二是给一个NFA要求用子集构造法转成DFA三是给一个DFA要求最小化。习题三里这道题往往还不是单独出现而是把三连问放在一起一步错步步错。所以必须在草稿纸上把三步流程分开写清楚每一步检查完再往下走。我见过很多同学在这类题上失分不是因为不会算法而是因为状态图画得太潦草导致后面的表填错。记住阅卷是按步骤给分的状态转换表一定画成规规矩矩的表格状态命名用容易区分的编号q0、q1、q2…不要中途改名字更不要用“s”“t”这种含义不明的标记。2.2 从正规式到NFAThompson构造法的固定三步当题目要求“画出正规式 (letter|digit)* 对应的NFA”时不要凭感觉画直接用Thompson构造法。这个方法虽然机械但不容易错对单个字符或单个符号构造一个“起始状态 → 终态”的两状态转移对连接运算 AB把A的终态与B的起始状态用ε边连接合并成一个整体对选择运算 A|B新增一个起始状态和一个终态分别用ε边连到A和B的起止位置对闭包运算 A*新增起止状态用ε边实现“可跳过A、可重复进入A”的环。举个典型例子标识符的正规式是letter(letter|digit)*。先用Thompson构造法得到NFA后会自动出现若干个ε转移。这里有个容易踩的坑很多人画完NFA之后不去掉ε边就直接拿去模拟输入串结果状态跳来跳去把自己绕晕。正确的做法是先保留ε边用来理解结构再在下一步子集构造法里用ε-closure把它消除掉不要在NFA阶段手工删除否则会把语言搞错。2.3 子集构造法与DFA最小化草稿纸上推演的核心流程从NFA到DFA核心算法是子集构造法。我在手算时习惯用一个表每一列对应一个输入符号每一行对应一个DFA状态。先取NFA初始状态的ε闭包作为DFA的初态然后对每个输入符号求出能到达的状态集合再对这个集合求ε闭包得到新的DFA状态。重复这个过程直到没有新状态出现。以letter(letter|digit)*为例设 letter adigit b简化为只含a、b两类字符那么DFA的意思就变成第一个必须读入a读入之后可以无限读a或b。算出来的DFA状态只有两个初态q0读入a后到终态q1q1读入a或b都回到q1。这样就不需要真的画出NFA直接能写出最终的DFA。接下来是最小化步骤。这个步骤最容易出错原因是很多人只做了第一步“把终态和终结态分开”就下结论“已经最小了”但忽略了每个分组内部在同一个输入符号下是否还能到达不同分组的成员。正确做法是先把DFA状态分成两个大组终态组和非终态组对每个大组按输入符号看内部状态迁移到哪个大组如果迁移去向不一致就把该大组拆开重复第2步直到没有分组可以被拆分。还是用上面的例子q0是非终态q1是终态分成两组后q0读a到q1、q1读a到q1迁移去向不同所以不会再合并不了状态数保持不变。但如果是一个多余的不可达状态在最小化之前就应该删掉否则会影响后面的判断。我在习题三里吃过这个亏有一个状态没有任何边能到达我一直留在DFA里结果最小化时分组怎么都分不对后来才反应过来要先删不可达状态。注意子集构造法生成的DFA可能含有不可达状态最小化前务必先把不可达状态删除否则可能出现“多余的等价状态”导致最终结果不是最简。3. 语法分析的送命题First/Follow/LL(1)的完整手算示范3.1 First集合和Follow集合不要跳步按产生式一层层推语法分析这一章习题三的大题通常给一个上下文无关文法要求“求所有非终结符的First集合和Follow集合判断是否为LL(1)文法构造预测分析表”。第一步求First集合规则其实很简单对产生式 A → X1 X2 … Xn先把First(X1)中除ε以外的元素加入First(A)如果X1能推导出ε再看X2把所有符号的First都看一遍如果每一个Xi都能推导出ε才把ε加入First(A)。手算时我习惯先在草稿纸上列出所有非终结符然后按“遇到终结符就停”“遇到非终结符递归找First”“没有产生式或能推ε就加入ε”三条规则反复迭代。这里有个教科书上不常强调的技巧如果文法里出现A → AB这种左递归产生式求First会陷入无限循环所以在做集合运算之前先检查文法是否含直接左递归或间接左递归。如果有要先消除左递归否则First集合根本算不完。Follow集合的规则比First稍微绕一点尤其是在处理产生式右部末尾时。规则核心有两条一是如果A → αBβ那么把First(β)里除ε以外的符号加入Follow(B)二是如果β能推导出ε包括 β 就是空的情况那么把Follow(A)加入Follow(B)。要注意的是Follow集合里永远没有ε而且文法的开始符号的Follow集合里一定有结束标记$或#。3.2 经典表达式文法的手算实例为了把流程说清楚我用一个非常典型的文法示范一遍。设文法G如下E → E T | T T → T * F | F F → (E) | id注意这个文法带有左递归实际构造LL(1)分析表前要先消除左递归。消除后的文法变成E、T是新增非终结符E → T E E → T E | ε T → F T T → * F T | ε F → (E) | id手算它的First集合First(F) { (, id }First(T) { *, ε }First(T) First(F) { (, id }First(E) { , ε }First(E) First(T) { (, id }接着算Follow集合这里最容易被绕晕的是E和T。按规则Follow(E) { ), $ }因为E在(E)中出现后面跟着 )且E是开始符号所以还有 $Follow(E) Follow(E) { ), $ }因为产生式E → T E中E在末尾所以Follow(E)传给EFollow(T) First(E)除去ε后得到 { }再加上Follow(E) { ), $ }所以Follow(T) { , ), $ }Follow(T) Follow(T) { , ), $ }Follow(F) First(T)除去ε后得到 { * }再加上Follow(T) { , ), $ }所以Follow(F) { *, , ), $ }。我当时做完这套手算最大的感受是Follow集合的“传递”路径很容易漏。尤其是E在末尾时必须要把Follow(E)传给Follow(E)再把Follow(E)传给Follow(T)一环扣一环。建议每算完一个非终结符就把它“被谁引用、出现在哪个产生式的哪个位置”标在纸上这样不会漏。3.3 判断LL(1)文法与构造预测分析表拿到First和Follow集合以后判断LL(1)要检查两件事第一同一非终结符的任意两条产生式 A → α 和 A → β必须满足 First(α) ∩ First(β) ∅第二如果其中某条产生式能推导出ε即α或β可为空那么 First(α) ∩ Follow(A) ∅ 或 First(β) ∩ Follow(A) ∅不能有交集。上面这个消除左递归后的文法满足这两个条件是LL(1)文法。构造预测分析表时用“填写规则”对产生式 A → α遍历First(α)中的每个终结符a把该产生式写入 M[A, a]如果First(α)中包含ε则遍历Follow(A)中的每个终结符b包括 $把该产生式写入 M[A, b]表中其余格子留空表示语法错误。很多同学会问预测分析表里的冲突和LL(1)条件不是一回事吗其实是两个角度。LL(1)条件是从文法本身能否无回溯地分析来定义预测分析表则把这个条件落实到具体的表格上。如果表里某个格出现两个产生式就叫“多重定义”说明文法不是LL(1)。考试时把这个对应关系答上阅卷老师一眼就能看出你是真懂还是背概念。4. LR分析从0到1项目集规范族、ACTION/GOTO表与冲突处理4.1 LR(0)项目集到底是干嘛的LR分析是习题三里最让人头疼的部分因为它的计算过程比LL(1)长得多。LR分析的基本思想是“自底向上”从输入串开始不断规约到文法的开始符号。LR分析器要知道每一步是“移进”还是“规约”就需要根据当前状态和输入符号查ACTION表。而这个“状态”是怎么来的答案是由LR(0)项目集规范族决定。什么是LR(0)项目就是在产生式右部的某个位置加一个圆点。比如产生式E → E T可以有四个项目E → .ET、E → E.T、E → E.T、E → ET.。圆点在右部最右端的项目叫“规约项目”意味着这个产生式的所有符号都已经读完可以进行规约。项目集规范族的构造分为两步求闭包和求转移。求闭包时对任何一个形如A → α. Bβ的项目把B → .γ这样的所有项目加入当前项目集直到不再增加求转移时对项目集中所有圆点后面跟着同一个符号X的项目把圆点向右移动一位再对新项目集求闭包。重复这两步就能得到整个LR(0)自动机。4.2 手算项目集时我用的“三层表格法”因为状态多、符号多手算很容易漏状态。我自己的做法是用一个三层表格第一层是项目集编号第二层是项目集内容第三层是每个输入符号对应的转移方向。每次从某个项目集出发分别看终结符和非终结符的转移新增的状态统一编号。这样最后生成ACTION/GOTO表时直接对照转移关系填写就行。以文法E → E T | T、T → id为例简化版本初始项目集I0包含E → .E 增广文法E → .E TE → .TT → .id从I0出发看各个符号的转移读入E后得到项目集I1读入T后得到I2读入id后得到I3。之后继续对I1、I2、I3求闭包和转移慢慢就把整个状态图铺出来了。我第一次手算时用了整整两页草稿纸期间因为某次闭包漏了一个项目导致后面全错后来老老实实把“每求一次闭包就划掉一个项目”作为规范动作才不再出这种低级错误。4.3 SLR(1)怎么用Follow集合解决冲突真正让人犯晕的是SLR(1)和LR(1)的区别。很多同学以为SLR(1)就是“LR(0)再加上Follow集合”原理上没错但理解不能停留在表面。SLR(1)在出现“移进-规约冲突”时会去看当前输入符号是否在某个规约项目的Follow集合里如果在该Follow集合中就规约如果不在就移进。正是这一条“向前看一个符号”的规则让SLR(1)比LR(0)能处理更多文法。习题三里很可能给你一个会产生冲突的文法问你是“移进-规约冲突”还是“规约-规约冲突”以及如何解决。我的经验是遇到这类判断题先画出项目集找出同一状态里同时存在“移进项目”和“规约项目”的情况再用Follow集合和当前输入符号做一次“选择”。回答时要把“哪些输入符号可以规约”写出来不能只写“存在冲突”四个字。4.4 LR(1)与LALR的考点向前看符号和合并同心项目集LR(1)比SLR(1)更精确区别在于每个项目除了产生式位置外还带了一个向前看符号形如A → α.β, a。这样规约时不仅查Follow(A)而是查由推导路径决定的具体向前看符号集合判断更精确。但这也导致状态数量爆炸。LALR方法就是把所有“同心项目集”即LR(0)项目相同、只是向前看符号不同的项目集合并起来减少状态数。考试一般不要求手算一个完整的LR(1)项目集规范族太费时间但很可能考概念和简化例子。比如给你两个LR(1)项目问能否合并或者给你一个LALR合并后的状态问合并后是否可能产生规约-规约冲突。这个知识点我在复习时特别容易忽略因为前面LL(1)和SLR(1)已经花了太多精力到LR(1)时就有点力不从心。但恰恰是这种“最后一点内容”最容易在期末大题里露脸所以建议还是花时间把LR(1)和LALR的对比好好整理一下。我刚整理了这份表格贴在复习笔记本的最后一页分析方法项目形式解决冲突的依据状态数量适用范围LR(0)A → α.β无向前看最少无冲突文法SLR(1)A → α.βFollow(A)与LR(0)相同多数程序设计语言LR(1)A → α.β, a特定向前看符号a最多所有LR(1)文法LALRA → α.β, a合并同心合并后的集合介于两者之间常见编译器中采用5. 语法制导翻译与中间代码属性文法、三地址码的实战套路5.1 综合属性和继承属性怎么判断到了语法制导翻译这章题目风格又不太一样了它不再让你画自动机、算集合而是给一个文法和一组语义规则让你写出每个产生式的语义动作或者判断某个属性是综合属性还是继承属性。判断的依据其实很朴素综合属性是在产生式左部非终结符上计算的属性它的值由右部非终结符或终结符的属性决定继承属性是在产生式右部非终结符上计算的属性它的值由产生式左部非终结符及右部其他符号的属性决定。我复习这部分时最大的困惑是明明属性定义都背下来了做题还是容易错。后来发现我的问题出在“没有把属性附在语法树上”。综合属性相当于语法树中自底向上的信息流继承属性是自顶向下和从左到右的信息流。在画了语法树之后每条属性都对应一条“从哪个节点到哪个节点”的箭头。箭头从子节点到父节点就是综合属性从父节点到子节点或从左兄弟到右兄弟就是继承属性。这样一来判断属性类型就不需要背定义看箭头方向就行。5.2 典型翻译模式把表达式变成三地址码习题三很可能给出类似E → E T的翻译规则让你为某个表达式生成中间代码。这里最常用的是语法制导定义SDD或翻译模式SDT。比如E → E1 T { E.place newtemp(); emit(E.place, :, E1.place, , T.place); } E → T { E.place T.place; } T → id { T.place id.place; }如果给的是a b * c按自上而下的推导先生成一个临时变量比如t1保存b * c再生成t2保存t1 a。这个过程中最重要的一点是不要试图把整棵语法树都画完再生成代码而是边归约边生成。因为三地址码本质上就是“遍历语法树的逆波兰式变形”语义动作在什么时候执行直接影响临时变量的顺序。5.3 四元式、三元式和间接三元式别混淆中间代码这一章的对比题几乎是期末必考而且习题三很可能会用一张表让你写出某个四元式序列对应的三元式序列。三种形式的本质差别在于“如何表示运算结果”四元式(op, arg1, arg2, result)结果用临时变量或变量名表示编译器在符号表里为它分配位置三元式(op, arg1, arg2)用“第几条三元式的结果”来引用运算结果所以经常写(1)这种形式间接三元式在三元式外面加一张间接码表方便代码优化时移动或删除三元式而不用修改所有引用。我做过一道真题给表达式a b * c d生成中间代码要求分别写出四元式和三元式。四元式版本生成两个结果(*, b, c, t1)和(, t1, d, a)。三元式版本则是(1) (*, b, c)(2) (, (1), d)最后赋值时引用第2条三元式的结果。很多同学把三元式里的(1)写成t1这就是把四元式和三元式混为一谈了一扣分。注意考试时如果要求“指出四元式与三元式的主要区别”一定要提到“三元式通过位置引用结果优化时修改困难所以引入间接三元式”这三点缺一不可。6. 运行时环境与代码优化容易被忽略的两块“稳定送分题”6.1 活动记录与栈式分配把过程调用想成“压箱底”运行时环境这一章看起来偏理论但习题三最喜欢出简答题或填空题考察活动记录的结构、栈式分配的过程、以及堆与栈的区别。我一开始总记不住活动记录里有哪些字段后来换了个生活化的类比才记住每次函数调用就像“往行李箱里塞一层东西”调用结束就把这一层拿掉。这一层东西就是活动记录里面至少包含返回值、实参、控制链指向调用者的活动记录、返回地址、局部变量和临时变量。栈式分配就是为每次过程调用在栈顶压入一个新的活动记录。递归调用时每一层都有自己的活动记录互不干扰这也是递归能正确返回的原因。考试里如果给出一段含递归调用的C函数代码问你运行时栈的变化情况千万不要只看代码逻辑要画出每次调用的活动记录压栈、出栈过程。6.2 基本块划分与DAG局部优化的基本功代码优化章节中最容易出大题的是“划分基本块并用DAG进行局部优化”。基本块的划分规则是先找出入口语句——第一条语句、跳转目标语句、跳转指令之后的语句都算入口。从入口语句到下一个入口语句之前的部分就是一个基本块。这个概念考试时一定要答得完整少一个入口类型都会扣分。DAG有向无环图的应用是把基本块中的每个运算表示成节点公共子表达式会被合并。比如a b c; d b c;在DAG中只会出现一个b c节点优化时就只会计算一次。我当时复习时专门练了“从基本块构造DAG再从DAG重写基本块”的题目因为这类题目完全按固定流程走多加练习基本不会失分。6.3 优化不能改变语义这条“红线”别踩最后提一个判断题高发区循环优化包括代码外提、强度削减、删除归纳变量这些优化在考试中经常要求“指出是否合法”。判断原则只有一条优化后的程序和原程序在“可观察行为”上必须保持一致。如果一个变量在循环内被多次赋值不能为了减少计算就把它提到循环外除非能证明它在循环内的所有取值都相同。我刷习题三时遇到过一道很刁的题把一个在循环内频繁使用的地址计算公式外提但循环内除了这个地址还有对同一数组的写操作如果外提时没有考虑到数组元素的访问顺序就会改变程序结果。当时做错了复盘才明白优化不仅要看数据流还要看指针别名、函数调用副作用这些问题。期末复习不需要做完整的数据流分析但至少要有“优化必须保证语义等价”的意识。7. 高频失分点与冲刺复习节奏一张清单帮你把习题三吃透7.1 最容易丢分的五个细节把习题三和我以前做过的期末题放在一起看失分点高度集中在以下几个地方。我把它们整理成了一张速查表考前看一遍特别管用失分点典型错误正确做法Follow集合漏传E在末尾时漏掉Follow(E)每算完一个非终结符检查所有产生式右部末尾NFA转DFA忘取ε闭包只取直接可达状态每走一步必须对结果集合求ε闭包DFA最小化前不删不可达状态多一个孤立状态导致分组错先删除所有“从初态不可达”的状态预测分析表里漏ε产生式忘了向Follow集合对应格子填写First含ε时遍历Follow填表LR(1)与LALR混为一谈认为LALR只是LR(1)子集明确LALR是合并同心项目集后的等价状态7.2 我的刷题方法三轮渐进距离考试还有两周时我一般把习题三的复习分成三轮。第一轮不看答案把每道大题从头到尾写一遍卡壳的地方做标记。第二轮只看标记过的题目对着教材和PPT把对应知识点重新过一遍然后合上书再来一遍。第三轮考前两天把所有大题的类型和规范流程写在A4纸上比如“求First/Follow四步走”“LR项目集三张表”“DAG重写基本块六步”每天默写一次。这个方法的核心在于“输出式复习”。只看书不动笔你永远不知道自己在哪一步会卡住。我第一遍做习题三的时候很多题看着都会真正动笔才发现问题一堆Follow集合漏了一个符号、LR项目集的闭包算少了、三地址码emit顺序反了。这些问题靠眼睛是发现不了的必须靠手。7.3 考前最后一天做什么考前最后一天我不建议再去钻偏题怪题而是回归三件小事第一把LR(0)项目集规范族的构造流程在纸上完整默写一遍这是多数人最不熟练的部分第二把First/Follow集合的定义和计算规则背一遍注意“First集合可以有εFollow集合永远没有”这种细节第三把四元式、三元式、间接三元式各写一个例子确保考场上能在两分钟内写出规范的格式。顺便说一句这门课期末笔试的题量通常不小手算LR项目集会消耗大量时间。我建议拿到试卷先把会做的题做了给最后那道大题留足30分钟以上。如果某道题的推导过程特别长一定要在草稿纸上标好状态编号免得誊写时抄串行。最后再分享一个我自己觉得特别管用的小习惯每次做完一道手算题别急着对答案先自己检查一遍边界的处理。比如求Follow集合时检查一下开始符号的Follow里有没有 $填预测分析表时检查一下每个非终结符对应Follow集合里的符号有没有被漏填构造LR项目集时检查一下有没有项目因为闭包运算被重复加入。这些检查只需要花两分钟但真的能救回不少分数。编译原理的复习没有捷径但把这几步走扎实期末上考场时手感和心态都会不一样。