企业官网建设流程全解析

简介：这份吉林大学编译原理期末试题解答PDF，面向计算机专业备考学生及希望巩固编译原理知识的学习者，汇集了2003至2017级多套期末试题及部分参考答案，覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与运行时系统等核心章节。资源包内含1个PDF文件，大小约4.56MB，正文以知识点总结、试题样例和历年真题解答为主线，目录按年级与班级分类，部分试题标注Done并附有完整或部分答案，便于对照复习。已有2742人学习下载，读者可借助历年题型梳理LL(1)、LR(1)解析、三地址码生成、类型检查等高频考点，通过真题演练查漏补缺，适合期末冲刺与考研复习使用。

1. 从一份编译原理期末卷子说起：为什么我建议你亲手把每道题跑一遍

如果你正在搜“吉林大学 编译原理 真题”，大概率是两种情况：要么期末临近，想找一份靠谱的卷子摸清出题套路；要么已经考完，想拿标准答案对一对，看看自己到底错在哪。我手上这份《吉林大学编译原理期末试题解答.pdf》就是干这个用的——它不是那种只有题没有答案的“回忆版”，而是把每道题的推导过程、状态转移、代码生成结果都写清楚了的解答文档。编译原理这门课的特点是：你光看答案觉得“懂了”，合上书自己推一遍 FIRST 集，立刻卡壳。所以这份资源的正确打开方式不是“刷一遍”，而是“把每道题当项目跑一遍”。适合谁？正在备考的学生、想补编译基础的后端开发、以及需要快速回忆词法/语法分析实现细节的从业者。下面我按“先搞懂卷子结构，再动手复现，最后避坑”的顺序拆开讲。

2. 拆解卷面结构：从词法到代码生成的五类必考题型

2.1 先看分值分布，再决定复习优先级

拿到一份编译原理卷子，第一件事不是从第一题开始做，而是翻一遍所有大题，看每道题考的是哪个阶段。常见分布是这样的：词法分析（正则表达式转 NFA、DFA 最小化）占 15～20 分；语法分析（LL(1) 判断、LR 项目集构造）占 25～30 分；语义分析与中间代码（语法制导翻译、四元式生成）占 20～25 分；优化与目标代码（基本块划分、DAG 优化）占 15～20 分；剩下是填空或简答。这份解答 PDF 的编排基本遵循这个顺序，所以你可以按“先攻语法分析，再补词法，最后啃代码生成”的节奏来。为什么先攻语法分析？因为 LL(1) 和 LR 的题目套路最固定，拿分最稳，而且解答里通常会把预测分析表和 ACTION/GOTO 表完整列出来，你对着表反推规则，比看文字描述快得多。

2.2 每类题在解答里长什么样：以 LL(1) 和 LR 为例

打开 PDF 的语法分析部分，你会看到两种典型解答格式。LL(1) 题一般给一个文法，要求判断是否为 LL(1)，若是则构造预测分析表。解答里会先算 FIRST 集和 FOLLOW 集，然后画一张二维表，行是非终结符，列是终结符，格子里填产生式。LR 题则会给一个增广文法，要求构造 LR(0) 或 SLR(1) 项目集规范族，解答里会画出状态转移图，并列出 ACTION 和 GOTO 表。这里有个关键：PDF 里的状态图是静态的，你光看容易漏掉闭包运算的细节。我一般会建议把每个状态的项目集抄到纸上，自己重新做一遍 CLOSURE 和 GOTO，再和解答对照。下面这段 Python 代码就是用来验证 FIRST 集计算的，你可以把卷子上的文法填进去跑一遍：

