企业官网建设流程全解析

简介：这份《吉林大学编译原理期末试题解答》面向计算机专业备考学生与复习编译原理的学习者，汇集了2003至2017级多套期末试题及部分参考答案，覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与运行时系统等核心知识模块，可帮助读者对照真题梳理考点、检验掌握程度。资源包为1个PDF文件，约4.56MB，内含知识点总结、试题样例与历年试题解答，目录按年份与班级分类，部分试题标注Done并附带完整或部分答案，便于按章节与年份检索学习。目前已有2739人学习下载，适合需要系统刷题、查漏补缺或考前冲刺的读者参考使用。

1. 吉林大学编译原理期末试题解答：一份能对着复盘考点的 PDF 怎么用

期末周翻遍群文件，最后发现最有用的往往不是那本厚得能砸死人的龙书，而是一份带解答的历年真题。吉林大学编译原理这门课，期末卷子的题型其实相当稳定：词法分析给正则表达式画 NFA、DFA，语法分析考 LL(1) 和 LR 分析表的构造，语义分析里塞一道语法制导翻译，中间代码生成让你写四元式，最后再来一道优化或者目标代码相关的综合题。这份《吉林大学编译原理期末试题解答.pdf》就是把这些题型按套卷整理出来，每道题配了推导过程和最终答案。它适合两类人：一类是期末前两周想快速摸清出题套路、把高频考点过一遍的；另一类是平时作业靠抄、现在想对着真题把 LL(1) 分析表和 LR 项目集重新手推一遍的。PDF 的好处是公式和表格不会像截图那样糊掉，打印出来做批注也方便。

2. 编译原理真题里的四类核心题型：从正则到四元式的推导链

2.1 词法分析：正则表达式到 DFA 的最小化

词法分析几乎是每套卷子的第一道大题，常见问法是给一个正则表达式或者一段自然语言描述，要求构造 NFA、确定化得到 DFA、再最小化。吉林大学的题有个特点，它喜欢在标识符和数字的识别上做文章，比如要求识别以字母开头、后跟字母数字下划线、且不能是 C 语言关键字的标识符。这类题的手工推导步骤是固定的，但每一步都有容易翻车的地方。

先看一个典型题面：构造识别ab|a的 DFA。用 Thompson 算法构造 NFA 时，a和b的连接、|的分支、闭包的处理顺序不能乱。我一般会先在草稿纸上把 NFA 的状态图画出来，标好 ε 闭包，再列状态转换表。确定化的时候用子集构造法，把每个状态集合当成新状态，这一步最容易漏掉空集状态——空集状态在 DFA 里通常作为死状态，如果题目要求最小化，它会被合并掉。

# 子集构造法核心逻辑示意（以识别 ab|a 为例） # 状态集合用 frozenset 表示，便于做字典 key from collections import deque def epsilon_closure(states, epsilon_trans): """求 ε 闭包：从 states 出发，沿 ε 边能到达的所有状态""" stack = list(states) closure = set(states) while stack: s = stack.pop() for nxt in epsilon_trans.get(s, []): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, symbol, trans): """从 states 出发，沿 symbol 边到达的状态集合""" result = set() for s in states: for nxt in trans.get((s, symbol), []): result.add(nxt) return frozenset(result) # 确定化主循环：初始状态是开始状态的 ε 闭包 # 对每个新状态集合，对字母表中每个符号求 move + ε 闭包 # 若得到的新集合未出现过，加入队列继续处理

这段代码的关键参数是epsilon_trans和trans，前者存 ε 边，后者存普通字符边。实际手推时不需要写代码，但把逻辑理清能避免漏状态。最小化用 Hopcroft 算法或者简单的分割法：先按终态和非终态分成两组，再看每组内状态对同一输入是否转移到同一组，不满足就继续分裂。吉林大学的题一般状态数不多，手工分割完全来得及。

注意：确定化后如果出现空集状态，且题目没要求补全 DFA，可以省略；但若要求最小化，空集状态通常单独成组，最后可能被合并到死状态里。

