简介《哈工大-编译原理-习题及答案汇总.pdf》是一份面向编译原理课程学习者的习题汇编资料重点覆盖源程序、目标程序、翻译程序、编译程序与解释程序的概念及关系以及编译系统各组成部分的主要功能。内容同时也涉及前后文无关文法与语言、语法树、二义性文法判定与化简、ε产生式消去等常考章节适合哈工大学子及其他高校计算机专业学生用于课后巩固、考研复习或期末突击。资源本身仅包含1个PDF文件整体大小约1.6MB内容紧凑、按章节组织目前已获得1743人学习下载。文件将习题与答案解析对照呈现在解释程序与编译程序工作方式的区别、C语言关键字及括号和逗号的多种用途、构造文法和消去无用产生式等典型题目上均有细致展开便于读者针对薄弱环节快速定位并专项突破是一份值得反复研读的课程配套资料。1. 在算法题刷无可刷的节点上很多人的复习盲区是编译原理半小时能做三道 LeetCode却在一道求 First 集合的题上卡了二十分钟这种事放在求职季特别常见。刷题带来的正反馈太强让人产生一种“基础都在手”的错觉。可一到涉及编译原理的面试题比如问“static 局部变量在符号表里怎么登记”“为什么 C 语言要求声明在前”这类实际考点经验丰富的从业者也常常说不到点子上。原因很简单编译原理的知识密度高、抽象层级多从正则到自动机从文法到分析表每一步都建立在前面概念之上。靠通读教材效率太低最有效的方式就是把前辈整理好的习题和答案作为复习主线——先看问题再定位理论最后通过答案反推自己的知识漏洞。这篇内容就围绕“哈工大-编译原理-习题及答案汇总.pdf”这类复习材料把词法分析、语法分析、语义分析、中间代码、优化这几条主线的经典题型和解题套路连同答案里容易忽略的细节一起拆开讲。2. 编译原理复习的主线词法、语法、语义与代码生成的连续脉络2.1 词法分析正则到 NFA 再到 DFA 是复习的第一道关词法分析题是所有习题集的起点。无论是哈工大还是其他学校的讲义第一类大题型基本都是“给出正规式构造 NFA再确定化为 DFA最后最小化”。这背后是一整套固定流程Thompson 构造法把每个正则表达式拆成带 ε 转移的 NFA子集构造法把 NFA 的状态集合映射为 DFA 的状态最后通过划分法消除等价状态。手工做题时我一般按三步走先拆正则表达式的最外层运算。比如(a|b)*abb最外层是连接先处理(a|b)*再连接abb。用 Thompson 构造法从左到右拼接 NFA 片段ε 边专门用来连接子片段。子集构造法求 DFA 时每个 DFA 状态是一个 NFA 状态集合要先用 ε-闭包打底再对每个输入符号求 move 闭包。下面是一段辅助验证的 Python 脚本可以帮你手工求 ε-闭包时核对结果def epsilon_closure(states, transitions): stack list(states) closure set(states) while stack: s stack.pop() for t in transitions.get(s, []): if t[0] ε and t[1] not in closure: closure.add(t[1]) stack.append(t[1]) return closure # 示例NFA 状态 0 通过 ε 能到达 {1, 2} transitions { 0: [(ε, 1)], 1: [(ε, 2), (a, 3)], 2: [(b, 4)], } print(epsilon_closure({0}, transitions)) # {0, 1, 2}这段代码的逻辑是stack保存待扩散的状态closure记录已收集的状态每次弹出一个状态扫描它的所有转移边如果边上是 ε 且目标状态尚未收录就加入闭包并压栈。实际刷题时考卷上通常要求手写闭包结果这个脚本的意义在于帮你建立“闭包就是不断沿 ε 边走”的直觉。除了 NFA 转 DFA词法分析习题里出现频率极高的另一个考点是直接用正则描述语言然后指出该正则对应的 DFA 最少需要几个状态。常见的陷阱是“最少状态数”忘了做最小化。北京理工、哈工大等多套真题里都出现过(a|b)*a(a|b)这种形式很多人的第一反应是画出 4 个状态但最小化后其实只有 3 个。原因在于状态 2 和状态 3 在读入a和b后的转移完全一致且同为接受状态划分法第一步就会把它们合并。提示答案里凡是出现“最简 DFA”或“最小 DFA”别只看最终图要自己拿划分法重新做一遍。划分法的终止条件是每个组内状态对所有输入符号都落在同一个组里这一步手工算很快但特别练耐心。2.2 语法分析LL(1) 与 LR(1) 的习题套路语法分析是编译原理习题集中占篇幅最大的一章。题型可以粗略分成三类计算 First 与 Follow 集合、判断文法是否为 LL(1)、构造 LR 分析表或 SLR 分析表。这三类题层层递进答案里给出的通常只是最终表格但做题时真正容易出错的恰恰是中间计算。先看 First 集合。规则是对每个产生式A - X1 X2 ... Xn先看X1如果X1是终结符则把X1加入First(A)如果X1是非终结符则把First(X1)中除 ε 外的所有符号加入如果X1能推出 ε再看X2以此类推。这里有一个常见的边界条件如果所有Xi都能推出 ε那么 ε 也要加入First(A)。Follow 集合的边界条件更多。Follow(S)一定包含$这是开始符号的固有属性对形如A - αBβ的产生式Follow(B)要加入First(β)中除 ε 外的所有符号如果β能推出 ε那么Follow(B)还要加入Follow(A)。这道题做完后很多人的答案错在First(β)是空集时忘了把Follow(A)的东西传下去。下面用一个小文法演示做题时的完整计算过程。假设文法GE - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这是经典的表达式文法去掉了左递归。手工计算时我习惯先把每个非终结符的 First 集合写出来非终结符First 集合E{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }然后基于 First 集合求 Follow 集合非终结符Follow 集合E{ $, ) }E{ $, ) }T{ , $, ) }T{ , $, ) }F{ *, , $, ) }注意T的 Follow 集合里有这是因为E - T E中在T之前但 Follow 集合只管出现在非终结符之后的内容所以Follow(T)取的是E的 First 集合中去掉 ε 的部分即{}再并上Follow(E)。这是习题答案里最容易被忽略的一步。判断 LL(1) 文法的条件也在这个环节直接用上对每个非终结符的所有产生式两两之间的 First 集合交集必须为空如果某个产生式能推出 ε那么它的 First 集合与对应 Follow 集合的交集也必须为空。用上面的文法验证各产生式的 First 集合互不重叠且E - ε的 First 是{ε}与Follow(E) { $, ) }交集为空因此是 LL(1) 文法。LR 系列习题的节奏不同。构造 SLR 分析表的核心是构建 LR(0) 项目集规范族然后对每个项目集分别处理归约项目只在 Follow 集合对应的输入符号上填r移进项目直接在对应终结符列填s。常见错误是把归约动作填满了整行这意味着把 SLR 当成 LR(0) 来用在考试里会丢分。2.3 语义分析与中间代码属性文法和三地址码的对应关系语义分析章节的习题与前面完全不同——不再有“求集合”这种封闭式问题而是给出一段程序或一个文法要求写出带语义动作的翻译方案或者直接生成中间代码。这里的核心概念是文法符号的属性综合属性自下而上计算继承属性自上而下传递。最常考的是算术表达式的三地址码生成。给定a : b * -c b * -c标准答案会先画出语法树然后对每个内部节点生成临时变量。一个容易忽略的优化是公共子表达式b * -c在中间代码层面会被计算两次除非后续做局部优化。这个例子在习题答案中经常同时出现在中间代码生成和代码优化两章做的时候要把这两处对照起来看。三地址码的具体形式通常是四元式(op, arg1, arg2, result)。上面的赋值语句可以翻译为(*, b, c, t1) # t1 b * c实际是 b * (-c)负号单独处理 (uminus, t1, _, t2) # t2 -t1 (*, b, c, t3) (uminus, t3, _, t4) (, t2, t4, t5) (:, t5, _, a)在考卷上uminus是单目运算符的标准写法它只有一个操作数。很多人在这一步会直接把b写成负号作用于c然后生成(*, b, -c, t1)这不符合规范——中间代码不区分正负常量负号要显式翻译成单目运算或取负指令。语义分析章节还有一类概念题值得注意数组元素的地址计算。习题集里最常见的题目是二维数组按行优先存储给出A[10][20]、每个元素 4 字节、首地址base求A[i][j]的地址。答案是base (i * 20 j) * 4。这题看着简单但在符号表练习里会衍生出“数组内情向量表应该记录哪些字段”的问题。标准答案是维数、各维上下界、元素类型宽度。这道题的变体会在后续章节反复出现因为内情向量表在运行存储分配里要用来计算地址。3. 把习题当工程做典型题型拆解与最小复现步骤3.1 词法分析实验题手工构造词法分析器的骨架习题集中必有一道“设计一个识别某语言子集的词法分析器”通常要求识别关键字、标识符、无符号数、运算符和分隔符。教材上的答案往往是一整段 C 语言代码但对于复习来说更好的方式是理解它背后的模式一个全局扫描指针一个关键字查表一个状态转移主循环。我一般会把词法分析器拆成四个函数next_char负责从输入缓冲区取字符scan负责状态流转reserve负责查关键字表error负责词法错误恢复。下面是一个极简的标识符/关键字识别骨架可以直接照着扩展keywords {if, else, while, return, int, float} def is_id_start(ch): return ch.isalpha() or ch _ def is_id_part(ch): return ch.isalnum() or ch _ def scan_identifier(src, pos): start pos while pos len(src) and is_id_part(src[pos]): pos 1 token src[start:pos] token_type kw if token in keywords else id return token_type, token, posscan_identifier的逻辑是从当前位置开始持续消费字母、数字和下划线遇到第一个不能作为标识符组成部分的字符就停下。判断关键字用的是集合成员测试这在 C 语言里对应的是逐步比较字符串或哈希查表。要特别注意关键字匹配必须发生在标识符识别完整之后否则会错误地把ifx识别成关键字if加标识符x。词法分析器在工程上还需要处理“超前读一个字符”的问题。手工实现时常见做法是维护一个lookahead变量每次读入下一个字符后如果发现它不是当前 token 的一部分就要把它压回输入流。习题答案不会明说这个细节但几乎所有“请写出词法分析器的输入缓冲处理方案”的题目都隐含这个考点。3.2 语法分析题递归下降子程序的设计模式语法分析习题里最实用的一类是实现递归下降分析器。用前面 2.2 节的表达式文法可以直接映射成一组函数每个非终结符对应一个函数名产生式右侧的终结符对应match调用非终结符对应相应函数调用。这个映射关系本身就是复习语法分析的最佳练习。class RecursiveDescentParser: def __init__(self, tokens): self.tokens tokens self.pos 0 def match(self, expected): if self.pos len(self.tokens) and self.tokens[self.pos] expected: self.pos 1 else: raise SyntaxError(fexpected {expected}, got {self.tokens[self.pos] if self.pos len(self.tokens) else EOF}) def parse_E(self): self.parse_T() self.parse_E_prime() def parse_E_prime(self): if self.pos len(self.tokens) and self.tokens[self.pos] : self.match() self.parse_T() self.parse_E_prime() # 遇到其他符号时ε 产生式直接返回 def parse_T(self): self.parse_F() self.parse_T_prime()parse_E_prime里的if判断就是E - T E | ε的实现当前输入是就展开第一种产生式否则走 ε 分支。如果习题要求判断该文法是不是 LL(1)你会发现递归下降能跑通的前提正是 2.2 节里那个两两不相交的条件。这套代码在面试里也经常被要求手写尤其是“给你一个 JSON 子集实现解析器”这种题底层思路完全一致。3.3 代码优化题基本块划分与 DAG 重建优化章节的习题通常给一段三地址码要求划分基本块、画出 DAG、重新生成代码。基本块划分的规则很简单入口语句是基本块的第一条语句无条件转移、条件转移、停机语句都算出口。但答案里真正想考察的是你能不能通过 DAG 合并公共子表达式。下面的三地址码是一道典型的考试题t1 a * b t2 a * b t3 t1 t2 t4 t3 1划分基本块后t2 a * b与t1 a * b的右部完全一致DAG 构造时可以直接复用t1节点t3 t1 t1整个基本块从 4 条指令缩减到 3 条。答案里如果直接把t2单独画成一个节点说明出题人期望看到的是“已优化版本”。做题时要注意DAG 节点合并的前提是两个节点的运算符号和所有子节点完全相同。4. 参考答案要看门道构造题的多解思路与易错点4.1 文法改写的两道必做题左递归消除与提取左因子几乎所有习题集的文法改写题都会包含这两个操作。前者是把A - Aα | β改写成A - βA、A - αA | ε消除直接左递归后者是把A - αβ1 | αβ2提取公因子为A - αA、A - β1 | β2。这两个变换的结果基本是唯一的但考试中容易混淆消除左递归是为了适配自顶向下分析提取左因子是为了保证 LL(1) 条件中的 First 集合互不相交两者服务于不同的目的。关于间接左递归比如S - Aa、A - Sd必须先代入再消除。步骤是把非终结符排序对每个Ai检查前面的Aj产生的规则中是否包含Ai开头的右部如果有就把Aj的右部代入再消除左递归。很多答案省略了代入的中间步骤直接给最终结果这时候要自己补一遍。4.2 SLR(1) 冲突的本质移进-归约冲突不能靠直觉判断构造 LR(0) 项目集规范族后如果某个项目集同时包含A - α·和B - β·aγ在a列上就会产生归约和移进的冲突。习题答案会在表格中用红色或用括号标出冲突位置但不会详细解释冲突出现的条件。实际上判断很简单看Follow(A)里是否包含a如果包含就冲突。比如典型二义性文法E - E E | E * E | id构造 SLR 分析表时在列和*列必然出现多重动作。这也是为什么所有教材都说二义性文法不是 LR(1) 文法。掌握这个判断方法后分析表题的正确率会明显上升。4.3 习题答案中运行期存储分配相关的隐藏考点运行存储分配这一章习题答案看起来都是文字题实际暗藏计算。最常见的是“画出栈式存储分配的活动记录布局”。题目会给一个函数嵌套调用的 Pascal 或 C 程序让你画出 main 调用 fun1、fun1 调用 fun2 时栈的变化。活动记录从低地址到高地址通常是局部变量、临时变量、保存的机器状态、实参、返回地址、控制链、访问链。答案里经常出现“控制链指向调用者的活动记录底部”“访问链用于访问非局部变量”这样的句子这两条链的含义必须分清楚。提示如果答案里给出了活动记录布局图别只看图要在旁边补上 SP栈指针和 FP帧指针的指向位置。大部分考试错图都错在 FP 指向了返回地址而不是活动记录底部。4.4 符号表组织的开放寻址与链地址对比符号表习题中最容易答漏的是链地址法 vs 开放寻址法的优缺点对比。标准的答题框架是链地址法通过哈希表加链表处理冲突插入和查找的平均时间在合理负载因子下是 O(1)但额外的指针存储开销大开放寻址法不需要额外空间但删除操作复杂不能直接置空否则会切断探测序列。答案中通常会把“删除时用墓碑标记”这个细节单独列出实际工程中大多数编译器的符号表使用链地址法或动态数组组织而不是开放寻址。5. 把复习收尾在“低频考题”上运行环境、错误处理与代码生成的常见考点5.1 运行环境静态作用域与动态作用域的实现差异前面 4.3 节的活动记录对应栈式分配这一节要补充的是作用域规则。静态作用域按词法嵌套关系决定名字的绑定非局部名字通过访问链逐层查找动态作用域则按调用链查找运行时沿控制链向上找。习题常见的考法是给出一段嵌套函数代码问同一名字在不同位置引用的是哪个声明。这种题的做法是先画出嵌套关系树再确定每个函数的最大包围作用域。比如外层声明int x内层函数声明同名int x内层函数引用x时优先绑定内层声明。动态作用域的结果可能不同要看调用栈。问题是很多学生混淆两种作用域的查找方向静态作用域看词法嵌套动态作用域看运行时调用链答案中的一句话就能决定这一点。5.2 错误处理词法错误、语法错误与语义错误的区分错误处理章节的习题基本上以选择题和简答题为主。核心考点是三类错误的典型例子词法错误如非法字符、数字越界语法错误如缺少分号、括号不匹配语义错误如类型不匹配、数组下标不是整数。答案最容易混淆的是把“函数未声明就调用”写成语法错误——这是语义错误符号表查不到的情况下需要在语义分析阶段报错。5.3 代码生成寄存器分配与待用信息表的结合代码生成章节的答案里最常见的是一张待用信息表配合寄存器分配描述。给定三地址码a : b c、d : a e要求用两个寄存器生成目标代码。标准做法是扫描每条指令记录每个变量在哪条指令之后不再被引用从而决定寄存器是否可以释放。做题时先画出变量的活跃区间再依次分配寄存器。如果寄存器不够用就要把变量溢出到内存。习题答案中经常提到“寄存器描述符”和“变量描述符”前者记录寄存器当前存放的变量后者记录变量的存放位置。这个考点在近年的期末考试中占比不低但容易被复习计划遗漏。本文还有配套的精品资源点击获取 编译原理复习指南：从词法分析到代码生成的核心考点
简介《哈工大-编译原理-习题及答案汇总.pdf》是一份面向编译原理课程学习者的习题汇编资料重点覆盖源程序、目标程序、翻译程序、编译程序与解释程序的概念及关系以及编译系统各组成部分的主要功能。内容同时也涉及前后文无关文法与语言、语法树、二义性文法判定与化简、ε产生式消去等常考章节适合哈工大学子及其他高校计算机专业学生用于课后巩固、考研复习或期末突击。资源本身仅包含1个PDF文件整体大小约1.6MB内容紧凑、按章节组织目前已获得1743人学习下载。文件将习题与答案解析对照呈现在解释程序与编译程序工作方式的区别、C语言关键字及括号和逗号的多种用途、构造文法和消去无用产生式等典型题目上均有细致展开便于读者针对薄弱环节快速定位并专项突破是一份值得反复研读的课程配套资料。1. 在算法题刷无可刷的节点上很多人的复习盲区是编译原理半小时能做三道 LeetCode却在一道求 First 集合的题上卡了二十分钟这种事放在求职季特别常见。刷题带来的正反馈太强让人产生一种“基础都在手”的错觉。可一到涉及编译原理的面试题比如问“static 局部变量在符号表里怎么登记”“为什么 C 语言要求声明在前”这类实际考点经验丰富的从业者也常常说不到点子上。原因很简单编译原理的知识密度高、抽象层级多从正则到自动机从文法到分析表每一步都建立在前面概念之上。靠通读教材效率太低最有效的方式就是把前辈整理好的习题和答案作为复习主线——先看问题再定位理论最后通过答案反推自己的知识漏洞。这篇内容就围绕“哈工大-编译原理-习题及答案汇总.pdf”这类复习材料把词法分析、语法分析、语义分析、中间代码、优化这几条主线的经典题型和解题套路连同答案里容易忽略的细节一起拆开讲。2. 编译原理复习的主线词法、语法、语义与代码生成的连续脉络2.1 词法分析正则到 NFA 再到 DFA 是复习的第一道关词法分析题是所有习题集的起点。无论是哈工大还是其他学校的讲义第一类大题型基本都是“给出正规式构造 NFA再确定化为 DFA最后最小化”。这背后是一整套固定流程Thompson 构造法把每个正则表达式拆成带 ε 转移的 NFA子集构造法把 NFA 的状态集合映射为 DFA 的状态最后通过划分法消除等价状态。手工做题时我一般按三步走先拆正则表达式的最外层运算。比如(a|b)*abb最外层是连接先处理(a|b)*再连接abb。用 Thompson 构造法从左到右拼接 NFA 片段ε 边专门用来连接子片段。子集构造法求 DFA 时每个 DFA 状态是一个 NFA 状态集合要先用 ε-闭包打底再对每个输入符号求 move 闭包。下面是一段辅助验证的 Python 脚本可以帮你手工求 ε-闭包时核对结果def epsilon_closure(states, transitions): stack list(states) closure set(states) while stack: s stack.pop() for t in transitions.get(s, []): if t[0] ε and t[1] not in closure: closure.add(t[1]) stack.append(t[1]) return closure # 示例NFA 状态 0 通过 ε 能到达 {1, 2} transitions { 0: [(ε, 1)], 1: [(ε, 2), (a, 3)], 2: [(b, 4)], } print(epsilon_closure({0}, transitions)) # {0, 1, 2}这段代码的逻辑是stack保存待扩散的状态closure记录已收集的状态每次弹出一个状态扫描它的所有转移边如果边上是 ε 且目标状态尚未收录就加入闭包并压栈。实际刷题时考卷上通常要求手写闭包结果这个脚本的意义在于帮你建立“闭包就是不断沿 ε 边走”的直觉。除了 NFA 转 DFA词法分析习题里出现频率极高的另一个考点是直接用正则描述语言然后指出该正则对应的 DFA 最少需要几个状态。常见的陷阱是“最少状态数”忘了做最小化。北京理工、哈工大等多套真题里都出现过(a|b)*a(a|b)这种形式很多人的第一反应是画出 4 个状态但最小化后其实只有 3 个。原因在于状态 2 和状态 3 在读入a和b后的转移完全一致且同为接受状态划分法第一步就会把它们合并。提示答案里凡是出现“最简 DFA”或“最小 DFA”别只看最终图要自己拿划分法重新做一遍。划分法的终止条件是每个组内状态对所有输入符号都落在同一个组里这一步手工算很快但特别练耐心。2.2 语法分析LL(1) 与 LR(1) 的习题套路语法分析是编译原理习题集中占篇幅最大的一章。题型可以粗略分成三类计算 First 与 Follow 集合、判断文法是否为 LL(1)、构造 LR 分析表或 SLR 分析表。这三类题层层递进答案里给出的通常只是最终表格但做题时真正容易出错的恰恰是中间计算。先看 First 集合。规则是对每个产生式A - X1 X2 ... Xn先看X1如果X1是终结符则把X1加入First(A)如果X1是非终结符则把First(X1)中除 ε 外的所有符号加入如果X1能推出 ε再看X2以此类推。这里有一个常见的边界条件如果所有Xi都能推出 ε那么 ε 也要加入First(A)。Follow 集合的边界条件更多。Follow(S)一定包含$这是开始符号的固有属性对形如A - αBβ的产生式Follow(B)要加入First(β)中除 ε 外的所有符号如果β能推出 ε那么Follow(B)还要加入Follow(A)。这道题做完后很多人的答案错在First(β)是空集时忘了把Follow(A)的东西传下去。下面用一个小文法演示做题时的完整计算过程。假设文法GE - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这是经典的表达式文法去掉了左递归。手工计算时我习惯先把每个非终结符的 First 集合写出来非终结符First 集合E{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }然后基于 First 集合求 Follow 集合非终结符Follow 集合E{ $, ) }E{ $, ) }T{ , $, ) }T{ , $, ) }F{ *, , $, ) }注意T的 Follow 集合里有这是因为E - T E中在T之前但 Follow 集合只管出现在非终结符之后的内容所以Follow(T)取的是E的 First 集合中去掉 ε 的部分即{}再并上Follow(E)。这是习题答案里最容易被忽略的一步。判断 LL(1) 文法的条件也在这个环节直接用上对每个非终结符的所有产生式两两之间的 First 集合交集必须为空如果某个产生式能推出 ε那么它的 First 集合与对应 Follow 集合的交集也必须为空。用上面的文法验证各产生式的 First 集合互不重叠且E - ε的 First 是{ε}与Follow(E) { $, ) }交集为空因此是 LL(1) 文法。LR 系列习题的节奏不同。构造 SLR 分析表的核心是构建 LR(0) 项目集规范族然后对每个项目集分别处理归约项目只在 Follow 集合对应的输入符号上填r移进项目直接在对应终结符列填s。常见错误是把归约动作填满了整行这意味着把 SLR 当成 LR(0) 来用在考试里会丢分。2.3 语义分析与中间代码属性文法和三地址码的对应关系语义分析章节的习题与前面完全不同——不再有“求集合”这种封闭式问题而是给出一段程序或一个文法要求写出带语义动作的翻译方案或者直接生成中间代码。这里的核心概念是文法符号的属性综合属性自下而上计算继承属性自上而下传递。最常考的是算术表达式的三地址码生成。给定a : b * -c b * -c标准答案会先画出语法树然后对每个内部节点生成临时变量。一个容易忽略的优化是公共子表达式b * -c在中间代码层面会被计算两次除非后续做局部优化。这个例子在习题答案中经常同时出现在中间代码生成和代码优化两章做的时候要把这两处对照起来看。三地址码的具体形式通常是四元式(op, arg1, arg2, result)。上面的赋值语句可以翻译为(*, b, c, t1) # t1 b * c实际是 b * (-c)负号单独处理 (uminus, t1, _, t2) # t2 -t1 (*, b, c, t3) (uminus, t3, _, t4) (, t2, t4, t5) (:, t5, _, a)在考卷上uminus是单目运算符的标准写法它只有一个操作数。很多人在这一步会直接把b写成负号作用于c然后生成(*, b, -c, t1)这不符合规范——中间代码不区分正负常量负号要显式翻译成单目运算或取负指令。语义分析章节还有一类概念题值得注意数组元素的地址计算。习题集里最常见的题目是二维数组按行优先存储给出A[10][20]、每个元素 4 字节、首地址base求A[i][j]的地址。答案是base (i * 20 j) * 4。这题看着简单但在符号表练习里会衍生出“数组内情向量表应该记录哪些字段”的问题。标准答案是维数、各维上下界、元素类型宽度。这道题的变体会在后续章节反复出现因为内情向量表在运行存储分配里要用来计算地址。3. 把习题当工程做典型题型拆解与最小复现步骤3.1 词法分析实验题手工构造词法分析器的骨架习题集中必有一道“设计一个识别某语言子集的词法分析器”通常要求识别关键字、标识符、无符号数、运算符和分隔符。教材上的答案往往是一整段 C 语言代码但对于复习来说更好的方式是理解它背后的模式一个全局扫描指针一个关键字查表一个状态转移主循环。我一般会把词法分析器拆成四个函数next_char负责从输入缓冲区取字符scan负责状态流转reserve负责查关键字表error负责词法错误恢复。下面是一个极简的标识符/关键字识别骨架可以直接照着扩展keywords {if, else, while, return, int, float} def is_id_start(ch): return ch.isalpha() or ch _ def is_id_part(ch): return ch.isalnum() or ch _ def scan_identifier(src, pos): start pos while pos len(src) and is_id_part(src[pos]): pos 1 token src[start:pos] token_type kw if token in keywords else id return token_type, token, posscan_identifier的逻辑是从当前位置开始持续消费字母、数字和下划线遇到第一个不能作为标识符组成部分的字符就停下。判断关键字用的是集合成员测试这在 C 语言里对应的是逐步比较字符串或哈希查表。要特别注意关键字匹配必须发生在标识符识别完整之后否则会错误地把ifx识别成关键字if加标识符x。词法分析器在工程上还需要处理“超前读一个字符”的问题。手工实现时常见做法是维护一个lookahead变量每次读入下一个字符后如果发现它不是当前 token 的一部分就要把它压回输入流。习题答案不会明说这个细节但几乎所有“请写出词法分析器的输入缓冲处理方案”的题目都隐含这个考点。3.2 语法分析题递归下降子程序的设计模式语法分析习题里最实用的一类是实现递归下降分析器。用前面 2.2 节的表达式文法可以直接映射成一组函数每个非终结符对应一个函数名产生式右侧的终结符对应match调用非终结符对应相应函数调用。这个映射关系本身就是复习语法分析的最佳练习。class RecursiveDescentParser: def __init__(self, tokens): self.tokens tokens self.pos 0 def match(self, expected): if self.pos len(self.tokens) and self.tokens[self.pos] expected: self.pos 1 else: raise SyntaxError(fexpected {expected}, got {self.tokens[self.pos] if self.pos len(self.tokens) else EOF}) def parse_E(self): self.parse_T() self.parse_E_prime() def parse_E_prime(self): if self.pos len(self.tokens) and self.tokens[self.pos] : self.match() self.parse_T() self.parse_E_prime() # 遇到其他符号时ε 产生式直接返回 def parse_T(self): self.parse_F() self.parse_T_prime()parse_E_prime里的if判断就是E - T E | ε的实现当前输入是就展开第一种产生式否则走 ε 分支。如果习题要求判断该文法是不是 LL(1)你会发现递归下降能跑通的前提正是 2.2 节里那个两两不相交的条件。这套代码在面试里也经常被要求手写尤其是“给你一个 JSON 子集实现解析器”这种题底层思路完全一致。3.3 代码优化题基本块划分与 DAG 重建优化章节的习题通常给一段三地址码要求划分基本块、画出 DAG、重新生成代码。基本块划分的规则很简单入口语句是基本块的第一条语句无条件转移、条件转移、停机语句都算出口。但答案里真正想考察的是你能不能通过 DAG 合并公共子表达式。下面的三地址码是一道典型的考试题t1 a * b t2 a * b t3 t1 t2 t4 t3 1划分基本块后t2 a * b与t1 a * b的右部完全一致DAG 构造时可以直接复用t1节点t3 t1 t1整个基本块从 4 条指令缩减到 3 条。答案里如果直接把t2单独画成一个节点说明出题人期望看到的是“已优化版本”。做题时要注意DAG 节点合并的前提是两个节点的运算符号和所有子节点完全相同。4. 参考答案要看门道构造题的多解思路与易错点4.1 文法改写的两道必做题左递归消除与提取左因子几乎所有习题集的文法改写题都会包含这两个操作。前者是把A - Aα | β改写成A - βA、A - αA | ε消除直接左递归后者是把A - αβ1 | αβ2提取公因子为A - αA、A - β1 | β2。这两个变换的结果基本是唯一的但考试中容易混淆消除左递归是为了适配自顶向下分析提取左因子是为了保证 LL(1) 条件中的 First 集合互不相交两者服务于不同的目的。关于间接左递归比如S - Aa、A - Sd必须先代入再消除。步骤是把非终结符排序对每个Ai检查前面的Aj产生的规则中是否包含Ai开头的右部如果有就把Aj的右部代入再消除左递归。很多答案省略了代入的中间步骤直接给最终结果这时候要自己补一遍。4.2 SLR(1) 冲突的本质移进-归约冲突不能靠直觉判断构造 LR(0) 项目集规范族后如果某个项目集同时包含A - α·和B - β·aγ在a列上就会产生归约和移进的冲突。习题答案会在表格中用红色或用括号标出冲突位置但不会详细解释冲突出现的条件。实际上判断很简单看Follow(A)里是否包含a如果包含就冲突。比如典型二义性文法E - E E | E * E | id构造 SLR 分析表时在列和*列必然出现多重动作。这也是为什么所有教材都说二义性文法不是 LR(1) 文法。掌握这个判断方法后分析表题的正确率会明显上升。4.3 习题答案中运行期存储分配相关的隐藏考点运行存储分配这一章习题答案看起来都是文字题实际暗藏计算。最常见的是“画出栈式存储分配的活动记录布局”。题目会给一个函数嵌套调用的 Pascal 或 C 程序让你画出 main 调用 fun1、fun1 调用 fun2 时栈的变化。活动记录从低地址到高地址通常是局部变量、临时变量、保存的机器状态、实参、返回地址、控制链、访问链。答案里经常出现“控制链指向调用者的活动记录底部”“访问链用于访问非局部变量”这样的句子这两条链的含义必须分清楚。提示如果答案里给出了活动记录布局图别只看图要在旁边补上 SP栈指针和 FP帧指针的指向位置。大部分考试错图都错在 FP 指向了返回地址而不是活动记录底部。4.4 符号表组织的开放寻址与链地址对比符号表习题中最容易答漏的是链地址法 vs 开放寻址法的优缺点对比。标准的答题框架是链地址法通过哈希表加链表处理冲突插入和查找的平均时间在合理负载因子下是 O(1)但额外的指针存储开销大开放寻址法不需要额外空间但删除操作复杂不能直接置空否则会切断探测序列。答案中通常会把“删除时用墓碑标记”这个细节单独列出实际工程中大多数编译器的符号表使用链地址法或动态数组组织而不是开放寻址。5. 把复习收尾在“低频考题”上运行环境、错误处理与代码生成的常见考点5.1 运行环境静态作用域与动态作用域的实现差异前面 4.3 节的活动记录对应栈式分配这一节要补充的是作用域规则。静态作用域按词法嵌套关系决定名字的绑定非局部名字通过访问链逐层查找动态作用域则按调用链查找运行时沿控制链向上找。习题常见的考法是给出一段嵌套函数代码问同一名字在不同位置引用的是哪个声明。这种题的做法是先画出嵌套关系树再确定每个函数的最大包围作用域。比如外层声明int x内层函数声明同名int x内层函数引用x时优先绑定内层声明。动态作用域的结果可能不同要看调用栈。问题是很多学生混淆两种作用域的查找方向静态作用域看词法嵌套动态作用域看运行时调用链答案中的一句话就能决定这一点。5.2 错误处理词法错误、语法错误与语义错误的区分错误处理章节的习题基本上以选择题和简答题为主。核心考点是三类错误的典型例子词法错误如非法字符、数字越界语法错误如缺少分号、括号不匹配语义错误如类型不匹配、数组下标不是整数。答案最容易混淆的是把“函数未声明就调用”写成语法错误——这是语义错误符号表查不到的情况下需要在语义分析阶段报错。5.3 代码生成寄存器分配与待用信息表的结合代码生成章节的答案里最常见的是一张待用信息表配合寄存器分配描述。给定三地址码a : b c、d : a e要求用两个寄存器生成目标代码。标准做法是扫描每条指令记录每个变量在哪条指令之后不再被引用从而决定寄存器是否可以释放。做题时先画出变量的活跃区间再依次分配寄存器。如果寄存器不够用就要把变量溢出到内存。习题答案中经常提到“寄存器描述符”和“变量描述符”前者记录寄存器当前存放的变量后者记录变量的存放位置。这个考点在近年的期末考试中占比不低但容易被复习计划遗漏。本文还有配套的精品资源点击获取