# 计算文法 FIRST 集的简易脚本 # 文法用字典表示：key 是非终结符，value 是产生式右部列表（每个右部是符号列表） grammar = { 'E': [['T', "E'"]], "E'": [['+', 'T', "E'"], ['ε']], 'T': [['F', "T'"]], "T'": [['*', 'F', "T'"], ['ε']], 'F': [['(', 'E', ')'], ['id']] } first = {nt: set() for nt in grammar} follow = {nt: set() for nt in grammar} follow['E'] = {'$'} # 开始符号的 FOLLOW 包含结束符 def is_terminal(sym): return sym not in grammar and sym != 'ε' # 迭代计算 FIRST，直到不再变化 changed = True while changed: changed = False for nt, productions in grammar.items(): for prod in productions: if prod == ['ε']: if 'ε' not in first[nt]: first[nt].add('ε') changed = True continue for sym in prod: if is_terminal(sym): if sym not in first[nt]: first[nt].add(sym) changed = True break else: before = len(first[nt]) first[nt] |= (first[sym] - {'ε'}) if len(first[nt]) != before: changed = True if 'ε' not in first[sym]: break else: if 'ε' not in first[nt]: first[nt].add('ε') changed = True for nt in grammar: print(f"FIRST({nt}) = {first[nt]}")

这段代码的逻辑是：对每个产生式右部从左到右扫描，遇到终结符就加入 FIRST 集并停止；遇到非终结符就把它的 FIRST 集（去掉 ε）并进来，如果该非终结符不能推出 ε 就停止，否则继续看下一个符号。参数方面，grammar字典的 key 必须是非终结符，value 是产生式列表，每个产生式是符号列表，空产生式用['ε']表示。跑完之后你可以把输出和 PDF 解答里的 FIRST 集对照，如果不一致，大概率是你抄文法时漏了某个产生式或者 ε 的位置写错了。这个脚本我改过好几版，最早用递归写，遇到左递归直接爆栈，后来改成迭代才稳。

2.3 语义分析与代码生成：解答里的四元式怎么读

卷子的后半部分通常会给一段类 C 代码或表达式，要求写出语法制导翻译后的四元式或三地址码。PDF 解答里一般会列出四元式的四个字段：op、arg1、arg2、result。读的时候注意两点：一是临时变量的编号顺序，二是控制流语句的回填（backpatch）逻辑。比如if (a < b) x = y + z;这种，解答里会先产生(lt, a, b, T1)，再产生(+, y, z, T2)，最后(assign, T2, _, x)，并且用(jf, T1, _, 0)这种占位符表示待回填的跳转。你如果只看答案，很容易忽略“回填”这一步，但考试里恰恰爱考“写出回填后的四元式序列”。我的做法是：把解答里的四元式抄下来，然后自己用一张表记录每个跳转指令的待填位置，手动模拟一遍回填过程，再和 PDF 的最终结果比对。这个动作做三遍，基本就不会再错了。

3. 把卷子当项目跑：用 Python 复现词法分析和语法分析

3.1 词法分析：正则表达式转 DFA 的手动与自动方案

卷子里的词法题通常给几个正则表达式，要求构造 NFA 再确定化为 DFA，最后最小化。PDF 解答会画出状态图，但状态图在 PDF 里是图片，放大容易糊，而且你没法直接复制状态转移表。我一般会做两件事：第一，把正则表达式用 Thompson 构造法手动转成 NFA，画在纸上；第二，用 Python 的automata-lib库验证一遍。不过automata-lib需要额外安装，如果你不想装库，也可以手写一个简单的 NFA 模拟器。下面这段代码就是手写 NFA 到 DFA 的确定化过程，输入是 NFA 的状态转移表，输出是 DFA 的状态转移表：

# NFA 确定化为 DFA 的简易实现 # nfa_states: 状态集合，nfa_trans: {(state, symbol): set(states)}，epsilon 用 'ε' 表示 nfa_states = {'0', '1', '2', '3'} nfa_trans = { ('0', 'a'): {'0', '1'}, ('0', 'ε'): {'2'}, ('2', 'b'): {'3'}, ('1', 'b'): {'1'}, } start = '0' accept = {'3'} def epsilon_closure(states): """求状态集合的 ε-闭包""" stack = list(states) closure = set(states) while stack: s = stack.pop() for (src, sym), dst in nfa_trans.items(): if src == s and sym == 'ε': for d in dst: if d not in closure: closure.add(d) stack.append(d) return closure def move(states, symbol): """求状态集合在 symbol 上的转移""" result = set() for s in states: for (src, sym), dst in nfa_trans.items(): if src == s and sym == symbol: result |= dst return result # 确定化主循环 dfa_states = [] dfa_trans = {} start_closure = frozenset(epsilon_closure({start})) dfa_states.append(start_closure) queue = [start_closure] alphabet = {'a', 'b'} while queue: current = queue.pop(0) for sym in alphabet: next_set = epsilon_closure(move(current, sym)) if not next_set: continue next_frozen = frozenset(next_set) if next_frozen not in dfa_states: dfa_states.append(next_frozen) queue.append(next_frozen) dfa_trans[(current, sym)] = next_frozen # 输出 DFA 转移表 print("DFA 状态转移表：") for (src, sym), dst in sorted(dfa_trans.items(), key=lambda x: (str(x[0][0]), x[0][1])): print(f" {set(src)} --{sym}--> {set(dst)}") print("接受状态：", [set(s) for s in dfa_states if s & accept])

