简介这份资源是吉林大学《编译原理》课程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[i1:] 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和FOLLOWLL(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和符号Xmove(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四元式序列是(*, c, d, t1)(, b, t1, t2)(, 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 ft{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 fid{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的假出口回填到idx22因为idx21是then分支的第一条指令idx22才是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求ε闭包→move→再闭包漏第二次闭包DFA最小化初始分区终态/非终态混在一起分FIRST集看右部第一个符号能推ε继续看漏ε传递FOLLOW集开始符号放$右部后面符号的FIRST漏FOLLOW左部LL(1)表FIRST填非εFOLLOW填ε冲突没发现LR(0)闭包点后非终结符加产生式闭包不彻底四元式临时变量全局编号编号重复回填先列编号再填目标目标差一条最后说一个我自己的教训有一次考试NFA转DFA的题我用了半小时手算结果终态标错后面最小化全崩。后来我学乖了每算完一步就花30秒验证——DFA的转移表每个状态对每个输入符号都要有定义除非是死状态终态集合要跟原NFA对照。这30秒能救回后面几十分。希望帮到你。本文还有配套的精品资源点击获取