简介这份《哈工大编译原理期末复习完整版》面向计算机专业本科生与考研、期末备考人群系统梳理编译原理全流程知识涵盖编译系统结构、语言文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等核心模块。内容从编译程序生成、正则表达式与有穷自动机到四元式与寄存器分配均有细致笔记与示例可帮助读者快速搭建知识框架、对照复习重点并查漏补缺。资源为PDF格式整包1个文件约31.14MB便携易用适合在电脑、平板与手机端随时翻阅。这份复习资料已有2311人下载学习经过较多学习者验证。无论是考前冲刺还是系统回顾编译原理这份完整版笔记都能提供扎实的知识支撑与清晰的复习主线。1. 哈工大编译原理期末复习一条主线串起整门课别按目录从头背“哈工大编译原理期末复习完整版涵盖编译原理所有内容”这个标题看起来很吓人但真正把它拆开看编译原理的期末卷其实永远在考同一条主线词法分析、语法分析、语法制导翻译与中间代码外加少量运行环境和代码生成的小题。只要先把这条主线走通再回头补课后题和实验就不需要从教材第一个字背到最后一个字。这套复习路径适合三类人考前还有两三周的在校生、想转码但被龙书劝退的自学者、以及实验能跑但理论题老丢分的动手党。如果你只剩三天那就只抓第二、三、四章其余章节当作查缺补漏。接下来我会按这条线把每个考点的原理、手算方法、参数设置和踩坑位置一次讲透。2. 词法分析复习从正规式到DFA的三步手算流程与最小化表格法2.1 期末卷面上词法分析考什么三道小题加一道大题的常见配比词法分析在期末卷子里通常占 15 到 20 分题型非常固定。小题部分一般是给你一个语言描述让你写出对应的正规式或者反过来给你正规式让你画出 NFA 或 DFA再或者给你一个 DFA 让你判断它能识别什么语言。大题部分往往是“构造一个能识别 C 语言标识符/注释/整数的词法分析器”或者是给出 DFA 要求手算最小化并填写状态转移表。哈工大课堂上的风格偏重“能不能手推”所以平时用工具一把梭的同学在这里最容易翻车。我见过不少实验拿满分的人期末词法大题却丢了五六分原因就是只会在 IDE 里写正则离开库函数就不知道 Thompson 构造法怎么画了。复习时建议按这个顺序过一遍先能写出常用语言的正规式再画 NFA再子集构造转 DFA最后用划分法最小化。这四步每步都是独立的给分点别跳步。一个小建议如果你手上是清华大学出版社第三版第二章课后题里就有大量正规式转 DFA 的经典题。期末考题不会原封不动搬课后题但题干里“长度至少为 2”“不以 0 开头”这类约束条件和课后题的出题方式几乎一样练熟之后手速会快很多。2.2 用子集构造法把 NFA 转成 DFA一个能对照手算的脚本把 NFA 转成 DFA 是期末必考的手算题但很多人卡在 ε 闭包上。手算流程其实只有三步先求出每个 NFA 状态集合的 ε 闭包再对每个输入符号求 move 集合最后把新得到的集合命名成 DFA 状态并重复直到没有新状态出现。下面这段 Python 脚本做的事情和手算完全一致可以用来对照你的草稿纸。# NFA 转移表dict[(state, symbol)] - set(states) # 用 e 表示 epsilon 转移 nfa { (0, e): {1}, (1, a): {2}, (2, e): {3}, (3, b): {4}, (4, e): {5}, } # 终态集合子集构造后只要包含 5 的 DFA 状态就是终态 accepting {5} def eps_closure(states, nfa): 求一个状态集合的 epsilon 闭包不断沿着 e 转移扩展 stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.get((s, e), set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure def move(states, symbol, nfa): 从状态集合出发读入一个符号后能到达的所有状态 res set() for s in states: res | nfa.get((s, symbol), set()) return res # 从起始状态 0 开始构造 DFA start_closure eps_closure({0}, nfa) dfa_states [start_closure] # DFA 状态用 frozenset 去重 worklist [start_closure] transitions {} while worklist: current worklist.pop() for sym in [a, b]: nxt eps_closure(move(current, sym, nfa), nfa) if not nxt: continue if nxt not in dfa_states: dfa_states.append(nxt) worklist.append(nxt) transitions[(frozenset(current), sym)] frozenset(nxt) print(DFA 状态:, len(dfa_states)) for (src, sym), dst in sorted(transitions.items(), keylambda x: str(x)): print(f{set(src)} --{sym}-- {set(dst)})这段代码里eps_closure用栈反复扩展 ε 可达状态move负责收集读入一个字符后的目标状态集合。手算时你应该在草稿纸上画一张表第一列是新 DFA 状态编号第二列是状态集合内容第三四列分别是读入 a 和 b 之后的新集合。脚本输出的set(src)就是纸上那张表的内容。注意 NFA 状态编号从 0 开始转移表里的(state, symbol)键值对一定要写全漏掉一条 ε 转移会让闭包少算一个状态这也是最隐蔽的丢分点。2.3 DFA 最小化的划分法终态非终态分组后还要再查一遍最小化 DFA 期末常考而且喜欢在“不可达状态”和“分组后再细分”这两个地方设坑。标准方法是先把所有状态分成两堆终态一堆、非终态一堆然后反复检查同一组里的两个状态读入同一个字符后如果落到了不同的组就必须拆开。重复到所有组不再变化为止。以 2.2 节构造出的 DFA 为例假设它有 6 个状态其中包含终态{5}的 DFA 状态是终态。第一轮划分自然是“终态组和非终态组”。然后对非终态组里的每个状态逐个检查读入 a、b 后落到哪个组。这里最容易犯的错是只检查一个符号就下了结论漏掉另一个符号也会导致分组不同。我的习惯是先画一张“读入符号后的落点矩阵”行是状态列是 a 和 b格子填组号然后再决定要不要拆分。另一个高频错误是忘了先删除不可达状态。正规式转出来的 DFA 偶尔会有从起始状态够不到的孤立状态最小化之前必须把它们剔除否则结果会多出一个永远用不上的组最终答案和标准答案对不上。删除不可达状态的方法是从起始状态出发做 BFS能访问到的才保留。3. 语法分析复习FIRST/FOLLOW手算顺序、LL(1)表与LR冲突处理3.1 求FIRST的迭代顺序先把能推出ε的非终结符找全语法分析是编译原理期末的绝对主力分值通常在 30 分以上。FIRST 和 FOLLOW 是所有后续题目的地基算错一个LL(1) 分析表和 LR 归约判断都会连环出错。求 FIRST 集合的标准流程是先把每个非终结符的 FIRST 初始化为空集然后反复扫描所有产生式直到一轮扫描下来没有新元素加入。关键点在处理 ε。看产生式A → X1 X2 ... Xn先看 X1如果 X1 是终结符直接把 X1 加入 FIRST(A)然后停止如果 X1 是非终结符把 FIRST(X1) 中除 ε 之外的全部元素加入 FIRST(A)如果 ε 在 FIRST(X1) 里就继续看 X2依次类推。如果所有 Xi 的 FIRST 都包含 ε那么 ε 也要加入 FIRST(A)。计算顺序上有个血泪经验一定要先找出“哪些非终结符能推出 ε”因为这个结论在 FOLLow 计算里还要再用一遍。建议先把所有产生式左边扫一遍标记能推出 ε 的符号再去算 FIRST否则边算边回头补 ε 集合很容易漏。下面这个脚本按“反复迭代直到不变”的方式实现 FIRST 计算保证和手算过程一致。productions [ (E, [T, E]), (E, [, T, E]), (E, []), # 空列表表示 ε 产生式 (T, [F, T]), (T, [*, F, T]), (T, []), (F, [(, E, )]), (F, [id]), ] FIRST {} for lhs, _ in productions: FIRST.setdefault(lhs, set()) changed True while changed: changed False for lhs, rhs in productions: if not rhs: # A - ε if ε not in FIRST[lhs]: FIRST[lhs].add(ε) changed True continue for sym in rhs: if sym.isupper(): # 非终结符 before len(FIRST[lhs]) FIRST[lhs] | (FIRST[sym] - {ε}) if len(FIRST[lhs]) ! before: changed True if ε not in FIRST[sym]: break # 当前符号不能推出 ε停止 else: # 终结符 if sym not in FIRST[lhs]: FIRST[lhs].add(sym) changed True break这段脚本用while changed做不动点迭代对应手算时的“反复扫描直到不再变化”。空列表[]表示 ε 产生式终结符直接用字符串如、(、id表示非终结符用大写字母开头。参数改起来很容易把文法产生式按同样的元组格式填进去就行。手算时我建议先手动标记能推 ε 的非终结符再对照脚本输出检查通常能发现的错误都是“漏了把 ε 从 FIRST 里去掉”或“提前 break 导致少加了元素”。3.2 构造LL(1)分析表冲突判定与消除左递归的标准动作构造 LL(1) 分析表只有两步对每个产生式A → α把FIRST(α)里的每个终结符填入表A行对应的列如果ε ∈ FIRST(α)再把FOLLOW(A)里的每个终结符也填入。填完以后表格里任何一个格子如果出现了两个产生式就说明这个文法不是 LL(1) 文法。期末最常考的 LL(1) 冲突有两种第一种是两个产生式右部 FIRST 集合相交比如S → if E then S | if E then S else S第二种是某个产生式能推出 ε且它的 FIRST 集合和 FOLLOW 集合有交集。前者的标准解法是提取左因子后者通常意味着文法有歧义或需要改写。消除左递归也是 LL(1) 复习里必考的动作。比如E → E T | T要改写成E → T E然后E → T E | ε。提取左因子的套路是把公共前缀提到外面剩下的部分用一个新增非终结符承接。这一步在综合大题里往往是第二问前面文法给得越复杂这里越需要耐心因为提取不干净后面分析表一定填不出。3.3 LR分析表的构造路径项目集规范族与SLR冲突的真实原因LR 部分期末通常考 LR(0) 项目集规范族、SLR 分析表构造和“给出输入串写出分析过程”。项目集的构造核心是 closure 和 goto 两个操作。closure 的规则是如果项目A → α . B β中的点后面是非终结符 B就把所有B → . γ加入当前项目集。goto 则是把点号后移一位后做 closure。SLR 冲突判断是翻车重灾区。如果一个项目集里同时出现了A → α .归约项目和B → β . a γ移进项目且 a 在 FOLLOW(A) 里就会产生移进归约冲突。SLR 的做法是检查 a 是否在 FOLLOW(A) 中在则归约不在则移进。问题在于 FOLLOW 集合往往比真正的文法前缀信息宽会把不该归约的符号也算进来所以很多文法 SLR 有冲突但 LR(1) 没有。这里有一个可以对照调试的最小例子。考虑文法S → id EE → E id | id它在某些项目集里会出现“看到 id 时既可以归约 E → id也可以移进 后面的内容”的假象。手算时我的经验是项目集里每出现一个归约项目就把它右侧的终结符逐个和当前输入符号对一遍不要在整张表做完后再统一判断更容易定位冲突来自哪个项目集。4. 语法制导翻译与中间代码属性文法、三地址码与回填技术4.1 S属性与L属性期末考的是综合/继承属性的区别语法制导翻译部分的期末题通常以属性文法填空或计算题形式出现。S 属性文法只用综合属性可以在自底向上分析的归约过程中边归约边计算L 属性文法允许继承属性但继承属性必须来自“左边的兄弟节点或父节点”所以适合自顶向下分析。判断一个属性是综合属性还是继承属性是基本功。综合属性在产生式左部非终结符上值由右部子节点的属性算出来继承属性在产生式右部非终结符上值来自左部或左边的兄弟。期末常考的表达式求值题比如给出E → E1 T且E.val E1.val T.val这是典型的综合属性而D → T id里id.type T.type就是继承属性。这部分计算题套路很固定先标出每个产生式对应的语义规则然后按分析树从下往上或从上往下逐层代值。只要属性类别判断对了计算本身不难丢分大多是因为把继承属性当成综合属性导致自底向上计算时发现某个值还没算出来。我的建议是拿到题先花三十秒标属性类别再动手填空。4.2 赋值语句与表达式的三地址码生成一个可运行的翻译小例三地址码生成是期末大题的最后一问常见考法是给你一个赋值语句a : b * c d要求写出翻译后的三地址指令序列。手算逻辑是从表达式的最深层开始每个运算符产生一条新指令用临时变量保存中间结果最终把结果赋给左部变量。下面这段 Python 模拟了递归生成三地址码的过程。# 表达式 2 * a b 的三地址码生成模拟 # 语法树节点用简单对象表示 class Node: def __init__(self, opNone, leftNone, rightNone, nameNone): self.op op self.left left self.right right self.name name # 叶节点变量名或常量 temp_count 0 def newtemp(): global temp_count temp_count 1 return ft{temp_count} def gen(node): 返回节点值所在的地址并打印生成的三地址指令 if node.op is None: # 叶节点 return node.name left_addr gen(node.left) right_addr gen(node.right) tmp newtemp() print(f{tmp} {left_addr} {node.op} {right_addr}) return tmp # 构造语法树2 * a b leaf2 Node(name2) leafa Node(namea) leafb Node(nameb) mul Node(op*, leftleaf2, rightleafa) root Node(op, leftmul, rightleafb) result gen(root) print(fresult {result})运行后会输出三条指令先算t1 2 * a再算t2 t1 b最后result t2。代码里newtemp()负责生成编号递增的临时变量gen函数对每个运算符节点先递归生成左右操作数再申请新临时变量并打印指令。手算时你也按这个顺序写先从最深的算子开始给每个中间结果编号不要跳步。参数需要注意的一点是叶节点直接返回变量名或常量名不生成临时变量只有运算结果才需要新临时变量。期末时如果题目要求写四元式把打印格式换成(op, arg1, arg2, result)即可。4.3 数组地址计算与布尔表达式短路两个常考翻译场景数组下标地址计算是期末选择题和填空题的常客。按行优先存储时a[i][j]的地址公式是base ((i - low1) * n (j - low2)) * w其中n是第二维的长度w是每个元素占用的字节数low1和low2是下标下界。一个典型考题是int a[10][20]起始地址base元素大小 4 字节求a[i][j]的地址。答案就是base (i * 20 j) * 4。最容易翻车的地方是忘记乘w或者把i * 20和j的顺序写反。布尔表达式短路翻译是期中期末考试都爱考的大题点。比如if (A or B) then S的翻译需要让A为真时直接跳到S的代码A为假时才计算B。这里的跳转目标一开始是未知的所以标准技术是“回填”backpatching先给跳转指令留空等后续标号确定后再把目标地址填进去。期末手算时画表格分三列“四元式序号”“操作符”“跳转目标先空着”最后再统一填标号比边写边填目标清晰得多。5. 期末复习避坑五个高频翻车现场与排查方法5.1 FOLLOW集合算错现象、原因与表格化重算现象FOLLOW 集合里多一个或少一个终结符导致 LL(1) 分析表空白格里冒出多余产生式或者 LR 归约判断出错。原因FOLLOW 计算依赖“产生式右部出现非终结符的位置”很多人算A → B C时只知道把 FOLLOW(B) 加入 FOLLOW(C)却忘了C后面没有符号时还要把 FOLLOW(A) 加入 FOLLOW(C)或者漏掉B → ε时还要继续往后看的规则。解决每轮迭代都把所有产生式完整扫一遍并且把“能推出 ε 的非终结符”列在草稿纸顶部扫描时逐个对照。最后用一个小符号串做验证比如对E → T E | εFOLLOW(E) 一定包含$和)如果算出来缺了其中一个就回头查产生式里的位置。5.2 LR分析表冲突画错SLR的FOLLOW信息不够用现象同一个(状态, 输入符号)的格子里既写了 s移进又写了 r归约但你确定文法本身没有歧义。原因SLR 用 FOLLOW 集合决定归约而 FOLLOW 集合包含了文法的所有上下文信息范围太宽。比如文法中某个非终结符理论上在特定位置根本不该归约但 FOLLOW 里有这个输入符号SLR 就误判为冲突。解决先检查是不是自己把 FOLLOW 算错了如果 FOLLOW 没错但仍有冲突把该状态的项目集完整写出来看看归约项目A → α .对应的向前看符号到底应该是哪些换成 LR(1) 思想重新算一遍精确的向前看符号。实际解题时也要学会在卷面上写出“SLR 冲突但 LR(1) 可解决”的结论这往往是得分点。5.3 SDT动作位置放错自底向上分析里的“中间动作”陷阱现象语法制导翻译题要求把语义动作嵌在产生式中间比如E → E1 { print() } T但你按自底向上分析写翻译结果时动作执行顺序总是不对。原因自底向上分析里产生式中间的动作无法直接执行只有当归约发生时才能执行动作而归约时整个右部已经全部入栈中间动作早就该执行了。解决把中间动作改到产生式末尾或者引入一个空的辅助非终结符M → ε把动作挂到M的产生式上。手算时如果题目指定了动作位置先标记每个动作“在哪个归约步骤触发”再写指令序列不要按阅读顺序从左到右执行。5.4 实验题词法分析器“能跑”但拿不到分最长匹配与行号维护现象期末实验题要求写词法分析器本地测试一两个输入都通过但老师给的测试集一跑就崩或漏token。原因最常见的是没有实现“最长匹配”比如输入ifx程序先把if识别成关键字剩下的x再识别成标识符而正确行为是把ifx整体识别成一个标识符。另一个高频问题是没记录行号错误恢复时跳不到准确位置。解决识别规则统一用“先匹配最长再查关键字表”——遇到字母开头的串先连续读完整串再查关键字集合是关键字就返回关键字 token否则是标识符。同时在状态里维护line变量遇到\n自增报错时带上行号。5.5 中间代码数组偏移翻车行优先与元素大小的统一公式现象计算a[i][j]地址时答案和标准答案差了几倍或者i、j的位置写反。原因只记了base i * n j忘了乘每个元素的字节数w或者把行优先误当成列优先。解决在任何卷子上都先写出完整公式addr base ((i - low1) * n (j - low2)) * w然后把n、w、low1、low2逐个代入全部带单位计算。我一般会在草稿纸上先写上“行优先 × 元素大小”再开始算避免写到一半忘记是行优先还是列优先。6. 考前一周的自检清单与两类综合大题套路考前最后一周不建议再从头翻教材而是把全部考点压缩成一张可勾选的清单逐项过。下面这张表是我自己在期末周用的自检标准每一项都要求“不看书能完整做出来”而不是“看着答案觉得懂了”。考点模块自检方式通过标准正规式转 NFA10 分钟内画出 a(ab)*b 的 NFANFA 转 DFA对上一步结果做子集构造表格完整终态判定正确DFA 最小化对含 6-8 个状态的 DFA 做划分法两轮划分后状态数稳定FIRST/FOLLOW手算含 ε 和左递归的文法与脚本或同学结果一致LL(1) 冲突判断构造分析表并标出所有冲突格能准确说出冲突来自哪些产生式LR(0) 项目集为一个 4 产生式文法构造项目集规范族goto 表与闭包结果无误三地址码生成翻译赋值语句a : b*c d临时变量编号与指令顺序正确回填技术翻译if A or B then S跳转目标最后全部正确填上两类综合大题建议各练一道代表题。第一类是词法综合给定语言描述依次写出正规式、画 NFA、子集构造、最小化、写词法分析器骨架。答题顺序严格按四步走最后一步注意“最长匹配”和“关键字优先查表”。第二类是语法语义综合给一个表达式文法先消除左递归再求 FIRST/FOLLOW判断 LL(1)再按 SDT 生成三地址码。翻译动作写在产生式右侧逐句生成指令临时变量从 t1 开始连续编号。每次复习到最后一晚我都会把 FOLLOW 和 LR 项目集各重算一遍这两处是我翻车最多的地方而且一错就是连环错。后来养成一个习惯所有分析表先拿铅笔打草稿再用不同颜色标终态和归约项目错误率立刻降下来。考前照着上面这张表逐项打勾比盲目刷题踏实得多。希望帮到你。本文还有配套的精品资源点击获取
简介这份《哈工大编译原理期末复习完整版》面向计算机专业本科生与考研、期末备考人群系统梳理编译原理全流程知识涵盖编译系统结构、语言文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等核心模块。内容从编译程序生成、正则表达式与有穷自动机到四元式与寄存器分配均有细致笔记与示例可帮助读者快速搭建知识框架、对照复习重点并查漏补缺。资源为PDF格式整包1个文件约31.14MB便携易用适合在电脑、平板与手机端随时翻阅。这份复习资料已有2311人下载学习经过较多学习者验证。无论是考前冲刺还是系统回顾编译原理这份完整版笔记都能提供扎实的知识支撑与清晰的复习主线。1. 哈工大编译原理期末复习一条主线串起整门课别按目录从头背“哈工大编译原理期末复习完整版涵盖编译原理所有内容”这个标题看起来很吓人但真正把它拆开看编译原理的期末卷其实永远在考同一条主线词法分析、语法分析、语法制导翻译与中间代码外加少量运行环境和代码生成的小题。只要先把这条主线走通再回头补课后题和实验就不需要从教材第一个字背到最后一个字。这套复习路径适合三类人考前还有两三周的在校生、想转码但被龙书劝退的自学者、以及实验能跑但理论题老丢分的动手党。如果你只剩三天那就只抓第二、三、四章其余章节当作查缺补漏。接下来我会按这条线把每个考点的原理、手算方法、参数设置和踩坑位置一次讲透。2. 词法分析复习从正规式到DFA的三步手算流程与最小化表格法2.1 期末卷面上词法分析考什么三道小题加一道大题的常见配比词法分析在期末卷子里通常占 15 到 20 分题型非常固定。小题部分一般是给你一个语言描述让你写出对应的正规式或者反过来给你正规式让你画出 NFA 或 DFA再或者给你一个 DFA 让你判断它能识别什么语言。大题部分往往是“构造一个能识别 C 语言标识符/注释/整数的词法分析器”或者是给出 DFA 要求手算最小化并填写状态转移表。哈工大课堂上的风格偏重“能不能手推”所以平时用工具一把梭的同学在这里最容易翻车。我见过不少实验拿满分的人期末词法大题却丢了五六分原因就是只会在 IDE 里写正则离开库函数就不知道 Thompson 构造法怎么画了。复习时建议按这个顺序过一遍先能写出常用语言的正规式再画 NFA再子集构造转 DFA最后用划分法最小化。这四步每步都是独立的给分点别跳步。一个小建议如果你手上是清华大学出版社第三版第二章课后题里就有大量正规式转 DFA 的经典题。期末考题不会原封不动搬课后题但题干里“长度至少为 2”“不以 0 开头”这类约束条件和课后题的出题方式几乎一样练熟之后手速会快很多。2.2 用子集构造法把 NFA 转成 DFA一个能对照手算的脚本把 NFA 转成 DFA 是期末必考的手算题但很多人卡在 ε 闭包上。手算流程其实只有三步先求出每个 NFA 状态集合的 ε 闭包再对每个输入符号求 move 集合最后把新得到的集合命名成 DFA 状态并重复直到没有新状态出现。下面这段 Python 脚本做的事情和手算完全一致可以用来对照你的草稿纸。# NFA 转移表dict[(state, symbol)] - set(states) # 用 e 表示 epsilon 转移 nfa { (0, e): {1}, (1, a): {2}, (2, e): {3}, (3, b): {4}, (4, e): {5}, } # 终态集合子集构造后只要包含 5 的 DFA 状态就是终态 accepting {5} def eps_closure(states, nfa): 求一个状态集合的 epsilon 闭包不断沿着 e 转移扩展 stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.get((s, e), set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure def move(states, symbol, nfa): 从状态集合出发读入一个符号后能到达的所有状态 res set() for s in states: res | nfa.get((s, symbol), set()) return res # 从起始状态 0 开始构造 DFA start_closure eps_closure({0}, nfa) dfa_states [start_closure] # DFA 状态用 frozenset 去重 worklist [start_closure] transitions {} while worklist: current worklist.pop() for sym in [a, b]: nxt eps_closure(move(current, sym, nfa), nfa) if not nxt: continue if nxt not in dfa_states: dfa_states.append(nxt) worklist.append(nxt) transitions[(frozenset(current), sym)] frozenset(nxt) print(DFA 状态:, len(dfa_states)) for (src, sym), dst in sorted(transitions.items(), keylambda x: str(x)): print(f{set(src)} --{sym}-- {set(dst)})这段代码里eps_closure用栈反复扩展 ε 可达状态move负责收集读入一个字符后的目标状态集合。手算时你应该在草稿纸上画一张表第一列是新 DFA 状态编号第二列是状态集合内容第三四列分别是读入 a 和 b 之后的新集合。脚本输出的set(src)就是纸上那张表的内容。注意 NFA 状态编号从 0 开始转移表里的(state, symbol)键值对一定要写全漏掉一条 ε 转移会让闭包少算一个状态这也是最隐蔽的丢分点。2.3 DFA 最小化的划分法终态非终态分组后还要再查一遍最小化 DFA 期末常考而且喜欢在“不可达状态”和“分组后再细分”这两个地方设坑。标准方法是先把所有状态分成两堆终态一堆、非终态一堆然后反复检查同一组里的两个状态读入同一个字符后如果落到了不同的组就必须拆开。重复到所有组不再变化为止。以 2.2 节构造出的 DFA 为例假设它有 6 个状态其中包含终态{5}的 DFA 状态是终态。第一轮划分自然是“终态组和非终态组”。然后对非终态组里的每个状态逐个检查读入 a、b 后落到哪个组。这里最容易犯的错是只检查一个符号就下了结论漏掉另一个符号也会导致分组不同。我的习惯是先画一张“读入符号后的落点矩阵”行是状态列是 a 和 b格子填组号然后再决定要不要拆分。另一个高频错误是忘了先删除不可达状态。正规式转出来的 DFA 偶尔会有从起始状态够不到的孤立状态最小化之前必须把它们剔除否则结果会多出一个永远用不上的组最终答案和标准答案对不上。删除不可达状态的方法是从起始状态出发做 BFS能访问到的才保留。3. 语法分析复习FIRST/FOLLOW手算顺序、LL(1)表与LR冲突处理3.1 求FIRST的迭代顺序先把能推出ε的非终结符找全语法分析是编译原理期末的绝对主力分值通常在 30 分以上。FIRST 和 FOLLOW 是所有后续题目的地基算错一个LL(1) 分析表和 LR 归约判断都会连环出错。求 FIRST 集合的标准流程是先把每个非终结符的 FIRST 初始化为空集然后反复扫描所有产生式直到一轮扫描下来没有新元素加入。关键点在处理 ε。看产生式A → X1 X2 ... Xn先看 X1如果 X1 是终结符直接把 X1 加入 FIRST(A)然后停止如果 X1 是非终结符把 FIRST(X1) 中除 ε 之外的全部元素加入 FIRST(A)如果 ε 在 FIRST(X1) 里就继续看 X2依次类推。如果所有 Xi 的 FIRST 都包含 ε那么 ε 也要加入 FIRST(A)。计算顺序上有个血泪经验一定要先找出“哪些非终结符能推出 ε”因为这个结论在 FOLLow 计算里还要再用一遍。建议先把所有产生式左边扫一遍标记能推出 ε 的符号再去算 FIRST否则边算边回头补 ε 集合很容易漏。下面这个脚本按“反复迭代直到不变”的方式实现 FIRST 计算保证和手算过程一致。productions [ (E, [T, E]), (E, [, T, E]), (E, []), # 空列表表示 ε 产生式 (T, [F, T]), (T, [*, F, T]), (T, []), (F, [(, E, )]), (F, [id]), ] FIRST {} for lhs, _ in productions: FIRST.setdefault(lhs, set()) changed True while changed: changed False for lhs, rhs in productions: if not rhs: # A - ε if ε not in FIRST[lhs]: FIRST[lhs].add(ε) changed True continue for sym in rhs: if sym.isupper(): # 非终结符 before len(FIRST[lhs]) FIRST[lhs] | (FIRST[sym] - {ε}) if len(FIRST[lhs]) ! before: changed True if ε not in FIRST[sym]: break # 当前符号不能推出 ε停止 else: # 终结符 if sym not in FIRST[lhs]: FIRST[lhs].add(sym) changed True break这段脚本用while changed做不动点迭代对应手算时的“反复扫描直到不再变化”。空列表[]表示 ε 产生式终结符直接用字符串如、(、id表示非终结符用大写字母开头。参数改起来很容易把文法产生式按同样的元组格式填进去就行。手算时我建议先手动标记能推 ε 的非终结符再对照脚本输出检查通常能发现的错误都是“漏了把 ε 从 FIRST 里去掉”或“提前 break 导致少加了元素”。3.2 构造LL(1)分析表冲突判定与消除左递归的标准动作构造 LL(1) 分析表只有两步对每个产生式A → α把FIRST(α)里的每个终结符填入表A行对应的列如果ε ∈ FIRST(α)再把FOLLOW(A)里的每个终结符也填入。填完以后表格里任何一个格子如果出现了两个产生式就说明这个文法不是 LL(1) 文法。期末最常考的 LL(1) 冲突有两种第一种是两个产生式右部 FIRST 集合相交比如S → if E then S | if E then S else S第二种是某个产生式能推出 ε且它的 FIRST 集合和 FOLLOW 集合有交集。前者的标准解法是提取左因子后者通常意味着文法有歧义或需要改写。消除左递归也是 LL(1) 复习里必考的动作。比如E → E T | T要改写成E → T E然后E → T E | ε。提取左因子的套路是把公共前缀提到外面剩下的部分用一个新增非终结符承接。这一步在综合大题里往往是第二问前面文法给得越复杂这里越需要耐心因为提取不干净后面分析表一定填不出。3.3 LR分析表的构造路径项目集规范族与SLR冲突的真实原因LR 部分期末通常考 LR(0) 项目集规范族、SLR 分析表构造和“给出输入串写出分析过程”。项目集的构造核心是 closure 和 goto 两个操作。closure 的规则是如果项目A → α . B β中的点后面是非终结符 B就把所有B → . γ加入当前项目集。goto 则是把点号后移一位后做 closure。SLR 冲突判断是翻车重灾区。如果一个项目集里同时出现了A → α .归约项目和B → β . a γ移进项目且 a 在 FOLLOW(A) 里就会产生移进归约冲突。SLR 的做法是检查 a 是否在 FOLLOW(A) 中在则归约不在则移进。问题在于 FOLLOW 集合往往比真正的文法前缀信息宽会把不该归约的符号也算进来所以很多文法 SLR 有冲突但 LR(1) 没有。这里有一个可以对照调试的最小例子。考虑文法S → id EE → E id | id它在某些项目集里会出现“看到 id 时既可以归约 E → id也可以移进 后面的内容”的假象。手算时我的经验是项目集里每出现一个归约项目就把它右侧的终结符逐个和当前输入符号对一遍不要在整张表做完后再统一判断更容易定位冲突来自哪个项目集。4. 语法制导翻译与中间代码属性文法、三地址码与回填技术4.1 S属性与L属性期末考的是综合/继承属性的区别语法制导翻译部分的期末题通常以属性文法填空或计算题形式出现。S 属性文法只用综合属性可以在自底向上分析的归约过程中边归约边计算L 属性文法允许继承属性但继承属性必须来自“左边的兄弟节点或父节点”所以适合自顶向下分析。判断一个属性是综合属性还是继承属性是基本功。综合属性在产生式左部非终结符上值由右部子节点的属性算出来继承属性在产生式右部非终结符上值来自左部或左边的兄弟。期末常考的表达式求值题比如给出E → E1 T且E.val E1.val T.val这是典型的综合属性而D → T id里id.type T.type就是继承属性。这部分计算题套路很固定先标出每个产生式对应的语义规则然后按分析树从下往上或从上往下逐层代值。只要属性类别判断对了计算本身不难丢分大多是因为把继承属性当成综合属性导致自底向上计算时发现某个值还没算出来。我的建议是拿到题先花三十秒标属性类别再动手填空。4.2 赋值语句与表达式的三地址码生成一个可运行的翻译小例三地址码生成是期末大题的最后一问常见考法是给你一个赋值语句a : b * c d要求写出翻译后的三地址指令序列。手算逻辑是从表达式的最深层开始每个运算符产生一条新指令用临时变量保存中间结果最终把结果赋给左部变量。下面这段 Python 模拟了递归生成三地址码的过程。# 表达式 2 * a b 的三地址码生成模拟 # 语法树节点用简单对象表示 class Node: def __init__(self, opNone, leftNone, rightNone, nameNone): self.op op self.left left self.right right self.name name # 叶节点变量名或常量 temp_count 0 def newtemp(): global temp_count temp_count 1 return ft{temp_count} def gen(node): 返回节点值所在的地址并打印生成的三地址指令 if node.op is None: # 叶节点 return node.name left_addr gen(node.left) right_addr gen(node.right) tmp newtemp() print(f{tmp} {left_addr} {node.op} {right_addr}) return tmp # 构造语法树2 * a b leaf2 Node(name2) leafa Node(namea) leafb Node(nameb) mul Node(op*, leftleaf2, rightleafa) root Node(op, leftmul, rightleafb) result gen(root) print(fresult {result})运行后会输出三条指令先算t1 2 * a再算t2 t1 b最后result t2。代码里newtemp()负责生成编号递增的临时变量gen函数对每个运算符节点先递归生成左右操作数再申请新临时变量并打印指令。手算时你也按这个顺序写先从最深的算子开始给每个中间结果编号不要跳步。参数需要注意的一点是叶节点直接返回变量名或常量名不生成临时变量只有运算结果才需要新临时变量。期末时如果题目要求写四元式把打印格式换成(op, arg1, arg2, result)即可。4.3 数组地址计算与布尔表达式短路两个常考翻译场景数组下标地址计算是期末选择题和填空题的常客。按行优先存储时a[i][j]的地址公式是base ((i - low1) * n (j - low2)) * w其中n是第二维的长度w是每个元素占用的字节数low1和low2是下标下界。一个典型考题是int a[10][20]起始地址base元素大小 4 字节求a[i][j]的地址。答案就是base (i * 20 j) * 4。最容易翻车的地方是忘记乘w或者把i * 20和j的顺序写反。布尔表达式短路翻译是期中期末考试都爱考的大题点。比如if (A or B) then S的翻译需要让A为真时直接跳到S的代码A为假时才计算B。这里的跳转目标一开始是未知的所以标准技术是“回填”backpatching先给跳转指令留空等后续标号确定后再把目标地址填进去。期末手算时画表格分三列“四元式序号”“操作符”“跳转目标先空着”最后再统一填标号比边写边填目标清晰得多。5. 期末复习避坑五个高频翻车现场与排查方法5.1 FOLLOW集合算错现象、原因与表格化重算现象FOLLOW 集合里多一个或少一个终结符导致 LL(1) 分析表空白格里冒出多余产生式或者 LR 归约判断出错。原因FOLLOW 计算依赖“产生式右部出现非终结符的位置”很多人算A → B C时只知道把 FOLLOW(B) 加入 FOLLOW(C)却忘了C后面没有符号时还要把 FOLLOW(A) 加入 FOLLOW(C)或者漏掉B → ε时还要继续往后看的规则。解决每轮迭代都把所有产生式完整扫一遍并且把“能推出 ε 的非终结符”列在草稿纸顶部扫描时逐个对照。最后用一个小符号串做验证比如对E → T E | εFOLLOW(E) 一定包含$和)如果算出来缺了其中一个就回头查产生式里的位置。5.2 LR分析表冲突画错SLR的FOLLOW信息不够用现象同一个(状态, 输入符号)的格子里既写了 s移进又写了 r归约但你确定文法本身没有歧义。原因SLR 用 FOLLOW 集合决定归约而 FOLLOW 集合包含了文法的所有上下文信息范围太宽。比如文法中某个非终结符理论上在特定位置根本不该归约但 FOLLOW 里有这个输入符号SLR 就误判为冲突。解决先检查是不是自己把 FOLLOW 算错了如果 FOLLOW 没错但仍有冲突把该状态的项目集完整写出来看看归约项目A → α .对应的向前看符号到底应该是哪些换成 LR(1) 思想重新算一遍精确的向前看符号。实际解题时也要学会在卷面上写出“SLR 冲突但 LR(1) 可解决”的结论这往往是得分点。5.3 SDT动作位置放错自底向上分析里的“中间动作”陷阱现象语法制导翻译题要求把语义动作嵌在产生式中间比如E → E1 { print() } T但你按自底向上分析写翻译结果时动作执行顺序总是不对。原因自底向上分析里产生式中间的动作无法直接执行只有当归约发生时才能执行动作而归约时整个右部已经全部入栈中间动作早就该执行了。解决把中间动作改到产生式末尾或者引入一个空的辅助非终结符M → ε把动作挂到M的产生式上。手算时如果题目指定了动作位置先标记每个动作“在哪个归约步骤触发”再写指令序列不要按阅读顺序从左到右执行。5.4 实验题词法分析器“能跑”但拿不到分最长匹配与行号维护现象期末实验题要求写词法分析器本地测试一两个输入都通过但老师给的测试集一跑就崩或漏token。原因最常见的是没有实现“最长匹配”比如输入ifx程序先把if识别成关键字剩下的x再识别成标识符而正确行为是把ifx整体识别成一个标识符。另一个高频问题是没记录行号错误恢复时跳不到准确位置。解决识别规则统一用“先匹配最长再查关键字表”——遇到字母开头的串先连续读完整串再查关键字集合是关键字就返回关键字 token否则是标识符。同时在状态里维护line变量遇到\n自增报错时带上行号。5.5 中间代码数组偏移翻车行优先与元素大小的统一公式现象计算a[i][j]地址时答案和标准答案差了几倍或者i、j的位置写反。原因只记了base i * n j忘了乘每个元素的字节数w或者把行优先误当成列优先。解决在任何卷子上都先写出完整公式addr base ((i - low1) * n (j - low2)) * w然后把n、w、low1、low2逐个代入全部带单位计算。我一般会在草稿纸上先写上“行优先 × 元素大小”再开始算避免写到一半忘记是行优先还是列优先。6. 考前一周的自检清单与两类综合大题套路考前最后一周不建议再从头翻教材而是把全部考点压缩成一张可勾选的清单逐项过。下面这张表是我自己在期末周用的自检标准每一项都要求“不看书能完整做出来”而不是“看着答案觉得懂了”。考点模块自检方式通过标准正规式转 NFA10 分钟内画出 a(ab)*b 的 NFANFA 转 DFA对上一步结果做子集构造表格完整终态判定正确DFA 最小化对含 6-8 个状态的 DFA 做划分法两轮划分后状态数稳定FIRST/FOLLOW手算含 ε 和左递归的文法与脚本或同学结果一致LL(1) 冲突判断构造分析表并标出所有冲突格能准确说出冲突来自哪些产生式LR(0) 项目集为一个 4 产生式文法构造项目集规范族goto 表与闭包结果无误三地址码生成翻译赋值语句a : b*c d临时变量编号与指令顺序正确回填技术翻译if A or B then S跳转目标最后全部正确填上两类综合大题建议各练一道代表题。第一类是词法综合给定语言描述依次写出正规式、画 NFA、子集构造、最小化、写词法分析器骨架。答题顺序严格按四步走最后一步注意“最长匹配”和“关键字优先查表”。第二类是语法语义综合给一个表达式文法先消除左递归再求 FIRST/FOLLOW判断 LL(1)再按 SDT 生成三地址码。翻译动作写在产生式右侧逐句生成指令临时变量从 t1 开始连续编号。每次复习到最后一晚我都会把 FOLLOW 和 LR 项目集各重算一遍这两处是我翻车最多的地方而且一错就是连环错。后来养成一个习惯所有分析表先拿铅笔打草稿再用不同颜色标终态和归约项目错误率立刻降下来。考前照着上面这张表逐项打勾比盲目刷题踏实得多。希望帮到你。本文还有配套的精品资源点击获取