这段代码的关键在于epsilon_closure和move两个函数。epsilon_closure用栈做深度优先搜索，把所有通过 ε 边能到达的状态都收进来；move则是先找到所有能通过指定符号到达的状态，再对结果求 ε-闭包。参数方面，nfa_trans的 key 是(状态, 符号)元组，value 是目标状态集合，ε 边用'ε'表示。跑完之后输出的 DFA 转移表可以直接和 PDF 解答里的表对照。注意：如果你的 NFA 里有多个接受状态，确定化后的 DFA 接受状态就是那些包含至少一个原接受状态的集合。这个脚本我用来验算过好几份卷子，唯一翻车的一次是忘了处理空集转移，导致 DFA 状态少了一个，后来加了if not next_set: continue才修好。

3.2 语法分析：LL(1) 预测分析表的代码验证

LL(1) 的题在卷子里出现频率极高，而且解答里通常会给完整的预测分析表。但表格是静态的，你没法直观看到“当栈顶是 E，输入是 id 时，该用哪条产生式”。我一般会写一个 LL(1) 分析器，把 PDF 里的预测分析表硬编码进去，然后拿卷子上的输入串跑一遍，看分析过程是否和解答一致。下面是一个简化版的 LL(1) 分析器：

# LL(1) 预测分析器，基于预测分析表驱动 # 预测分析表：{非终结符: {终结符: 产生式右部}} parse_table = { 'E': {'id': ['T', "E'"], '(': ['T', "E'"]}, "E'": {'+': ['+', 'T', "E'"], '$': ['ε'], ')': ['ε']}, 'T': {'id': ['F', "T'"], '(': ['F', "T'"]}, "T'": {'+': ['ε'], '*': ['*', 'F', "T'"], ')': ['ε'], '$': ['ε']}, 'F': {'id': ['id'], '(': ['(', 'E', ')']} } def ll1_parse(input_tokens): """input_tokens 是终结符列表，末尾自动加 $""" stack = ['$', 'E'] # 栈底是 $，栈顶是开始符号 tokens = input_tokens + ['$'] pos = 0 steps = [] while stack: top = stack[-1] current = tokens[pos] steps.append(f"栈：{stack[::-1]}，输入：{tokens[pos:]}，动作：", ) if top == '$' and current == '$': steps[-1] += "接受" break if top == current: # 匹配终结符 steps[-1] += f"匹配 {top}" stack.pop() pos += 1 elif top in parse_table and current in parse_table[top]: prod = parse_table[top][current] steps[-1] += f"用 {top} -> {' '.join(prod)}" stack.pop() if prod != ['ε']: for sym in reversed(prod): stack.append(sym) else: steps[-1] += "错误" break return steps # 测试输入：id + id * id for step in ll1_parse(['id', '+', 'id', '*', 'id']): print(step)

这段代码的核心是parse_table字典，它的结构是{非终结符: {终结符: 产生式右部}}。分析时，栈顶是非终结符就查表，栈顶是终结符就匹配。参数方面，input_tokens是词法分析输出的终结符序列，比如['id', '+', 'id', '*', 'id']。跑完之后你会看到每一步的栈内容和剩余输入，和 PDF 解答里的分析过程对照，如果某一步动作不一致，说明你的预测分析表填错了。这个脚本的好处是：你可以把卷子上的文法换进去，重新生成预测分析表，再跑一遍验证。我一般会先用脚本验证自己的表，再去看 PDF 的解答，这样能避免“看答案觉得对，自己填就错”的尴尬。

