企业官网建设流程全解析

简介：这份资源是吉林大学《编译原理》课程2003至2017级期末试题的解答合集，面向正在备考或希望巩固编译原理知识的高校学生。内容覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、错误处理与运行时系统等核心章节，并包含唐敖庆班试题及回忆版本，部分试题附有完整或部分参考答案。资源包为1个PDF文件，大小约4.56MB，内含知识点总结与历年试题解答，目录按年份与班级分类，便于按需检索。目前已有2742人学习下载，读者可借助它梳理各阶段考点、对照解析查漏补缺，理解LL(1)、LR(1)解析、三地址码生成等典型题型的解题思路，适合作为期末复习与知识强化的实践材料。

1. 编译原理期末试题解答：从一道DFA最小化题看透整张卷子的出题逻辑

每年一到期末，总有人在群里甩出一份《编译原理期末试题解答.pdf》，然后问“这题为什么选C”。我翻过不少这类解答文档，发现一个反直觉的现象：大部分丢分不是因为不会，而是因为把“解答”当成了“答案”。一份好的试题解答，价值不在于告诉你选什么，而在于把出题人埋的坑一个个标出来——哪些是必须手算的、哪些是可以套模板的、哪些是换个数字就会翻车的。编译原理这门课，期末卷子的结构其实高度稳定：词法分析必考NFA转DFA和最小化，语法分析必考LL(1)和LR分析表，语义分析常考语法制导翻译，中间代码生成和优化则看老师心情。如果你手里正拿着一份试题解答在啃，或者准备靠刷题过这门课，下面这套拆解思路应该能帮你省下不少时间。

2. 词法分析大题：NFA转DFA和最小化的手算模板

2.1 为什么子集构造法总是算错

子集构造法的核心就一句话：从初态闭包出发，对每个输入符号求转移后的闭包，新出现的状态集就加进DFA状态表。听起来简单，但手算时最容易翻车的地方有三个。

第一个坑是ε闭包漏算。很多人在求move(S, a)之后直接把它当成新状态，忘了再求一次ε闭包。比如状态集{1,2}经过a到达{3}，而3有一条ε到4，那实际新状态应该是{3,4}。这个错误在解答文档里经常被标红，但自己算的时候还是照错不误。

第二个坑是状态命名混乱。子集构造出来的DFA状态是集合，手算时如果不用A、B、C重新编号，写到后面自己都不认识。我一般建议在草稿纸上先列一张对照表：A={0,1,2}，B={3,4}，C={5}，后面所有转移都写字母。

第三个坑是终态判断遗漏。只要集合里包含原NFA的终态，这个DFA状态就是终态。有人只盯着集合里有没有那个“唯一的终态”，结果含终态的集合被漏标。

下面是一个典型的手算流程，用Python把步骤验证一遍，方便对照：

# NFA定义：状态0-5，字母表{a,b}，ε用''表示 nfa = { 0: {'': [1], 'a': [2]}, 1: {'': [3]}, 2: {'a': [2], 'b': [4]}, 3: {'b': [5]}, 4: {'a': [5]}, 5: {} } start = 0 accept = {5} def epsilon_closure(states): """求状态集合的ε闭包，用栈做深度优先""" stack = list(states) closure = set(states) while stack: s = stack.pop() for nxt in nfa.get(s, {}).get('', []): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, ch): """求状态集合经过字符ch能到达的状态集（不含ε闭包）""" result = set() for s in states: for nxt in nfa.get(s, {}).get(ch, []): result.add(nxt) return result # 子集构造主循环 dfa_states = {} queue = [epsilon_closure({start})] dfa_states[queue[0]] = 'A' transitions = {} idx = ord('A') while queue: current = queue.pop(0) name = dfa_states[current] for ch in ['a', 'b']: nxt_set = epsilon_closure(move(current, ch)) if not nxt_set: continue if nxt_set not in dfa_states: idx += 1 dfa_states[nxt_set] = chr(idx) queue.append(nxt_set) transitions[(name, ch)] = dfa_states[nxt_set] # 输出DFA转移表和终态 print("DFA状态对应：") for k, v in dfa_states.items(): print(f" {v} = {set(k)}") print("\n转移表：") for (src, ch), dst in sorted(transitions.items()): print(f" {src} --{ch}--> {dst}") print("\n终态：", [dfa_states[s] for s in dfa_states if s & accept])

这段代码的关键在于epsilon_closure用栈而不是递归，避免状态多的时候递归深度爆炸。move函数只做直接转移，闭包单独求，逻辑分离清楚。运行后你会得到一张完整的DFA转移表，终态就是那些包含原终态5的集合。