2.2 语法分析：LL(1) 分析表的构造与冲突处理

LL(1) 是吉林大学编译原理期末的必考内容，通常给一个文法，要求判断是否为 LL(1) 文法、构造预测分析表、给出输入串的分析过程。这里面的核心是 FIRST 集和 FOLLOW 集的计算，以及 SELECT 集的推导。很多人在 FOLLOW 集上栽跟头，尤其是当文法里有形如A -> αBβ且 β 能推导出 ε 的情况，FOLLOW(B) 要并上 FOLLOW(A)。

我一般按这个顺序手推：先找能推出 ε 的非终结符，标记出来；然后算 FIRST 集，从终结符开始往上推；再算 FOLLOW 集，开始符号的 FOLLOW 里先放#；最后对每个产生式算 SELECT 集。SELECT 集的规则是：如果 α 不能推 ε，SELECT(A->α) = FIRST(α)；如果能推 ε，SELECT(A->α) = (FIRST(α)-{ε}) ∪ FOLLOW(A)。分析表里同一格出现两个产生式就是冲突，说明不是 LL(1) 文法。

# 计算 FIRST 集的迭代法示意 def compute_first(grammar, non_terminals, terminals): first = {nt: set() for nt in non_terminals} # 初始化：终结符的 FIRST 是它自己 for t in terminals: first[t] = {t} changed = True while changed: changed = False for head, bodies in grammar.items(): for body in bodies: # 逐个符号看，若当前符号能推 ε，继续看下一个 for sym in body: before = len(first[head]) first[head] |= (first[sym] - {'ε'}) if 'ε' not in first[sym]: break else: # 所有符号都能推 ε，则 head 也能推 ε first[head].add('ε') if len(first[head]) > before: changed = True return first

参数说明：grammar是字典，key 是非终结符，value 是产生式右部的列表；non_terminals和terminals分别是非终结符和终结符集合。这段代码的for...else结构容易写错，else 分支只在循环正常结束（没 break）时执行，正好对应“所有符号都能推 ε”的情况。考试时手算 FIRST 集，建议从最简单的产生式开始，逐步往上推，每算完一个就标记，避免重复劳动。

2.3 语义分析与中间代码：语法制导翻译和四元式生成

语义分析部分，吉林大学喜欢考语法制导定义（SDD）和语法制导翻译方案（SDT），常见题型是给一个简单表达式文法，要求写出带语义动作的翻译方案，并给出某个输入串的四元式序列。四元式的格式是(op, arg1, arg2, result)，比如a = b + c * d会生成(*, c, d, t1)、(+, b, t1, t2)、(=, t2, _, a)。

这里的关键是理解综合属性和继承属性的传递方向。综合属性自下而上，继承属性自上而下。如果题目要求用 LR 分析实现 SDT，那就要把语义动作嵌入到产生式右部，注意动作符号的位置决定了属性计算的时机。我一般会先在草稿纸上画出语法树，标出每个节点的属性，再按后序遍历的顺序写四元式。这样不容易漏掉临时变量的生成。

# 四元式生成器示意：处理简单赋值和二元运算 class QuadGenerator: def __init__(self): self.quads = [] self.temp_count = 0 def new_temp(self): self.temp_count += 1 return f"t{self.temp_count}" def emit(self, op, arg1, arg2, result): self.quads.append((op, arg1, arg2, result)) def gen_binop(self, op, left, right): # left/right 可能是变量名或临时变量 temp = self.new_temp() self.emit(op, left, right, temp) return temp # 对 a = b + c * d 的调用顺序： # t1 = gen_binop('*', 'c', 'd') # t2 = gen_binop('+', 'b', t1) # emit('=', t2, '_', 'a')

参数说明：op是运算符，arg1和arg2是操作数，result是存放结果的临时变量或目标变量。_表示空操作数。实际考试时不需要写类，但把临时变量的编号规则记清楚——按生成顺序递增，不要跳号。如果题目要求优化，比如删除公共子表达式，那就要在生成四元式后再做一遍局部优化，把重复计算的临时变量合并。

