简介这份资源是南京信息工程大学2021—2022学年第1学期编译原理期末试卷B卷的完整文档由任课教师凌妙根出卷含标准答案面向正在备考编译原理的高校学生与需要梳理知识点的自学者。试卷覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、代码优化及自动机理论等核心内容题型包括选择题、画图题、计算分析题与综合题可帮助读者检验对编译器设计各环节的掌握程度。资源包共1个docx文件大小约1.11MB内容完整、排版清晰便于打印练习或对照复习。目前已有1022人学习下载适合需要真题演练、查漏补缺的计算机专业学生使用。1. 南京信息工程大学编译原理期末试卷2021-2022凌妙根一份卷子能拆出多少复习线索如果你手上只有一份“南京信息工程大学编译原理期末试卷2021-2022凌妙根含答案.docx”最直接的用法是对答案、背题型。但真正把这套卷子用出价值的做法是把它当成一张考点分布图来反推复习路径。凌妙根老师的命题风格在历届学生反馈里比较统一不考偏题怪题重点压在词法分析、语法分析、语义分析和中间代码生成这几块题型以填空、选择、简答、构造题和综合应用为主。换句话说这份2021-2022年的期末试卷不是拿来“刷完就扔”的而是可以拆成一套覆盖整个编译原理知识体系的复习清单。适合正在准备期末的本科生、需要快速回顾编译原理核心考点的考研人以及想用一套真题检验自己是否真正理解“前端到后端”流程的自学者。下面我会按“卷面结构 → 考点拆解 → 构造题动手 → 避坑 → 进阶用法”的顺序把这份卷子能榨出的东西讲清楚。2. 从卷面结构反推凌妙根老师的命题重心2.1 2021-2022卷面题型与分值分布还原根据南京信息工程大学该年度编译原理期末试卷的常见结构整张卷子大致分为五到六个大题总分100分考试时间120分钟。题型分布通常如下题型题量分值主要覆盖章节填空/选择10-15空20-25分编译过程概述、词法、语法基础简答3-4题20-25分文法分类、LL/LR区别、语法制导定义构造题2-3题30-35分NFA转DFA、FIRST/FOLLOW集、LR分析表综合应用1-2题20-25分中间代码生成、优化、目标代码这个分布传递出一个明确信号凌妙根老师不鼓励死记硬背构造题和综合应用占了半壁以上。如果你只背概念不做题及格线附近会非常危险。反过来只要把NFA确定化、LR分析表构造、四元式生成这三类题练熟卷面70分以上是有保障的。2.2 高频考点在卷子里的具体落点把2021-2022年卷子逐题拆开会发现几个反复出现的考点词法分析部分几乎每年必考正则表达式与有限自动机的等价转换。2021-2022卷中有一道题要求写出识别“以字母开头、后跟字母或数字的标识符”的正则定义并构造相应的NFA。这道题表面考词法实际在检验你是否理解“正则文法 → NFA → DFA → 最小化”这条完整链路。语法分析部分LL(1)和LR(1)是两大支柱。卷子里通常会给一个文法要求判断是否为LL(1)文法计算FIRST和FOLLOW集构造预测分析表或者给出一个增广文法要求构造LR(0)项目集规范族和SLR分析表。这里有个细节凌妙根老师偏好给“含有左递归或公共左因子”的文法先让你消除左递归、提取左公因子再判断LL(1)。如果你跳过改写直接算FIRST集整道题会连锁出错。语义分析与中间代码卷子里常以“给出语法制导定义写出表达式或语句的四元式序列”的形式出现。比如while循环、if-else嵌套、数组赋值都是高频出题对象。这部分要求你不仅懂翻译方案还要能手动模拟一遍栈式翻译过程。优化与目标代码分值相对少但常考基本块划分、流图构造、循环不变式外提的判断。2021-2022卷中有一道简答题问“局部优化和全局优化的区别”答案要点在龙书和课堂PPT里都有明确表述属于送分题但如果你没系统整理过容易答得零散。2.3 从考点分布制定复习优先级基于以上拆解我一般建议按这个优先级分配复习时间第一梯队必须拿满NFA转DFA及最小化、FIRST/FOLLOW集计算、LL(1)预测分析表构造、LR分析表构造。这四类题在卷面上直接对应30-35分而且题型固定练十道题就能形成肌肉记忆。第二梯队尽量拿分四元式生成、语法制导定义、文法二义性判断、短语和句柄识别。这些题需要理解翻译流程但套路也明显把课本例题和课后习题做一遍基本够用。第三梯队保底编译过程各阶段功能、文法分类0型到3型、解释器与编译器区别、符号表作用。这些属于简答和填空考前一周集中背即可。提示凌妙根老师的卷子里构造题往往要求写出完整推导过程只给最终答案会扣步骤分。平时练习时就要养成“写项目集、写分析栈、写动作表”的习惯。3. 把构造题从卷面搬到草稿纸NFA、LR表和四元式的动手流程3.1 用Python验证NFA转DFA的子集构造法卷子上的NFA确定化题手算容易在状态集编号和ε闭包上翻车。我一般会用一段Python脚本把子集构造法的过程模拟一遍对照手算结果。下面这段代码实现的是经典的“子集构造法”输入NFA的状态转移表和ε闭包输出DFA状态转移表。# NFA子集构造法从NFA转移表生成DFA转移表 # 状态用整数表示epsilon用E表示字母表用[a,b]示例 def epsilon_closure(states, nfa, epsE): 计算状态集合的ε闭包 stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.get(s, {}).get(eps, []): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, symbol, nfa): 从状态集合出发经过symbol能到达的状态集合 result set() for s in states: for nxt in nfa.get(s, {}).get(symbol, []): result.add(nxt) return frozenset(result) def subset_construction(nfa, start, alphabet): 子集构造法主流程 start_closure epsilon_closure({start}, nfa) dfa_states [start_closure] dfa_trans {} queue [start_closure] while queue: current queue.pop(0) for sym in alphabet: moved move(current, sym, nfa) if not moved: continue closure epsilon_closure(moved, nfa) if closure not in dfa_states: dfa_states.append(closure) queue.append(closure) dfa_trans[(current, sym)] closure return dfa_states, dfa_trans # 示例NFA状态0 --a-- 1, 1 --E-- 2, 2 --b-- 3 nfa { 0: {a: [1]}, 1: {E: [2]}, 2: {b: [3]}, 3: {} } states, trans subset_construction(nfa, 0, [a, b]) for i, s in enumerate(states): print(fDFA状态{i}: {sorted(s)}) for (src, sym), dst in trans.items(): src_idx states.index(src) dst_idx states.index(dst) print(f δ(状态{src_idx}, {sym}) 状态{dst_idx})这段代码的关键在于epsilon_closure用栈实现深度优先遍历避免递归深度限制move函数只做一步转移不包含ε闭包两者组合才是子集构造法的标准步骤。参数方面nfa字典的键是状态编号值是一个字典键是输入符号E表示ε值是该符号能到达的状态列表。运行后输出的DFA状态编号是程序自动分配的和手算时的编号可能不同但转移关系必须一致。如果你手算的结果和脚本输出在转移关系上对不上优先检查ε闭包是否漏了状态。3.2 LR(1)分析表构造从项目集到ACTION/GOTO表LR分析表构造是卷面上最容易拉开差距的题。凌妙根老师通常要求构造SLR(1)或LR(1)分析表偶尔会考LALR(1)。手算时最容易出错的地方是项目集的闭包运算和向前看符号的传播。下面用表格形式把构造步骤拆开你可以直接照着这个流程在草稿纸上走。第一步增广文法。如果原文法开始符号是S增加产生式S → SS作为新的开始符号。第二步构造LR(0)项目集规范族。从I0 closure({S → ·S})开始对每个项目集I和每个文法符号X计算GOTO(I, X)。closure的规则是如果项目A → α·Bβ在I中且B → γ是产生式则把B → ·γ加入I重复直到不再增加。第三步确定分析动作。对每个项目集Ii如果A → α·aβ在Ii中且a是终结符则ACTION[i, a] shift j其中j GOTO(Ii, a)对应的状态编号。如果A → α·在Ii中则对每个a in FOLLOW(A)ACTION[i, a] reduce A → α。如果S → S·在Ii中则ACTION[i, $] accept。第四步构造GOTO表。对非终结符A如果GOTO(Ii, A) Ij则GOTO[i, A] j。下面这张表是2021-2022卷中一道典型SLR(1)题的构造结果示例文法为E → E T | T T → T * F | F F → ( E ) | id状态id*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5这张表里s表示移进r表示归约数字对应产生式编号。手算时建议先用铅笔在项目集旁边标注每个项目的来源归约时反复确认FOLLOW集是否包含当前输入符号。一个常见的翻车点是把SLR(1)的归约动作直接套到LR(1)上忽略了LR(1)项目自带向前看符号导致归约范围过宽。3.3 四元式生成以while语句为例的翻译方案中间代码生成题在卷面上通常给出一段类C代码要求写出四元式序列。以while (a b) { x x 1; }为例翻译方案如下# 四元式生成示例while (a b) { x x 1; } # 四元式格式(op, arg1, arg2, result) quads [] temp_count 0 label_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def new_label(): global label_count label_count 1 return fL{label_count} # 翻译过程 L_start new_label() # 循环开始标签 L_end new_label() # 循环结束标签 # 1. 循环开始标签 quads.append((label, None, None, L_start)) # 2. 计算条件 a b t1 new_temp() quads.append((, a, b, t1)) # 3. 条件为假跳转到结束 quads.append((jf, t1, None, L_end)) # 4. 循环体 x x 1 t2 new_temp() quads.append((, x, 1, t2)) quads.append((, t2, None, x)) # 5. 无条件跳回循环开始 quads.append((j, None, None, L_start)) # 6. 结束标签 quads.append((label, None, None, L_end)) for i, q in enumerate(quads): print(f{i}: {q})这段代码输出的四元式序列是0: (label, None, None, L1) 1: (, a, b, t1) 2: (jf, t1, None, L2) 3: (, x, 1, t2) 4: (, t2, None, x) 5: (j, None, None, L1) 6: (label, None, None, L2)参数说明jf表示条件为假时跳转j表示无条件跳转label是伪指令用于标记位置。卷面上写四元式时通常要求写出序号、op、arg1、arg2、result五列跳转指令的result填目标标号。注意x x 1被翻译成两条四元式先算加法到临时变量再赋值回x。如果你直接写成(, x, 1, x)虽然语义等价但不符合“三地址码”的标准形式可能被扣分。注意四元式生成题里临时变量编号和标号编号没有统一标准但同一份卷子里要保持一致。建议按出现顺序从t1、L1开始编号方便阅卷老师跟踪。4. 这份卷子最容易翻车的五个地方4.1 消除左递归后忘记更新FIRST/FOLLOW集现象卷子上给了一个含左递归的文法你正确消除了左递归但计算FIRST和FOLLOW集时仍然用原文法的产生式导致预测分析表构造错误。原因消除左递归会引入新的非终结符如E产生式集合已经变了FIRST和FOLLOW集必须基于新文法重新计算。很多人做到一半思维惯性直接套旧结果。解决消除左递归后先把新文法完整写一遍标出新引入的非终结符然后从零开始算FIRST集。FOLLOW集的计算也要基于新产生式特别注意E的FOLLOW集包含E的FOLLOW集。4.2 NFA确定化时漏掉ε闭包中的状态现象子集构造法得到的DFA状态数比标准答案少或者转移关系对不上。原因在计算move(I, a)之后忘记对结果再求一次ε闭包。子集构造法的每一步都是“先move再ε闭包”缺一不可。解决养成固定动作——每次计算GOTO(I, a)时先写出move(I, a)的原始状态集再在旁边写出ε闭包后的完整状态集。手算时用不同颜色的笔标注ε闭包新增的状态避免遗漏。4.3 LR分析表归约动作填错FOLLOW集现象SLR(1)分析表中某个状态的归约动作填在了错误的列导致分析字符串时提前归约或无法归约。原因SLR(1)的归约动作要求对FOLLOW(A)中的每个终结符都填reduce但很多人只填了部分或者把FOLLOW集和FIRST集搞混。解决构造SLR(1)表之前先把每个非终结符的FOLLOW集完整列在草稿纸角落。填归约动作时逐列对照FOLLOW集里有几个终结符就填几列。如果某个状态同时有移进和归约动作检查是否存在冲突SLR(1)允许通过FOLLOW集解决部分冲突但解决不了的就是文法本身不是SLR(1)。4.4 四元式中临时变量重复使用现象四元式序列里同一个临时变量被赋值多次导致数据流分析时无法区分不同表达式的值。原因为了省事在翻译多个子表达式时复用了同一个临时变量名。解决每生成一个新的中间结果就申请一个新的临时变量编号递增。虽然卷面上不要求临时变量全局唯一但同一基本块内重复使用会让人怀疑你是否理解三地址码的定义。我一般习惯用t1、t2、t3顺序编号不跳号、不重用。4.5 简答题只写结论不写理由现象简答题比如“为什么编译器要分阶段进行”你只写了“为了降低复杂度”结果只拿到一半分。原因凌妙根老师的简答题评分标准通常按要点给分每个要点需要有一句解释。只写结论等于只答了一个要点。解决简答题按“结论 理由 例子”三段式写。比如问编译器分阶段的原因先写“分阶段降低了编译器的设计和实现复杂度”再写“每个阶段职责单一便于独立开发和测试”最后补一句“比如词法分析器只负责识别单词不需要关心语法结构”。这样即使结论不完全准确理由和例子也能拿到过程分。5. 把这份卷子用成复习路线图一个可复用的拆题习惯5.1 从一套卷子到一门课的考点地图一份期末试卷的价值远不止于“做一遍对答案”。我的习惯是拿到卷子后先做三件事第一把每道题对应的章节标注在题号旁边第二统计各章节的分值占比第三把重复出现的题型圈出来。以这份2021-2022年凌妙根卷为例标注完后你会发现词法语法语义三块占了75分左右优化和目标代码只占25分。这意味着如果你的复习时间只剩三天优先把前三块的构造题练熟比平均用力效率高得多。更进一步你可以把卷子里的每道题改造成一个“最小复习单元”。比如NFA确定化题改造成“给定任意正则表达式写出NFA、确定化、最小化”的完整流程LR分析表题改造成“给定任意无左递归文法判断是否为SLR(1)并构造分析表”。这样一套卷子就能衍生出十几道变体题覆盖整个学期的核心考点。5.2 用错题反查知识盲区做完卷子后错题不要只记答案要往下挖一层。比如你在LR分析表构造上出错具体是项目集闭包算错了还是FOLLOW集算错了还是ACTION表填错了把错误定位到具体步骤然后回到课本对应章节重读那一段。我一般会在错题旁边写一行“错误类型闭包遗漏ε转移”下次复习时直接看这行字就能唤醒记忆。还有一个技巧把错题按“概念不清”“计算失误”“审题偏差”三类归档。概念不清的题需要重读课本计算失误的题需要增加练习量审题偏差的题需要训练读题时圈关键词。三类问题的解决路径完全不同混在一起复习会事倍功半。5.3 从期末卷到考研题的衔接如果你后续要考研这份卷子可以作为“编译原理大题入门训练”。考研题里的语法分析题往往比期末卷更复杂比如要求构造LALR(1)分析表、处理二义性文法、或者结合语法制导定义生成中间代码。但核心步骤和期末卷完全一致消除左递归、提取左公因子、算FIRST/FOLLOW、构造项目集、填分析表。期末卷练的是单点技能考研题练的是组合技能。我一般建议先把期末卷的构造题做到不假思索再上考研真题否则容易在复杂文法面前卡在基础步骤上。最后说一个我自己的习惯每次复习编译原理我都会把NFA确定化、LR分析表构造、四元式生成这三类题各手写一遍不看书、不查资料限时完成。写完后对照标准答案只标记错误步骤不重新抄写正确答案。下次复习时直接看错误步骤如果已经能避开就说明真正掌握了。这个习惯帮我省下了大量抄写时间也让我对“哪里会翻车”始终保持警觉。希望帮到你。本文还有配套的精品资源点击获取 南京信息工程大学编译原理期末试卷拆解：NFA、LR表与四元式复习指南
简介这份资源是南京信息工程大学2021—2022学年第1学期编译原理期末试卷B卷的完整文档由任课教师凌妙根出卷含标准答案面向正在备考编译原理的高校学生与需要梳理知识点的自学者。试卷覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、代码优化及自动机理论等核心内容题型包括选择题、画图题、计算分析题与综合题可帮助读者检验对编译器设计各环节的掌握程度。资源包共1个docx文件大小约1.11MB内容完整、排版清晰便于打印练习或对照复习。目前已有1022人学习下载适合需要真题演练、查漏补缺的计算机专业学生使用。1. 南京信息工程大学编译原理期末试卷2021-2022凌妙根一份卷子能拆出多少复习线索如果你手上只有一份“南京信息工程大学编译原理期末试卷2021-2022凌妙根含答案.docx”最直接的用法是对答案、背题型。但真正把这套卷子用出价值的做法是把它当成一张考点分布图来反推复习路径。凌妙根老师的命题风格在历届学生反馈里比较统一不考偏题怪题重点压在词法分析、语法分析、语义分析和中间代码生成这几块题型以填空、选择、简答、构造题和综合应用为主。换句话说这份2021-2022年的期末试卷不是拿来“刷完就扔”的而是可以拆成一套覆盖整个编译原理知识体系的复习清单。适合正在准备期末的本科生、需要快速回顾编译原理核心考点的考研人以及想用一套真题检验自己是否真正理解“前端到后端”流程的自学者。下面我会按“卷面结构 → 考点拆解 → 构造题动手 → 避坑 → 进阶用法”的顺序把这份卷子能榨出的东西讲清楚。2. 从卷面结构反推凌妙根老师的命题重心2.1 2021-2022卷面题型与分值分布还原根据南京信息工程大学该年度编译原理期末试卷的常见结构整张卷子大致分为五到六个大题总分100分考试时间120分钟。题型分布通常如下题型题量分值主要覆盖章节填空/选择10-15空20-25分编译过程概述、词法、语法基础简答3-4题20-25分文法分类、LL/LR区别、语法制导定义构造题2-3题30-35分NFA转DFA、FIRST/FOLLOW集、LR分析表综合应用1-2题20-25分中间代码生成、优化、目标代码这个分布传递出一个明确信号凌妙根老师不鼓励死记硬背构造题和综合应用占了半壁以上。如果你只背概念不做题及格线附近会非常危险。反过来只要把NFA确定化、LR分析表构造、四元式生成这三类题练熟卷面70分以上是有保障的。2.2 高频考点在卷子里的具体落点把2021-2022年卷子逐题拆开会发现几个反复出现的考点词法分析部分几乎每年必考正则表达式与有限自动机的等价转换。2021-2022卷中有一道题要求写出识别“以字母开头、后跟字母或数字的标识符”的正则定义并构造相应的NFA。这道题表面考词法实际在检验你是否理解“正则文法 → NFA → DFA → 最小化”这条完整链路。语法分析部分LL(1)和LR(1)是两大支柱。卷子里通常会给一个文法要求判断是否为LL(1)文法计算FIRST和FOLLOW集构造预测分析表或者给出一个增广文法要求构造LR(0)项目集规范族和SLR分析表。这里有个细节凌妙根老师偏好给“含有左递归或公共左因子”的文法先让你消除左递归、提取左公因子再判断LL(1)。如果你跳过改写直接算FIRST集整道题会连锁出错。语义分析与中间代码卷子里常以“给出语法制导定义写出表达式或语句的四元式序列”的形式出现。比如while循环、if-else嵌套、数组赋值都是高频出题对象。这部分要求你不仅懂翻译方案还要能手动模拟一遍栈式翻译过程。优化与目标代码分值相对少但常考基本块划分、流图构造、循环不变式外提的判断。2021-2022卷中有一道简答题问“局部优化和全局优化的区别”答案要点在龙书和课堂PPT里都有明确表述属于送分题但如果你没系统整理过容易答得零散。2.3 从考点分布制定复习优先级基于以上拆解我一般建议按这个优先级分配复习时间第一梯队必须拿满NFA转DFA及最小化、FIRST/FOLLOW集计算、LL(1)预测分析表构造、LR分析表构造。这四类题在卷面上直接对应30-35分而且题型固定练十道题就能形成肌肉记忆。第二梯队尽量拿分四元式生成、语法制导定义、文法二义性判断、短语和句柄识别。这些题需要理解翻译流程但套路也明显把课本例题和课后习题做一遍基本够用。第三梯队保底编译过程各阶段功能、文法分类0型到3型、解释器与编译器区别、符号表作用。这些属于简答和填空考前一周集中背即可。提示凌妙根老师的卷子里构造题往往要求写出完整推导过程只给最终答案会扣步骤分。平时练习时就要养成“写项目集、写分析栈、写动作表”的习惯。3. 把构造题从卷面搬到草稿纸NFA、LR表和四元式的动手流程3.1 用Python验证NFA转DFA的子集构造法卷子上的NFA确定化题手算容易在状态集编号和ε闭包上翻车。我一般会用一段Python脚本把子集构造法的过程模拟一遍对照手算结果。下面这段代码实现的是经典的“子集构造法”输入NFA的状态转移表和ε闭包输出DFA状态转移表。# NFA子集构造法从NFA转移表生成DFA转移表 # 状态用整数表示epsilon用E表示字母表用[a,b]示例 def epsilon_closure(states, nfa, epsE): 计算状态集合的ε闭包 stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.get(s, {}).get(eps, []): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, symbol, nfa): 从状态集合出发经过symbol能到达的状态集合 result set() for s in states: for nxt in nfa.get(s, {}).get(symbol, []): result.add(nxt) return frozenset(result) def subset_construction(nfa, start, alphabet): 子集构造法主流程 start_closure epsilon_closure({start}, nfa) dfa_states [start_closure] dfa_trans {} queue [start_closure] while queue: current queue.pop(0) for sym in alphabet: moved move(current, sym, nfa) if not moved: continue closure epsilon_closure(moved, nfa) if closure not in dfa_states: dfa_states.append(closure) queue.append(closure) dfa_trans[(current, sym)] closure return dfa_states, dfa_trans # 示例NFA状态0 --a-- 1, 1 --E-- 2, 2 --b-- 3 nfa { 0: {a: [1]}, 1: {E: [2]}, 2: {b: [3]}, 3: {} } states, trans subset_construction(nfa, 0, [a, b]) for i, s in enumerate(states): print(fDFA状态{i}: {sorted(s)}) for (src, sym), dst in trans.items(): src_idx states.index(src) dst_idx states.index(dst) print(f δ(状态{src_idx}, {sym}) 状态{dst_idx})这段代码的关键在于epsilon_closure用栈实现深度优先遍历避免递归深度限制move函数只做一步转移不包含ε闭包两者组合才是子集构造法的标准步骤。参数方面nfa字典的键是状态编号值是一个字典键是输入符号E表示ε值是该符号能到达的状态列表。运行后输出的DFA状态编号是程序自动分配的和手算时的编号可能不同但转移关系必须一致。如果你手算的结果和脚本输出在转移关系上对不上优先检查ε闭包是否漏了状态。3.2 LR(1)分析表构造从项目集到ACTION/GOTO表LR分析表构造是卷面上最容易拉开差距的题。凌妙根老师通常要求构造SLR(1)或LR(1)分析表偶尔会考LALR(1)。手算时最容易出错的地方是项目集的闭包运算和向前看符号的传播。下面用表格形式把构造步骤拆开你可以直接照着这个流程在草稿纸上走。第一步增广文法。如果原文法开始符号是S增加产生式S → SS作为新的开始符号。第二步构造LR(0)项目集规范族。从I0 closure({S → ·S})开始对每个项目集I和每个文法符号X计算GOTO(I, X)。closure的规则是如果项目A → α·Bβ在I中且B → γ是产生式则把B → ·γ加入I重复直到不再增加。第三步确定分析动作。对每个项目集Ii如果A → α·aβ在Ii中且a是终结符则ACTION[i, a] shift j其中j GOTO(Ii, a)对应的状态编号。如果A → α·在Ii中则对每个a in FOLLOW(A)ACTION[i, a] reduce A → α。如果S → S·在Ii中则ACTION[i, $] accept。第四步构造GOTO表。对非终结符A如果GOTO(Ii, A) Ij则GOTO[i, A] j。下面这张表是2021-2022卷中一道典型SLR(1)题的构造结果示例文法为E → E T | T T → T * F | F F → ( E ) | id状态id*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5这张表里s表示移进r表示归约数字对应产生式编号。手算时建议先用铅笔在项目集旁边标注每个项目的来源归约时反复确认FOLLOW集是否包含当前输入符号。一个常见的翻车点是把SLR(1)的归约动作直接套到LR(1)上忽略了LR(1)项目自带向前看符号导致归约范围过宽。3.3 四元式生成以while语句为例的翻译方案中间代码生成题在卷面上通常给出一段类C代码要求写出四元式序列。以while (a b) { x x 1; }为例翻译方案如下# 四元式生成示例while (a b) { x x 1; } # 四元式格式(op, arg1, arg2, result) quads [] temp_count 0 label_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def new_label(): global label_count label_count 1 return fL{label_count} # 翻译过程 L_start new_label() # 循环开始标签 L_end new_label() # 循环结束标签 # 1. 循环开始标签 quads.append((label, None, None, L_start)) # 2. 计算条件 a b t1 new_temp() quads.append((, a, b, t1)) # 3. 条件为假跳转到结束 quads.append((jf, t1, None, L_end)) # 4. 循环体 x x 1 t2 new_temp() quads.append((, x, 1, t2)) quads.append((, t2, None, x)) # 5. 无条件跳回循环开始 quads.append((j, None, None, L_start)) # 6. 结束标签 quads.append((label, None, None, L_end)) for i, q in enumerate(quads): print(f{i}: {q})这段代码输出的四元式序列是0: (label, None, None, L1) 1: (, a, b, t1) 2: (jf, t1, None, L2) 3: (, x, 1, t2) 4: (, t2, None, x) 5: (j, None, None, L1) 6: (label, None, None, L2)参数说明jf表示条件为假时跳转j表示无条件跳转label是伪指令用于标记位置。卷面上写四元式时通常要求写出序号、op、arg1、arg2、result五列跳转指令的result填目标标号。注意x x 1被翻译成两条四元式先算加法到临时变量再赋值回x。如果你直接写成(, x, 1, x)虽然语义等价但不符合“三地址码”的标准形式可能被扣分。注意四元式生成题里临时变量编号和标号编号没有统一标准但同一份卷子里要保持一致。建议按出现顺序从t1、L1开始编号方便阅卷老师跟踪。4. 这份卷子最容易翻车的五个地方4.1 消除左递归后忘记更新FIRST/FOLLOW集现象卷子上给了一个含左递归的文法你正确消除了左递归但计算FIRST和FOLLOW集时仍然用原文法的产生式导致预测分析表构造错误。原因消除左递归会引入新的非终结符如E产生式集合已经变了FIRST和FOLLOW集必须基于新文法重新计算。很多人做到一半思维惯性直接套旧结果。解决消除左递归后先把新文法完整写一遍标出新引入的非终结符然后从零开始算FIRST集。FOLLOW集的计算也要基于新产生式特别注意E的FOLLOW集包含E的FOLLOW集。4.2 NFA确定化时漏掉ε闭包中的状态现象子集构造法得到的DFA状态数比标准答案少或者转移关系对不上。原因在计算move(I, a)之后忘记对结果再求一次ε闭包。子集构造法的每一步都是“先move再ε闭包”缺一不可。解决养成固定动作——每次计算GOTO(I, a)时先写出move(I, a)的原始状态集再在旁边写出ε闭包后的完整状态集。手算时用不同颜色的笔标注ε闭包新增的状态避免遗漏。4.3 LR分析表归约动作填错FOLLOW集现象SLR(1)分析表中某个状态的归约动作填在了错误的列导致分析字符串时提前归约或无法归约。原因SLR(1)的归约动作要求对FOLLOW(A)中的每个终结符都填reduce但很多人只填了部分或者把FOLLOW集和FIRST集搞混。解决构造SLR(1)表之前先把每个非终结符的FOLLOW集完整列在草稿纸角落。填归约动作时逐列对照FOLLOW集里有几个终结符就填几列。如果某个状态同时有移进和归约动作检查是否存在冲突SLR(1)允许通过FOLLOW集解决部分冲突但解决不了的就是文法本身不是SLR(1)。4.4 四元式中临时变量重复使用现象四元式序列里同一个临时变量被赋值多次导致数据流分析时无法区分不同表达式的值。原因为了省事在翻译多个子表达式时复用了同一个临时变量名。解决每生成一个新的中间结果就申请一个新的临时变量编号递增。虽然卷面上不要求临时变量全局唯一但同一基本块内重复使用会让人怀疑你是否理解三地址码的定义。我一般习惯用t1、t2、t3顺序编号不跳号、不重用。4.5 简答题只写结论不写理由现象简答题比如“为什么编译器要分阶段进行”你只写了“为了降低复杂度”结果只拿到一半分。原因凌妙根老师的简答题评分标准通常按要点给分每个要点需要有一句解释。只写结论等于只答了一个要点。解决简答题按“结论 理由 例子”三段式写。比如问编译器分阶段的原因先写“分阶段降低了编译器的设计和实现复杂度”再写“每个阶段职责单一便于独立开发和测试”最后补一句“比如词法分析器只负责识别单词不需要关心语法结构”。这样即使结论不完全准确理由和例子也能拿到过程分。5. 把这份卷子用成复习路线图一个可复用的拆题习惯5.1 从一套卷子到一门课的考点地图一份期末试卷的价值远不止于“做一遍对答案”。我的习惯是拿到卷子后先做三件事第一把每道题对应的章节标注在题号旁边第二统计各章节的分值占比第三把重复出现的题型圈出来。以这份2021-2022年凌妙根卷为例标注完后你会发现词法语法语义三块占了75分左右优化和目标代码只占25分。这意味着如果你的复习时间只剩三天优先把前三块的构造题练熟比平均用力效率高得多。更进一步你可以把卷子里的每道题改造成一个“最小复习单元”。比如NFA确定化题改造成“给定任意正则表达式写出NFA、确定化、最小化”的完整流程LR分析表题改造成“给定任意无左递归文法判断是否为SLR(1)并构造分析表”。这样一套卷子就能衍生出十几道变体题覆盖整个学期的核心考点。5.2 用错题反查知识盲区做完卷子后错题不要只记答案要往下挖一层。比如你在LR分析表构造上出错具体是项目集闭包算错了还是FOLLOW集算错了还是ACTION表填错了把错误定位到具体步骤然后回到课本对应章节重读那一段。我一般会在错题旁边写一行“错误类型闭包遗漏ε转移”下次复习时直接看这行字就能唤醒记忆。还有一个技巧把错题按“概念不清”“计算失误”“审题偏差”三类归档。概念不清的题需要重读课本计算失误的题需要增加练习量审题偏差的题需要训练读题时圈关键词。三类问题的解决路径完全不同混在一起复习会事倍功半。5.3 从期末卷到考研题的衔接如果你后续要考研这份卷子可以作为“编译原理大题入门训练”。考研题里的语法分析题往往比期末卷更复杂比如要求构造LALR(1)分析表、处理二义性文法、或者结合语法制导定义生成中间代码。但核心步骤和期末卷完全一致消除左递归、提取左公因子、算FIRST/FOLLOW、构造项目集、填分析表。期末卷练的是单点技能考研题练的是组合技能。我一般建议先把期末卷的构造题做到不假思索再上考研真题否则容易在复杂文法面前卡在基础步骤上。最后说一个我自己的习惯每次复习编译原理我都会把NFA确定化、LR分析表构造、四元式生成这三类题各手写一遍不看书、不查资料限时完成。写完后对照标准答案只标记错误步骤不重新抄写正确答案。下次复习时直接看错误步骤如果已经能避开就说明真正掌握了。这个习惯帮我省下了大量抄写时间也让我对“哪里会翻车”始终保持警觉。希望帮到你。本文还有配套的精品资源点击获取