参数说明：nfa字典的键是状态编号，值是一个字典，''对应ε转移，其他键对应输入字符。如果你的题目里ε用其他符号表示，改一下键名就行。accept集合里放原NFA的所有终态。

2.2 DFA最小化：分区法的手算步骤与验证

DFA最小化用分区法（也叫填表法），步骤是：先分成终态集和非终态集，然后不断细分，直到每个子集内所有状态对所有输入符号都转移到相同的子集。

手算时最容易出错的是细分顺序。有人先把所有状态按转移目标分一遍，结果把终态和非终态混在一起了。正确顺序是：初始分区一定是{终态}和{非终态}两个组，然后对每个组检查是否需要拆分。

拆分的判断标准：对于组内任意两个状态p和q，如果存在某个输入符号a，使得p经过a到达的组和q经过a到达的组不同，那p和q就不等价，必须拆开。

下面用代码验证最小化结果：

# 基于上一步得到的DFA转移表 dfa_trans = { ('A', 'a'): 'B', ('A', 'b'): 'C', ('B', 'a'): 'B', ('B', 'b'): 'D', ('C', 'a'): 'B', ('C', 'b'): 'C', ('D', 'a'): 'B', ('D', 'b'): 'C', } dfa_accept = {'D'} all_states = {'A', 'B', 'C', 'D'} alphabet = ['a', 'b'] def minimize(states, accept, trans, alpha): # 初始分区：终态组和非终态组 partitions = [accept, states - accept] partitions = [p for p in partitions if p] # 去掉空集 changed = True while changed: changed = False new_partitions = [] for group in partitions: # 尝试把group拆成若干子组 split_map = {} for s in group: # 对每个状态，记录它对各输入符号落在哪个分区 signature = [] for ch in alpha: dst = trans.get((s, ch)) if dst is None: signature.append(-1) else: for i, p in enumerate(partitions): if dst in p: signature.append(i) break signature = tuple(signature) split_map.setdefault(signature, set()).add(s) if len(split_map) > 1: changed = True new_partitions.extend(split_map.values()) partitions = new_partitions return partitions result = minimize(all_states, dfa_accept, dfa_trans, alphabet) print("最小化后的状态分组：") for i, group in enumerate(result): print(f" 组{i}: {group}")

这段代码的signature是关键：它把每个状态对字母表中所有字符的转移目标映射成分区编号，签名相同的状态才能留在同一组。如果某个转移目标不存在（比如死状态），用-1表示，单独成组。

运行后如果输出是{A, B, C}和{D}两组，说明A、B、C等价，可以合并。这时候最小化DFA就只有两个状态了。注意：如果题目要求画出最小化DFA，记得把合并后的状态用新名字标出来，转移关系从原表中继承。

3. 语法分析大题：LL(1)分析表和LR分析表的构造

3.1 FIRST集和FOLLOW集的手算口诀

FIRST集和FOLLOW集是LL(1)分析表的基础，手算时有一套口诀可以少犯错。

FIRST集口诀：看产生式右部第一个符号，终结符直接进，非终结符递归找，遇到ε要传递。具体来说，对于A → X1X2...Xn，先把FIRST(X1)中所有非ε元素加入FIRST(A)，如果X1能推出ε，再把FIRST(X2)的非ε元素加入，以此类推。如果所有Xi都能推出ε，那ε也加入FIRST(A)。

FOLLOW集口诀：开始符号先放$，产生式右部找非终结符，后面符号的FIRST去掉ε加进来，后面全能推ε就把左部FOLLOW加进来。对于A → αBβ，把FIRST(β)-{ε}加入FOLLOW(B)；如果β能推出ε，把FOLLOW(A)也加入FOLLOW(B)。

下面是一个完整的计算脚本：