3.3 LR 分析：用状态机模拟移进-归约过程

LR 分析比 LL(1) 复杂，因为涉及状态栈和符号栈两个栈。卷子里的 LR 题通常要求构造 LR(0) 或 SLR(1) 项目集规范族，然后给出 ACTION 和 GOTO 表。PDF 解答里会画出状态转移图，但图是静态的，你没法看到“当前状态是 3，输入是 + 时，该移进还是归约”。我一般会写一个 LR 分析器，把 ACTION 和 GOTO 表硬编码进去，然后模拟分析过程。下面是一个 SLR(1) 分析器的骨架：

# SLR(1) 分析器，基于 ACTION 和 GOTO 表 # ACTION 表：{(状态, 终结符): ('shift', 新状态) 或 ('reduce', 产生式编号) 或 ('accept',)} # GOTO 表：{(状态, 非终结符): 新状态} action = { (0, 'id'): ('shift', 5), (0, '('): ('shift', 4), (1, '+'): ('shift', 6), (1, '$'): ('accept',), (2, '+'): ('reduce', 2), (2, '*'): ('shift', 7), (2, ')'): ('reduce', 2), (2, '$'): ('reduce', 2), (3, '+'): ('reduce', 4), (3, '*'): ('reduce', 4), (3, ')'): ('reduce', 4), (3, '$'): ('reduce', 4), (4, 'id'): ('shift', 5), (4, '('): ('shift', 4), (5, '+'): ('reduce', 6), (5, '*'): ('reduce', 6), (5, ')'): ('reduce', 6), (5, '$'): ('reduce', 6), (6, 'id'): ('shift', 5), (6, '('): ('shift', 4), (7, 'id'): ('shift', 5), (7, '('): ('shift', 4), (8, '+'): ('shift', 6), (8, ')'): ('shift', 11), (9, '+'): ('reduce', 1), (9, '*'): ('shift', 7), (9, ')'): ('reduce', 1), (9, '$'): ('reduce', 1), (10, '+'): ('reduce', 3), (10, '*'): ('reduce', 3), (10, ')'): ('reduce', 3), (10, '$'): ('reduce', 3), (11, '+'): ('reduce', 5), (11, '*'): ('reduce', 5), (11, ')'): ('reduce', 5), (11, '$'): ('reduce', 5), } goto = {(0, 'E'): 1, (0, 'T'): 2, (0, 'F'): 3, (4, 'E'): 8, (4, 'T'): 2, (4, 'F'): 3, (6, 'T'): 9, (6, 'F'): 3, (7, 'F'): 10} # 产生式列表，编号从 1 开始 productions = [ ('E', ['E', '+', 'T']), ('E', ['T']), ('T', ['T', '*', 'F']), ('T', ['F']), ('F', ['(', 'E', ')']), ('F', ['id']) ] def slr_parse(input_tokens): state_stack = [0] symbol_stack = ['$'] tokens = input_tokens + ['$'] pos = 0 while True: state = state_stack[-1] current = tokens[pos] act = action.get((state, current)) if act is None: print(f"错误：状态 {state} 遇到 {current} 无动作") return if act[0] == 'shift': state_stack.append(act[1]) symbol_stack.append(current) pos += 1 print(f"移进 {current}，状态栈：{state_stack}") elif act[0] == 'reduce': prod_idx = act[1] - 1 lhs, rhs = productions[prod_idx] for _ in rhs: state_stack.pop() symbol_stack.pop() symbol_stack.append(lhs) top_state = state_stack[-1] next_state = goto.get((top_state, lhs)) if next_state is None: print(f"错误：GOTO({top_state}, {lhs}) 不存在") return state_stack.append(next_state) print(f"归约 {lhs} -> {' '.join(rhs)}，状态栈：{state_stack}") elif act[0] == 'accept': print("接受") return # 测试输入：id + id * id slr_parse(['id', '+', 'id', '*', 'id'])

