简介本资源为北京交通大学2021—2022学年第二学期《编译原理》期末试卷A卷PDF文档面向计算机专业本科生及考研复习者用于检验和巩固编译原理核心知识。试卷覆盖文法分析、正则表达式与有限自动机、消除左递归与回溯、算符优先文法、LR(0)与SLR(1)分析、语法制导翻译及四元式序列优化等模块题型包含语言求解、状态转换图构造、FIRSTVT/LASTVT集合计算、分析表构造、拉链-回填与DAG重构等能帮助读者系统梳理编译器前端到优化的完整流程。资源包共1个PDF文件大小约396KB内容为原版试题便于打印练习与对照复习。目前已有355人学习下载适合需要真题演练、查漏补缺或备考冲刺的学习者使用。1. 一份期末试卷能教你的远不止考试重点北京交通大学2021-2022学年第二学期《编译原理》期末试卷(A卷)这份PDF在期末季被反复检索很多人第一反应是找答案、对题型、押考点。但如果你正在学编译原理或者准备做编译原理实验、啃清华大学出版社第三版第二章答案这份卷子的价值其实在另一个方向它是一张被压缩过的知识地图告诉你这门课到底在考什么、哪些环节是真正的硬骨头、哪些地方一考就翻车。编译原理这门课很多人学完的感觉是“每个字都认识连起来不知道在说什么”。词法分析、语法分析、语义分析、中间代码、优化、目标代码生成六大阶段听起来清清楚楚一到做题就发现正则表达式转NFA再转DFA手写递归下降算FIRST集和FOLLOW集画LR分析表每一样都能让人卡住。这份试卷能帮你把这些环节串起来看清考试和实验之间的对应关系也能让你在做编译原理实验时少走弯路。这篇文章不打算给你一份“试卷答案回忆版”而是顺着这份卷子涉及的知识点把编译原理从理论到动手的路径拆开讲。适合正在学这门课、准备期末、或者想用Java写一个简单编译器练手的人。如果你只是想知道考了什么题那可能帮不到你但如果你想真正搞懂这些题背后的机制并且能自己动手复现一遍那往下看。2. 从试卷题型反推编译原理到底在考哪几层能力2.1 期末卷子的典型结构六类题对应六个知识块北京交通大学这份A卷从常见题型分布来看基本覆盖了编译原理课程的核心模块。虽然我手里没有原卷的逐题内容但根据同类院校的命题规律和这份卷子的标题信息可以合理推断它包含以下几类题目第一类是概念辨析与简答比如“编译程序和解释程序的区别”“词法分析和语法分析的分工”。这类题看似送分实际上是在检验你有没有建立阶段划分的思维框架。第二类是正则表达式与有限自动机通常要求你写出某个语言的正则定义然后构造NFA、确定化为DFA、最小化。第三类是文法与语法分析包括消除左递归、提取左公因子、求FIRST和FOLLOW集、判断LL(1)文法。第四类是LR分析要求构造LR(0)或SLR(1)项目集规范族填分析表。第五类是语义分析与中间代码可能涉及语法制导翻译、三地址码生成。第六类是优化与目标代码比如基本块划分、流图构造、常见优化技术。这六类题不是孤立的它们对应的是编译器流水线上的不同工位。你在卷子上做一道“正则转DFA”的题实际上是在模拟词法分析器的核心算法你做一道“构造SLR分析表”的题实际上是在走语法分析器的自动生成流程。理解这一点比死记硬背题型重要得多。2.2 词法分析正则表达式到DFA的手工推演词法分析是编译器的第一道关口任务是把字符流切分成有意义的单词符号。试卷里常见的考法是给定一个语言描述要求写出正则表达式然后构造NFA再确定化为DFA最后最小化。这个过程在龙书和清华版教材里都有详细步骤但手工做起来容易出错。我一般会按这个顺序推进先用自然语言把单词模式说清楚比如“标识符是以字母开头、后跟字母或数字的串”然后写正则表达式letter (letter | digit)*接着用Thompson构造法把正则转成NFA再用子集构造法做确定化最后用Hopcroft算法或填表法最小化。每一步都有明确的规则但手工画图时最容易在ε闭包和状态编号上翻车。下面用Python演示一个最小化的DFA模拟帮你验证手工结果# 一个简单的DFA模拟器用于验证标识符识别 # 状态0初始状态状态1已读入至少一个字母状态2死状态 dfa_transitions { (0, letter): 1, (0, digit): 2, (1, letter): 1, (1, digit): 1, (1, other): 2, (2, letter): 2, (2, digit): 2, (2, other): 2, } def classify_char(ch): if ch.isalpha(): return letter elif ch.isdigit(): return digit else: return other def run_dfa(input_string): state 0 for ch in input_string: category classify_char(ch) state dfa_transitions.get((state, category), 2) if state 2: return False # 进入死状态不是合法标识符 return state 1 # 必须以字母开头且至少一个字母 # 测试 test_cases [abc, a1b2, 1abc, abc!, ] for s in test_cases: print(f{s!r} - {run_dfa(s)})这段代码的逻辑很直接状态0是起点读到字母进入状态1读到数字进入死状态2状态1下继续读字母或数字都留在状态1读到其他字符进入死状态。参数说明dfa_transitions是状态转移表键是当前状态字符类别值是下一状态classify_char把字符映射到类别run_dfa逐字符驱动状态机。运行结果会告诉你哪些串被接受。手工做题时你可以用这个思路反向检查自己的DFA是否漏了转移或多了状态。注意考试时最小化DFA要求你写出划分过程不能只给最终状态图。划分的依据是“是否接受状态”和“转移目标是否在同一组”这两条要写清楚。2.3 语法分析FIRST/FOLLOW集与LL(1)判定的手算流程语法分析是编译原理里最容易拉开差距的部分。LL(1)文法的判定需要算FIRST集、FOLLOW集和SELECT集然后检查同一非终结符的各产生式SELECT集是否不相交。这个过程步骤固定但手工算容易漏掉ε产生式的影响。我通常按这个流程走第一步把文法写成产生式集合标记出终结符和非终结符第二步对每个符号求FIRST集遇到ε要特别处理第三步对每个非终结符求FOLLOW集起始符号的FOLLOW集包含结束符第四步对每条产生式求SELECT集第五步检查冲突。下面用Python实现一个FIRST/FOLLOW计算器你可以直接套用到试卷题目上# 计算FIRST集和FOLLOW集的简化实现 # 文法示例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]] } non_terminals set(grammar.keys()) terminals {, *, (, ), id, $} start_symbol E def first_of_sequence(seq, first_sets): 计算一个符号串的FIRST集 result set() for sym in seq: if sym in terminals: result.add(sym) return result else: 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: before len(first_sets[nt]) first_sets[nt] | first_of_sequence(prod, first_sets) if len(first_sets[nt]) ! before: 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 in non_terminals: rest prod[i1:] first_rest first_of_sequence(rest, first_sets) if rest else {ε} before len(follow_sets[sym]) follow_sets[sym] | (first_rest - {ε}) if ε in first_rest or not rest: follow_sets[sym] | follow_sets[nt] if len(follow_sets[sym]) ! before: changed True print(FIRST sets:) for nt in sorted(non_terminals): print(f FIRST({nt}) {first_sets[nt]}) print(FOLLOW sets:) for nt in sorted(non_terminals): print(f FOLLOW({nt}) {follow_sets[nt]})这段代码的核心是迭代到不动点。first_of_sequence处理符号串的FIRST集遇到终结符直接加入并返回遇到非终结符先加入其FIRST集去掉ε的部分如果该非终结符不能推出ε就停止否则继续看下一个符号。FOLLOW集的计算依赖FIRST集对每条产生式扫描每个非终结符看它后面跟着的符号串的FIRST集如果后面能推出ε或者为空就把左部非终结符的FOLLOW集加进来。参数说明grammar是文法字典键是非终结符值是产生式列表每个产生式是符号列表terminals包含所有终结符和结束符$。运行后对照试卷题目检查你的手算结果是否一致。提示SELECT集等于FIRST(α)减去ε如果α能推出ε还要加上FOLLOW(A)。判定LL(1)时同一非终结符的不同产生式SELECT集不能有交集。3. LR分析表构造从项目集到分析表的完整走一遍3.1 LR(0)项目集规范族的构造逻辑LR分析是自底向上语法分析的核心也是试卷里分值高、容易丢分的部分。构造LR(0)项目集规范族本质上是在追踪“当前可能匹配到产生式的哪个位置”。一个项目就是产生式加一个点点表示已经识别了多少。比如产生式E - E T项目E - E · T表示已经识别了左部的E期待看到加号。构造过程从增广文法开始先加一条S - S然后求闭包、求转移。闭包操作是如果项目A - α · B β中的点后面是非终结符B就把B的所有产生式加进来点在最左边。转移操作是对某个项目集看所有点后面的符号对每个符号求GOTO即把点移过该符号后求闭包。重复直到没有新项目集产生。手工做的时候最容易出错的地方是闭包求不全或者GOTO时漏了项目。我一般会先把所有产生式编号然后画一个表格行是项目集编号列是各个符号的GOTO目标这样不容易乱。下面用Python演示一个LR(0)项目集构造的骨架# LR(0)项目集规范族构造的简化演示 # 文法S - E; E - E T | T; T - T * F | F; F - ( E ) | id grammar { S: [[E]], E: [[E, , T], [T]], T: [[T, *, F], [F]], F: [[(, E, )], [id]] } non_terminals set(grammar.keys()) terminals {, *, (, ), id, $} def closure(items): 求项目集的闭包item是(产生式左部, 产生式右部元组, 点的位置) result set(items) changed True while changed: changed False for lhs, rhs, dot in list(result): if dot len(rhs) and rhs[dot] in non_terminals: for prod in grammar[rhs[dot]]: new_item (rhs[dot], tuple(prod), 0) if new_item not in result: result.add(new_item) changed True return frozenset(result) def goto(items, symbol): 求GOTO函数 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(moved) # 初始项目集 start_item (S, (E,), 0) I0 closure({start_item}) states [I0] transitions {} queue [I0] while queue: current queue.pop(0) for sym in terminals | non_terminals: target goto(current, sym) if target and target not in states: states.append(target) queue.append(target) if target: transitions[(states.index(current), sym)] states.index(target) print(f共构造 {len(states)} 个项目集) for i, state in enumerate(states): print(fI{i}:) for item in sorted(state): lhs, rhs, dot item rhs_str .join(rhs[:dot]) · .join(rhs[dot:]) print(f {lhs} - {rhs_str})这段代码的逻辑是closure不断把点后面是非终结符的项目展开直到不再新增goto把点移过指定符号后求闭包主循环用队列遍历所有可达项目集记录状态编号和转移。参数说明grammar是增广后的文法start_item是增广产生式的初始项目。运行后你会得到所有项目集和它们之间的转移关系这就是画DFA和填分析表的基础。3.2 SLR(1)分析表的填写与冲突处理有了LR(0)项目集规范族接下来就是填ACTION表和GOTO表。SLR(1)在LR(0)的基础上用FOLLOW集来解决归约-归约冲突和移进-归约冲突。具体规则是如果项目A - α ·在状态I中且a在FOLLOW(A)中那么ACTION[I, a]填归约A - α如果项目A - α · a β在状态I中且a是终结符那么ACTION[I, a]填移进到GOTO(I, a)如果项目S - S ·在状态I中ACTION[I, $]填接受。冲突处理是考试的重点。移进-归约冲突时SLR(1)看移进符号是否在归约项目的FOLLOW集中如果在就冲突不在就按移进处理。归约-归约冲突时看两个归约项目的FOLLOW集是否有交集有交集就冲突。如果SLR(1)解决不了就要用LR(1)或LALR(1)。下面用表格展示一个SLR(1)分析表的片段方便你对照状态id*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5表中s表示移进并转到对应状态r表示按第几条产生式归约acc表示接受。这个表是SLR(1)分析表的典型形式你可以用它来模拟分析过程。比如输入串id id * id从状态0开始读到id移进到状态5然后按F-id归约到状态3再按T-F归约到状态2再按E-T归约到状态1读到移进到状态6继续处理后面的部分。每一步都查表直到接受或报错。注意填表时归约项目的FOLLOW集一定要算对否则会把不该归约的符号填成归约导致分析表冲突或分析错误。这是血泪经验很多人在这里翻车。4. 语义分析与中间代码从语法树到三地址码4.1 语法制导翻译的基本框架语义分析阶段编译器要检查程序的意义是否合法并生成中间表示。试卷里常见的考法是给一个简单的赋值语句或表达式文法要求写出语法制导定义然后给出对应的三地址码。语法制导翻译的核心思想是为每个产生式关联语义规则在语法分析过程中计算属性值。属性分两种综合属性从子节点传到父节点继承属性从父节点或兄弟节点传到子节点。对于表达式求值通常用综合属性就够了。比如产生式E - E1 T语义规则可以是E.code E1.code || T.code || gen(, E1.place, T.place, E.place)其中||表示代码拼接gen生成一条三地址指令。我一般会先画出语法树然后自底向上计算每个节点的place和code。place表示存放结果的临时变量或变量名code是生成的指令序列。下面用Python演示一个简单的三地址码生成器# 简单表达式的三地址码生成 # 文法E - E T | T; T - T * F | F; F - ( E ) | id class TACGenerator: def __init__(self): self.temp_count 0 self.code [] def new_temp(self): self.temp_count 1 return ft{self.temp_count} def gen(self, op, arg1, arg2None): result self.new_temp() if arg2: self.code.append(f{result} {arg1} {op} {arg2}) else: self.code.append(f{result} {op} {arg1}) return result # 模拟解析过程这里直接按表达式树后序遍历 def generate_tac(node, gen): node是元组(操作符, 左子节点, 右子节点) 或 标识符 if isinstance(node, str): return node # 标识符直接返回名字 op, left, right node left_place generate_tac(left, gen) right_place generate_tac(right, gen) return gen.gen(op, left_place, right_place) # 测试表达式a b * c expr_tree (, a, (*, b, c)) gen TACGenerator() result generate_tac(expr_tree, gen) print(三地址码) for line in gen.code: print(f {line}) print(f最终结果存放在{result})这段代码的逻辑是对表达式树做后序遍历先处理左右子树得到它们的place然后为当前操作生成一条三地址指令并返回新的临时变量。参数说明TACGenerator维护临时变量计数器和代码列表gen方法根据操作符和参数生成指令generate_tac递归处理树节点。运行结果会输出t1 b * c和t2 a t1最终结果在t2中。考试时你需要根据语法制导定义写出类似的语义规则并手动模拟生成过程。4.2 控制流语句的翻译与回填技术除了表达式试卷还可能考控制流语句的翻译比如if-else和while。这类语句的翻译难点在于跳转指令的目标地址在生成时还不确定需要用回填技术。基本思路是先生成跳转指令但目标地址留空把这些指令放入一个列表等到目标地址确定后再回填到指令中。以if E then S1 else S2为例翻译过程是生成E的代码E的结果放在临时变量中生成条件跳转指令如果E为假跳到S2的开始生成S1的代码生成无条件跳转指令跳到整个if语句的结束确定S2的开始地址回填前面的条件跳转生成S2的代码确定结束地址回填无条件跳转。回填技术的关键是维护两个列表truelist和falselist分别记录需要回填为真出口和假出口的跳转指令。在语法分析过程中这些列表随着归约操作合并和传递。考试时通常会要求你写出布尔表达式的翻译方案并给出回填后的代码序列。提示回填的顺序很重要先确定哪个地址就先回填哪个列表。如果顺序搞反跳转目标会指向错误的指令。这是编译原理实验里最常见的bug之一。5. 避坑与排查编译原理学习和实验中的五个典型翻车现场5.1 正则转DFA时ε闭包漏状态现象手工构造的DFA在模拟时某些应该接受的串被拒绝或者应该拒绝的串被接受。原因在子集构造法中ε闭包没有求完整漏掉了通过ε转移可达的状态。解决每次求闭包时反复扫描直到没有新状态加入可以用一个栈来管理待处理状态确保每个状态都被展开。检查时把每个项目集的状态编号列出来对照NFA的ε转移逐条验证。5.2 FIRST/FOLLOW集计算时忽略ε产生式现象LL(1)判定时SELECT集算错导致明明无冲突的文法被判为有冲突或者有冲突的漏判。原因FIRST集计算时遇到非终结符能推出ε的情况没有继续看后面的符号FOLLOW集计算时没有把左部的FOLLOW集传给右部末尾的非终结符。解决严格按照定义迭代到不动点每次更新后检查是否有变化对于含ε的产生式单独标记并特殊处理。可以用前面给的Python代码交叉验证手算结果。5.3 LR分析表填错归约项目的FOLLOW集现象SLR(1)分析表在某个状态对某个输入符号填了归约但实际分析时应该移进导致分析动作冲突或错误归约。原因归约项目的FOLLOW集算错把不该归约的符号包含了进来。解决重新计算FOLLOW集特别注意起始符号的FOLLOW集包含结束符$对于每个归约项目只在其左部非终结符的FOLLOW集对应的列填归约。填完后用几个典型输入串模拟一遍看是否有冲突。5.4 三地址码生成时临时变量命名冲突现象生成的中间代码中两个不同的临时变量用了同一个名字导致后续优化或目标代码生成时结果错误。原因临时变量计数器没有正确递增或者在递归生成时作用域混乱。解决用一个全局计数器每次生成新临时变量时递增确保递归调用中传递的是同一个生成器实例。如果用手写方式给临时变量加前缀区分不同表达式层级。5.5 回填时跳转目标地址错位现象控制流语句翻译后跳转指令的目标地址指向了错误的指令程序执行流程混乱。原因回填列表合并时顺序错误或者目标地址确定后没有及时回填所有相关指令。解决维护清晰的回填列表每次确定一个地址就立即回填对应的列表在合并列表时保持顺序一致。调试时把生成的代码打印出来逐条检查跳转目标是否指向正确的标号。6. 用Java写一个微型编译器把试卷知识点串成可运行代码如果你已经看完了前面的理论部分现在想动手验证一遍我建议用Java写一个微型编译器处理简单的算术表达式和赋值语句。这个练习能把词法分析、语法分析、语义分析和中间代码生成串起来比单独做每道题更有收获。先定义词法分析器。输入是字符串输出是Token序列。Token类型包括标识符、数字、运算符、括号和结束符。用有限自动机的手写方式实现每个字符读入后根据当前状态决定下一步。核心代码如下// 简化的词法分析器 import java.util.*; public class Lexer { private String input; private int pos 0; private ListToken tokens new ArrayList(); public Lexer(String input) { this.input input; } public ListToken tokenize() { while (pos input.length()) { char ch input.charAt(pos); if (Character.isWhitespace(ch)) { pos; } else if (Character.isLetter(ch)) { StringBuilder sb new StringBuilder(); while (pos input.length() (Character.isLetterOrDigit(input.charAt(pos)))) { sb.append(input.charAt(pos)); } tokens.add(new Token(TokenType.ID, sb.toString())); } else if (Character.isDigit(ch)) { StringBuilder sb new StringBuilder(); while (pos input.length() Character.isDigit(input.charAt(pos))) { sb.append(input.charAt(pos)); } tokens.add(new Token(TokenType.NUM, sb.toString())); } else { switch (ch) { case : tokens.add(new Token(TokenType.PLUS, )); break; case *: tokens.add(new Token(TokenType.MUL, *)); break; case (: tokens.add(new Token(TokenType.LPAREN, ()); break; case ): tokens.add(new Token(TokenType.RPAREN, ))); break; case : tokens.add(new Token(TokenType.ASSIGN, )); break; default: throw new RuntimeException(非法字符: ch); } pos; } } tokens.add(new Token(TokenType.EOF, $)); return tokens; } }这段代码的逻辑是逐字符扫描遇到空白跳过遇到字母开始收集标识符遇到数字收集数字遇到运算符生成对应Token。参数说明input是源字符串pos是当前扫描位置tokens是结果列表。Token类需要定义类型枚举和值。这个词法分析器对应试卷里正则转DFA的知识点只是用代码实现了状态转移。接下来是语法分析器用递归下降法处理表达式。文法可以写成E - T EE - T E | εT - F TT - * F T | εF - ( E ) | id | num。每个非终结符对应一个方法方法内部根据当前Token决定走哪条产生式。递归下降的优点是直观缺点是遇到左递归要改写文法。代码如下// 递归下降语法分析器同时生成三地址码 public class Parser { private ListToken tokens; private int pos 0; private int tempCount 0; private ListString code new ArrayList(); public Parser(ListToken tokens) { this.tokens tokens; } private Token peek() { return tokens.get(pos); } private Token consume() { return tokens.get(pos); } private String newTemp() { return t (tempCount); } public String parseE() { String place parseT(); while (peek().type TokenType.PLUS) { consume(); String right parseT(); String temp newTemp(); code.add(temp place right); place temp; } return place; } private String parseT() { String place parseF(); while (peek().type TokenType.MUL) { consume(); String right parseF(); String temp newTemp(); code.add(temp place * right); place temp; } return place; } private String parseF() { Token t peek(); if (t.type TokenType.LPAREN) { consume(); String place parseE(); if (peek().type ! TokenType.RPAREN) { throw new RuntimeException(缺少右括号); } consume(); return place; } else if (t.type TokenType.ID || t.type TokenType.NUM) { consume(); return t.value; } else { throw new RuntimeException(意外的Token: t.value); } } public ListString getCode() { return code; } }这段代码的逻辑是parseE处理加减parseT处理乘除parseF处理括号和原子。每遇到一个运算符就生成一条三地址指令用临时变量保存结果。参数说明tokens是词法分析器的输出pos是当前Token位置tempCount是临时变量计数器code是生成的指令列表。这个语法分析器对应试卷里LL(1)文法和递归下降的知识点同时完成了语义分析和中间代码生成。把词法分析器和语法分析器串起来主程序如下public class MiniCompiler { public static void main(String[] args) { String source a b * (c d); Lexer lexer new Lexer(source); ListToken tokens lexer.tokenize(); Parser parser new Parser(tokens); String result parser.parseE(); System.out.println(三地址码); for (String line : parser.getCode()) { System.out.println( line); } System.out.println(最终结果 result); } }运行这个程序输入a b * (c d)你会得到类似t1 c d、t2 b * t1、t3 a t2的输出。这个过程完整复现了从源程序到中间代码的编译流程也把试卷里的词法、语法、语义知识点串了起来。我自己的习惯是每学完一个编译阶段就用Java写一个最小实现哪怕只能处理最简单的文法。写多了你会发现那些考试题不再是抽象符号而是代码里一个个具体的状态转移和递归调用。编译原理实验里常见的坑比如ε闭包漏状态、FOLLOW集算错、回填地址错位在动手写一遍之后都会变得具体。希望帮到你。本文还有配套的精品资源点击获取