# 文法：E -> T E', E' -> + T E' | ε, T -> F T', T' -> * F T' | ε, F -> ( E ) | id grammar = { 'E': [['T', "E'"]], "E'": [['+', 'T', "E'"], ['ε']], 'T': [['F', "T'"]], "T'": [['*', 'F', "T'"], ['ε']], 'F': [['(', 'E', ')'], ['id']] } start_symbol = 'E' terminals = {'+', '*', '(', ')', 'id', '$'} non_terminals = set(grammar.keys()) def first_of_sequence(seq, first_sets): """求一个符号串的FIRST集""" result = set() for sym in seq: if sym in terminals: result.add(sym) return result result |= (first_sets[sym] - {'ε'}) if 'ε' not in first_sets[sym]: return result result.add('ε') return result # 迭代计算FIRST集 first_sets = {nt: set() for nt in non_terminals} changed = True while changed: changed = False for nt, productions in grammar.items(): for prod in productions: if prod == ['ε']: if 'ε' not in first_sets[nt]: first_sets[nt].add('ε') changed = True else: f = first_of_sequence(prod, first_sets) if not f.issubset(first_sets[nt]): first_sets[nt] |= f changed = True # 迭代计算FOLLOW集 follow_sets = {nt: set() for nt in non_terminals} follow_sets[start_symbol].add('$') changed = True while changed: changed = False for nt, productions in grammar.items(): for prod in productions: for i, sym in enumerate(prod): if sym not in non_terminals: continue rest = prod[i+1:] if rest: f = first_of_sequence(rest, first_sets) add_set = f - {'ε'} if not add_set.issubset(follow_sets[sym]): follow_sets[sym] |= add_set changed = True if 'ε' in f: if not follow_sets[nt].issubset(follow_sets[sym]): follow_sets[sym] |= follow_sets[nt] changed = True else: if not follow_sets[nt].issubset(follow_sets[sym]): follow_sets[sym] |= follow_sets[nt] changed = True print("FIRST集：") for nt in sorted(non_terminals): print(f" FIRST({nt}) = {first_sets[nt]}") print("\nFOLLOW集：") for nt in sorted(non_terminals): print(f" FOLLOW({nt}) = {follow_sets[nt]}")

这段代码的first_of_sequence处理了符号串的FIRST计算，遇到能推ε的符号会继续看下一个。FOLLOW集计算里，rest是产生式右部当前符号之后的部分，如果rest为空，直接把左部的FOLLOW加进来。

参数说明：grammar字典的键是非终结符，值是产生式列表，每个产生式是符号列表，ε用'ε'表示。如果你的题目用其他符号表示空串，改一下就行。

3.2 LL(1)分析表的构造与冲突处理

有了FIRST和FOLLOW，LL(1)分析表的构造就机械了：对每个产生式A → α，对FIRST(α)中每个终结符a，把A → α填入M[A, a]；如果ε在FIRST(α)中，对FOLLOW(A)中每个终结符b，把A → α填入M[A, b]。

冲突处理是考试重点。如果同一个格子要填两个产生式，说明文法不是LL(1)的。常见的冲突原因有：左递归没消除、公共左因子没提取、或者文法本身有歧义。考试时如果要求改写成LL(1)，通常就是提左因子和消左递归两步。

下面构造分析表：

# 基于上面的FIRST和FOLLOW集 parsing_table = {} conflicts = [] for nt, productions in grammar.items(): for prod in productions: if prod == ['ε']: for b in follow_sets[nt]: key = (nt, b) if key in parsing_table: conflicts.append((key, parsing_table[key], prod)) parsing_table[key] = prod else: f = first_of_sequence(prod, first_sets) for a in f - {'ε'}: key = (nt, a) if key in parsing_table: conflicts.append((key, parsing_table[key], prod)) parsing_table[key] = prod print("LL(1)分析表：") for nt in sorted(non_terminals): for t in sorted(terminals): key = (nt, t) if key in parsing_table: print(f" M[{nt}, {t}] = {nt} -> {' '.join(parsing_table[key])}") if conflicts: print("\n发现冲突：") for c in conflicts: print(f" {c}") else: print("\n无冲突，文法是LL(1)的")

运行后如果输出“无冲突”，说明这个经典表达式文法是LL(1)的。如果有冲突，考试时通常要求你指出冲突并说明原因。

3.3 LR(1)和LALR(1)的项目集构造

LR分析比LL强大，但手算项目集更繁琐。LR(0)项目集构造的关键是闭包运算和转移函数。闭包运算：如果项目A → α·Bβ在集合中，且B → γ是产生式，那B → ·γ也加入集合。转移函数：对项目集I和符号X，move(I, X)是I中所有形如A → α·Xβ的项目转移后得到的A → αX·β的集合，再求闭包。

LR(1)项目比LR(0)多了一个搜索符，闭包运算时搜索符的传递规则是：对于A → α·Bβ, a，对每个B → γ，把FIRST(βa)加入搜索符。

LALR(1)是在LR(1)基础上合并同心项目集，合并后如果产生冲突，说明不是LALR(1)的。

手算时建议用表格跟踪：项目集编号、包含的项目、转移关系。下面是一个LR(0)项目集构造的简化代码：

