简介这份哈工大编译原理习题及答案汇总面向正在学习编译原理课程的高校学生与考研备考者用于课后练习自测与期末、复试阶段的系统复习。资源以PDF形式呈现压缩包内共1个文件整体约1.6MB轻量便于随时查阅。内容围绕源程序、目标程序、翻译程序、编译程序与解释程序的概念辨析展开并梳理编译系统各组成部分及其功能涵盖词法分析、语法分析、语义分析、中间代码生成、代码优化与目标代码生成等环节。习题部分还涉及程序设计语言关键字、括号与逗号的用途高级语言程序的编译运行过程以及前后文无关文法、推导与语法树、二义性判定、文法化简与无用产生式消去等典型题目并配有对应解答。目前已有1743人学习适合作为课堂同步练习与考前查漏补缺的参考材料。1. 编译原理习题册怎么用才不白刷从一道DFA最小化题说起很多人拿到一份编译原理习题汇总第一反应是“刷完它”。但真实情况是编译原理这门课的习题和数据结构、算法题完全不是一个物种——它的每一道题背后都压着一整套形式化系统你刷题的方式决定了你是真的在学编译原理还是只是在背答案。我见过太多人把DFA最小化、LL(1)分析表构造、LR项目集规范族这些题反复做考试一过全忘光等到真正要写词法分析器或者排查语法分析器的冲突时脑子里只剩一个模糊的“好像做过”。这份习题汇总的价值不在于题量而在于它覆盖了从词法分析到语义分析、从正则表达式到语法制导翻译的完整链路。适合两类人一类是在校学生正在上编译原理课需要把课堂上的形式化定义转化成可动手推导的步骤另一类是想自己写解释器或DSL的工程师需要把编译前端的基础打扎实。如果你属于后者这份习题册其实是一份被低估的“最小可行知识清单”——它逼你手算的那些东西恰恰是你在用ANTLR、LLVM或者手写递归下降时绕不开的底层逻辑。我自己的习惯是每做一道题先不看答案用纸笔把推导过程写完整然后对照答案找差异。差异往往不在结果而在中间步骤的某个假设——比如在构造LR(1)项目集时向前看符号的传播规则搞错了或者在做语法制导翻译时继承属性和综合属性的求值顺序弄反了。这些细节才是真正长本事的地方。2. 从正则到DFA手算一遍比看十遍书管用2.1 为什么词法分析题值得你花时间手推词法分析是编译原理里最“接地气”的部分因为它直接对应你写代码时用的正则表达式。但习题里的正则到DFA的转换和你在Python里写re.match是两回事——前者要求你理解Thompson构造法、子集构造法和DFA最小化的完整链条。这个链条的每一步都有明确的算法但每一步也都有容易翻车的地方。我一般会建议按这个顺序做习题先做正则表达式到NFA的Thompson构造再做NFA到DFA的子集构造最后做DFA最小化。这三步走完你对“正则语言”这个概念的理解会从“知道”变成“能算”。而且这个顺序有个好处每一步的输出是下一步的输入你可以用前一步的结果验证后一步的正确性。2.2 用Python验证你的手算结果手算容易出错尤其是子集构造法里状态集合的闭包计算。我习惯用一段小脚本验证自己的答案。下面这段代码实现了从NFA到DFA的子集构造你可以把习题里的NFA定义成字典传进去看看输出的DFA状态集合和你手算的是否一致。# NFA到DFA的子集构造 # 状态转移表格式{状态: {输入符号: [目标状态列表]}} # epsilon用表示 def epsilon_closure(states, nfa): 计算状态集合的epsilon闭包 stack list(states) closure set(states) while stack: s stack.pop() for next_s in nfa.get(s, {}).get(, []): if next_s not in closure: closure.add(next_s) stack.append(next_s) return frozenset(closure) def subset_construction(nfa, start, alphabet): 子集构造法NFA - DFA start_closure epsilon_closure({start}, nfa) dfa_states {start_closure: 0} # DFA状态 - 编号 queue [start_closure] transitions {} # (dfa_state, symbol) - dfa_state while queue: current queue.pop(0) for symbol in alphabet: # 计算move(current, symbol) move_result set() for s in current: for next_s in nfa.get(s, {}).get(symbol, []): move_result.add(next_s) if not move_result: continue # 计算epsilon闭包 next_closure epsilon_closure(move_result, nfa) if next_closure not in dfa_states: dfa_states[next_closure] len(dfa_states) queue.append(next_closure) transitions[(dfa_states[current], symbol)] dfa_states[next_closure] return dfa_states, transitions # 示例习题中常见的NFA nfa { q0: {a: [q0, q1], b: [q0]}, q1: {a: [q2], b: [q2]}, q2: {a: [q3], b: [q3]}, q3: {} } alphabet [a, b] dfa_states, transitions subset_construction(nfa, q0, alphabet) print(DFA状态数:, len(dfa_states)) for (src, sym), dst in sorted(transitions.items()): print(f {src} --{sym}-- {dst})这段代码的关键在于epsilon_closure函数——它用栈来避免递归深度问题同时保证闭包计算的正确性。subset_construction里用frozenset作为DFA状态的键因为集合本身不可哈希而frozenset可以。参数alphabet需要你根据习题里的字母表手动传入通常是[a, b]或者[0, 1]。跑完这段代码你会得到DFA的状态数和转移表。把它和你手算的结果对比如果状态数不一致大概率是某个状态的epsilon闭包漏算了或者move操作的目标状态集合搞错了。这种“手算脚本验证”的方式比单纯对答案有效得多因为你能定位到具体是哪一步出了问题。2.3 DFA最小化的三个必调参数DFA最小化是词法分析习题里最容易“看起来会了但一做就错”的部分。Hopcroft算法或者填表法都可以但不管用哪种方法有三个地方必须盯紧第一初始划分。终态和非终态必须分开这是最小化的起点。但习题里经常有“陷阱状态”——那些无法到达终态的中间状态它们可能被误分到非终态组里。我一般会先做一次可达性分析把不可达状态直接删掉再做划分。第二等价类的合并条件。两个状态等价当且仅当对于所有输入符号它们都转移到同一个等价类。这里容易翻车的地方是只检查了部分输入符号就下结论。习题里经常只给两个输入符号但如果你自己扩展了字母表就要检查全部。第三最小化后的状态命名。很多习题答案用A、B、C重新命名但你的手算结果可能用原状态名。对比时不要被命名迷惑看的是划分本身是否一致。提示DFA最小化后如果状态数比预期多一个先检查是不是把“死状态”单独成组了。死状态是指那些对所有输入都转移到自身的非终态它在最小化时通常可以和其他非终态合并但有些教材要求保留。3. 语法分析习题的动手路线LL(1)和LR你该先做哪个3.1 LL(1)分析表构造FIRST集和FOLLOW集的联动LL(1)是语法分析里最适合入门的部分因为它的分析表构造有明确的算法而且不需要理解“项目集”这种抽象概念。但习题里最常见的错误是FIRST集和FOLLOW集算错导致分析表里出现多重入口。我一般会按这个流程做LL(1)习题先消除左递归和提取左公因子然后计算FIRST集再计算FOLLOW集最后填分析表。这个顺序不能乱因为FOLLOW集的计算依赖FIRST集而分析表的填充依赖两者。计算FIRST集时关键规则是如果X是一个非终结符且X - Y1Y2...Yk那么FIRST(Y1)中的终结符加入FIRST(X)如果Y1能推导出空串则FIRST(Y2)也加入以此类推。习题里经常有“Y1能推导出空串”的情况被忽略导致FIRST集少算。计算FOLLOW集时关键规则是对于产生式A - αBβFIRST(β)中的终结符加入FOLLOW(B)如果β能推导出空串则FOLLOW(A)加入FOLLOW(B)。这里容易翻车的是“β能推导出空串”的判断——它需要递归地看β的每个符号是否都能推导出空串。3.2 用代码块验证FIRST集和FOLLOW集下面这段Python代码实现了FIRST集和FOLLOW集的计算你可以把习题里的文法定义成字典传进去验证自己的手算结果。# 计算FIRST集和FOLLOW集 # 文法格式{非终结符: [产生式右部列表]} # 产生式右部用空格分隔的符号串表示空串用ε表示 def compute_first(grammar, terminals): 计算所有非终结符的FIRST集 first {nt: set() for nt in grammar} # 终结符的FIRST集是它自己 for t in terminals: first[t] {t} changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: symbols prod.split() if symbols [ε]: if ε not in first[nt]: first[nt].add(ε) changed True continue # 遍历产生式右部 all_nullable True for sym in symbols: if sym not in first: first[sym] {sym} # 把FIRST(sym)中非ε的符号加入FIRST(nt) for f in first[sym] - {ε}: if f not in first[nt]: first[nt].add(f) changed True # 如果sym不能推导出ε停止 if ε not in first[sym]: all_nullable False break if all_nullable: if ε not in first[nt]: first[nt].add(ε) changed True return first def compute_follow(grammar, first, start_symbol): 计算所有非终结符的FOLLOW集 follow {nt: set() for nt in grammar} follow[start_symbol].add($) # 结束符 changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: symbols prod.split() for i, sym in enumerate(symbols): if sym not in grammar: continue # 计算FIRST(β)其中β是sym后面的符号串 rest symbols[i1:] if not rest: # 如果sym在末尾FOLLOW(nt)加入FOLLOW(sym) for f in follow[nt]: if f not in follow[sym]: follow[sym].add(f) changed True else: all_nullable True for r in rest: if r not in first: first[r] {r} for f in first[r] - {ε}: if f not in follow[sym]: follow[sym].add(f) changed True if ε not in first[r]: all_nullable False break if all_nullable: for f in follow[nt]: if f not in follow[sym]: follow[sym].add(f) changed True return follow # 示例文法消除左递归后的表达式文法 grammar { E: [T E\], E\: [ T E\, ε], T: [F T\], T\: [* F T\, ε], F: [( E ), id] } terminals {, *, (, ), id} first compute_first(grammar, terminals) follow compute_follow(grammar, first, E) print(FIRST集:) for nt in grammar: print(f FIRST({nt}) {first[nt]}) print(FOLLOW集:) for nt in grammar: print(f FOLLOW({nt}) {follow[nt]})这段代码的核心逻辑在compute_first的while changed循环——它反复扫描所有产生式直到FIRST集不再变化。这种迭代法比递归法更容易调试因为你可以打印每一轮的变化。compute_follow里对rest的处理是关键如果rest为空说明sym在产生式末尾直接把FOLLOW(nt)加入FOLLOW(sym)如果rest不为空则计算FIRST(rest)如果rest能推导出空串还要把FOLLOW(nt)加入。参数start_symbol通常是文法的开始符号比如E。terminals集合需要你根据习题里的终结符手动传入。跑完这段代码把输出的FIRST集和FOLLOW集和你手算的对比如果某个非终结符的FOLLOW集少了$检查开始符号是否设置正确。3.3 LR项目集规范族闭包和GOTO的边界条件LR分析是语法分析里最难的部分但也是习题里最能拉开差距的部分。LR(0)、SLR(1)、LR(1)、LALR(1)层层递进每一层都有新的约束条件。我一般会建议先做LR(0)的项目集规范族再做SLR(1)的分析表最后做LR(1)和LALR(1)。构造LR(0)项目集规范族时闭包操作和GOTO操作是两个核心。闭包操作的规则是如果项目A - α·Bβ在闭包中且B - γ是产生式则B - ·γ加入闭包。这个规则要反复应用直到闭包不再变化。GOTO操作的规则是对于项目集I和符号XGOTO(I, X)是I中所有形如A - α·Xβ的项目对应的A - αX·β的闭包。习题里最容易翻车的地方是闭包操作时漏掉了新加入项目的闭包扩展。比如先加入了B - ·γ但忘了对γ中的非终结符继续做闭包。这种错误会导致项目集规范族的状态数偏少后续分析表构造时出现冲突。注意LR(1)项目比LR(0)项目多了一个向前看符号闭包操作时向前看符号的传播规则更复杂。如果习题要求构造LR(1)项目集规范族建议先用LR(0)练手确认闭包和GOTO的逻辑没问题再处理向前看符号。4. 语法制导翻译和中间代码生成习题里最容易被跳过的那部分4.1 为什么语义分析题不能只对答案语法制导翻译SDT和中间代码生成是编译原理习题里最“软”的部分——它不像DFA最小化那样有唯一正确答案也不像LL(1)分析表那样有明确的算法。很多习题的答案只给了一个翻译方案但实际实现时可能有多种等价写法。这就导致很多人做这部分题时只要结果和答案“看起来差不多”就过了但实际上对继承属性、综合属性的求值顺序、以及翻译方案和语法分析器的配合方式并没有真正理解。我自己的经验是做SDT习题时不要只看答案的翻译方案要自己画一遍注释分析树标出每个属性的求值顺序。如果某个属性的求值依赖另一个属性但它们在树上的位置不允许这种依赖那就是翻译方案设计错了。这种“画树验证”的方法比单纯对答案有效得多。4.2 用表格拆解一个语法制导翻译习题下面用一个常见的表达式求值SDT习题来演示怎么拆解。假设文法如下产生式语义规则E - E1 TE.val E1.val T.valE - TE.val T.valT - T1 * FT.val T1.val * F.valT - FT.val F.valF - ( E )F.val E.valF - idF.val id.lexval这个SDT是S属性定义只有综合属性所以可以在自底向上的语法分析过程中直接求值。但习题里经常把它改造成L属性定义加入继承属性比如让E携带一个累加值。这时候求值顺序就变得关键了。我一般会按这个步骤做先确定每个属性的类型综合还是继承再确定求值顺序自底向上还是自顶向下最后检查翻译方案是否和语法分析方法兼容。如果习题要求用递归下降法实现那么继承属性可以作为参数传递综合属性作为返回值如果要求用LR分析器实现那么继承属性需要放在栈里求值时机要仔细设计。4.3 中间代码生成的三种常见形式中间代码生成习题通常要求把表达式或语句翻译成三地址码、四元式或者抽象语法树。这三种形式各有用途三地址码适合做优化四元式适合做代码生成AST适合做语义检查。做这类习题时我习惯先写出AST再把AST转成三地址码。这样做的原因是AST的结构最直观不容易出错而从AST到三地址码的转换有固定的模式比如每个二元操作生成一个临时变量。习题里经常有“把while循环翻译成三地址码”的题如果直接写三地址码很容易在标签和跳转指令上翻车但如果先画AST再按模式生成就稳得多。下面是一个简单的三地址码生成示例用Python模拟了从AST到三地址码的转换# 从AST生成三地址码 # AST节点格式(op, left, right) 或 (id, name) 或 (num, value) 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 generate(self, node): if node[0] num: return str(node[1]) elif node[0] id: return node[1] elif node[0] op: left self.generate(node[1]) right self.generate(node[2]) temp self.new_temp() self.code.append(f{temp} {left} {node[3]} {right}) return temp else: raise ValueError(f未知节点类型: {node[0]}) # 示例表达式 a b * c ast (op, (id, a), (op, (id, b), (id, c), *), ) gen TACGenerator() result gen.generate(ast) print(三地址码:) for line in gen.code: print(f {line}) print(f结果在: {result})这段代码的关键在于generate函数的递归结构对于二元操作先递归生成左操作数和右操作数的代码然后创建一个新的临时变量来存放结果。new_temp方法用计数器生成唯一的临时变量名避免冲突。参数node的格式需要你根据习题里的AST定义调整但核心逻辑是一样的。跑完这段代码你会得到类似t1 b * c和t2 a t1的输出。如果习题要求生成四元式只需要把self.code.append那行改成(op, left, right, temp)的元组形式即可。5. 刷编译原理习题时最容易翻车的五个地方5.1 坑一正则表达式到NFA时漏掉空串转移现象手算的NFA和答案对比状态数一样但转移表里少了几条空串转移导致后续子集构造出的DFA状态数偏少。原因Thompson构造法里对于r r1 | r2需要引入新的开始状态和接受状态并用空串转移连接。很多人只画了r1和r2的内部结构忘了加这两个空串转移。对于r r1*也需要用空串转移实现“零次或多次”的语义。解决每次用Thompson构造法时先画出r1和r2的NFA然后严格按照规则添加新的开始状态、接受状态和空串转移。画完后检查每个新引入的状态是否有入边和出边空串转移是否完整。5.2 坑二FIRST集计算时忽略“可空”传播现象LL(1)分析表里某个非终结符的FIRST集少了几个终结符导致分析表出现空缺或者FOLLOW集计算错误。原因计算FIRST集时如果产生式右部的某个符号能推导出空串那么下一个符号的FIRST集也要加入。很多人只看了第一个符号忘了检查它是否可空。比如产生式A - B C如果B能推导出空串那么FIRST(C)也要加入FIRST(A)。解决计算FIRST集时对每个产生式右部从左到右扫描维护一个“当前是否可空”的标志。如果当前符号可空继续看下一个符号如果不可空停止。扫描结束后如果所有符号都可空才把空串加入FIRST集。5.3 坑三LR项目集闭包操作不彻底现象LR(0)项目集规范族的状态数比答案少或者分析表里出现不该有的冲突。原因闭包操作需要反复应用直到不再变化。很多人只做了一轮闭包加入了新项目但没有对新项目继续做闭包。比如项目A - α·Bβ加入闭包后B的产生式B - ·γ也要加入然后γ中的非终结符又要继续展开。解决闭包操作用一个工作列表实现把初始项目加入列表然后循环取出项目如果点后面的符号是非终结符把它的所有产生式的初始项目加入列表如果还没加入过。直到列表为空。5.4 坑四语法制导翻译的求值顺序和语法分析方向不匹配现象翻译方案在纸面上看起来正确但实际实现时发现某个属性的值还没算出来就被用了。原因S属性定义只有综合属性适合自底向上的语法分析L属性定义有继承属性适合自顶向下的语法分析。如果习题要求用递归下降法实现一个S属性定义的翻译方案或者用LR分析器实现一个L属性定义的翻译方案就会出现求值顺序问题。解决先确定属性的类型再选择语法分析方法。如果必须混用需要把继承属性转换成综合属性比如通过全局变量或栈传递或者把翻译方案改写成适合目标分析方法的格式。5.5 坑五中间代码生成时临时变量命名冲突现象生成的三地址码里两个不同的临时变量用了同一个名字导致后续优化或代码生成时出错。原因临时变量的命名没有全局唯一性保证。比如在递归生成代码时每个递归层都从t1开始命名就会冲突。解决用一个全局计数器生成临时变量名每次需要新临时变量时计数器加一。如果习题要求生成四元式临时变量通常用编号表示同样需要全局唯一。6. 把习题册变成自己的编译前端知识库6.1 用习题驱动一个最小编译器的实现刷完习题后最有效的巩固方式是写一个最小编译器。不需要支持完整的语言只需要覆盖习题里出现过的核心概念正则表达式词法分析、LL(1)或LR语法分析、语法制导翻译生成三地址码。我自己的习惯是从习题里挑一个最简单的文法比如只支持整数四则运算和变量赋值然后用Python实现完整的编译前端。这个最小编译器的结构可以完全对应习题册的章节词法分析器对应正则到DFA的习题语法分析器对应LL(1)或LR的习题语义分析和中间代码生成对应SDT的习题。每实现一个模块就回头做几道对应的习题看看手算结果和代码输出是否一致。这种“习题-代码”双向验证的方式比单纯刷题或者单纯写代码都有效。6.2 用习题里的边界条件设计测试用例编译原理习题里有很多“边界条件”题比如空串、嵌套括号、运算符优先级、左递归消除后的文法等。这些边界条件恰恰是测试编译器前端的最好用例。我一般会把习题里的边界条件整理成一个测试集每实现一个功能就用这些用例跑一遍。比如习题里经常有“包含空串的正则表达式”题对应的测试用例就是空输入有“嵌套括号”题对应的测试用例就是多层嵌套有“运算符优先级”题对应的测试用例就是混合运算。这些用例比随机生成的测试数据更有针对性因为它们直接来自形式化定义的边界。6.3 一个具体的技巧用习题答案反推算法实现习题答案通常只给最终结果不给中间步骤。但如果你仔细看答案的结构可以反推出算法的实现细节。比如DFA最小化的答案里状态划分的编号顺序往往反映了算法的执行顺序LR项目集规范族的答案里状态编号的顺序往往反映了BFS或DFS的遍历顺序。我自己的做法是拿到一个习题答案后先不看推导过程只看最终结果然后尝试用代码复现这个结果。如果代码输出的结果和答案一致说明算法实现正确如果不一致再回头检查代码里的每一步和手算过程对比。这种“答案反推”的方式能逼你把算法的每个细节都搞清楚而不是停留在“大概知道”的层面。6.4 把习题册当成查阅手册而不是刷题集最后说一个我自己的习惯不要把习题册当成“刷完就扔”的练习集而是当成查阅手册。当你写编译器遇到问题时回头翻翻习题册里对应的章节往往能找到形式化的定义和标准的解法。比如词法分析器状态爆炸时翻翻DFA最小化的习题语法分析器出现冲突时翻翻LL(1)和LR的习题语义分析时属性求值顺序搞不清时翻翻SDT的习题。这种“用中学”的方式比考前突击刷题有效得多。因为你是带着具体问题去查的习题册里的形式化定义和算法步骤会直接映射到你代码里的某个函数或某个数据结构。这种映射一旦建立编译原理就不再是一门“考完就忘”的课而是你工具箱里随时能用的东西。希望帮到你。本文还有配套的精品资源点击获取