2.4 优化与目标代码：基本块划分和 DAG 表示

最后一道大题通常是优化相关，给一段中间代码，要求划分基本块、构造流图、或者用 DAG 做局部优化。吉林大学的题一般不会太复杂，基本块划分的规则是：遇到跳转目标、跳转语句、或者跳转语句的下一条，就断开。DAG 构造时，每个变量和常量作为叶子，运算作为内部节点，相同运算的子节点相同就合并。

我一般会先给每条中间代码编号，然后标出所有的入口语句：第一条代码、跳转目标、跳转语句的下一条。从每个入口语句开始，直到下一个入口语句之前，就是一个基本块。DAG 构造时注意变量的重命名——如果两个变量被赋了相同的值，它们在 DAG 里可以指向同一个节点，但后续如果其中一个被重新赋值，就要新建节点。

注意：DAG 优化后如果某个变量在基本块内没有被再次引用，且不是活跃变量，可以删除其赋值语句。但考试时如果没要求活跃变量分析，一般只做公共子表达式消除和常量合并。

3. 对着 PDF 手推分析表：一套可复现的刷题流程

3.1 从题目到答案的完整推导步骤

拿到一份真题解答 PDF，最忌讳的是直接看答案。我的习惯是先把题目抄到草稿纸上，自己推一遍，推完再对照 PDF 里的解答，看哪一步卡住了。具体流程分四步：第一步，通读题目，判断考的是哪个知识点，是词法、语法、语义还是优化；第二步，在草稿纸上按标准步骤推导，比如 LL(1) 就先算 FIRST 和 FOLLOW，LR 就先写项目集规范族；第三步，对照 PDF 解答，重点看自己跳过的步骤和写错的符号；第四步，把错题标记出来，隔两天再推一遍。

以 LL(1) 分析表为例，手推时建议用表格形式，行是非终结符，列是终结符，格子里填产生式。填表时按 SELECT 集来，不要凭感觉。如果某个格子有两个产生式，说明文法有冲突，题目可能会问如何消除左递归或提取左公因子。消除左递归的公式是：把A -> Aα | β改成A -> βA'、A' -> αA' | ε。提取左公因子的公式是：把A -> αβ | αγ改成A -> αA'、A' -> β | γ。

# 消除直接左递归的转换示意 def eliminate_left_recursion(head, bodies): """ head: 非终结符，如 'A' bodies: 产生式右部列表，如 [['A', 'α'], ['β']] 返回新的产生式字典 """ recursive = [] # 以 head 开头的右部 non_recursive = [] # 不以 head 开头的右部 for body in bodies: if body and body[0] == head: recursive.append(body[1:]) # 去掉开头的 head else: non_recursive.append(body) if not recursive: return {head: bodies} # 无左递归，原样返回 new_head = head + "'" new_bodies = [nr + [new_head] for nr in non_recursive] new_recursive = [r + [new_head] for r in recursive] + [['ε']] return {head: new_bodies, new_head: new_recursive}

参数说明：head是待处理的非终结符，bodies是它的所有产生式右部。函数返回新的产生式字典，包含原非终结符和新引入的非终结符。注意ε产生式要显式加入，否则新非终结符可能无法推导出空串。考试时手写这一步，建议把新非终结符命名为A'或A1，并在旁边注明它是新引入的。

3.2 用 PDF 做错题归因：区分概念模糊和计算失误

刷真题的价值不在于做对多少，而在于把错题归因。我一般把错题分成三类：第一类是概念模糊，比如不知道 FOLLOW 集里要不要加#，或者分不清 SLR 和 LR(1) 的区别；第二类是计算失误，比如 FIRST 集里漏了一个终结符，或者 DFA 最小化时分组分错了；第三类是步骤遗漏，比如忘了画语法树就直接写四元式。概念模糊要回去翻教材对应章节，计算失误要多练几道同类题，步骤遗漏则要在草稿纸上固定一个模板，每次按模板走。

