简介这份资源是南京信息工程大学2021—2022学年第一学期编译原理期末试卷B卷的完整文档由凌妙根老师出卷含标准答案面向正在备考编译原理的高校学生与需要梳理知识点的自学者。试卷覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、代码优化及自动机理论等核心内容题型包括选择题、画图题、计算分析题与综合题可帮助读者检验对编译器设计各环节的掌握程度。资源包共1个docx文件约1.11MB内容为可直接查阅的试卷与答案文档结构清晰便于打印练习。目前已有1022人学习下载。通过这份真题读者能熟悉该校命题风格与难度分布借助答案核对最左推导、语法分析树、DAG优化、FIRST与FOLLOW集、预测分析表、SLR项集族及NFA到DFA确定化等典型题型的解题思路适合期末冲刺与查漏补缺。1. 南京信息工程大学编译原理期末试卷2021-2022凌妙根一份卷子能挖出多少复习线索每年一到期末周总有人在群里甩出一份「南京信息工程大学编译原理期末试卷2021-2022凌妙根含答案.docx」然后配一句「谁有完整版」。我当年也是这么过来的后来自己带学弟学妹复习才意识到这份卷子的价值远不止「对答案」——凌妙根老师这套题的题型分布、考点权重、甚至出题顺序本身就是一份浓缩的复习大纲。编译原理这门课从词法分析、语法分析到语义分析、中间代码生成、优化和目标代码生成链条长、概念密光看教材很容易抓不住重点。而一份真实的期末试卷恰好能告诉你哪些知识点是必考的、哪些只是了解即可。这篇文章面向正在备考编译原理的本科生也面向想快速回顾编译原理核心考点的开发者。我会以这份2021-2022试卷为线索拆解每类题背后的知识模块给出可复现的复习路径和自测方法让你不只是在背答案而是真正能把编译原理的骨架搭起来。2. 从试卷题型反推编译原理的五大知识模块2.1 试卷结构拆解选择、填空、简答、计算、综合各考什么凌妙根老师这套2021-2022试卷从我拿到的版本来看题型分布大致是选择题10道左右填空题10个空简答题3到4道计算分析题3道综合题1到2道。这个结构在南信大编译原理期末里算是比较典型的既覆盖了基本概念又重点考察了动手推导能力。选择题和填空题主要考的是「定义级」知识编译程序的整体结构、词法分析中正规式和有限自动机的等价性、语法分析中LL(1)和LR(1)的基本判别条件、语法制导翻译中继承属性和综合属性的区别、运行时存储组织里活动记录的结构。这些题目看起来零散但其实每道题都对应教材里一个明确的章节。我的建议是拿到试卷后先别急着做题把每道题对应的章节标出来你会发现重复率最高的几个章节就是复习的优先级。简答题通常考的是「对比型」和「流程型」问题。比如「简述编译程序各阶段的主要任务」「比较自顶向下和自底向上语法分析方法的优缺点」「什么是语法制导定义什么是语法制导翻译方案两者有何区别」。这类题目的答案在教材里都有现成的但关键在于你能不能用自己的话把逻辑串起来。我一般会让学生先合上书用白纸画一遍编译流程的框图然后对着框图口述每个阶段做什么说不清楚的地方就是薄弱点。计算分析题是整张卷子的重头戏也是最能拉开差距的部分。2021-2022这套卷子里计算题主要集中在这几个方向构造正规式的NFA、将NFA确定化为DFA、求FIRST集和FOLLOW集、构造LL(1)分析表、构造LR(0)或SLR(1)分析表、语法制导翻译计算属性值。这些题目有一个共同特点步骤固定、套路明确但计算量大容易在细节上翻车。比如求FOLLOW集的时候漏掉某个产生式或者构造分析表的时候把移进和归约的冲突处理错了。综合题一般会把多个阶段串起来比如给一段简单语言的代码要求写出词法分析结果、语法分析树、语法制导翻译后的中间代码。这种题目考的是你对整个编译流程的贯通理解而不是孤立的知识点。2.2 五大模块的权重排序哪些章节值得花80%的时间把试卷拆完之后我把考点归为五大模块按出现频率和分值权重排个序模块对应章节试卷占比复习优先级语法分析第4章自顶向下自底向上约35%最高词法分析第3章正规式、NFA、DFA约20%高语法制导翻译第5章SDD、SDT、属性计算约20%高中间代码与优化第6-7章三地址码、基本块、DAG约15%中引论与运行时存储第1-2章编译过程、活动记录约10%低这个权重不是绝对的不同年份可能微调但大方向不会变。语法分析永远是编译原理期末的核心因为它是唯一一个既有理论深度又有大量计算题的模块。词法分析和语法制导翻译紧随其后前者是基础后者是连接前端和后端的桥梁。中间代码和优化部分如果课时紧张老师可能会压缩但基本概念和三地址码的生成一定要会。引论和运行时存储部分选择题和填空题为主背就完了。我一般会建议学弟学妹按这个优先级分配复习时间语法分析花40%词法分析和语法制导翻译各花20%中间代码和优化花15%剩下的5%留给引论和运行时存储。当然如果你时间充裕全面覆盖肯定更好但如果只剩三天这个分配能让你拿到大部分分数。2.3 从「凌妙根」出题风格看复习策略重推导、轻死记凌妙根老师的出题风格从我做过和看过的几套卷子来看有几个明显特点。第一计算题步骤要求写清楚不能只给最终答案。比如构造LR分析表他会要求你写出每个项目的闭包、GO函数、分析表的每一行。这意味着你不仅要会算还要能规范地表达计算过程。第二简答题喜欢考「区别与联系」而不是单纯的定义背诵。比如「比较LR(0)、SLR(1)、LALR(1)和LR(1)分析表的构造方法和能力差异」这种题目如果你只背了定义很难答完整。第三综合题往往会给一段简单的类C代码要求你手动模拟编译过程。这种题目考的是真功夫临时抱佛脚很难应付。针对这种风格我的复习策略是少背多推。具体来说每复习一个知识点就找一道对应的计算题从头到尾手推一遍。推完之后再问自己三个问题这个算法的输入是什么输出是什么中间每一步的依据是什么如果能回答清楚这个知识点就算过关了。另外建议把教材上的例题和课后习题都做一遍凌老师的出题风格和教材例题的契合度很高很多题目就是例题的变体。3. 词法分析与语法分析从正规式到LR分析表的完整推导链3.1 正规式转NFA再确定化为DFA手把手推导一遍词法分析的核心是正规式和有限自动机的相互转换。试卷里常见的题目是给一个正规式要求构造等价的NFA然后确定化为DFA最后最小化。这个流程看起来机械但每一步都有容易出错的地方。先看正规式转NFA。假设正规式是(a|b)*abb这是教材里的经典例子。构造NFA的规则很简单每个基本符号对应一个两状态的NFA片段然后按照连接、选择、闭包三种运算组合起来。具体步骤我不在这里展开因为教材上讲得很清楚。我要强调的是构造出来的NFA必须满足「只有一个初态、一个终态」的规范形式否则后续确定化会出问题。确定化的过程就是子集构造法。核心是维护一个状态集合的集合初始时把NFA的初态的ε闭包放进去然后对每个输入符号计算转移后的ε闭包直到没有新状态集产生。这个过程可以用表格来辅助每一行是一个DFA状态每一列是一个输入符号。# 子集构造法NFA确定化为DFA的核心逻辑 # 输入NFA的状态转移表、初态集合、终态集合、字母表 # 输出DFA的状态转移表 def epsilon_closure(states, nfa_transitions): 计算状态集合的ε闭包 stack list(states) closure set(states) while stack: state stack.pop() # 找到所有ε转移的目标状态 for next_state in nfa_transitions.get((state, ε), []): if next_state not in closure: closure.add(next_state) stack.append(next_state) return frozenset(closure) def subset_construction(nfa_states, nfa_transitions, start_state, accept_states, alphabet): 子集构造法主流程 start_closure epsilon_closure({start_state}, nfa_transitions) dfa_states {start_closure: 0} # DFA状态集到编号的映射 dfa_transitions {} unmarked [start_closure] while unmarked: current unmarked.pop() current_id dfa_states[current] for symbol in alphabet: # 计算move(current, symbol)的ε闭包 move_result set() for state in current: for next_state in nfa_transitions.get((state, symbol), []): move_result.add(next_state) if not move_result: continue next_closure epsilon_closure(move_result, nfa_transitions) if next_closure not in dfa_states: dfa_states[next_closure] len(dfa_states) unmarked.append(next_closure) dfa_transitions[(current_id, symbol)] dfa_states[next_closure] # 标记DFA的终态包含NFA终态的状态集 dfa_accept {dfa_states[s] for s in dfa_states if s accept_states} return dfa_states, dfa_transitions, dfa_accept这段代码的关键在于epsilon_closure函数它用栈来避免递归深度问题同时用集合去重。subset_construction里维护了一个unmarked列表每次取出一个未处理的状态集计算它在每个输入符号下的转移。注意frozenset的使用因为普通集合不能作为字典的键。参数nfa_transitions是一个字典键是(状态, 符号)元组值是目标状态列表。这个结构在手动推导时也可以用表格代替。确定化之后DFA最小化是另一个常考点。最小化的核心是划分等价类先按终态和非终态分成两组然后不断细分直到每个组内的状态对所有输入符号都转移到相同的组。这个过程用表格手动做就行代码实现反而容易绕晕。3.2 FIRST集和FOLLOW集三个易错点和一套自检方法FIRST集和FOLLOW集是LL(1)分析的基础也是计算题里最容易丢分的地方。我总结了三个易错点。第一个易错点FIRST集计算时忘记处理ε。如果某个非终结符可以推导出ε那么它的FIRST集里要包含ε而且在计算其他符号的FIRST集时这个ε会影响后续符号的加入。比如A - B C如果B的FIRST集包含ε那么C的FIRST集也要加入A的FIRST集。第二个易错点FOLLOW集计算时漏掉产生式右部的最后一个符号。规则是如果A - αB那么FOLLOW(A)要加入FOLLOW(B)。很多人在处理A - αBβ时只记得把FIRST(β)加入FOLLOW(B)却忘了当β可以推导出ε时还要把FOLLOW(A)加入FOLLOW(B)。第三个易错点开始符号的FOLLOW集里忘记加$。这个错误很低级但每年都有人犯。自检方法很简单算完FIRST和FOLLOW集之后用教材上的例题验证一遍。如果教材例题的结果和你算的一致说明方法没问题。另外可以写一个小脚本来自动计算和手算结果对比。# 计算FIRST集的迭代算法 def compute_first(grammar, non_terminals, terminals): grammar: 产生式字典键为非终结符值为产生式右部的列表 每个产生式右部是一个符号列表例如 [B, C] 或 [ε] first {nt: set() for nt in non_terminals} # 初始化终结符的FIRST集是它自己 for t in terminals: first[t] {t} changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: if prod [ε]: if ε not in first[nt]: first[nt].add(ε) changed True continue # 遍历产生式右部的每个符号 all_nullable True for symbol in prod: before_len len(first[nt]) first[nt] | (first[symbol] - {ε}) if len(first[nt]) before_len: changed True if ε not in first[symbol]: all_nullable False break if all_nullable: if ε not in first[nt]: first[nt].add(ε) changed True return first这段代码用迭代法计算FIRST集直到不再变化为止。关键逻辑是对于每个产生式从左到右扫描右部符号把每个符号的FIRST集去掉ε加入当前非终结符的FIRST集。如果当前符号不能推导出ε就停止扫描如果所有符号都能推导出ε就把ε加入。参数grammar的格式要注意每个产生式右部是一个列表空产生式用[ε]表示。FOLLOW集的计算类似但需要先算出FIRST集。我一般会建议手算一遍再用代码验证。手算能帮你理解规则代码能帮你检查遗漏。3.3 LL(1)分析表构造预测分析表的填写与冲突处理LL(1)分析表的构造规则很直接对于每个产生式A - α如果终结符a在FIRST(α)中就把A - α填入M[A, a]如果ε在FIRST(α)中那么对于FOLLOW(A)中的每个终结符b把A - α填入M[A, b]。所有未填写的条目都是出错条目。冲突处理是LL(1)分析表的难点。如果同一个单元格里要填两个产生式说明这个文法不是LL(1)的。常见的冲突有两种FIRST-FIRST冲突和FIRST-FOLLOW冲突。前者是两个产生式的FIRST集有交集后者是某个产生式的FIRST集包含ε且它的FOLLOW集和另一个产生式的FIRST集有交集。解决冲突的方法通常是提取左公因子或消除左递归。提取左公因子的做法是把公共前缀提出来引入新的非终结符。消除左递归的做法是把A - Aα | β改写成A - βA和A - αA | ε。这两个操作在教材上都有详细步骤这里不展开。我建议在构造分析表之前先检查文法是否满足LL(1)的条件无左递归、无二义性、任意两个产生式的FIRST集不相交、如果某个产生式能推导出ε则其FIRST集和FOLLOW集不相交。如果满足直接填表如果不满足先改造文法。3.4 LR分析表构造从LR(0)到SLR(1)的递进关系LR分析表的构造比LL(1)复杂但能力更强。试卷里常考的是LR(0)和SLR(1)偶尔会考LALR(1)或LR(1)。这四种分析表的能力递进关系是LR(0) SLR(1) LALR(1) LR(1)。LR(0)分析表的构造步骤是先求文法的LR(0)项目集规范族然后根据项目集之间的GO函数构造DFA最后填分析表。填表规则是如果项目A - α·aβ在状态i中且a是终结符那么ACTION[i, a] 移进如果项目A - α·在状态i中那么对于所有终结符和$ACTION[i, a] 归约如果项目S - S·在状态i中那么ACTION[i, $] 接受。LR(0)的问题是归约-移进冲突很常见因为它不考虑FOLLOW集。SLR(1)的改进就是归约时只看FOLLOW(A)中的符号。这样能解决一部分冲突但仍有局限。LALR(1)进一步合并同心项目集LR(1)则给每个项目带上搜索符。手动构造LR分析表时最容易出错的地方是项目集的闭包计算。闭包规则是如果项目A - α·Bβ在项目集中且B是非终结符那么对于B的每个产生式B - γ项目B - ·γ也要加入闭包。这个过程要反复进行直到没有新项目加入。# LR(0)项目集闭包计算 def closure_lr0(items, grammar): items: 项目集合每个项目是(产生式左部, 右部符号列表, 点的位置) grammar: 产生式字典 closure set(items) changed True while changed: changed False for (lhs, rhs, dot) in list(closure): if dot len(rhs) and rhs[dot] in grammar: # 点后面是非终结符 B rhs[dot] for prod in grammar[B]: new_item (B, tuple(prod), 0) if new_item not in closure: closure.add(new_item) changed True return closure这段代码实现了LR(0)闭包的核心逻辑。参数items是一个项目集合每个项目用(左部, 右部元组, 点的位置)表示。grammar是产生式字典。注意rhs要用元组而不是列表因为元组可以哈希能放进集合。闭包计算是一个不动点迭代过程每次扫描当前闭包中的所有项目如果点后面是非终结符就把该非终结符的所有产生式的初始项目加入闭包。GO函数的计算是对于项目集I和符号XGO(I, X)是所有形如A - αX·β的项目其中A - α·Xβ在I中的闭包。这个计算在手动推导时用表格做每个状态一行每个符号一列。SLR(1)分析表的填表和LR(0)类似唯一的区别是归约时只填FOLLOW(A)中的符号。这样能减少冲突但要求你先算好FOLLOW集。4. 语法制导翻译与中间代码属性计算和回填patch的实操细节4.1 综合属性与继承属性自底向上和自顶向下的计算差异语法制导定义SDD是编译原理里比较抽象的一章但试卷里的计算题往往很具体。核心概念是综合属性和继承属性。综合属性的值由子节点的属性值计算得到适合自底向上的计算继承属性的值由父节点或兄弟节点的属性值计算得到适合自顶向下的计算。在L-属性定义中每个产生式对应的属性计算规则必须满足继承属性只依赖于父节点的继承属性和左边兄弟节点的属性综合属性只依赖于自身节点的继承属性和子节点的属性。这个限制保证了属性计算可以在语法分析过程中一次完成。试卷里常见的题目是给一个SDD要求写出注释分析树并计算每个节点的属性值。做这类题目的关键是先确定属性的计算顺序。对于纯综合属性的SDD后序遍历语法树即可对于带继承属性的SDD需要按照依赖关系确定计算顺序通常是深度优先遍历。我一般会建议学生用表格来辅助计算。表格的每一行对应一个节点列包括节点编号、产生式、继承属性值、综合属性值。这样不容易漏算。4.2 三地址码生成从表达式到四元式的转换规则三地址码是中间代码的常见形式试卷里常考的是把表达式或控制流语句转换成三地址码。三地址码的每条指令最多有三个操作数形式如x y op z或x y或goto L。表达式a b * c - d的三地址码生成过程是先算b * c得到临时变量t1再算a t1得到t2最后算t2 - d得到t3。用四元式表示就是序号oparg1arg2result1*bct12at1t23-t2dt3控制流语句的三地址码生成稍微复杂一些。比如if (a b) x y z; else x y - z;的三地址码需要用到标号和跳转指令。常见的做法是1. if a b goto 3 2. goto 5 3. t1 y z 4. x t1 5. goto 7 6. t2 y - z 7. x t2注意这里的标号是示意实际生成时标号由编译器分配。试卷里可能会要求你写出带标号的三地址码或者要求你回填跳转指令的目标。4.3 回填patch技术布尔表达式的短路计算与跳转链回填技术是语法制导翻译里的一个重点也是难点。核心思想是生成跳转指令时目标标号可能还不知道先把指令的跳转目标留空等目标确定后再回填。布尔表达式的短路计算是回填技术的典型应用。以a b || c d e f为例短路计算的语义是如果a b为真整个表达式为真不再计算后面如果a b为假继续计算c d如果c d为假整个表达式为假不再计算e f如果c d为真继续计算e f。回填技术用两个列表来管理跳转链truelist和falselist。每个列表里存放的是需要回填真/假出口的跳转指令的编号。当整个布尔表达式的真假出口确定后遍历列表把目标标号填入。# 回填技术中合并跳转链的辅助函数 def merge(*lists): 合并多个跳转链返回合并后的列表 result [] for lst in lists: result.extend(lst) return result def backpatch(lst, target): 把跳转链中所有指令的目标地址回填为target for instr_id in lst: instructions[instr_id].target target这段代码展示了回填的两个核心操作merge用于合并跳转链backpatch用于回填目标。在实际的语法制导翻译中每个非终结符会携带truelist和falselist属性产生式对应的语义动作会调用这两个函数。参数instructions是全局的指令列表每条指令有一个target字段。手动做回填题时建议先画出语法树然后自底向上计算每个节点的truelist和falselist最后统一回填。这个过程比较繁琐但套路固定多练几道就能掌握。5. 避坑与排查编译原理期末复习中最容易翻车的五个地方5.1 坑一NFA确定化时状态集编号混乱现象手动做子集构造法时DFA状态集的编号和NFA状态集对不上导致后续填表时转移关系错乱。原因没有维护一个清晰的映射表或者中途修改了状态集的编号规则。解决在开始确定化之前先画一张表格左边是DFA状态编号右边是对应的NFA状态集。每产生一个新的状态集就立即分配编号并记录。编号从0开始按产生顺序递增。不要中途重新编号。5.2 坑二FIRST集计算时遗漏ε的传播现象某个非终结符明明可以推导出ε但它的FIRST集里没有ε导致后续FOLLOW集和LL(1)分析表全错。原因计算FIRST集时只处理了直接产生式没有处理间接推导出ε的情况。解决用迭代法计算FIRST集每次扫描所有产生式直到不再变化。对于A - B C这样的产生式如果B的FIRST集包含ε就要继续看C如果C的FIRST集也包含ε才把ε加入A的FIRST集。5.3 坑三LR分析表归约条目填错FOLLOW集现象SLR(1)分析表的归约条目填了所有终结符而不是只填FOLLOW集中的符号导致分析表出现大量冲突。原因把LR(0)的填表规则和SLR(1)的规则搞混了。解决记住LR(0)归约时填所有终结符和$SLR(1)归约时只填FOLLOW(A)中的符号。填表前先把每个非终结符的FOLLOW集算好填归约条目时严格对照。5.4 坑四语法制导翻译中属性计算顺序错误现象计算注释分析树的属性值时用了还没算出来的属性值导致结果错误。原因没有分析属性之间的依赖关系随意选择遍历顺序。解决先画出属性依赖图确定拓扑排序。对于L-属性定义可以用深度优先遍历先算继承属性再算综合属性。如果依赖关系复杂用表格记录每个属性的计算状态避免循环依赖。5.5 坑五三地址码生成时临时变量命名冲突现象生成的三地址码里临时变量名重复导致后续优化或解释执行时结果错误。原因手动生成时没有维护一个全局的临时变量计数器。解决每生成一个新的临时变量计数器加一变量名用t1、t2、t3这样的格式。不要复用已经用过的临时变量名除非你确定它的值不再需要。6. 用一份试卷做自测从错题反推知识盲区的具体方法6.1 三遍做题法限时模拟、逐题分析、错题重做拿到这份2021-2022试卷后不要直接看答案。我建议按三遍来做。第一遍限时模拟。给自己90分钟完全按照考试要求做题不翻书、不查资料。做完之后对照答案批改记录每道题的得分。这一遍的目的是暴露真实水平。第二遍逐题分析。对于做错的题不要只看正确答案要分析错误原因。是概念不清、计算失误、还是审题偏差把错误原因分类记录。对于做对的题也要看一遍解析确认自己的思路和标准答案一致。有时候蒙对的题比做错的题更危险。第三遍错题重做。隔一天之后把第一遍做错的题重新做一遍。如果这次做对了说明你掌握了如果还错说明这个知识点有深层问题需要回到教材重新学习。6.2 错题归因表把每道错题映射到教材章节我一般会让学生建一张错题归因表格式如下题号题型错误原因对应章节补救措施3选择混淆了LR(0)和SLR(1)的归约条件4.5节重读教材做课后题7计算FOLLOW集漏了$4.4节重算三遍代码验证12综合三地址码临时变量冲突6.2节重做例题整理模板这张表能帮你快速定位薄弱环节。如果某个章节反复出错说明你需要系统复习而不是零散地补漏。6.3 从错题到知识树把零散考点串成可检索的体系错题归因之后下一步是把这些零散的知识点串成一棵树。编译原理的知识体系本身就是一棵树根是「编译程序的结构」一级分支是「词法分析」「语法分析」「语义分析」「中间代码」「优化」「目标代码」每个分支下面又有具体的算法和数据结构。我习惯用思维导图来整理。每个错题对应的知识点作为一个节点标注错误原因和正确解法。整理完之后你会发现某些节点之间有关联比如「FIRST集」和「FOLLOW集」都挂在「LL(1)分析」下面「回填技术」挂在「语法制导翻译」下面。这种关联能帮你从整体上理解编译原理的流程而不是孤立地记忆每个算法。最后说一个我自己的习惯每次复习完一个模块我会合上书用白纸画一遍这个模块的流程图然后对着流程图口述每个步骤的输入、输出和关键操作。如果卡壳了就说明这个模块还没吃透。这个方法看起来笨但效果很好。希望帮到你。本文还有配套的精品资源点击获取