# 文法：S' -> S, S -> C C, C -> c C | d lr_grammar = { "S'": [['S']], 'S': [['C', 'C']], 'C': [['c', 'C'], ['d']] } lr_start = "S'" def closure_lr0(items): """LR(0)闭包""" result = set(items) changed = True while changed: changed = False for lhs, rhs, dot in list(result): if dot < len(rhs) and rhs[dot] in lr_grammar: for prod in lr_grammar[rhs[dot]]: item = (rhs[dot], tuple(prod), 0) if item not in result: result.add(item) changed = True return frozenset(result) def goto_lr0(items, symbol): """转移函数""" moved = set() for lhs, rhs, dot in items: if dot < len(rhs) and rhs[dot] == symbol: moved.add((lhs, rhs, dot + 1)) if not moved: return None return closure_lr0(moved) # 构造项目集族 start_item = (lr_start, ('S',), 0) I0 = closure_lr0({start_item}) states = [I0] trans = {} queue = [I0] while queue: current = queue.pop(0) idx_cur = states.index(current) symbols = set() for lhs, rhs, dot in current: if dot < len(rhs): symbols.add(rhs[dot]) for sym in symbols: nxt = goto_lr0(current, sym) if nxt and nxt not in states: states.append(nxt) queue.append(nxt) if nxt: trans[(idx_cur, sym)] = states.index(nxt) print(f"共 {len(states)} 个项目集") for i, s in enumerate(states): print(f"\nI{i}:") for lhs, rhs, dot in sorted(s): rhs_str = ' '.join(rhs[:dot] + ('·',) + rhs[dot:]) print(f" {lhs} -> {rhs_str}") print("\n转移：") for (src, sym), dst in sorted(trans.items()): print(f" I{src} --{sym}--> I{dst}")

这段代码构造了LR(0)项目集族，输出每个项目集的内容和转移关系。考试时如果要求画LR(0)自动机，照着这个输出画就行。注意项目里的点位置，rhs[:dot]是点前面的部分，rhs[dot:]是点后面的部分。

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

4.1 语法制导定义怎么落到四元式

语法制导翻译的核心是给每个产生式配一个语义动作，在语法分析过程中执行。考试常考的是表达式和赋值语句翻译成四元式。

四元式格式是(op, arg1, arg2, result)。比如a = b + c * d，四元式序列是：

1. (*, c, d, t1)
2. (+, b, t1, t2)
3. (=, t2, _, a)

手算时容易犯的错是临时变量编号混乱。建议从t1开始顺序编号，不要跳号。另外，赋值语句的四元式result放左部变量，arg2通常用下划线占位。

下面是一个简单的语法制导翻译模拟：

# 表达式文法（已消除左递归）： # E -> T E', E' -> + T E' | ε, T -> F T', T' -> * F T' | ε, F -> id | ( E ) # 用递归下降+语义动作生成四元式 quads = [] temp_count = [0] def new_temp(): temp_count[0] += 1 return f"t{temp_count[0]}" def emit(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) # 简化的递归下降翻译器，输入是token列表 tokens = ['id', '+', 'id', '*', 'id', '$'] pos = [0] def peek(): return tokens[pos[0]] def match(expected): if peek() == expected: pos[0] += 1 else: raise SyntaxError(f"期望 {expected}，实际 {peek()}") def parse_F(): if peek() == 'id': name = f"id{pos[0]}" match('id') return name elif peek() == '(': match('(') result = parse_E() match(')') return result def parse_T_prime(inherited): if peek() == '*': match('*') right = parse_F() t = new_temp() emit('*', inherited, right, t) return parse_T_prime(t) else: return inherited def parse_T(): left = parse_F() return parse_T_prime(left) def parse_E_prime(inherited): if peek() == '+': match('+') right = parse_T() t = new_temp() emit('+', inherited, right, t) return parse_E_prime(t) else: return inherited def parse_E(): left = parse_T() return parse_E_prime(left) result = parse_E() print("四元式序列：") for i, q in enumerate(quads, 1): print(f" {i}: {q}")

这段代码用递归下降的方式模拟了语法制导翻译。parse_T_prime和parse_E_prime接收继承属性inherited，返回综合属性。每次遇到运算符就生成一个新临时变量并发射四元式。

参数说明：tokens是词法分析输出的token序列，id代表标识符。实际考试中token会带具体名字，这里简化了。emit函数把四元式追加到全局列表。

4.2 布尔表达式和控制流语句的回填

回填技术是考试难点。核心思想是：生成跳转指令时目标地址还不知道，先留空，等目标确定后再填回去。

布尔表达式B → B1 or B2的真出口是B1的真出口和B2的真出口，假出口是B2的假出口。B → B1 and B2的真出口是B2的真出口，假出口是B1的假出口和B2的假出口。