PDF 解答的好处是它通常会把中间步骤写出来，比如 LR 分析表的构造，它会列出每个状态的项目集和 GO 函数。对照的时候，重点看自己的项目集有没有漏项，GO 函数的转移目标对不对。如果 PDF 里用了不同的记号，比如用I0表示初始状态，而你习惯用S0，那就在旁边标注一下，不要因为记号不同就怀疑自己错了。

提示：如果 PDF 里的解答和教材上的方法不一致，以教材为准，因为期末考试通常按教材的符号体系出题。PDF 只是参考，不是标准答案。

3.3 把解答 PDF 转成可检索的笔记

PDF 的缺点是没法全文检索，尤其是公式和表格。我一般会把每道题的解答手动敲成 Markdown 或者用 OCR 转成文本，然后按知识点分类整理。比如把所有 LL(1) 的题放在一起，把所有 LR 的题放在一起，这样复习时能看出同一知识点的不同考法。OCR 工具对公式的识别率一般，所以关键公式还是手敲一遍更靠谱。

整理笔记时，我会给每道题打两个标签：一个是知识点标签，比如#LL1、#LR1、#四元式；另一个是难度标签，比如#基础、#综合、#易错。这样考前最后一天只需要看#易错标签下的题。另外，把每道题的“踩坑点”用一句话写在题目下面，比如“FOLLOW 集忘了加#”“DFA 最小化时死状态没合并”，复习时一眼就能看到。

# 用 pdftotext 把 PDF 转成文本，方便后续检索 pdftotext -layout "吉林大学编译原理期末试题解答.pdf" output.txt # -layout 参数保留原始排版，表格和公式的相对位置不会乱 # 转完后用 grep 搜关键词，比如搜 "FIRST" 或 "四元式" grep -n "FIRST" output.txt grep -n "四元式" output.txt

参数说明：-layout是 pdftotext 的常用参数，能尽量保留原 PDF 的版面布局，对表格和分栏比较友好。如果 PDF 是扫描版，pdftotext 可能转不出文字，那就需要 OCR 工具。转出来的文本里，公式可能会变成乱码或者错位，所以只用来做关键词检索，具体推导还是要看原 PDF。

4. 避坑与排查：编译原理刷题时最容易翻车的五个地方

4.1 现象：FOLLOW 集算出来和答案对不上

原因：最常见的是忘了把#加入开始符号的 FOLLOW 集，或者在处理A -> αBβ时，只把 FIRST(β) 加进去，忘了当 β 能推 ε 时还要并上 FOLLOW(A)。另一个隐蔽的坑是，当 B 后面跟着多个符号且它们都能推 ε 时，要一直往后看，直到遇到不能推 ε 的符号或者到达产生式末尾。

解决：每次算 FOLLOW 集之前，先把所有能推 ε 的非终结符列出来。然后对每个产生式右部，从右往左扫描，维护一个“当前 FOLLOW 集合”，遇到能推 ε 的符号就继续往左并，遇到不能推 ε 的就停止。开始符号的 FOLLOW 里先放#。

4.2 现象：LR 分析表里同一个格子出现两个动作

原因：这说明文法不是 LR(0) 或 SLR(1) 的，存在移进-归约冲突或归约-归约冲突。SLR(1) 用 FOLLOW 集来解决冲突，但如果 FOLLOW 集有交集，冲突依然存在。LR(1) 通过增加展望符来细化项目，能解决更多冲突，但项目集数量会膨胀。

解决：先判断冲突类型。如果是移进-归约冲突，检查移进符号是否在归约项目的 FOLLOW 集中；如果是归约-归约冲突，检查两个归约项目的 FOLLOW 集是否有交集。如果 SLR 解决不了，就改用 LR(1) 或 LALR(1)。考试时如果题目明确要求构造 SLR 分析表，那冲突就是题目要你发现并说明的。

