企业官网建设流程全解析

简介：这份资源是南京信息工程大学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, inherited=None): 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 题给了一个基本块，包含D=A-C、E=A*C、F=D*E、S=2、T=A-C、Q=A*C、G=2*S、J=T*Q、K=G*5、L=K+J、M=L，要求画 DAG 并写出优化后的三地址指令序列。这题的命门是公共子表达式消除：T=A-C和D=A-C是同一个表达式，Q=A*C和E=A*C也是同一个，S=2和G=2*S里的 2 是常量。

DAG 画法：每个变量和常量作为叶子，运算符作为内部节点，相同子节点和相同运算符的节点合并。优化后只保留对出口活跃变量 M 有贡献的计算。参考答案给的是D=A-C、E=A*C、F=D*E、M=F+20，这里20来自2*S中 S=2 再乘 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 自动机与 7+5 的翻译栈过程

综合题第 1 题要求对 L 属性文法用 SLR 自动机做自底向上分析，构造 SLR 项集族和语法分析表，并对输入7+5画出语法制导翻译栈过程。SLR 在 LR(0) 项集族基础上，用 FOLLOW 集解决归约冲突：如果项A → α·在状态 I 中，且a在 FOLLOW(A) 里，就填归约动作。

7+5的分析过程要跟踪状态栈、符号栈、输入串和语义栈。每步 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 脚本验证。手算和代码结果对不上，说明规则理解有偏差。这个交叉验证比反复看书快得多。

下面这张表是我建议的自测记录格式，你可以直接抄：

最后说一条血泪教训。我当年第一次做这类卷子，觉得选择题简单先跳过，结果最后综合题时间不够，SLR 项集族画了一半就交卷。从那以后我每次自测都强制按分值分配时间，选择题再简单也不超过 10 分钟。这套凌妙根 2021-2022 B 卷的题型分布很典型，拿它练时间分配和错题归类，比刷十套来源不明的模拟题都管用。希望帮到你。

本文还有配套的精品资源，点击获取