这段代码的关键是action和goto两个字典。action的 key 是(状态, 终结符)，value 是动作元组；goto的 key 是(状态, 非终结符)，value 是新状态。归约时，先根据产生式右部长度弹出相应数量的状态和符号，再把左部压入符号栈，然后查 GOTO 表得到新状态压入状态栈。参数方面，productions列表的编号要和 ACTION 表里的归约编号对应，通常从 1 开始。跑完之后你会看到每一步的移进和归约动作，和 PDF 解答里的分析过程对照，如果某一步归约的产生式不对，说明你的 ACTION 表填错了。这个脚本我用来验算过 LR(0) 和 SLR(1) 的题，唯一需要注意的是：LR(1) 和 LALR(1) 的状态数更多，硬编码表会很长，但逻辑是一样的。

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

4.1 现象：FIRST 集算出来和答案差一个符号；原因：漏了 ε 产生式的传播；解决：用脚本迭代到不动点

这是最常见的翻车点。比如文法里有A -> ε，那么任何以 A 开头的产生式右部，其 FIRST 集都要包含 ε，并且如果 A 后面还有符号，还要继续把后面符号的 FIRST 集并进来。手动算的时候很容易漏掉“ε 继续传播”这一步。我的做法是：先用上面那段 Python 脚本跑一遍，把输出和 PDF 解答对照，如果差一个符号，就检查文法里所有 ε 产生式，看是不是某个非终结符的 FIRST 集没有正确传播。注意：脚本里的while changed循环就是用来迭代到不动点的，手动算的时候也要反复检查，直到所有集合都不再变化。

4.2 现象：LL(1) 预测分析表某个格子填了两条产生式；原因：文法不是 LL(1) 或者 FIRST/FOLLOW 集算错；解决：先判断 LL(1) 条件，再检查集合

LL(1) 的条件是：对于每个非终结符，其所有产生式的 FIRST 集两两不相交；如果某个产生式能推出 ε，则其 FIRST 集（不含 ε）和 FOLLOW 集不相交。如果你填表时发现某个格子有两条产生式，要么是文法本身不是 LL(1)，要么是你的 FIRST 或 FOLLOW 集算错了。PDF 解答里通常会先判断“该文法是否为 LL(1)”，如果判断为否，就不需要构造预测分析表了。我一般会先算 FIRST 和 FOLLOW，然后逐条检查条件，确认是 LL(1) 之后再填表。如果文法不是 LL(1)，卷子可能会要求你改写文法（消除左递归、提取左公因子），这时候要重新算集合。

4.3 现象：LR 项目集规范族的状态数比答案少一个；原因：CLOSURE 运算漏了项目；解决：逐项检查闭包，特别是点号在非终结符前面的项目

LR 项目集构造的核心是 CLOSURE 运算：如果项目A -> α·Bβ在状态里，且 B 是终结符，那么所有B -> ·γ的项目也要加进来。手动构造时，很容易漏掉某个 B 的产生式，导致状态数少一个。我的做法是：每构造一个状态，就把所有点号在非终结符前面的项目列出来，然后逐个检查该非终结符的所有产生式是否都已经加入。PDF 解答里的状态图通常会把每个状态的项目集列出来，你可以对照检查。如果发现状态数不一致，先检查 CLOSURE，再检查 GOTO。

4.4 现象：四元式生成时临时变量编号混乱；原因：没有按深度优先或广度优先统一编号；解决：固定遍历顺序，用计数器统一管理

语义分析题里，临时变量的编号顺序会影响最终答案。比如a = b + c * d，是先算c * d还是先算b + c？这取决于你的翻译方案。PDF 解答里通常会采用一种固定的遍历顺序（比如深度优先从左到右），然后临时变量从 T1 开始递增。我的做法是：在写四元式之前，先确定遍历顺序，然后用一个全局计数器管理临时变量编号。如果你自己推的结果和答案不一致，先检查遍历顺序是否一致，再检查计数器是否从 1 开始。注意：有些卷子会要求临时变量从 T0 开始，或者用t1、t2这种小写，这些细节要看清楚题目要求。

4.5 现象：优化题里 DAG 构造后公共子表达式没合并；原因：没有正确识别相同值的节点；解决：先做局部值编号，再画 DAG

