简介这份资料面向北京工业大学北工大修读编译原理课程的学生专为期末一纸开卷考试整理帮助考生在有限篇幅内快速梳理核心考点、构建知识框架。压缩包内仅含1个doc文档大小约1.01MB内容以问答形式覆盖编译程序工作过程、语法分析、语义分析与中间代码生成、语法制导翻译、参数传递方式、自展与交叉编译、LL(1)分析、二义性、标识符与名字等高频考点并配有规范归约、句柄、素短语、活动记录与符号表管理等细节解释。文档将零散概念归纳为条目式笔记便于开卷时按关键词快速定位答案适合考前突击背诵与查漏补缺。目前已有789人学习下载可作为北工大编译原理期末复习的参考材料。1. 一纸开卷的编译原理期末到底该往纸上抄什么“一纸开卷”这四个字考过的人都懂——它比闭卷更折磨人。闭卷你还能安慰自己“没背到就算了”一纸开卷意味着你明明知道答案就在那张 A4 纸上但考试时翻不到、抄错了、或者压根没抄上去。我带过三届编译原理的期末复习见过太多人把整本教材的目录抄上去结果 LL(1) 的 SELECT 集算错、LR(1) 的项目集画崩、语法制导翻译的继承属性传反。这份复习总结要解决的核心问题只有一个在有限的一页纸空间里把编译原理从词法分析到语法制导翻译的判定条件、构造步骤、计算模板压缩成可考场直接套用的形式。适合正在准备期末的本科生也适合需要快速回顾编译前端核心算法的开发者。接下来的内容按考试出现频率和计算量排序先讲词法再攻语法分析两大山头最后收在语法制导翻译和几个考场救命技巧上。2. 词法分析与正则表达式从 NFA 到 DFA 的手工推导模板2.1 为什么词法分析是整张卷子的送分题词法分析在编译原理期末里通常占 15 到 20 分题型高度固定给一个正则表达式或自然语言描述要求构造 NFA、确定化得到 DFA、最小化、然后写词法分析器。这四步里NFA 到 DFA 的子集构造法是唯一必须手算的环节也是最容易在考场上因为状态编号混乱而翻车的地方。我一般建议复习时把子集构造法的表格模板背下来而不是每次现推。具体来说NFA 的状态转移表横轴是输入符号纵轴是状态集合。初始状态集合是 NFA 的初态闭包然后对每个输入符号求 move 再求 ε-闭包。这里的关键是ε-闭包必须递归求到不动点很多人在考场上只求一层就停了导致 DFA 状态数少算后面最小化全错。下面用经典例子(a|b)*abb演示从 NFA 到 DFA 的完整手工推导。这个例子在龙书和国内教材里反复出现考试换汤不换药。# 子集构造法手工推导的辅助验证脚本 # 输入NFA 的状态转移字典格式 {状态: {符号: [目标状态]}} # 输出DFA 状态集合和转移表 def epsilon_closure(states, nfa, epsilonε): 求 ε-闭包递归到不动点 stack list(states) closure set(states) while stack: s stack.pop() for t in nfa.get(s, {}).get(epsilon, []): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def move(states, symbol, nfa): 求 move 集合 result set() for s in states: result.update(nfa.get(s, {}).get(symbol, [])) return frozenset(result) # 定义 (a|b)*abb 的 NFA状态 0-10 nfa { 0: {ε: [1, 7]}, 1: {ε: [2, 4]}, 2: {a: [3]}, 3: {ε: [6]}, 4: {b: [5]}, 5: {ε: [6]}, 6: {ε: [1, 7]}, 7: {a: [8]}, 8: {b: [9]}, 9: {b: [10]}, 10: {} } # 子集构造 start epsilon_closure({0}, nfa) dfa_states {start: A} queue [start] transitions {} state_names {start: A} name_counter ord(B) while queue: current queue.pop(0) current_name state_names[current] transitions[current_name] {} for symbol in [a, b]: next_set epsilon_closure(move(current, symbol, nfa), nfa) if not next_set: continue if next_set not in state_names: state_names[next_set] chr(name_counter) name_counter 1 queue.append(next_set) transitions[current_name][symbol] state_names[next_set] print(DFA 状态数:, len(state_names)) for state, trans in transitions.items(): print(f状态 {state}: {trans})这段代码的逻辑是先定义 NFA 的转移关系然后从初态的 ε-闭包出发对每个输入符号计算 move 后再求 ε-闭包得到新的 DFA 状态。参数说明nfa字典的键是状态编号值是该状态在各输入符号下的目标状态列表epsilon参数默认用ε表示空串。运行结果会输出 DFA 的状态数和转移表考场上手算时对照这个结构填表即可。2.2 DFA 最小化的分割法考场上的表格怎么画DFA 最小化用 Hopcroft 分割法考试里通常要求把状态集划分成等价类。步骤是先按终态和非终态分成两个集合然后对每个集合检查是否对每个输入符号都转移到同一个集合不是就继续分裂直到所有集合都稳定。这里有个考场技巧先画状态转移矩阵再在矩阵上做标记。把状态按行排列列是输入符号每个格子填目标状态。然后拿两张纸一张写当前划分一张写分裂依据。分裂时只看目标状态落在哪个划分块里不要去看具体状态编号。我见过太多人在这里把目标状态编号和划分块编号搞混导致划分永远不稳定。最小化之后还要判断哪些状态是等价的合并后重新画 DFA。这一步在卷面上通常要求画出最终 DFA 图注意初态和终态要标清楚。如果题目还要求写词法分析器那就用合并后的 DFA 直接写 switch-case 或状态表驱动的代码状态表驱动更省纸。注意子集构造法得到的 DFA 状态命名建议用 A、B、C 顺序编号不要用集合本身写否则最小化时卷面会非常乱。考场上时间紧命名清晰比推导优雅重要得多。3. LL(1) 文法FIRST 集、FOLLOW 集与预测分析表的考场速算3.1 FIRST 和 FOLLOW 集的手算顺序与三个易错点LL(1) 是语法分析里性价比最高的考点通常考一道 15 到 20 分的大题给文法求 FIRST 和 FOLLOW 集判断是否是 LL(1)构造预测分析表然后对某个输入串写出分析过程。这四步环环相扣第一步算错后面全崩。FIRST 集的求法对每个非终结符看它的产生式右部第一个符号。如果是终结符直接加入 FIRST如果是非终结符把该非终结符的 FIRST 集除去 ε加入如果该非终结符能推导出 ε继续看下一个符号直到遇到不能推 ε 的符号或右部结束。如果整个右部都能推 ε把 ε 加入 FIRST。FOLLOW 集的求法开始符号的 FOLLOW 集包含#。对每个产生式A - αBβ把 FIRST(β) 除去 ε 加入 FOLLOW(B)如果 β 能推 ε 或 β 为空把 FOLLOW(A) 加入 FOLLOW(B)。这里有个循环依赖FOLLOW 集可能需要在多个产生式之间反复迭代直到不动点。考场上我一般建议先算 FIRST 再算 FOLLOW算 FOLLOW 时把所有产生式列出来逐个扫描扫完一遍再扫一遍直到没有新的符号加入。三个易错点第一FIRST 集里 ε 的处理只有整个右部能推 ε 时才加 ε第二FOLLOW 集里不要漏掉#第三如果文法有左递归必须先消除左递归再求 LL(1)否则 FIRST 和 FOLLOW 算出来也没用。# FIRST 和 FOLLOW 集计算模板 # 输入文法产生式列表格式 [(A, [α, B, β]), ...] # 输出FIRST 和 FOLLOW 字典 def compute_first(grammar, non_terminals, terminals): first {nt: set() for nt in non_terminals} changed True while changed: changed False for head, body in grammar: # body 是符号列表如 [a, B] if not body: if ε not in first[head]: first[head].add(ε) changed True continue all_nullable True for sym in body: if sym in terminals: if sym not in first[head]: first[head].add(sym) changed True all_nullable False break else: add_set first[sym] - {ε} if not add_set.issubset(first[head]): first[head].update(add_set) changed True if ε not in first[sym]: all_nullable False break if all_nullable and ε not in first[head]: first[head].add(ε) changed True return first def compute_follow(grammar, non_terminals, terminals, start_symbol, first): follow {nt: set() for nt in non_terminals} follow[start_symbol].add(#) changed True while changed: changed False for head, body in grammar: for i, sym in enumerate(body): if sym not in non_terminals: continue rest body[i1:] # 计算 rest 的 FIRST 集 rest_first set() all_nullable True for s in rest: if s in terminals: rest_first.add(s) all_nullable False break else: rest_first.update(first[s] - {ε}) if ε not in first[s]: all_nullable False break if all_nullable: rest_first.add(ε) # 把 FIRST(rest) - ε 加入 FOLLOW(sym) add_set rest_first - {ε} if not add_set.issubset(follow[sym]): follow[sym].update(add_set) changed True # 如果 rest 能推 ε把 FOLLOW(head) 加入 FOLLOW(sym) if ε in rest_first: if not follow[head].issubset(follow[sym]): follow[sym].update(follow[head]) changed True return follow # 示例文法E - T E, E - T E | ε, T - F T, T - * F T | ε, F - ( E ) | id grammar [ (E, [T, E]), (E, [, T, E]), (E, []), (T, [F, T]), (T, [*, F, T]), (T, []), (F, [(, E, )]), (F, [id]) ] non_terminals {E, E, T, T, F} terminals {, *, (, ), id} first compute_first(grammar, non_terminals, terminals) follow compute_follow(grammar, non_terminals, terminals, E, first) print(FIRST:, {k: sorted(v) for k, v in first.items()}) print(FOLLOW:, {k: sorted(v) for k, v in follow.items()})这段代码的逻辑是compute_first用迭代法反复扫描产生式直到 FIRST 集不再变化处理了 ε 传播的情况compute_follow同样迭代对每个产生式右部的每个非终结符计算其后面符号串的 FIRST 集如果后面能推 ε 则把左部的 FOLLOW 加进来。参数说明grammar是产生式列表空列表表示 ε 产生式start_symbol是文法开始符号。运行结果直接给出 FIRST 和 FOLLOW 集考场上手算后可以用这个脚本验证。3.2 预测分析表的构造与 LL(1) 判定条件预测分析表的行是非终结符列是终结符加#。对每个产生式A - α如果终结符a在 FIRST(α) 中把产生式填入M[A, a]如果 ε 在 FIRST(α) 中对每个b在 FOLLOW(A) 中把产生式填入M[A, b]。如果同一个格子要填两个产生式说明不是 LL(1) 文法。LL(1) 的判定条件对每个非终结符的任意两个产生式A - α和A - β满足 FIRST(α) ∩ FIRST(β) ∅如果 β 能推 ε还要满足 FIRST(α) ∩ FOLLOW(A) ∅。考场上判断 LL(1) 时先看有没有左递归有就直接不是没有左递归再看有没有公共左因子有也不是都没有再算 FIRST 和 FOLLOW 验证。分析过程用栈来写初始栈里是#和开始符号然后读输入串。栈顶是非终结符就查预测分析表是终结符就和当前输入符号匹配。这一步在卷面上通常要求写出每一步的栈内容、剩余输入串和动作建议用表格形式三列栈、输入、动作。动作写“用 A - α 展开”或“匹配 a”。提示预测分析表的构造题如果文法有 ε 产生式FOLLOW 集一定要算对否则 ε 那一行会填错。我一般建议先把所有非 ε 产生式填完再处理 ε 产生式这样不容易漏。4. LR(1) 与 LALR(1)项目集闭包、分析表与冲突排查4.1 LR(0) 项目集规范族的构造从增广文法开始LR 分析是编译原理期末的压轴题通常考 LR(1) 或 LALR(1)分值 20 分以上。第一步是增广文法加一个S - S的产生式然后构造项目集规范族。LR(0) 项目是产生式加一个点点表示当前分析位置。闭包运算如果点后面是非终结符把该非终结符的所有产生式加进来点在最左。转移函数对每个项目集和每个文法符号求 move 后的闭包。LR(0) 项目集规范族的构造在考场上建议用“项目集编号 转移表”的方式。先写 I0 的闭包然后对每个符号求转移得到新项目集新项目集再求闭包直到没有新的项目集。这里最容易翻车的是闭包运算漏项目尤其是点后面是非终结符时要把该非终结符的所有产生式都加进来包括 ε 产生式如果有的话。# LR(0) 项目集规范族构造模板 # 输入增广文法产生式列表 # 输出项目集列表和转移表 def closure_lr0(items, grammar): LR(0) 闭包如果点后是非终结符加入其所有产生式 result set(items) changed True while changed: changed False for head, body, dot in list(result): if dot len(body) and body[dot] in grammar: for prod in grammar[body[dot]]: new_item (body[dot], tuple(prod), 0) if new_item not in result: result.add(new_item) changed True return frozenset(result) def goto_lr0(items, symbol, grammar): 转移函数点后是 symbol 的项目点右移一位后求闭包 moved set() for head, body, dot in items: if dot len(body) and body[dot] symbol: moved.add((head, body, dot 1)) return closure_lr0(moved, grammar) # 示例文法S - S, S - C C, C - c C | d grammar { S: [(S,)], S: [(C, C)], C: [(c, C), (d,)] } start_item (S, (S,), 0) I0 closure_lr0({start_item}, grammar) items_list [I0] transitions {} queue [I0] while queue: current queue.pop(0) idx items_list.index(current) transitions[idx] {} symbols set() for head, body, dot in current: if dot len(body): symbols.add(body[dot]) for sym in symbols: next_set goto_lr0(current, sym, grammar) if next_set not in items_list: items_list.append(next_set) queue.append(next_set) transitions[idx][sym] items_list.index(next_set) print(f项目集数量: {len(items_list)}) for i, items in enumerate(items_list): print(fI{i}:) for head, body, dot in sorted(items): body_str .join(body[:dot] (·,) body[dot:]) print(f {head} - {body_str}) print(f 转移: {transitions[i]})这段代码的逻辑是closure_lr0对项目集求闭包遇到点后是非终结符就加入其所有产生式goto_lr0对每个符号求转移点右移后求闭包。参数说明grammar字典的键是非终结符值是产生式右部元组的列表。运行结果输出所有项目集和转移关系考场上手算时对照这个结构画项目集图。4.2 LR(1) 项目集与 LALR(1) 合并向前看符号怎么算LR(1) 项目比 LR(0) 多一个向前看符号形式是[A - α·β, a]。闭包运算时如果点后是非终结符 B对 B 的每个产生式B - γ计算 FIRST(βa) 作为向前看符号。这里 β 是点后面的符号串a 是当前项目的向前看符号。如果 β 能推 ε向前看符号就是 a否则是 FIRST(β)。LR(1) 项目集规范族的构造和 LR(0) 类似但闭包和转移都要带向前看符号。考场上画 LR(1) 项目集时建议每个项目写成[产生式, 向前看符号]的形式向前看符号用花括号括起来。转移时向前看符号不变闭包时重新计算。LALR(1) 是在 LR(1) 的基础上合并同心项目集忽略向前看符号如果两个项目集的核心项目点不在最左的项目相同就合并向前看符号取并集。合并后可能产生归约-归约冲突这是 LALR(1) 比 LR(1) 弱的地方。考场上如果题目要求判断是 LR(1) 还是 LALR(1)先构造 LR(1) 项目集看有没有同心集有的话合并后检查冲突。分析表的构造对每个项目集如果项目是[A - α·aβ, b]且 a 是终结符填ACTION[i, a] shift j如果项目是[A - α·, a]填ACTION[i, a] reduce A - α如果项目是[S - S·, #]填ACTION[i, #] accept。GOTO 表填非终结符的转移。冲突排查移进-归约冲突发生在同一个项目集里既有移进项目又有归约项目且向前看符号有交集归约-归约冲突发生在多个归约项目的向前看符号有交集。LR(1) 能解决移进-归约冲突但归约-归约冲突可能仍然存在。LALR(1) 合并后可能引入新的归约-归约冲突。注意LR(1) 项目集的向前看符号计算是考场最大的坑。FIRST(βa) 里的 β 是点后面的符号串不是整个产生式右部。我见过太多人把整个右部的 FIRST 算进去导致向前看符号多算项目集数量爆炸。5. 语法制导翻译与中间代码生成继承属性、综合属性与三地址码5.1 语法制导定义的计算顺序依赖图与拓扑排序语法制导翻译是编译原理期末的另一个大题通常考语法制导定义SDD或语法制导翻译方案SDT要求写注释分析树或计算属性值。属性分综合属性和继承属性综合属性从子节点传到父节点继承属性从父节点或兄弟节点传到子节点。计算顺序由依赖图决定拓扑排序后按顺序计算。考场上写注释分析树时建议在每个节点旁边写属性值综合属性写在节点上方继承属性写在节点下方。计算时先算继承属性再算综合属性因为继承属性可能依赖父节点或左兄弟。如果依赖图有环说明属性定义有循环依赖需要改写文法。# 语法制导定义的计算模板表达式求值 # 文法E - E T | T, T - T * F | F, F - ( E ) | digit # 属性E.val, T.val, F.val 都是综合属性 class SDDNode: def __init__(self, symbol, childrenNone, valueNone): self.symbol symbol self.children children or [] self.value value def evaluate(node): 后序遍历计算综合属性 for child in node.children: evaluate(child) if node.symbol E and len(node.children) 3: # E - E T node.value node.children[0].value node.children[2].value elif node.symbol E and len(node.children) 1: node.value node.children[0].value elif node.symbol T and len(node.children) 3: # T - T * F node.value node.children[0].value * node.children[2].value elif node.symbol T and len(node.children) 1: node.value node.children[0].value elif node.symbol F and len(node.children) 3: # F - ( E ) node.value node.children[1].value elif node.symbol F and len(node.children) 1: node.value node.children[0].value elif node.symbol digit: pass # value 已设置 return node.value # 构造 3 4 * 5 的分析树 digit3 SDDNode(digit, value3) digit4 SDDNode(digit, value4) digit5 SDDNode(digit, value5) F3 SDDNode(F, [digit3]) F4 SDDNode(F, [digit4]) F5 SDDNode(F, [digit5]) T4 SDDNode(T, [F4]) T5 SDDNode(T, [F5]) T_mul SDDNode(T, [T4, SDDNode(*), F5]) E3 SDDNode(E, [T3 : SDDNode(T, [F3])]) E_add SDDNode(E, [E3, SDDNode(), T_mul]) print(3 4 * 5 , evaluate(E_add))这段代码的逻辑是定义 SDD 节点类后序遍历计算综合属性。参数说明symbol是文法符号children是子节点列表value是属性值。运行结果输出表达式求值结果。考场上写注释分析树时按这个后序顺序标注属性值即可。5.2 三地址码的生成从注释分析树到四元式三地址码是中间代码生成的常考题型要求把表达式或控制流语句翻译成四元式、三元式或间接三元式。四元式格式是(op, arg1, arg2, result)三元式是(op, arg1, arg2)用编号引用结果。考场上建议用四元式因为结果有名字不容易乱。生成三地址码时对每个非终结符分配临时变量。表达式a b * c的四元式序列(*, b, c, t1)、(, a, t1, t2)。控制流语句if E then S1 else S2的四元式先算 E 的条件然后(jnz, E, -, L1)、(j, -, -, L2)、(label, -, -, L1)、S1 的代码、(j, -, -, L3)、(label, -, -, L2)、S2 的代码、(label, -, -, L3)。回填技术是控制流翻译的关键先生成跳转指令但目标地址空着等目标确定后再回填。考场上如果考回填建议用“跳转指令列表”的方式每个非终结符维护truelist和falselist最后统一回填。提示三地址码生成题临时变量命名建议用 t1、t2、t3 顺序编号不要用 t、t、t卷面上容易看错。标签用 L1、L2、L3和临时变量区分开。6. 考场避坑与一纸开卷的排版技巧6.1 五个血泪踩坑记录坑一FIRST 集里 ε 加错位置。现象预测分析表里 ε 产生式填错列分析过程匹配失败。原因只有整个产生式右部能推 ε 时才把 ε 加入 FIRST部分符号能推 ε 不代表整个右部能推。解决对每个产生式右部从左到右扫描遇到不能推 ε 的符号就停止只有全部符号都能推 ε 才加 ε。坑二FOLLOW 集忘记迭代到不动点。现象FOLLOW 集少符号预测分析表某些格子空着。原因FOLLOW 集的计算有循环依赖一遍扫描不够。解决反复扫描所有产生式直到没有新的符号加入 FOLLOW 集。坑三LR(1) 向前看符号算成整个右部的 FIRST。现象项目集数量异常多分析表巨大。原因向前看符号是 FIRST(βa)β 是点后面的符号串不是整个右部。解决只看点后面的符号如果点后面为空向前看符号就是当前项目的向前看符号。坑四LALR(1) 合并同心集后忘记检查冲突。现象分析表出现多重入口分析器无法决策。原因合并同心集可能引入归约-归约冲突。解决合并后检查每个项目集如果同一个向前看符号对应多个归约项目说明有冲突需要回退到 LR(1) 或改写文法。坑五语法制导翻译的继承属性传反。现象注释分析树的属性值算错尤其是变量声明和类型检查。原因继承属性从父节点或左兄弟传到子节点方向搞反了。解决画依赖图箭头从依赖方指向被依赖方拓扑排序后按顺序算。6.2 一页纸的排版把计算模板压缩成可套用的形式一纸开卷的 A4 纸空间有限我一般建议按“左栏公式、右栏例子”的方式排版。左栏写 FIRST、FOLLOW、LR(1) 闭包、三地址码生成的模板右栏写一个完整例子的每一步结果。模板用箭头和缩写比如ε-closure写成ε-clFIRST写成FFOLLOW写成Fo。例子用最小文法能说明步骤就行。具体排版建议第一块写词法分析的子集构造法表格模板第二块写 LL(1) 的 FIRST/FOLLOW 计算规则和预测分析表模板第三块写 LR(1) 的项目集闭包和转移规则第四块写三地址码的四元式模板和回填规则。每块之间留空白考试时方便补充。最后说一个我自己的习惯考前一周把近五年的期末题按题型分类每类只做三道做完后把解题步骤压缩成关键词写在 A4 纸上。上考场前只看这张纸不再翻书。编译原理的考试计算量比概念多手熟比背熟重要。希望帮到你。本文还有配套的精品资源点击获取