简介这份资源是南京信息工程大学2021—2022学年第一学期编译原理期末试卷B卷的完整文档由凌妙根老师出卷含标准答案面向正在备考编译原理的高校学生与需要梳理知识点的自学者。试卷覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、代码优化及自动机理论等核心内容题型包括选择题、画图题、计算分析题与综合题可帮助读者检验对编译器设计各环节的掌握程度。资源包共1个docx文件约1.11MB内容完整、排版清晰便于打印练习或对照复习。目前已有1022人学习下载适合需要真题演练、查漏补缺的读者使用。通过这份试卷读者可熟悉南信大编译原理的命题风格与难度掌握最左推导、语法分析树、DAG优化、FIRST与FOLLOW集、预测分析表、SLR分析及NFA与DFA构造等典型题型的解题思路是期末冲刺阶段的高效复习材料。1. 一份能当“错题本”用的编译原理期末卷凌妙根 2021-2022 B 卷拆解如果你正在搜“南京信息工程大学 编译原理 期末试卷 2021-2022 凌妙根”大概率不是想随便看看而是手里缺一份能对着复盘、能摸清出题人套路的真题。这份 B 卷共 2 页、考试时间 120 分钟任课教师凌妙根出卷时间 2021 年 12 月覆盖计算机与软件学院。它最值钱的地方不在“有答案”而在于题型分布非常典型选择 10 分、画图 25 分、计算分析 20 分、综合 45 分把词法分析、语法分析、错误处理、语法制导翻译、DAG 优化、SLR 分析、NFA 到 DFA 确定化全串了一遍。适合正在期末冲刺的本科生也适合想用一套卷子快速定位自己编译原理薄弱环节的人。下面我按“这卷子考什么 → 每类题怎么下手 → 哪里最容易翻车”的顺序拆开讲。2. 选择题与非递归预测分析10 分里藏着 4 个高频判断点2.1 从 5 道选择看凌妙根的出题偏好这 5 道选择题不是随便凑的每一道都卡在编译原理的“概念边界”上。第 1 题问“哪个不是编译程序的组成部分”答案 C 设备管理程序——这是操作系统的东西混进来考你分不分得清编译器前端后端。第 2 题文法定义的语言答案 C考的是文法生成语言的形式化定义。第 3 题遇到错误怎么办答案 C“跳过错误所在的语法单位继续分析”这是典型的错误恢复策略不是“立即停止”。第 4 题非递归预测分析中翻译的说法答案 D“综合属性在 A 出现之前就可以计算”——错综合属性必须等 A 归约完才能算。第 5 题语法制导翻译方案答案 A“只限自底向上”——错自顶向下也能用。把这 5 题连起来看出题人真正想筛的是你有没有把“编译器组件”“错误恢复”“属性计算时机”“SDD 与 SDT 的适用方向”这几个概念真正分清。很多人背了 LR、LL 的流程却在这些判断上栽跟头。2.2 非递归预测分析里属性栈怎么扩第 4 题背后是 LL(1) 非递归预测分析做翻译的核心机制。普通预测分析只有状态栈和输入指针要做属性翻译就得扩展语法分析栈把继承属性和综合属性分开存放。常见做法是栈里每个记录带一个属性槽非终结符 A 的继承属性在 A 展开时由父产生式传入综合属性在 A 归约时回填。下面用 Python 模拟一个极简的扩展栈记录结构帮你把“继承属性先算、综合属性后算”这个时机差异看明白class StackRecord: def __init__(self, symbol, inheritedNone): self.symbol symbol # 栈中符号终结符或非终结符 self.inherited inherited # 继承属性展开时由父产生式传入 self.synthesized None # 综合属性归约完成时才回填 def expand_nonterminal(stack, A, prod, inherited_vals): # 用产生式右部替换栈顶 A继承属性在此刻分配 stack.pop() for sym in reversed(prod.right): rec StackRecord(sym) if sym in prod.inherited_map: rec.inherited inherited_vals[prod.inherited_map[sym]] stack.append(rec) def reduce_nonterminal(stack, A, semantic_rule): # 归约时计算 A 的综合属性此时右部符号的综合属性已就绪 children [] while stack[-1].symbol ! A: children.append(stack.pop()) rec stack.pop() rec.synthesized semantic_rule(children[::-1]) stack.append(rec)逻辑说明StackRecord把继承属性和综合属性放在同一条记录的不同字段对应试卷第 4 题 C 选项“存放在不同的纪录中”的说法。expand_nonterminal在展开时给继承属性赋值reduce_nonterminal在归约时才算综合属性。参数上inherited_vals是父产生式传下来的属性字典semantic_rule是产生式对应的语义动作。如果你把综合属性提前到展开阶段算就会踩中第 4 题 D 选项那个坑。提示考试里遇到“非递归预测分析 翻译”的组合先问自己一句——这个属性是往下传的还是往上传的往下传的继承属性在展开时算往上传的综合属性在归约时算时机搞反必错。3. 画图题语法分析树、短语句柄与 DAG 优化的手算流程3.1 最左推导、语法分析树、短语直接短语句柄一条龙画图题第 1 题给了一个文法 G(S)要求对句子(a,(a,a))给出最左推导并画语法分析树再对句型((T,S),a)求短语、直接短语和句柄。这类题看着简单但每年都有人把“短语”和“直接短语”搞混。短语是语法树中任意一棵子树叶子组成的串直接短语是只有父子两代的子树叶子串句柄是最左直接短语。手算步骤我一般这么走先按最左推导把树画出来标好每个内部节点对应的产生式然后从叶子往上找每棵子树列出所有短语再筛出深度为 1 的子树得到直接短语最后取最左边那个直接短语就是句柄。注意句型((T,S),a)里 T、S、a 都是终结符还是非终结符要看文法定义别想当然。3.2 基本块 DAG 与三地址指令优化画图题第 2 题给了一个基本块包含DA-C、EA*C、FD*E、S2、TA-C、QA*C、G2*S、JT*Q、KG*5、LKJ、ML要求画 DAG 并写出优化后的三地址指令序列。这题的命门是公共子表达式消除TA-C和DA-C是同一个表达式QA*C和EA*C也是同一个S2和G2*S里的 2 是常量。DAG 画法每个变量和常量作为叶子运算符作为内部节点相同子节点和相同运算符的节点合并。优化后只保留对出口活跃变量 M 有贡献的计算。参考答案给的是DA-C、EA*C、FD*E、MF20这里20来自2*S中 S2 再乘 5 再乘 2 的常量折叠。下面用一段 Python 演示常量折叠和公共子表达式合并的判断逻辑def optimize_block(instructions): expr_map {} # 表达式 - 结果变量 const_map {} # 变量 - 常量值 optimized [] for op, arg1, arg2, res in instructions: # 常量折叠两个操作数都是常量时直接算 if arg1 in const_map and arg2 in const_map: val eval(f{const_map[arg1]} {op} {const_map[arg2]}) const_map[res] val continue key (op, arg1, arg2) if key in expr_map: # 公共子表达式复用已有结果 const_map[res] const_map.get(expr_map[key]) continue expr_map[key] res optimized.append((op, arg1, arg2, res)) return optimized逻辑说明expr_map记录已经算过的表达式遇到相同(op, arg1, arg2)就跳过实现公共子表达式消除。const_map记录常量传播结果两个操作数都是常量时直接折叠。参数上instructions是四元组列表(运算符, 左操作数, 右操作数, 结果)。实际考试手算时你不需要写代码但要有这个“先折叠常量、再合并相同表达式、最后只保留活跃变量相关计算”的顺序意识。注意DAG 优化题最容易翻车的地方是“出口活跃变量”判断。题目说“假设所有基本块出口时只有 M 还被引用”那所有对 M 没有贡献的指令都可以删。如果你把中间变量也当成活跃的优化结果就会多出好几条无用指令。4. 计算分析题消除左递归、FIRST/FOLLOW 与预测分析表4.1 消除左递归的标准套路计算分析题第 2 题给了一个文法 G[S]要求消除左递归、构造 FIRST 和 FOLLOW 集合、构造预测分析表。消除左递归有固定公式对于产生式A → Aα | β改成A → βA、A → αA | ε。如果是间接左递归先代入再消除。这一步不能跳因为左递归不消除LL(1) 预测分析直接没法做。我一般会先把文法写成产生式集合逐条检查有没有形如A → A...的直接左递归有就套公式。间接左递归比如A → B...、B → A...先把 B 的产生式代入 A再消除。消除完记得检查有没有引入新的 ε 产生式这会影响 FIRST 集计算。4.2 FIRST 与 FOLLOW 集合的填表法FIRST 集规则终结符的 FIRST 是它自己非终结符看它所有产生式右部第一个符号如果是终结符就加入如果是非终结符就递归求它的 FIRST如果该非终结符能推出 ε还要继续看下一个符号。FOLLOW 集规则开始符号的 FOLLOW 加$对于产生式A → αBβ把 FIRST(β) 去掉 ε 加入 FOLLOW(B)如果 β 能推出 ε把 FOLLOW(A) 加入 FOLLOW(B)。下面用 Python 实现一个 FIRST/FOLLOW 计算器你可以直接拿它验证手算结果def compute_first(grammar, nonterminals, terminals): first {nt: set() for nt in nonterminals} for nt in nonterminals: for prod in grammar[nt]: if prod[0] in terminals: first[nt].add(prod[0]) changed True while changed: changed False for nt in nonterminals: for prod in grammar[nt]: if prod [ε]: if ε not in first[nt]: first[nt].add(ε); changed True continue for sym in prod: if sym in terminals: if sym not in first[nt]: first[nt].add(sym); changed True break else: before len(first[nt]) first[nt] | (first[sym] - {ε}) if ε not in first[sym]: break if len(first[nt]) ! before: changed True return first逻辑说明grammar是字典键为非终结符值为产生式右部列表每个产生式是符号列表。terminals是终结符集合。外层while changed循环反复迭代直到 FIRST 集不再变化因为非终结符之间可能相互依赖。参数上prod [ε]判断空产生式first[sym] - {ε}去掉 ε 再加入当前非终结符的 FIRST。FOLLOW 集计算类似但要多一步“把 FOLLOW(A) 传给 FOLLOW(B)”的处理。4.3 预测分析表的构造与冲突处理预测分析表行是非终结符列是终结符加$。对每个产生式A → α如果终结符 a 在 FIRST(α) 里就把A → α填进M[A, a]如果 ε 在 FIRST(α) 里就对 FOLLOW(A) 里每个符号 b 填M[A, b] A → α。填完检查有没有一格多填有就是冲突说明不是 LL(1) 文法。提示考试里构造预测分析表先算 FIRST 再算 FOLLOW顺序不能反。FOLLOW 集依赖 FIRST 集先算 FOLLOW 会漏符号。填表时逐条产生式填填完再检查冲突比边填边检查更稳。5. 综合题SLR 项集族、语法制导翻译栈与 NFA 确定化5.1 SLR 自动机与 75 的翻译栈过程综合题第 1 题要求对 L 属性文法用 SLR 自动机做自底向上分析构造 SLR 项集族和语法分析表并对输入75画出语法制导翻译栈过程。SLR 在 LR(0) 项集族基础上用 FOLLOW 集解决归约冲突如果项A → α·在状态 I 中且a在 FOLLOW(A) 里就填归约动作。75的分析过程要跟踪状态栈、符号栈、输入串和语义栈。每步 shift 把终结符压栈reduce 时按产生式弹栈并计算属性。语法制导翻译栈里语义值跟着符号栈同步压弹。手算时建议画一张四列表状态栈、符号栈、输入、动作动作里标注 shift/reduce 和语义计算。5.2 倒数第二字符为 1 的正则语言正则表达式到最小 DFA综合题第 2 题定义在{0,1}上的正则语言 S 由倒数第二个字符为 1 的所有字符串组成。正则表达式是(0|1)*1(0|1)。构造 NFA 时先画一个接受(0|1)*的循环再串一个1再串一个(0|1)最后到终态。确定化用子集构造法最小化用 Hopcroft 算法或填表法。下面用 Python 演示子集构造法从 NFA 到 DFA 的核心步骤def subset_construction(nfa_states, nfa_trans, start, accepts): dfa_states [frozenset([start])] dfa_trans {} queue [frozenset([start])] while queue: current queue.pop(0) for sym in [0, 1]: next_set set() for state in current: next_set | nfa_trans.get((state, sym), set()) if not next_set: continue next_frozen frozenset(next_set) dfa_trans[(current, sym)] next_frozen if next_frozen not in dfa_states: dfa_states.append(next_frozen) queue.append(next_frozen) dfa_accepts [s for s in dfa_states if s accepts] return dfa_states, dfa_trans, dfa_accepts逻辑说明nfa_states是 NFA 状态集合nfa_trans是字典(状态, 符号) - 状态集合start是初态accepts是终态集合。subset_construction用 BFS 遍历所有可达子集每个子集成为一个 DFA 状态。dfa_accepts是包含任一 NFA 终态的子集。参数上frozenset用来做哈希键因为普通 set 不可哈希。最小化时先按“是否终态”分成两组再逐步细分直到不可分。注意NFA 确定化时ε 闭包别漏。如果 NFA 里有 ε 转移每次求 next_set 之前要先算当前子集的 ε 闭包再对每个符号求转移后的 ε 闭包。这题虽然没明说有没有 ε 转移但构造时养成先算闭包的习惯考试不会吃亏。6. 用这套卷子做自测三个验证习惯和一条血泪教训这套卷子最大的价值不是“背答案”而是当自测工具用。我建议你按下面三个习惯走一遍比单纯看答案有效得多。第一个习惯限时 120 分钟闭卷做一遍做完再对答案。选择题 10 分控制在 10 分钟内画图题 25 分给 30 分钟计算分析 20 分给 25 分钟综合 45 分留 55 分钟。时间分配本身就是考试策略的一部分很多人不是不会是最后综合题没时间写。第二个习惯对完答案后把每道错题归到具体知识点而不是只标“错了”。比如第 4 题错了归到“非递归预测分析属性计算时机”DAG 优化错了归到“公共子表达式消除与常量折叠”。归类的过程就是建错题本的过程。第三个习惯手算一遍 FIRST/FOLLOW 和预测分析表再用前面给的 Python 脚本验证。手算和代码结果对不上说明规则理解有偏差。这个交叉验证比反复看书快得多。下面这张表是我建议的自测记录格式你可以直接抄题号题型分值我的得分错因归类重做日期一.1选择22无—二.2画图1510DAG 活跃变量判断考前 3 天三.2计算158FOLLOW 集漏符号考前 5 天四.1综合157SLR 归约冲突处理考前 2 天最后说一条血泪教训。我当年第一次做这类卷子觉得选择题简单先跳过结果最后综合题时间不够SLR 项集族画了一半就交卷。从那以后我每次自测都强制按分值分配时间选择题再简单也不超过 10 分钟。这套凌妙根 2021-2022 B 卷的题型分布很典型拿它练时间分配和错题归类比刷十套来源不明的模拟题都管用。希望帮到你。本文还有配套的精品资源点击获取 南京信息工程大学编译原理2021-2022 B卷真题拆解与自测指南
简介这份资源是南京信息工程大学2021—2022学年第一学期编译原理期末试卷B卷的完整文档由凌妙根老师出卷含标准答案面向正在备考编译原理的高校学生与需要梳理知识点的自学者。试卷覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、代码优化及自动机理论等核心内容题型包括选择题、画图题、计算分析题与综合题可帮助读者检验对编译器设计各环节的掌握程度。资源包共1个docx文件约1.11MB内容完整、排版清晰便于打印练习或对照复习。目前已有1022人学习下载适合需要真题演练、查漏补缺的读者使用。通过这份试卷读者可熟悉南信大编译原理的命题风格与难度掌握最左推导、语法分析树、DAG优化、FIRST与FOLLOW集、预测分析表、SLR分析及NFA与DFA构造等典型题型的解题思路是期末冲刺阶段的高效复习材料。1. 一份能当“错题本”用的编译原理期末卷凌妙根 2021-2022 B 卷拆解如果你正在搜“南京信息工程大学 编译原理 期末试卷 2021-2022 凌妙根”大概率不是想随便看看而是手里缺一份能对着复盘、能摸清出题人套路的真题。这份 B 卷共 2 页、考试时间 120 分钟任课教师凌妙根出卷时间 2021 年 12 月覆盖计算机与软件学院。它最值钱的地方不在“有答案”而在于题型分布非常典型选择 10 分、画图 25 分、计算分析 20 分、综合 45 分把词法分析、语法分析、错误处理、语法制导翻译、DAG 优化、SLR 分析、NFA 到 DFA 确定化全串了一遍。适合正在期末冲刺的本科生也适合想用一套卷子快速定位自己编译原理薄弱环节的人。下面我按“这卷子考什么 → 每类题怎么下手 → 哪里最容易翻车”的顺序拆开讲。2. 选择题与非递归预测分析10 分里藏着 4 个高频判断点2.1 从 5 道选择看凌妙根的出题偏好这 5 道选择题不是随便凑的每一道都卡在编译原理的“概念边界”上。第 1 题问“哪个不是编译程序的组成部分”答案 C 设备管理程序——这是操作系统的东西混进来考你分不分得清编译器前端后端。第 2 题文法定义的语言答案 C考的是文法生成语言的形式化定义。第 3 题遇到错误怎么办答案 C“跳过错误所在的语法单位继续分析”这是典型的错误恢复策略不是“立即停止”。第 4 题非递归预测分析中翻译的说法答案 D“综合属性在 A 出现之前就可以计算”——错综合属性必须等 A 归约完才能算。第 5 题语法制导翻译方案答案 A“只限自底向上”——错自顶向下也能用。把这 5 题连起来看出题人真正想筛的是你有没有把“编译器组件”“错误恢复”“属性计算时机”“SDD 与 SDT 的适用方向”这几个概念真正分清。很多人背了 LR、LL 的流程却在这些判断上栽跟头。2.2 非递归预测分析里属性栈怎么扩第 4 题背后是 LL(1) 非递归预测分析做翻译的核心机制。普通预测分析只有状态栈和输入指针要做属性翻译就得扩展语法分析栈把继承属性和综合属性分开存放。常见做法是栈里每个记录带一个属性槽非终结符 A 的继承属性在 A 展开时由父产生式传入综合属性在 A 归约时回填。下面用 Python 模拟一个极简的扩展栈记录结构帮你把“继承属性先算、综合属性后算”这个时机差异看明白class StackRecord: def __init__(self, symbol, inheritedNone): self.symbol symbol # 栈中符号终结符或非终结符 self.inherited inherited # 继承属性展开时由父产生式传入 self.synthesized None # 综合属性归约完成时才回填 def expand_nonterminal(stack, A, prod, inherited_vals): # 用产生式右部替换栈顶 A继承属性在此刻分配 stack.pop() for sym in reversed(prod.right): rec StackRecord(sym) if sym in prod.inherited_map: rec.inherited inherited_vals[prod.inherited_map[sym]] stack.append(rec) def reduce_nonterminal(stack, A, semantic_rule): # 归约时计算 A 的综合属性此时右部符号的综合属性已就绪 children [] while stack[-1].symbol ! A: children.append(stack.pop()) rec stack.pop() rec.synthesized semantic_rule(children[::-1]) stack.append(rec)逻辑说明StackRecord把继承属性和综合属性放在同一条记录的不同字段对应试卷第 4 题 C 选项“存放在不同的纪录中”的说法。expand_nonterminal在展开时给继承属性赋值reduce_nonterminal在归约时才算综合属性。参数上inherited_vals是父产生式传下来的属性字典semantic_rule是产生式对应的语义动作。如果你把综合属性提前到展开阶段算就会踩中第 4 题 D 选项那个坑。提示考试里遇到“非递归预测分析 翻译”的组合先问自己一句——这个属性是往下传的还是往上传的往下传的继承属性在展开时算往上传的综合属性在归约时算时机搞反必错。3. 画图题语法分析树、短语句柄与 DAG 优化的手算流程3.1 最左推导、语法分析树、短语直接短语句柄一条龙画图题第 1 题给了一个文法 G(S)要求对句子(a,(a,a))给出最左推导并画语法分析树再对句型((T,S),a)求短语、直接短语和句柄。这类题看着简单但每年都有人把“短语”和“直接短语”搞混。短语是语法树中任意一棵子树叶子组成的串直接短语是只有父子两代的子树叶子串句柄是最左直接短语。手算步骤我一般这么走先按最左推导把树画出来标好每个内部节点对应的产生式然后从叶子往上找每棵子树列出所有短语再筛出深度为 1 的子树得到直接短语最后取最左边那个直接短语就是句柄。注意句型((T,S),a)里 T、S、a 都是终结符还是非终结符要看文法定义别想当然。3.2 基本块 DAG 与三地址指令优化画图题第 2 题给了一个基本块包含DA-C、EA*C、FD*E、S2、TA-C、QA*C、G2*S、JT*Q、KG*5、LKJ、ML要求画 DAG 并写出优化后的三地址指令序列。这题的命门是公共子表达式消除TA-C和DA-C是同一个表达式QA*C和EA*C也是同一个S2和G2*S里的 2 是常量。DAG 画法每个变量和常量作为叶子运算符作为内部节点相同子节点和相同运算符的节点合并。优化后只保留对出口活跃变量 M 有贡献的计算。参考答案给的是DA-C、EA*C、FD*E、MF20这里20来自2*S中 S2 再乘 5 再乘 2 的常量折叠。下面用一段 Python 演示常量折叠和公共子表达式合并的判断逻辑def optimize_block(instructions): expr_map {} # 表达式 - 结果变量 const_map {} # 变量 - 常量值 optimized [] for op, arg1, arg2, res in instructions: # 常量折叠两个操作数都是常量时直接算 if arg1 in const_map and arg2 in const_map: val eval(f{const_map[arg1]} {op} {const_map[arg2]}) const_map[res] val continue key (op, arg1, arg2) if key in expr_map: # 公共子表达式复用已有结果 const_map[res] const_map.get(expr_map[key]) continue expr_map[key] res optimized.append((op, arg1, arg2, res)) return optimized逻辑说明expr_map记录已经算过的表达式遇到相同(op, arg1, arg2)就跳过实现公共子表达式消除。const_map记录常量传播结果两个操作数都是常量时直接折叠。参数上instructions是四元组列表(运算符, 左操作数, 右操作数, 结果)。实际考试手算时你不需要写代码但要有这个“先折叠常量、再合并相同表达式、最后只保留活跃变量相关计算”的顺序意识。注意DAG 优化题最容易翻车的地方是“出口活跃变量”判断。题目说“假设所有基本块出口时只有 M 还被引用”那所有对 M 没有贡献的指令都可以删。如果你把中间变量也当成活跃的优化结果就会多出好几条无用指令。4. 计算分析题消除左递归、FIRST/FOLLOW 与预测分析表4.1 消除左递归的标准套路计算分析题第 2 题给了一个文法 G[S]要求消除左递归、构造 FIRST 和 FOLLOW 集合、构造预测分析表。消除左递归有固定公式对于产生式A → Aα | β改成A → βA、A → αA | ε。如果是间接左递归先代入再消除。这一步不能跳因为左递归不消除LL(1) 预测分析直接没法做。我一般会先把文法写成产生式集合逐条检查有没有形如A → A...的直接左递归有就套公式。间接左递归比如A → B...、B → A...先把 B 的产生式代入 A再消除。消除完记得检查有没有引入新的 ε 产生式这会影响 FIRST 集计算。4.2 FIRST 与 FOLLOW 集合的填表法FIRST 集规则终结符的 FIRST 是它自己非终结符看它所有产生式右部第一个符号如果是终结符就加入如果是非终结符就递归求它的 FIRST如果该非终结符能推出 ε还要继续看下一个符号。FOLLOW 集规则开始符号的 FOLLOW 加$对于产生式A → αBβ把 FIRST(β) 去掉 ε 加入 FOLLOW(B)如果 β 能推出 ε把 FOLLOW(A) 加入 FOLLOW(B)。下面用 Python 实现一个 FIRST/FOLLOW 计算器你可以直接拿它验证手算结果def compute_first(grammar, nonterminals, terminals): first {nt: set() for nt in nonterminals} for nt in nonterminals: for prod in grammar[nt]: if prod[0] in terminals: first[nt].add(prod[0]) changed True while changed: changed False for nt in nonterminals: for prod in grammar[nt]: if prod [ε]: if ε not in first[nt]: first[nt].add(ε); changed True continue for sym in prod: if sym in terminals: if sym not in first[nt]: first[nt].add(sym); changed True break else: before len(first[nt]) first[nt] | (first[sym] - {ε}) if ε not in first[sym]: break if len(first[nt]) ! before: changed True return first逻辑说明grammar是字典键为非终结符值为产生式右部列表每个产生式是符号列表。terminals是终结符集合。外层while changed循环反复迭代直到 FIRST 集不再变化因为非终结符之间可能相互依赖。参数上prod [ε]判断空产生式first[sym] - {ε}去掉 ε 再加入当前非终结符的 FIRST。FOLLOW 集计算类似但要多一步“把 FOLLOW(A) 传给 FOLLOW(B)”的处理。4.3 预测分析表的构造与冲突处理预测分析表行是非终结符列是终结符加$。对每个产生式A → α如果终结符 a 在 FIRST(α) 里就把A → α填进M[A, a]如果 ε 在 FIRST(α) 里就对 FOLLOW(A) 里每个符号 b 填M[A, b] A → α。填完检查有没有一格多填有就是冲突说明不是 LL(1) 文法。提示考试里构造预测分析表先算 FIRST 再算 FOLLOW顺序不能反。FOLLOW 集依赖 FIRST 集先算 FOLLOW 会漏符号。填表时逐条产生式填填完再检查冲突比边填边检查更稳。5. 综合题SLR 项集族、语法制导翻译栈与 NFA 确定化5.1 SLR 自动机与 75 的翻译栈过程综合题第 1 题要求对 L 属性文法用 SLR 自动机做自底向上分析构造 SLR 项集族和语法分析表并对输入75画出语法制导翻译栈过程。SLR 在 LR(0) 项集族基础上用 FOLLOW 集解决归约冲突如果项A → α·在状态 I 中且a在 FOLLOW(A) 里就填归约动作。75的分析过程要跟踪状态栈、符号栈、输入串和语义栈。每步 shift 把终结符压栈reduce 时按产生式弹栈并计算属性。语法制导翻译栈里语义值跟着符号栈同步压弹。手算时建议画一张四列表状态栈、符号栈、输入、动作动作里标注 shift/reduce 和语义计算。5.2 倒数第二字符为 1 的正则语言正则表达式到最小 DFA综合题第 2 题定义在{0,1}上的正则语言 S 由倒数第二个字符为 1 的所有字符串组成。正则表达式是(0|1)*1(0|1)。构造 NFA 时先画一个接受(0|1)*的循环再串一个1再串一个(0|1)最后到终态。确定化用子集构造法最小化用 Hopcroft 算法或填表法。下面用 Python 演示子集构造法从 NFA 到 DFA 的核心步骤def subset_construction(nfa_states, nfa_trans, start, accepts): dfa_states [frozenset([start])] dfa_trans {} queue [frozenset([start])] while queue: current queue.pop(0) for sym in [0, 1]: next_set set() for state in current: next_set | nfa_trans.get((state, sym), set()) if not next_set: continue next_frozen frozenset(next_set) dfa_trans[(current, sym)] next_frozen if next_frozen not in dfa_states: dfa_states.append(next_frozen) queue.append(next_frozen) dfa_accepts [s for s in dfa_states if s accepts] return dfa_states, dfa_trans, dfa_accepts逻辑说明nfa_states是 NFA 状态集合nfa_trans是字典(状态, 符号) - 状态集合start是初态accepts是终态集合。subset_construction用 BFS 遍历所有可达子集每个子集成为一个 DFA 状态。dfa_accepts是包含任一 NFA 终态的子集。参数上frozenset用来做哈希键因为普通 set 不可哈希。最小化时先按“是否终态”分成两组再逐步细分直到不可分。注意NFA 确定化时ε 闭包别漏。如果 NFA 里有 ε 转移每次求 next_set 之前要先算当前子集的 ε 闭包再对每个符号求转移后的 ε 闭包。这题虽然没明说有没有 ε 转移但构造时养成先算闭包的习惯考试不会吃亏。6. 用这套卷子做自测三个验证习惯和一条血泪教训这套卷子最大的价值不是“背答案”而是当自测工具用。我建议你按下面三个习惯走一遍比单纯看答案有效得多。第一个习惯限时 120 分钟闭卷做一遍做完再对答案。选择题 10 分控制在 10 分钟内画图题 25 分给 30 分钟计算分析 20 分给 25 分钟综合 45 分留 55 分钟。时间分配本身就是考试策略的一部分很多人不是不会是最后综合题没时间写。第二个习惯对完答案后把每道错题归到具体知识点而不是只标“错了”。比如第 4 题错了归到“非递归预测分析属性计算时机”DAG 优化错了归到“公共子表达式消除与常量折叠”。归类的过程就是建错题本的过程。第三个习惯手算一遍 FIRST/FOLLOW 和预测分析表再用前面给的 Python 脚本验证。手算和代码结果对不上说明规则理解有偏差。这个交叉验证比反复看书快得多。下面这张表是我建议的自测记录格式你可以直接抄题号题型分值我的得分错因归类重做日期一.1选择22无—二.2画图1510DAG 活跃变量判断考前 3 天三.2计算158FOLLOW 集漏符号考前 5 天四.1综合157SLR 归约冲突处理考前 2 天最后说一条血泪教训。我当年第一次做这类卷子觉得选择题简单先跳过结果最后综合题时间不够SLR 项集族画了一半就交卷。从那以后我每次自测都强制按分值分配时间选择题再简单也不超过 10 分钟。这套凌妙根 2021-2022 B 卷的题型分布很典型拿它练时间分配和错题归类比刷十套来源不明的模拟题都管用。希望帮到你。本文还有配套的精品资源点击获取