4.3 现象：四元式生成时临时变量编号混乱

原因：没有按统一的规则生成临时变量，比如有的地方从t1开始，有的地方从t0开始，或者跳号了。另一个原因是，在处理嵌套表达式时，没有按后序遍历的顺序生成，导致临时变量的使用顺序和计算顺序不一致。

解决：固定一个临时变量命名规则，比如从t1开始，每生成一个就递增。生成四元式时，严格按语法树的后序遍历顺序，先算子节点，再算父节点。如果题目要求优化，临时变量的编号可以重排，但优化前的版本要保留。

4.4 现象：DFA 最小化后状态数比答案多

原因：分组时没有把终态和非终态严格分开，或者在同一组内没有检查所有输入符号的转移目标是否在同一组。另一个常见错误是，把死状态（空集状态）单独成组后忘了它和其他状态的区别，导致该合并的没合并。

解决：最小化的第一步一定是按终态和非终态分成两组。然后对每组，检查每个状态对每个输入符号的转移目标是否落在同一组。如果某个状态的转移目标落在不同组，就把该状态从当前组分裂出来。重复直到不能再分裂。死状态如果和某个非终态组的行为一致，可以合并。

4.5 现象：PDF 里的解答和教材符号不一致

原因：不同教材对编译原理的符号约定不同，比如龙书用E'表示消除左递归后的新非终结符，而国内教材可能用E1。LR 分析表里，有的教材用s表示移进，r表示归约，有的用shift和reduce。

解决：以任课老师指定的教材为准。如果 PDF 里的符号和教材不一致，在 PDF 旁边标注教材对应的符号，不要强行记忆 PDF 的符号。考试时按教材的符号写，阅卷老师通常只认教材的约定。

5. 从真题到考场：把 PDF 用出最大价值的两个进阶技巧

5.1 用真题反推考点权重，做减法复习

吉林大学编译原理的期末卷子，题型和分值分布其实有规律。把近几年的真题解答 PDF 摊开，按知识点统计每类题出现的次数和分值，你会发现词法分析和语法分析通常占 50% 以上，语义分析和中间代码占 30% 左右，优化和目标代码占 20% 左右。如果时间不够，优先保证词法和语法的题不丢分，因为这两类题的解题步骤最固定，练几套就能形成肌肉记忆。

我一般会做一个简单的权重表：把每套卷子的题号、知识点、分值列出来，然后按知识点汇总。比如 LL(1) 分析表构造出现了 5 次，平均分值 12 分；LR 分析表出现了 4 次，平均分值 15 分；四元式生成出现了 3 次，平均分值 10 分。这样复习时就知道该把时间花在哪里。如果某个知识点只出现过一次，而且分值不高，可以放到最后再看。

这张表是根据常见题型估的，具体到某一年可能会有变化，但整体趋势差不多。做减法复习的意思是，如果时间只够看三个知识点，就选词法、LL(1) 和 LR，这三个几乎年年考。

5.2 模拟考场：限时手推一套卷子

看解答 PDF 看多了会产生“我会了”的错觉，真正上考场手推又是另一回事。我的习惯是考前一周找一套没做过的真题，限时两小时，完全模拟考场环境：不翻书、不查 PDF、不用计算器，只用草稿纸和笔。推完之后再对照 PDF 解答，按步骤给分，看看自己到底能拿多少。

限时模拟的关键是暴露“卡壳点”。比如 LL(1) 分析表构造，你可能在 FOLLOW 集上卡了十分钟，导致后面的题没时间做。这种卡壳点在平时刷题时不容易发现，因为你可以随时翻书。限时模拟后，把卡壳的知识点记下来，考前最后一天专门看这些。另外，手推时要注意书写规范，分析表要画清楚行列，四元式要标好编号，避免因为卷面混乱被扣分。

从那以后我每次带编译原理的期末复习，都强制自己先限时手推一套真题，再对着 PDF 归因，最后按权重表做减法。这套流程走下来，心里会踏实很多。希望帮到你。

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