回填时用两个列表truelist和falselist分别记录需要回填真出口和假出口的指令编号。

下面是一个回填的简化实现：

# 回填四元式生成：if (a < b) then x = 1 else x = 2 quads = [] next_quad = [0] def emit(op, arg1, arg2, result): quads.append([op, arg1, arg2, result]) idx = next_quad[0] next_quad[0] += 1 return idx def backpatch(lst, target): for idx in lst: quads[idx][3] = target # 生成条件跳转 # if a < b goto _ idx1 = emit('<', 'a', 'b', None) # 真出口待回填 # goto _ (假出口跳转) idx2 = emit('goto', None, None, None) # then分支：x = 1 emit('=', '1', None, 'x') # goto _ (跳过else) idx3 = emit('goto', None, None, None) # 回填条件为真的目标：跳到then分支开始 backpatch([idx1], idx2 + 1) # else分支：x = 2 emit('=', '2', None, 'x') # 回填then分支结束后的跳转：跳过else backpatch([idx3], next_quad[0]) # 回填条件为假的目标：跳到else分支开始 backpatch([idx2], idx2 + 2) print("回填后的四元式：") for i, q in enumerate(quads): print(f" {i}: {q}")

这段代码演示了最基本的回填流程。emit返回指令编号，backpatch把列表里所有指令的目标字段填成指定编号。注意idx2的假出口回填到idx2+2，因为idx2+1是then分支的第一条指令，idx2+2才是else分支的开始。

考试时如果要求写回填后的四元式序列，照着这个逻辑手推一遍就行。关键是搞清楚每个跳转指令的目标到底是哪一条。

5. 避坑与排查：编译原理期末卷子上最容易丢分的五个地方

5.1 坑一：NFA转DFA时终态标错

现象：子集构造出来的DFA终态少标了一个，导致后面最小化全错。

原因：只检查了集合里有没有原NFA的“唯一终态”，忘了原NFA可能有多个终态，或者终态经过ε闭包后扩展了。

解决：在代码里用s & accept判断集合与终态集的交集是否非空，手算时逐个集合对照原NFA终态列表，别凭记忆。

5.2 坑二：FIRST集计算时ε传递遗漏

现象：FIRST集里少了某个终结符，导致LL(1)分析表缺项。

原因：产生式右部第一个非终结符能推出ε时，忘了继续看第二个符号的FIRST集。

解决：用first_of_sequence函数处理整个符号串，遇到能推ε的符号就继续往后看，直到遇到不能推ε的终结符或非终结符为止。

5.3 坑三：LR项目集闭包运算漏项目

现象：LR(0)自动机状态数比答案少，转移关系对不上。

原因：闭包运算时只对点后面的第一个非终结符求了闭包，忘了新加入的项目还可能继续触发闭包。

解决：闭包运算要用循环直到集合不再变化，代码里用changed标志控制。手算时每加入一个新项目，都要检查它的点后面是不是非终结符。

5.4 坑四：四元式临时变量编号重复

现象：两个不同的中间结果用了同一个临时变量名，导致语义错误。

原因：手算时临时变量编号没有全局计数器，写到后面忘了前面用到几。

解决：在草稿纸角落维护一个计数器，每生成一个新临时变量就加一。代码里用temp_count列表做可变计数器。

5.5 坑五：回填时跳转目标算错

现象：回填后的四元式跳转目标差一条，程序执行流不对。

原因：四元式编号从0还是从1开始没统一，或者回填时忘了目标指令本身的编号。

解决：统一编号规则，建议从0开始。回填前先列出所有四元式的编号和内容，确认目标编号后再填。代码里backpatch的目标参数要仔细核对。

6. 从试题解答到考场实战：一套可复用的检查清单

考场上时间紧，不可能每道题都从头推导。我的习惯是：拿到卷子先花两分钟扫一遍，把题目分成三类——模板题（NFA转DFA、FIRST/FOLLOW、LL(1)表）、推导题（LR项目集、回填）、综合题（语法制导翻译+四元式）。模板题必须拿满分，推导题尽量拿步骤分，综合题能写多少写多少。

下面这张检查清单是我考前会默写一遍的，你可以直接拿去用：

最后说一个我自己的教训：有一次考试，NFA转DFA的题我用了半小时手算，结果终态标错，后面最小化全崩。后来我学乖了，每算完一步就花30秒验证——DFA的转移表每个状态对每个输入符号都要有定义（除非是死状态），终态集合要跟原NFA对照。这30秒能救回后面几十分。希望帮到你。

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