简介常州工学院《编译原理》试卷A是面向计算机科学与技术及相关专业学生的期末复习资料覆盖编译原理课程中词法分析、语法分析、语义分析与中间代码生成等核心模块。试卷包含正规表达式与最简DFA构造、逆波兰表示、文法二义性证明、LL(1)文法判定及预测分析表构建、条件语句四元式序列翻译等经典题型题型设置贴近教学重点适合备考期末或自测掌握程度。压缩包仅含1个doc文档大小55KB打开即可查看完整试卷内容便于打印或对照学习。目前已有391人学习下载被不少同类课程学习者参考。通过完整作答这些题目读者可以系统训练有限自动机、First/Follow集计算、预测分析等关键技能加深对自顶向下语法分析及中间代码生成的理解是一份针对性较强的练习材料。1. 一份编译原理试卷A考的不是背概念是这几条主线拿到一份某高校的《编译原理》试卷A很多人的第一反应是背概念什么是句柄、什么是活前缀、什么叫回填。但真正上了考场才会发现这份试卷A的设计思路很清楚——概念题只占一小部分剩下的大题全都在考你能不能动手构造给你一个正则表达式你能不能画出DFA给你一个文法你能不能算出FIRST和FOLLOW给你一条语句你能不能写出中间代码。我见过不少同学定义背得很熟遇到构造题照样翻车。这份试卷A真正在考的不是“知不知道”而是“会不会做”。无论你是考前突击还是想拿高分只要把题型分布摸清、把每类题的标准解法练成肌肉记忆及格不难高分也有明确路径。下面按我这些年刷题和带人的经验把试卷A的拆解、做题顺序和踩坑点一次讲透。2. 试卷结构拆解先搞清楚A卷在考什么再决定怎么复习一份试卷A拿到手先别急着刷题。我一般会花半小时把整张卷子的题型、分值和知识点分布画成一张表然后照表分配复习时间。这样比盲目刷三遍历年题高效得多。2.1 常见题型分布与分值逻辑不同学校的试卷结构会有差异但编译原理的考查骨架高度一致。我按常见的工科院校试卷A归纳通常分为以下几块题型常考内容分值占比复习优先级选择题/填空题基本概念、编译阶段、形式语言分类15% - 20%低考前过一遍即可简答题编译器结构、各阶段任务、符号表作用10% - 15%低背要点词法分析大题正则表达式转NFA/DFA、DFA最小化15% - 20%高必须能手算语法分析大题FIRST/FOLLOW、LL(1)预测分析表、LR项目集25% - 30%高最拉分语义分析与中间代码语法制导翻译、三地址码、回填15% - 20%高易错但套路固定代码优化题基本块划分、DAG、循环优化5% - 10%中锦上添花这个分值逻辑说明一件事语法分析永远是试卷A的“心脏”。语法分析大题一旦做错后面语义分析和中间代码题往往也会连带出错因为中间代码生成是建立在语法分析树之上的。所以复习顺序必须是“词法 → 语法 → 语义”不能跳也不能只背概念。2.2 从试卷A反推考纲哪些知识点是必考主干我把近十年的试卷A考点做了一次归并发现必考主干非常稳定词法分析三件套正则表达式、NFA、DFA之间的转换以及DFA最小化自顶向下分析FIRST集合、FOLLOW集合、LL(1)文法的判断和预测分析表构造自底向上分析LR(0)项目集规范族、SLR(1)分析表的构造或者LR(1)项目集的区分语法制导翻译在产生式右部合适位置插入语义动作生成三地址码布尔表达式与控制流语句的回填技术中间代码的常见形式四元式、三元式、间接三元式、三地址码的相互转换。反推之后你会发现试卷A不爱考偏门优化算法重点全在编译前端。这跟课堂教学的课时分配是一致的大部分学校把精力放在词法、语法、语义这三条主线上后端优化只讲基础。所以复习时不要钻牛角尖去啃全局优化的复杂算法把前端题型练熟分数就到手了八成。2.3 用真题跑一遍复习节奏我一般建议按三轮走每轮目标不同轮次目标具体操作时间占比第一轮暴露短板不看答案限时做一份真题标记所有卡壳的题20%第二轮题型专练按“词法/语法/语义”分块刷题每块吃透再换下一块50%第三轮模考提速整卷限时模拟重点练计算速度和检查习惯30%第一轮的作用是让你知道“哪类题一看就慌”。我见过太多同学从第一章开始背教材背到第四章才发现时间不够这是典型的没做诊断。真题是第一手的诊断工具哪怕做得一塌糊涂也没关系你只需要记下哪道题卡了五分钟以上。第二轮就照着卡壳点去补。第三轮必须严格限时因为编译原理题目计算量大尤其LR项目集和FIRST/FOLLOW一道题就可能耗掉二十分钟平时不限时考场必翻车。3. 词法与语法分析把正则、NFA/DFA、LL(1)、LR这几个硬骨头逐个啃透词法和语法这两章是试卷A的绝对主力也是新手最容易“看着懂、算不对”的部分。这里没有玄学全是固定算法。我把每个题型的做题模板拆开讲。3.1 词法正则表达式转NFA/DFA的做题模板试卷A最常见的词法题是给定一个正则表达式要求先构造NFA再用子集构造法转成DFA最后最小化。这个题型分值高但完全是机械步骤。第一步画NFA。按优先级从高到低展开先处理括号内的“或”再处理连接最后处理闭包。每处理一个运算符就引入新的状态。常见做法是引入两个状态用ε边连接子表达式。这里有个小技巧不要把ε转移画得满天飞尽量让状态编号有序后面做子集构造时不容易看错。第二步子集构造法。先求初始状态的ε闭包作为DFA的初始状态然后对每个DFA状态逐个读入每个输入符号求转移后的ε闭包。这一步必须写成表格DFA状态ε闭包输入a输入bA{0,1,2}{3,4,5}...............表格行每新增一个状态就追加一行直到没有新状态出现。注意这里最容易漏的是“已经出现过的状态集合”不加新编号。我一般会把状态集合写成有序列表比如{1,2,3}这样比对是否重复时不会乱。第三步DFA最小化。先把状态分成终态和非终态两组然后反复划分对每一组看它们在每个输入符号下是否落入同一组如果某个符号落入不同组就把该状态拆出去。重复直到所有组不再变化。这个划分过程是试卷A的经典送分题但很多人在“看每个符号落入哪组”时把表格看串行导致整个最小化结果错误。这三步做完词法大题基本全对。唯一需要额外注意的是题目如果要求直接写DFA而不是先画NFA你可以跳步但考试时我建议仍然先在草稿纸上画NFA不要直接凭感觉写DFA因为人脑很难一步从正则表达式跳到正确DFA跳步必错。3.2 语法LL(1)的FIRST/FOLLOW计算与预测分析表LL(1)是试卷A第二道高频大题通常分四小问求FIRST集合、求FOLLOW集合、判断是否LL(1)文法、构造预测分析表。FIRST集合的计算口诀是“看产生式右部第一个符号”。如果是终结符直接加入如果是非终结符递归求它的FIRST如果非终结符能推导出ε还要继续看下一个符号。这里有个常见坑很多教材先讲非终结符的FIRST再讲终结符学生容易混。做题时我习惯用“自底向上”的方式先把所有能推出ε的非终结符标出来然后从最简单产生式开始逐个集合避免递归死循环。FOLLOW集合更麻烦。规则只有三条开始符号的FOLLOW加入结束符$产生式A→αBβ把FIRST(β)去掉ε加入FOLLOW(B)产生式A→αB或A→αBβ且β能推出ε则把FOLLOW(A)加入FOLLOW(B)。最容易错的是第三条很多人忘记“β能推出ε”这个条件。还有一种情况同一非终结符在多个产生式右部出现要分别处理每个位置漏一个就会导致FOLLOW集合不完整。预测分析表构造对每个产生式A→α计算FIRST(α)把产生式填入表中[A, FIRST(α)]如果FIRST(α)包含ε还要把产生式填入[A, FOLLOW(A)] 对应位置。矩阵的行是非终结符列是终结符加结束符。填完之后如果表中某个格子出现两个产生式说明不是LL(1)文法。很多同学试卷A失分就在这个判断上——前面FIRST/FOLLOW算错了后面判断和填表全错。所以这个题型的唯一解法是算完一个集合就检查一遍尤其是ε是否被漏掉或错加。3.3 LR分析LR(0)/SLR(1)的项目集闭包与移进-归约LR分析是试卷A难度天花板也是很多人的噩梦。其实只要掌握了项目集规范族的构造方法它比LL(1)更机械。常见考法是给出文法求LR(0)项目集规范族然后构造SLR(1)分析表。项目集构造的步骤先增广文法加入产生式S→S然后把初始项目S→·S放进I0求闭包。闭包操作是对项目A→α·Bβ把所有B→·γ项目加入当前状态。注意这里的点就是分析位置闭包只看点后面的非终结符不是看整个产生式。构造完项目集后要画状态转移图。每个状态读入一个符号终结符或非终结符后跳到下一个状态。这里我会用表格记录项目集项目内容输入符号转移状态I0S→·S, S→·aB, ...aI1I1...BI2SLR(1)分析表构造规则如果项目A→α·aβ属于状态Ik且a是终结符则在表[k, a]填“移进”转到对应状态如果项目A→α·属于状态Ik则对每个a属于FOLLOW(A)在表[k, a]填“归约”归约产生式编号如果项目S→S·属于状态Ik则在表[k, $]填“接受”。最常翻车的点是归约项目的FOLLOW集合算错或者漏掉某个终结符。还有LR(0)项目集中的“移进-归约冲突”和“归约-归约冲突”在一些文法中是正常的SLR(1)通过FOLLOW来解决部分冲突。但如果冲突无法解决题目就会让你说明它不是SLR(1)。这个判断逻辑一定要写在答题纸上能拿步骤分。做题时我强烈建议把每个项目集完整写出来不要只写编号否则状态转移时容易对不上。阅卷时看的就是过程完整性跳步丢了中间步骤即使答案对也可能被扣分。4. 语义分析与中间代码语法制导翻译和三地址码的得分套路试卷A从语法分析往下走就到了语义分析和中间代码。这块的分值不如语法高但题型固定只要背住几个翻译模板得分率极高。它也是“背了就能写写了就能得分”的部分没有太多弯弯绕。4.1 语法制导定义与翻译方案语法制导翻译的题目通常给一个产生式集合要求写出每个产生式对应的语义动作。这里要分清楚两个概念语法制导定义SDD是给每个产生式绑定属性和计算规则翻译方案SDT是把语义动作显式地插入产生式右部某个位置。考试中常见的是SDT。关键在“动作插入位置”对计算综合属性的动作比如生成中间代码一般放在产生式右部末尾如果是继承属性需要放在相应非终结符的左边确保属性在被使用前已经计算。例如产生式E → E1 T对应生成中间代码的动作应该放在末尾E → E1 T { 生成四元式: (add, E1.place, T.place, E.place) }动作花括号里的代码就是语义动作。很多同学把动作写成独立步骤不看位置这会导致继承属性使用时报“未定义”或者把生成顺序搞错。做题时要先标出每个非终结符的属性和每个动作依赖的属性再决定插入位置。4.2 声明语句与赋值语句的中间代码生成试卷A常见的中间代码题型是给定一段类C代码要求写出对应的三地址码或四元式。这类题就是套模板。赋值语句x a b * c先生成t1 b * c再生成t2 a t1最后x t2。每一步都要引入新的临时变量。我总结的生成顺序是从运算优先级最低的运算符开始分解。先找到赋值号右边的整体表达式按“最外层运算最后生成”的逆序处理。优先考虑括号、数组下标、函数调用等特殊形式。对于声明语句int a[10]的中间代码除了要记录变量名和类型还要生成数组首地址、元素大小等属性。如果题目要求写出符号表内容则要给出变量名、类型、作用域、偏移量等字段。这里有个细节数组元素访问a[i]的中间代码生成需要先计算i * ww为元素宽度再与数组基地址相加得到实际访问地址。这步很多人漏了乘以元素宽度导致地址计算错误。4.3 数组、布尔表达式的回填技术重点难点回填技术是试卷A一道典型的压轴题。它解决的是生成跳转指令时跳转目标还不知道先留空等已知后回填。常见题型是给一个布尔表达式或if-else语句要求用回填方式生成中间代码。以布尔表达式a b || c d为例需要为每个条件生成一条条件跳转或无条件跳转指令并用链表记录待回填指令序号。做题时我习惯先画出控制流结构短路计算下||左操作数为真时跳过右操作数直接跳转到“真出口”左操作数为假时才继续计算右操作数。回填的步骤可以写成伪代码// 产生式: B → B1 || B2 // B1.code 之后, 生成跳转指令: if false, B1.false 链表, 跳转到 B2.code // 用 nextquad 记录当前四元式序号 backpatch(B1.false, B2.code_start); // 把B1为假的跳转目标填成B2的起始处 B.false merge(B1.false_after_backpatch, B2.false); // 真出口合并: B.true merge(B1.true, B2.true);这段伪代码里的merge是在合并两个跳转指令链表。实际考试中要求写四元式序列并在需要回填的地方标出“待回填”。最容易错的是先把所有跳转指令都生成了然后回填时把真出口和假出口弄反。所以我会在草稿上先画出“真出口”和“假出口”两个集合再把指令序号填进去最后写正式答案。这个方法虽然慢但几乎不会错。5. 编译原理试卷A的避坑清单5个高频失分点与排查方法这部分写的是我在历年试卷A上反复看到的高频失分点每一条都按“现象 → 原因 → 解决”来梳理考前对照这个清单自查能少丢一截冤枉分。5.1 现象FIRST/FOLLOW算错还查不出来很多同学算完FIRST/FOLLOW对答案时发现差一两个元素但怎么也找不到错在哪。原因是把“非终结符能推出ε”这个条件漏了或者求FOLLOW时没有把产生式中同一非终结符的所有出现位置都遍历到。解决方法是在草稿上把每个非终结符的“可空性”先列表标出比如A → ε | AB先标A可空再求FIRST求FOLLOW时逐个扫产生式右部遇到目标非终结符就停一下检查它后面紧跟什么以及整个余串是否可空。按这个顺序走一遍就不会漏。5.2 现象LR项目集合并时丢掉闭包构造LR(0)项目集规范族时很多同学做完初始项目集I0后遇到状态转移就只写“点移动后的那个项目”忘记对新状态继续求闭包。比如状态Ik里有项目A → α·Bβ转移后得到状态Ij里面至少包含A → αB·β但还应该把所有B → ·γ项目加入Ij。原因是对“闭包”理解不深只当是复制项目。解决方法是每生成一个新项目集第一步就是求闭包闭包做完才允许做下一个符号的转移。用表格管理每行状态生成后先写“闭包项目”再写“转移项目”两层分开写基本不会漏。5.3 现象语法制导翻译的语义动作位置写错题目让写SDT有同学把生成四元式的动作写在产生式右部最前面导致动作执行时属性还没计算完结果变成使用未初始化的属性。原因是把SDD的“计算规则”和SDT的“动作位置”混为一谈。解决方法是记住一条铁律涉及该产生式左部非终结符“综合属性”的动作必须放在右部所有符号之后涉及继承属性时动作要放在属性值来源符号的后面、使用符号的前面。实在拿不准时就先把每个属性的依赖关系画成有向图动作位置必须满足依赖序。5.4 现象回填技术里跳转目标记错布尔表达式回填是失分重灾区最常见的就是把false链表和true链表的回填目标搞反。原因是短路计算的语义理解不到位||中左操作数为真就直接得到真所以左操作数的“真出口”是整体真出口左操作数的“假出口”才指向右操作数则相反。解决方法是做题前先在答案区写两行真出口链表、假出口链表。每生成一个跳转指令就问自己“这条跳转在什么条件下发生”然后决定它应该进哪个链表。用这个自问法可以避开绝大多数回填错位。5.5 现象优化题把基本块边界画错代码优化题里如果需要划分基本块很多人在遇到转移指令后忘记结束当前块或者把紧随转移指令的标签错误地并入前一块。原因是基本块划分的三条规则只记住了两条入口语句是程序第一条、转移目标语句是入口、转移指令后的语句是入口。解决方法是先不理结构把代码按行号列出来逐行打标记只要某一行是跳转/条件跳转它之后的第一个标签行必须另起基本块。标记完后再把每个基本块内部的三地址码列出来最后画程序流图。这样边界就不会画错。6. 把一份试卷A变成复习工具错题归因与两遍刷题法试卷A不只是一份考试题它其实是一套很好的复习工具。我自己的习惯是每一份真题做完不只对答案而是把错题分成三类——计算错误、步骤缺失、概念混淆。计算错误比如FIRST集合少算一个元素这类错多练一遍就行步骤缺失比如LR项目集没有求闭包说明算法流程不熟概念混淆比如分不清综合属性和继承属性必须回去翻教材。每道错题在边上标一个类别复习第二轮时只看标了“概念混淆”的题效率比从头做一遍高得多。第二遍刷题时我不建议整卷重做而是按题型做“限时单题训练”。比如今天只练LR限时十五分钟做一道SLR(1)构造题做完立刻对照标准流程检查项目集有没有漏闭包、分析表有没有填错FOLLOW、冲突有没有判断。第二天只练回填第三只练中间代码。这种方法让大脑保持在“单一任务”模式比整卷混刷更能暴露深层问题。我见过很多同学一遍遍整卷刷分数始终停在及格线附近就是因为每次都在同样的地方错而自己没意识到。还有一个小技巧值得分享把试卷A中的构造题答案“倒着看”。比如看到最终的DFA尝试反推它的正则表达式看到预测分析表尝试反推它来自哪个文法。这个逆向练习特别能锻炼对算法约束的理解考场上遇到稍微变形的新题也不会慌。这比做十道同类型题更管用。最后想说的是编译原理虽然被很多人说抽象但试卷A的题型就那么几种公式和模板是死的。只要老老实实按这里的模板练两遍错题归类做好分数一定对得起你的付出。希望帮到你。本文还有配套的精品资源点击获取 编译原理试卷A题型拆解：词法语法分析与LL/LR考点备考攻略
简介常州工学院《编译原理》试卷A是面向计算机科学与技术及相关专业学生的期末复习资料覆盖编译原理课程中词法分析、语法分析、语义分析与中间代码生成等核心模块。试卷包含正规表达式与最简DFA构造、逆波兰表示、文法二义性证明、LL(1)文法判定及预测分析表构建、条件语句四元式序列翻译等经典题型题型设置贴近教学重点适合备考期末或自测掌握程度。压缩包仅含1个doc文档大小55KB打开即可查看完整试卷内容便于打印或对照学习。目前已有391人学习下载被不少同类课程学习者参考。通过完整作答这些题目读者可以系统训练有限自动机、First/Follow集计算、预测分析等关键技能加深对自顶向下语法分析及中间代码生成的理解是一份针对性较强的练习材料。1. 一份编译原理试卷A考的不是背概念是这几条主线拿到一份某高校的《编译原理》试卷A很多人的第一反应是背概念什么是句柄、什么是活前缀、什么叫回填。但真正上了考场才会发现这份试卷A的设计思路很清楚——概念题只占一小部分剩下的大题全都在考你能不能动手构造给你一个正则表达式你能不能画出DFA给你一个文法你能不能算出FIRST和FOLLOW给你一条语句你能不能写出中间代码。我见过不少同学定义背得很熟遇到构造题照样翻车。这份试卷A真正在考的不是“知不知道”而是“会不会做”。无论你是考前突击还是想拿高分只要把题型分布摸清、把每类题的标准解法练成肌肉记忆及格不难高分也有明确路径。下面按我这些年刷题和带人的经验把试卷A的拆解、做题顺序和踩坑点一次讲透。2. 试卷结构拆解先搞清楚A卷在考什么再决定怎么复习一份试卷A拿到手先别急着刷题。我一般会花半小时把整张卷子的题型、分值和知识点分布画成一张表然后照表分配复习时间。这样比盲目刷三遍历年题高效得多。2.1 常见题型分布与分值逻辑不同学校的试卷结构会有差异但编译原理的考查骨架高度一致。我按常见的工科院校试卷A归纳通常分为以下几块题型常考内容分值占比复习优先级选择题/填空题基本概念、编译阶段、形式语言分类15% - 20%低考前过一遍即可简答题编译器结构、各阶段任务、符号表作用10% - 15%低背要点词法分析大题正则表达式转NFA/DFA、DFA最小化15% - 20%高必须能手算语法分析大题FIRST/FOLLOW、LL(1)预测分析表、LR项目集25% - 30%高最拉分语义分析与中间代码语法制导翻译、三地址码、回填15% - 20%高易错但套路固定代码优化题基本块划分、DAG、循环优化5% - 10%中锦上添花这个分值逻辑说明一件事语法分析永远是试卷A的“心脏”。语法分析大题一旦做错后面语义分析和中间代码题往往也会连带出错因为中间代码生成是建立在语法分析树之上的。所以复习顺序必须是“词法 → 语法 → 语义”不能跳也不能只背概念。2.2 从试卷A反推考纲哪些知识点是必考主干我把近十年的试卷A考点做了一次归并发现必考主干非常稳定词法分析三件套正则表达式、NFA、DFA之间的转换以及DFA最小化自顶向下分析FIRST集合、FOLLOW集合、LL(1)文法的判断和预测分析表构造自底向上分析LR(0)项目集规范族、SLR(1)分析表的构造或者LR(1)项目集的区分语法制导翻译在产生式右部合适位置插入语义动作生成三地址码布尔表达式与控制流语句的回填技术中间代码的常见形式四元式、三元式、间接三元式、三地址码的相互转换。反推之后你会发现试卷A不爱考偏门优化算法重点全在编译前端。这跟课堂教学的课时分配是一致的大部分学校把精力放在词法、语法、语义这三条主线上后端优化只讲基础。所以复习时不要钻牛角尖去啃全局优化的复杂算法把前端题型练熟分数就到手了八成。2.3 用真题跑一遍复习节奏我一般建议按三轮走每轮目标不同轮次目标具体操作时间占比第一轮暴露短板不看答案限时做一份真题标记所有卡壳的题20%第二轮题型专练按“词法/语法/语义”分块刷题每块吃透再换下一块50%第三轮模考提速整卷限时模拟重点练计算速度和检查习惯30%第一轮的作用是让你知道“哪类题一看就慌”。我见过太多同学从第一章开始背教材背到第四章才发现时间不够这是典型的没做诊断。真题是第一手的诊断工具哪怕做得一塌糊涂也没关系你只需要记下哪道题卡了五分钟以上。第二轮就照着卡壳点去补。第三轮必须严格限时因为编译原理题目计算量大尤其LR项目集和FIRST/FOLLOW一道题就可能耗掉二十分钟平时不限时考场必翻车。3. 词法与语法分析把正则、NFA/DFA、LL(1)、LR这几个硬骨头逐个啃透词法和语法这两章是试卷A的绝对主力也是新手最容易“看着懂、算不对”的部分。这里没有玄学全是固定算法。我把每个题型的做题模板拆开讲。3.1 词法正则表达式转NFA/DFA的做题模板试卷A最常见的词法题是给定一个正则表达式要求先构造NFA再用子集构造法转成DFA最后最小化。这个题型分值高但完全是机械步骤。第一步画NFA。按优先级从高到低展开先处理括号内的“或”再处理连接最后处理闭包。每处理一个运算符就引入新的状态。常见做法是引入两个状态用ε边连接子表达式。这里有个小技巧不要把ε转移画得满天飞尽量让状态编号有序后面做子集构造时不容易看错。第二步子集构造法。先求初始状态的ε闭包作为DFA的初始状态然后对每个DFA状态逐个读入每个输入符号求转移后的ε闭包。这一步必须写成表格DFA状态ε闭包输入a输入bA{0,1,2}{3,4,5}...............表格行每新增一个状态就追加一行直到没有新状态出现。注意这里最容易漏的是“已经出现过的状态集合”不加新编号。我一般会把状态集合写成有序列表比如{1,2,3}这样比对是否重复时不会乱。第三步DFA最小化。先把状态分成终态和非终态两组然后反复划分对每一组看它们在每个输入符号下是否落入同一组如果某个符号落入不同组就把该状态拆出去。重复直到所有组不再变化。这个划分过程是试卷A的经典送分题但很多人在“看每个符号落入哪组”时把表格看串行导致整个最小化结果错误。这三步做完词法大题基本全对。唯一需要额外注意的是题目如果要求直接写DFA而不是先画NFA你可以跳步但考试时我建议仍然先在草稿纸上画NFA不要直接凭感觉写DFA因为人脑很难一步从正则表达式跳到正确DFA跳步必错。3.2 语法LL(1)的FIRST/FOLLOW计算与预测分析表LL(1)是试卷A第二道高频大题通常分四小问求FIRST集合、求FOLLOW集合、判断是否LL(1)文法、构造预测分析表。FIRST集合的计算口诀是“看产生式右部第一个符号”。如果是终结符直接加入如果是非终结符递归求它的FIRST如果非终结符能推导出ε还要继续看下一个符号。这里有个常见坑很多教材先讲非终结符的FIRST再讲终结符学生容易混。做题时我习惯用“自底向上”的方式先把所有能推出ε的非终结符标出来然后从最简单产生式开始逐个集合避免递归死循环。FOLLOW集合更麻烦。规则只有三条开始符号的FOLLOW加入结束符$产生式A→αBβ把FIRST(β)去掉ε加入FOLLOW(B)产生式A→αB或A→αBβ且β能推出ε则把FOLLOW(A)加入FOLLOW(B)。最容易错的是第三条很多人忘记“β能推出ε”这个条件。还有一种情况同一非终结符在多个产生式右部出现要分别处理每个位置漏一个就会导致FOLLOW集合不完整。预测分析表构造对每个产生式A→α计算FIRST(α)把产生式填入表中[A, FIRST(α)]如果FIRST(α)包含ε还要把产生式填入[A, FOLLOW(A)] 对应位置。矩阵的行是非终结符列是终结符加结束符。填完之后如果表中某个格子出现两个产生式说明不是LL(1)文法。很多同学试卷A失分就在这个判断上——前面FIRST/FOLLOW算错了后面判断和填表全错。所以这个题型的唯一解法是算完一个集合就检查一遍尤其是ε是否被漏掉或错加。3.3 LR分析LR(0)/SLR(1)的项目集闭包与移进-归约LR分析是试卷A难度天花板也是很多人的噩梦。其实只要掌握了项目集规范族的构造方法它比LL(1)更机械。常见考法是给出文法求LR(0)项目集规范族然后构造SLR(1)分析表。项目集构造的步骤先增广文法加入产生式S→S然后把初始项目S→·S放进I0求闭包。闭包操作是对项目A→α·Bβ把所有B→·γ项目加入当前状态。注意这里的点就是分析位置闭包只看点后面的非终结符不是看整个产生式。构造完项目集后要画状态转移图。每个状态读入一个符号终结符或非终结符后跳到下一个状态。这里我会用表格记录项目集项目内容输入符号转移状态I0S→·S, S→·aB, ...aI1I1...BI2SLR(1)分析表构造规则如果项目A→α·aβ属于状态Ik且a是终结符则在表[k, a]填“移进”转到对应状态如果项目A→α·属于状态Ik则对每个a属于FOLLOW(A)在表[k, a]填“归约”归约产生式编号如果项目S→S·属于状态Ik则在表[k, $]填“接受”。最常翻车的点是归约项目的FOLLOW集合算错或者漏掉某个终结符。还有LR(0)项目集中的“移进-归约冲突”和“归约-归约冲突”在一些文法中是正常的SLR(1)通过FOLLOW来解决部分冲突。但如果冲突无法解决题目就会让你说明它不是SLR(1)。这个判断逻辑一定要写在答题纸上能拿步骤分。做题时我强烈建议把每个项目集完整写出来不要只写编号否则状态转移时容易对不上。阅卷时看的就是过程完整性跳步丢了中间步骤即使答案对也可能被扣分。4. 语义分析与中间代码语法制导翻译和三地址码的得分套路试卷A从语法分析往下走就到了语义分析和中间代码。这块的分值不如语法高但题型固定只要背住几个翻译模板得分率极高。它也是“背了就能写写了就能得分”的部分没有太多弯弯绕。4.1 语法制导定义与翻译方案语法制导翻译的题目通常给一个产生式集合要求写出每个产生式对应的语义动作。这里要分清楚两个概念语法制导定义SDD是给每个产生式绑定属性和计算规则翻译方案SDT是把语义动作显式地插入产生式右部某个位置。考试中常见的是SDT。关键在“动作插入位置”对计算综合属性的动作比如生成中间代码一般放在产生式右部末尾如果是继承属性需要放在相应非终结符的左边确保属性在被使用前已经计算。例如产生式E → E1 T对应生成中间代码的动作应该放在末尾E → E1 T { 生成四元式: (add, E1.place, T.place, E.place) }动作花括号里的代码就是语义动作。很多同学把动作写成独立步骤不看位置这会导致继承属性使用时报“未定义”或者把生成顺序搞错。做题时要先标出每个非终结符的属性和每个动作依赖的属性再决定插入位置。4.2 声明语句与赋值语句的中间代码生成试卷A常见的中间代码题型是给定一段类C代码要求写出对应的三地址码或四元式。这类题就是套模板。赋值语句x a b * c先生成t1 b * c再生成t2 a t1最后x t2。每一步都要引入新的临时变量。我总结的生成顺序是从运算优先级最低的运算符开始分解。先找到赋值号右边的整体表达式按“最外层运算最后生成”的逆序处理。优先考虑括号、数组下标、函数调用等特殊形式。对于声明语句int a[10]的中间代码除了要记录变量名和类型还要生成数组首地址、元素大小等属性。如果题目要求写出符号表内容则要给出变量名、类型、作用域、偏移量等字段。这里有个细节数组元素访问a[i]的中间代码生成需要先计算i * ww为元素宽度再与数组基地址相加得到实际访问地址。这步很多人漏了乘以元素宽度导致地址计算错误。4.3 数组、布尔表达式的回填技术重点难点回填技术是试卷A一道典型的压轴题。它解决的是生成跳转指令时跳转目标还不知道先留空等已知后回填。常见题型是给一个布尔表达式或if-else语句要求用回填方式生成中间代码。以布尔表达式a b || c d为例需要为每个条件生成一条条件跳转或无条件跳转指令并用链表记录待回填指令序号。做题时我习惯先画出控制流结构短路计算下||左操作数为真时跳过右操作数直接跳转到“真出口”左操作数为假时才继续计算右操作数。回填的步骤可以写成伪代码// 产生式: B → B1 || B2 // B1.code 之后, 生成跳转指令: if false, B1.false 链表, 跳转到 B2.code // 用 nextquad 记录当前四元式序号 backpatch(B1.false, B2.code_start); // 把B1为假的跳转目标填成B2的起始处 B.false merge(B1.false_after_backpatch, B2.false); // 真出口合并: B.true merge(B1.true, B2.true);这段伪代码里的merge是在合并两个跳转指令链表。实际考试中要求写四元式序列并在需要回填的地方标出“待回填”。最容易错的是先把所有跳转指令都生成了然后回填时把真出口和假出口弄反。所以我会在草稿上先画出“真出口”和“假出口”两个集合再把指令序号填进去最后写正式答案。这个方法虽然慢但几乎不会错。5. 编译原理试卷A的避坑清单5个高频失分点与排查方法这部分写的是我在历年试卷A上反复看到的高频失分点每一条都按“现象 → 原因 → 解决”来梳理考前对照这个清单自查能少丢一截冤枉分。5.1 现象FIRST/FOLLOW算错还查不出来很多同学算完FIRST/FOLLOW对答案时发现差一两个元素但怎么也找不到错在哪。原因是把“非终结符能推出ε”这个条件漏了或者求FOLLOW时没有把产生式中同一非终结符的所有出现位置都遍历到。解决方法是在草稿上把每个非终结符的“可空性”先列表标出比如A → ε | AB先标A可空再求FIRST求FOLLOW时逐个扫产生式右部遇到目标非终结符就停一下检查它后面紧跟什么以及整个余串是否可空。按这个顺序走一遍就不会漏。5.2 现象LR项目集合并时丢掉闭包构造LR(0)项目集规范族时很多同学做完初始项目集I0后遇到状态转移就只写“点移动后的那个项目”忘记对新状态继续求闭包。比如状态Ik里有项目A → α·Bβ转移后得到状态Ij里面至少包含A → αB·β但还应该把所有B → ·γ项目加入Ij。原因是对“闭包”理解不深只当是复制项目。解决方法是每生成一个新项目集第一步就是求闭包闭包做完才允许做下一个符号的转移。用表格管理每行状态生成后先写“闭包项目”再写“转移项目”两层分开写基本不会漏。5.3 现象语法制导翻译的语义动作位置写错题目让写SDT有同学把生成四元式的动作写在产生式右部最前面导致动作执行时属性还没计算完结果变成使用未初始化的属性。原因是把SDD的“计算规则”和SDT的“动作位置”混为一谈。解决方法是记住一条铁律涉及该产生式左部非终结符“综合属性”的动作必须放在右部所有符号之后涉及继承属性时动作要放在属性值来源符号的后面、使用符号的前面。实在拿不准时就先把每个属性的依赖关系画成有向图动作位置必须满足依赖序。5.4 现象回填技术里跳转目标记错布尔表达式回填是失分重灾区最常见的就是把false链表和true链表的回填目标搞反。原因是短路计算的语义理解不到位||中左操作数为真就直接得到真所以左操作数的“真出口”是整体真出口左操作数的“假出口”才指向右操作数则相反。解决方法是做题前先在答案区写两行真出口链表、假出口链表。每生成一个跳转指令就问自己“这条跳转在什么条件下发生”然后决定它应该进哪个链表。用这个自问法可以避开绝大多数回填错位。5.5 现象优化题把基本块边界画错代码优化题里如果需要划分基本块很多人在遇到转移指令后忘记结束当前块或者把紧随转移指令的标签错误地并入前一块。原因是基本块划分的三条规则只记住了两条入口语句是程序第一条、转移目标语句是入口、转移指令后的语句是入口。解决方法是先不理结构把代码按行号列出来逐行打标记只要某一行是跳转/条件跳转它之后的第一个标签行必须另起基本块。标记完后再把每个基本块内部的三地址码列出来最后画程序流图。这样边界就不会画错。6. 把一份试卷A变成复习工具错题归因与两遍刷题法试卷A不只是一份考试题它其实是一套很好的复习工具。我自己的习惯是每一份真题做完不只对答案而是把错题分成三类——计算错误、步骤缺失、概念混淆。计算错误比如FIRST集合少算一个元素这类错多练一遍就行步骤缺失比如LR项目集没有求闭包说明算法流程不熟概念混淆比如分不清综合属性和继承属性必须回去翻教材。每道错题在边上标一个类别复习第二轮时只看标了“概念混淆”的题效率比从头做一遍高得多。第二遍刷题时我不建议整卷重做而是按题型做“限时单题训练”。比如今天只练LR限时十五分钟做一道SLR(1)构造题做完立刻对照标准流程检查项目集有没有漏闭包、分析表有没有填错FOLLOW、冲突有没有判断。第二天只练回填第三只练中间代码。这种方法让大脑保持在“单一任务”模式比整卷混刷更能暴露深层问题。我见过很多同学一遍遍整卷刷分数始终停在及格线附近就是因为每次都在同样的地方错而自己没意识到。还有一个小技巧值得分享把试卷A中的构造题答案“倒着看”。比如看到最终的DFA尝试反推它的正则表达式看到预测分析表尝试反推它来自哪个文法。这个逆向练习特别能锻炼对算法约束的理解考场上遇到稍微变形的新题也不会慌。这比做十道同类型题更管用。最后想说的是编译原理虽然被很多人说抽象但试卷A的题型就那么几种公式和模板是死的。只要老老实实按这里的模板练两遍错题归类做好分数一定对得起你的付出。希望帮到你。本文还有配套的精品资源点击获取