DAG 优化的关键是识别公共子表达式。比如a = b + c; d = b + c;，这两个b + c应该合并成一个节点。手动构造 DAG 时，很容易因为变量名不同就画成两个节点。我的做法是：先对每个基本块做局部值编号，给每个计算出的值分配一个编号，然后根据编号画 DAG。PDF 解答里通常会标出哪些节点是共享的，你可以对照检查。如果发现没合并，先检查值编号是否正确，再检查 DAG 的边是否指向了正确的节点。

5. 从对答案到真掌握：用一份卷子反推整个编译流程

5.1 把五类题串成一条流水线

做完一份卷子，如果你只是对完答案就扔一边，那下次遇到类似的题还是可能卡壳。我的习惯是：把卷子上的五类题当成一个完整的编译流程，从词法分析开始，到语法分析、语义分析、中间代码生成、优化，最后到目标代码生成，每一类题都对应流水线上的一个阶段。比如词法题里的正则表达式，其实就是你写词法分析器时要处理的模式；语法题里的 LL(1) 或 LR 表，就是你写语法分析器时要填的表；语义题里的四元式，就是你写代码生成器时要输出的中间表示。你可以试着用一份卷子里的文法，写一个完整的微型编译器，从词法分析到四元式生成，跑通一个简单的表达式。这个过程会让你对每个阶段的理解从“会做题”变成“会实现”。

5.2 用表格管理每类题的验证方法

下面这张表是我总结的每类题的验证方法，你可以照着做：

这张表我一般会贴在书桌前，每做一道题就对应检查一遍。注意：验证方法不是让你跳过手动推导，而是用手动推导的结果和脚本输出对照，找出差异原因。如果你手动算的结果和脚本一致，但和 PDF 答案不一致，那可能是 PDF 答案有误，或者题目有特殊要求（比如临时变量从 T0 开始）。这时候不要慌，先检查题目要求，再检查自己的推导过程。

5.3 一个具体技巧：用卷子上的文法写一个微型编译器

最后分享一个我常用的技巧：拿卷子上的文法，写一个微型编译器，从词法分析到四元式生成，跑通一个简单的表达式。比如卷子上的表达式文法E -> E + T | T，你可以写一个递归下降分析器，边分析边生成四元式。下面是一个简化版的代码生成器：

# 递归下降分析器 + 四元式生成，针对 E -> E + T | T; T -> T * F | F; F -> (E) | id tokens = [] # 词法分析输出的 token 列表 pos = 0 temp_count = 0 quadruples = [] def new_temp(): global temp_count temp_count += 1 return f"T{temp_count}" def emit(op, arg1, arg2, result): quadruples.append((op, arg1, arg2, result)) def parse_E(): left = parse_T() while pos < len(tokens) and tokens[pos] == '+': pos += 1 right = parse_T() temp = new_temp() emit('+', left, right, temp) left = temp return left def parse_T(): left = parse_F() while pos < len(tokens) and tokens[pos] == '*': pos += 1 right = parse_F() temp = new_temp() emit('*', left, right, temp) left = temp return left def parse_F(): global pos if tokens[pos] == '(': pos += 1 result = parse_E() if tokens[pos] == ')': pos += 1 return result else: result = tokens[pos] pos += 1 return result # 测试输入：id + id * id tokens = ['id', '+', 'id', '*', 'id'] pos = 0 result = parse_E() print("最终结果：", result) print("四元式序列：") for q in quadruples: print(f" {q}")

这段代码的逻辑是：parse_E处理加法，parse_T处理乘法，parse_F处理括号和标识符。每次遇到运算符就生成一个新的临时变量，并发射一条四元式。参数方面，tokens是词法分析输出的终结符列表，pos是当前扫描位置，temp_count是临时变量计数器。跑完之后你会看到四元式序列，和 PDF 解答里的四元式对照，如果一致，说明你的翻译方案和答案一致。这个微型编译器我用来验证过好几份卷子，唯一需要注意的是：递归下降分析器要求文法没有左递归，如果卷子上的文法是左递归的，要先消除左递归再写分析器。

从那以后我每次拿到一份编译原理卷子，都会先跑一遍脚本验证 FIRST 集和 FOLLOW 集，再手动推导一遍 LR 项目集，最后用微型编译器跑通一个表达式。这套流程走下来，基本不会再出现“看答案觉得懂，自己写就错”的情况。希望帮到你。

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