企业官网建设流程全解析

简介：《哈工大-编译原理-习题及答案汇总.pdf》是一份面向编译原理课程学习者的习题汇编资料，重点覆盖源程序、目标程序、翻译程序、编译程序与解释程序的概念及关系，以及编译系统各组成部分的主要功能。内容同时也涉及前后文无关文法与语言、语法树、二义性文法判定与化简、ε产生式消去等常考章节，适合哈工大学子及其他高校计算机专业学生用于课后巩固、考研复习或期末突击。资源本身仅包含1个PDF文件，整体大小约1.6MB，内容紧凑、按章节组织，目前已获得1743人学习下载。文件将习题与答案解析对照呈现，在解释程序与编译程序工作方式的区别、C语言关键字及括号和逗号的多种用途、构造文法和消去无用产生式等典型题目上均有细致展开，便于读者针对薄弱环节快速定位并专项突破，是一份值得反复研读的课程配套资料。

1. 在算法题刷无可刷的节点上，很多人的复习盲区是编译原理

半小时能做三道 LeetCode，却在一道求 First 集合的题上卡了二十分钟，这种事放在求职季特别常见。刷题带来的正反馈太强，让人产生一种“基础都在手”的错觉。可一到涉及编译原理的面试题，比如问“static 局部变量在符号表里怎么登记”“为什么 C 语言要求声明在前”这类实际考点，经验丰富的从业者也常常说不到点子上。原因很简单：编译原理的知识密度高、抽象层级多，从正则到自动机，从文法到分析表，每一步都建立在前面概念之上。靠通读教材效率太低，最有效的方式就是把前辈整理好的习题和答案作为复习主线——先看问题，再定位理论，最后通过答案反推自己的知识漏洞。这篇内容就围绕“哈工大-编译原理-习题及答案汇总.pdf”这类复习材料，把词法分析、语法分析、语义分析、中间代码、优化这几条主线的经典题型和解题套路，连同答案里容易忽略的细节一起拆开讲。

2. 编译原理复习的主线：词法、语法、语义与代码生成的连续脉络

2.1 词法分析：正则到 NFA 再到 DFA 是复习的第一道关

词法分析题是所有习题集的起点。无论是哈工大还是其他学校的讲义，第一类大题型基本都是“给出正规式，构造 NFA，再确定化为 DFA，最后最小化”。这背后是一整套固定流程：Thompson 构造法把每个正则表达式拆成带 ε 转移的 NFA，子集构造法把 NFA 的状态集合映射为 DFA 的状态，最后通过划分法消除等价状态。

手工做题时，我一般按三步走：

1. 先拆正则表达式的最外层运算。比如(a|b)*abb，最外层是连接，先处理(a|b)*，再连接abb。
2. 用 Thompson 构造法从左到右拼接 NFA 片段，ε 边专门用来连接子片段。
3. 子集构造法求 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)的东西传下去。

下面用一个小文法演示做题时的完整计算过程。假设文法G：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

这是经典的表达式文法，去掉了左递归。手工计算时我习惯先把每个非终结符的 First 集合写出来：

然后基于 First 集合求 Follow 集合：

注意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, pos

scan_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(f"expected {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，要求用两个寄存器生成目标代码。标准做法是扫描每条指令，记录每个变量在哪条指令之后不再被引用，从而决定寄存器是否可以释放。

做题时先画出变量的活跃区间，再依次分配寄存器。如果寄存器不够用，就要把变量溢出到内存。习题答案中经常提到“寄存器描述符”和“变量描述符”，前者记录寄存器当前存放的变量，后者记录变量的存放位置。这个考点在近年的期末考试中占比不低，但容易被复习计划遗漏。

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