简介这份PDF是哈工大编译原理课程的习题及答案汇总围绕源程序/目标程序、翻译程序、编译程序与解释程序等核心概念展开并按章节整理成体系适合期末复习、考研备考或自学自测。资源包内共有1个PDF文件大小约1.6MB内容集中方便离线阅读和打印。目前已有1743人学习浏览。文档从编译系统的词法分析、语法分析、语义分析等组成部分的说明讲起通过C语言关键字、括号和逗号的用途等具体题目帮助理解语言成分第二章进一步覆盖前后文无关文法、语言描述、最左/最右推导、句柄识别和二义性证明等经典难点每题后附有较完整的解题思路与答案便于对照查漏补缺。尽管文件仅1个但习题层次从基础概念到句型分析逐步递进可作为系统训练材料。1. 哈工大编译原理习题集复习到底靠什么打通编译器全景如果你和我一样曾经为了应付考试把编译原理教材从头翻到尾合上书却连“词法分析器输出的是 token 还是字符串”都说不清问题多半出在练习量上看得多、练得少。哈工大-编译原理-习题及答案汇总.pdf 这类资料最大的价值不是让你背下几道题而是把词法分析、语法分析、语义分析、中间代码生成和代码优化这些阶段拆成一个个能当场检验的小任务。它适合准备课程考试或考研复试、要做编译原理实验却不知从哪下手、以及面试前临时补编译器常识的同学。用的时候记住一条答案不是用来背的是用来在你卡住时对照的。2. 编译原理复习地图按编译器工作阶段分配练习时间很多人复习时会犯同一个错从第一章线性看到最后一章看自动机时还能跟上看到 LR 分析表就开始迷糊到语法制导翻译基本放弃。原因是没把题目和编译器的工作阶段对应起来。词法分析解决的是“如何把字符串切成 token”语法分析解决“这串 token 是否符合文法”语义分析和中间代码解决“这棵语法树怎么变成指令层面的动作”。所以拿到题集的第一件事不是从头做而是先翻目录把题按五个阶段归档词法、语法、语义/中间代码、优化、运行时环境。归档之后你会立刻发现语法分析相关题目占了一半以上而优化题大多是概念题。时间分配也应该按这个比例来。你如果手里是《编译原理》第三版答案或哈工大、燕山大学、山东科技大学等院校的复习资料会发现题目顺序基本一致从正则式到 DFA然后文法分析再一路推到目标代码。顺着这个顺序练比随机刷题高效得多。2.1 词法分析常考题从正则式到 DFA 的最小化词法分析题开篇就是经典语言 L (a|b)*abb。这类题表面是画自动机实际考的是三条算法把正则式转成 NFA、用子集构造法把 NFA 转成 DFA、用分划法把 DFA 最小化。题集答案通常直接给出最小化后的状态图比如 4 个状态而不是 6 个这背后的原因是读入第二个 b 时前一个 b 同时参与后缀 abb 的匹配状态必须被复用。如果你自己画出的 DFA 有 6 个状态且无法再合并说明你漏了不可达状态或等价状态合并。做题时不要直接从 NFA 跳到答案。先写出 ε-闭包的计算过程再用状态集合编号。举个例子NFA 初始状态的 ε-闭包是 {0,1,2}读入一个 a 后可能到达 {1,3}这个 {1,3} 就成为一个 DFA 状态。要特别注意每次求闭包都要把经由 ε 边到达的所有状态包含进去。分划法最小化时先把接受状态和非接受状态分成两组再对每组检查每个输入符号的转移目标是否仍落在同一组如果目标不一致就继续分组直到无法再分。读答案时有一个重要观念状态叫什么名字不重要接受的语言一样就算对。你从 a 出发画出的 DFA 可能和答案的 b 出发状态编号不同这不算错。词法分析题在题集里占少部分但它是编译原理实验的基础实验里用 Java 或 Python 手写扫描器时token 的正则匹配思想就是这一节的延伸别跳过。2.2 语法分析主线左递归、FIRST/FOLLOW 与 LL(1) 判定语法分析是编译原理习题集的绝对核心。自顶向下部分题目几乎固定围绕三件事消除左递归、提取公共左因子、计算 FIRST/FOLLOW 集并判断是否 LL(1)。每一件都有固定算法。消除左递归对 A → Aα | β 这类直接左递归改写为 A → βA′A′ → αA′ | ε间接左递归要先给非终结符编号逐个代入展开。做题集答案时不要只抄改写后的文法把代入步骤也写一遍因为考试只看最终文法经常不给分。FIRST 集计算相对机械看产生式右部第一个符号终结符直接加入非终结符则把它的 FIRST 集搬进来如果它可空继续看下一个符号。FOLLOW 集是最容易失分的地方规则只有三条开始符号的 FOLLOW 里放结束符 $对 A → αBβ把 FIRST(β) 去掉 ε 后加入 FOLLOW(B)如果 β 能推出 ε则把 FOLLOW(A) 整个加入 FOLLOW(B)。这里最关键的判断是“右部整体是否可空”。我建议做题前先列一张可空表把所有能推出 ε 的非终结符标出来然后再算 FOLLOW每一步都问自己β 能不能推出 ε能就要往下继承不能就只加 FIRST。举个例子对文法非终结符FIRSTFOLLOW可空S{a, b}{$}是A{a, ε}{b, $}是B{b, ε}{$}是这个表来自文法 S → A BA → a | εB → b | ε。FOLLOW(A) 为什么是 {b, $}因为 FIRST(B) 去掉 ε 得到 {b}而 B 可空所以 FOLLOW(S) 的 $ 也要并入。这种嵌套判断是题集答案里最容易一笔带过的地方自己动手时千万别省。2.3 自底向上分析与 LR 家族为什么更值得花时间自底向上分析题在考卷里出现频率更高尤其是 SLR 分析表构造和 LR(1) 与 LALR 的区分。这部分的学习链条是LR(0) 不看下一输入符号出现移进-归约冲突就无解SLR 用 FOLLOW 集来决定归约时机缓解了一部分冲突LR(1) 把向前看符号直接写进项目能力更强但状态爆炸LALR 再把同心项目合并状态数回落。题集里常见的问法是“构造 SLR(1) 分析表并分析句子 id id * id 的分析过程”。答案会给出一张 ACTION/GOTO 表和一串状态栈变化比如“0 5 3 1”这样的压栈序列。如果只背这张序列换个句子就傻眼。正确做法是先把 LR(0) 项目集规范族画出来至少画到能看清每个状态的转移再填 ACTION 表最后填 GOTO 表。SLR 的核心思想是把“归约权利”限定在 FOLLOW 集合内所以答案里出现的每一个 reduce 动作都要能对应到某个非终结符的 FOLLOW 集成员。这里还必须理解 LALR 和实验的关系。写编译原理实验时如果用了 Yacc/Bison 这类生成器默认构造的就是 LALR(1) 分析表。所以题集里的 LR 题目不只是为考试服务它直接决定你能不能看懂实验工具生成的 parser 报错信息。建议把 LR 部分当成重点中的重点来刷。3. 手算 LR 分析表如何在参考解答里读懂项目集规范族LR 题的回答为何总是让人一头雾水因为答案直接给出项目集和状态编号省略了闭包和 goto 的中间推导。我的习惯是先把文法的终结符、非终结符、开始符号列出来再准备一张空白状态转移表然后在答案给出的项目集基础上自己重画一遍箭头。跳过闭包计算去背表等于把分析表当黑匣子考场上换个文法就翻车。3.1 项目集与自动机先分清“状态”是什么一个 LR(0) 项目就是产生式右部加了一个圆点例如 E → E·T 表示已经识别了 E正等待加号。项目集则由多个项目构成闭包计算规则是对项目 A → α·Bβ把 B 的所有产生式 B → ·γ 都加入当前项目集。Goto 则是把某个状态里所有“圆点后是 X”的项目圆点后移一位再取闭包。比如给定文法 S → EE → E T | TT → id初始项目集可写为I0 { S → ·E, E → ·ET, E → ·T, T → ·id }这里 S → ·E 来自增广文法E → ·ET 和 E → ·T 则是因为圆点后面是非终结符 E闭包一层层展开得到的。题集里经常直接给出 I0 这样的集合新手以为它是凭空列出来的实际上是闭包算法强制生成的结果。阅读答案时建议把每个项目编号例如 S → ·E 记为 1E → ·ET 记为 2然后写“I0 看到 E 转移到 I1”而不是写英文项目全称。这样可以更快看清状态之间的转移关系。有一个常见混淆点项目集是分析器的抽象状态和运行时压栈的状态栈不是一回事。做分析表题时别把栈里压入的符号序列和项目集状态混在一起否则填表必乱。3.2 SLR 表的填法ACTION 与 GOTO 两步走SLR 分析表的构造分两路。第一路是 ACTION 表对每个项目集 I如果圆点后是终结符 a则对应 ACTION[I][a] 移进如果圆点已在末尾且该产生式左侧非终结符为 A则对 FOLLOW(A) 里的每个终结符填归约对增广产生式 S → S· 填接受。第二路是 GOTO 表如果圆点后是非终结符 A则把 goto(I, A) 对应的状态编号填入 GOTO[I][A]。做题时的具体步骤是先列出每个状态里的归约项目。假如状态 I 里同时有 T → T·*F 和 F → (E)·那么当输入是 * 且 * 在 FOLLOW(F) 中时这个状态就有移进-归约冲突要处理。SLR 的解决方案是如果当前输入不在 FOLLOW(F) 中就放心归约在则冲突存在这不是 SLR(1) 文法。一个实用技巧是填表前先把每个状态的所有归约产生式左侧非终结符的 FOLLOW 集抄到表边上。这样填 ACTION 表时不用反复翻前面的计算。如果答案说“该文法是 SLR(1)”你检查时只需看每个状态对同一个输入是否同时有 shift 和 reduce答案说“不是 SLR(1)请构造 LR(1)”你就该停止填 SLR 表直接转向向前看符号的项目构造别强求。3.3 LR(1) 与 LALR合并同心项集时的冲突风险LR(1) 项目比 LR(0) 多一个向前看符号形式是 [A → α·β, a]。闭包计算时向前看符号来自 FIRST(βα)其中 β 是圆点后的符号串a 是原有向前看符。计算量比 LR(0) 大不少但规则一致。习题答案中频繁出现“构造 LR(1) 项目集规范族”的指令目的就是考察对向前看符号传播的理解。LALR 的做法是把“核心相同”的 LR(1) 项目合并产生式相同、圆点位置相同只是向前看符号不同。合并后状态数减少但如果两个项目集各自包含不同的归约项目合并后可能出现 reduce-reduce 冲突。判断方法很简单合并后的状态里如果同时存在两个圆点在末尾且产生式不同的项目并且它们的向前看符号有交集就产生了冲突。一道典型题是判断某文法是否为 LALR(1)。答案往往会直接说“该文法不是 LALR(1)合并后出现 reduce-reduce 冲突”。想真正看懂就要自己把 LR(1) 状态画出来检查哪些状态是同心再模拟合并。只看结论不看合并过程下次遇到底层文法照样无法判断。这里可以做一个基本判断LALR 合并不会引入新的移进-归约冲突但可能引入归约-归约冲突所以遇到冲突先看是不是两个归约项目撞在一起不要在移进上找原因。4. 语法制导翻译与中间代码把“翻译方案”做成固定套路语法分析识别句子结构语义动作才让编译器真正“做事”。题集里有一类题是“为表达式文法写语法制导定义”或“写出每个产生式的语义动作”分值占比不如 LR 表但直接体现你会不会把语法树翻译成中间代码。做这类题按三个问题展开属性值怎么挂、依赖方向朝哪、中间代码格式选哪种。4.1 综合属性与继承属性判断属性能不能自底向上计算属性是挂在文法符号上的信息。E.val 表示表达式值T.type 表示类型。综合属性由子节点传给父节点继承属性由父节点或兄弟传给子节点。判断一个语法制导定义能不能用最稳的方法是画属性依赖图把每个属性当作节点属性计算规则当作边看依赖图有没有环。环意味着属性计算顺序无法确定需要改写文法或者改成 L 属性定义。题集里最典型的是算术表达式求值E → E1 T { E.val E1.val T.val }val 是综合属性可以自底向上扫一遍算完。声明语句则常用继承属性比如把类型从声明头下传给标识符列表。读答案时先判断每个产生式里属性流向全是向上飞的是 S 属性定义可以用自底向上方式处理有向下传的就是 L 属性定义需要自顶向下或特殊处理。这个判断比背定义更实用也是实验里构造 AST 时的核心决策。4.2 表达式与赋值一遍扫描产出三地址码三地址码的每条指令最多包含一个运算符、两个操作数和一个结果常见形式是四元式 (op, arg1, arg2, result)。答案里如果出现三元式不要慌它只是把 arg 和 result 合并成位置编号本质一样。我建议做题统一写四元式因为它不依赖指令位置操作数顺序清晰不容易把减法左右边搞反。以下是表达式产生式的一种语义动作写法和题集里常见的答案同构E - E1 T { E.place newtemp(); emit(, E1.place, T.place, E.place); } E - T { E.place T.place; } T - id { T.place id.name; }逻辑说明emit 表示往中间代码序列里追加一条四元式newtemp 申请一个新的临时变量名比如 t1、t2E.place 表示该表达式的结果存储在哪个变量或临时量中。第一个产生式先把左右两个操作数的 place 取出来再生成一条加法四元式结果为新的临时变量。不管实验用 C、Java 还是 Python 写这套逻辑完全相同只是数据结构包装不同。做此类题还要注意临时变量的释放和复用。题集答案里常出现 t1、t2、t3 按顺序递增很少复用如果自己想优化并复用临时变量要确保答案的四元式序列还能一一对应上否则对比时会自找麻烦。没有特殊要求时按顺序分配最稳健。4.3 控制流回填真/假链怎么跟答案对齐涉及 if-else 和 while 的翻译题答案多半提到回填。回填的动机是跳转指令的目标地址在生成时还不知道所以先留空等代码生成后再填。题集里会看到 E.true、E.false 这样的属性分别指向条件为真和条件为假时的跳转地址链表。做题顺序建议先理解布尔表达式的两个出口E1 or E2 中若 E1 为真整个表达式立即为真此时真出口的地址先记在链上若 E1 为假要继续算 E2。答案给出的 nextlist、truelist 就是这些待填充位置的链表。对新手最友好的练习法是给每条三地址码手工编号比如第 100 条是 jump 到哪条先用编号占位最后统一回填。这样和答案里的回填表对照时不会因为指令编号不同而晕。5. 避坑用习题与答案复习编译原理时最常见的 5 个翻车点理论看着都懂一动手就对不上答案这类问题基本集中在下面五个地方。我按“现象 → 原因 → 解决”的顺序写都是自己踩过或带人时反复见到的。5.1 FIRST 集与 FOLLOW 集的计算边界现象自己算 FIRST 集和答案只差一两个终结符FOLLOW 集差得更多尤其搞不清开始符号的 FOLLOW 里到底该不该有 $。原因可空非终结符的判断漏了。拿产生式 A → B C 举例如果 C 可空FOLLOW(B) 必须并入 FOLLOW(A)如果 C 不可空只并入 FIRST(C) 去掉 ε 的部分。很多人只记“并入 FIRST”忘了“如果右侧可空还要继承 FOLLOW”于是 FOLLOW 链断掉。解决先把所有非终结符的可空性列成一张表再算 FOLLOW。算到某个符号右侧整体可空时在纸上画一个箭头表示“FOLLOW 继续向上继承”。这样检查答案时只需核对可空表不用重新推导整个集合。5.2 LR 状态合并不能只看项目名称现象两个项目集看起来都有 A → α·Bβ 和 C → γ·就认为它们同一个状态直接合并结果分析表对不上答案。原因LR(0) 状态按项目完全集合区分LALR 的同心合并也只允许“产生式相同、圆点位置相同、只是向前看符号不同”的状态合并。只看非终结符相同就合并会把不同核心的项目混在一起轻则状态编号错位重则制造出原本不存在的 reduce-reduce 冲突。解决合并前把每个项目按“产生式编号 圆点位置”编号比较编号集合是否完全一致一致才允许合并。合并后再检查归约项目是否共存于同一个状态并触发冲突。这个过程机械但可靠。5.3 中间代码的“四元式/三元式”选择现象题目答案给四元式序列自己写三元式结构和运算结果觉得都差不多但对答案时操作数编号怎么也对不上。原因三元式用指令位置编号引用操作数一旦前面插入一条指令后续编号全部错位四元式用临时变量名引用顺序依赖弱得多。不少题集答案为了可读性统一用四元式题干却没写死格式自己选了三元式就吃亏。解决没有明确要求时一律写四元式临时变量从 t1 开始递增。如果答案给的是三元式先把它还原成四元式再读重点看操作数依赖而不是指令位置。遇到减法、除法这类不对称运算四元式的 arg1、arg2 顺序能有效防止你把减数和被减数写反。5.4 符号表与活动记录题千万别跳现象题集从词法到优化都有题但有人为了省时间直接跳过“符号表与作用域”“运行时环境”两节结果遇到“画出某函数调用链下活动记录布局”就交白卷。原因这部分没有直观的自动机图也没有语法树可画面孔陌生。但考点其实死板活动记录里返回值、动态链、静态链、参数、局部变量的排列顺序和偏移。解决必做题只有一道——画三次嵌套调用的活动记录栈标清每个字段偏移。关键是对齐教材里栈的增长方向从低地址向高地址还是反过来。方向写反答案里的 offset 全部对不上这是最容易丢分的地方。建议在纸上把栈图画成横向按“先压入的参数”在左还是右来记忆。5.5 只看答案不做闭卷自测现象拿习题及答案汇总的方式是一边看题一边看答案看完觉得全懂了合上资料遇到变体题却不知道第一步做什么。原因编译原理的知识是程序性技能FIRST/FOLLOW 计算、LR 表构造、翻译方案都是算法流程看答案只能知道入口建立不了手算肌肉记忆。解决每次只打开题目页闭卷做 15 分钟再对照答案。如果中间状态和答案不同先别急着否定自己检查是不是因为等价文法改写导致的状态编号不同。只要最终接受的语言相同或生成的代码序列等价就算你做对了。这个过程视觉上效率低实际是刷题集最快的路径。提示不同教材对结束符写法不同有的用 $有的用 #题集答案里也可能混用。动笔前先确认全篇符号约定否则一个符号差异会引发大量无效争论。6. 进阶把习题集合成编译原理实验的“读—改—查”清单做完题不等于做完实验。我建议把题集当实验起步材料词法题对应词法分析器LL(1) 题对应递归下降解析器语法制导翻译题对应中间代码生成器。具体拆成三步。第一步“读”从题集里挑一道词法题比如识别关键字、标识符、整数的自动机。先用正则表达式把 token 规则写出来再手动模拟几个输入串看是否符合答案的接受状态。第二步“改”把题集里的表达式文法改成自己的语言比如支持加减乘除和括号然后写递归下降函数每个非终结符对应一个函数。第三步“查”准备 8 个用例一半合法一半非法验证解析结果是“接受”还是“拒绝”和题集答案的逻辑对照。做完这三步纸面推导就变成可运行程序了。极简的递归下降骨架可以这样起头# 文法 E - E T | T 去掉左递归后 # E - T E # E - T E | ε def expr(tokens): term(tokens) while tokens and tokens[0] : tokens.pop(0) term(tokens)逻辑说明expr 先调用 term 解析一个项然后循环判断下一个 token 是不是加号。是加号就消耗掉再解析一个 term不是就结束对应产生式中的 ε。term 还需要继续细化成乘除和括号形成优先级层级这里略去。参数说明用 list 模拟 token 流tokens.pop(0) 每步 O(n)做小规模实验没问题要做较大输入时改用索引下标推进更合适。把“读改查”做完再回头刷题集你会发现原来背不下来的 LR 状态表其实就是一张跳转表原来绕不清的回填其实就是地址链表。我自己有个习惯每做完一道大题把答案里的判断条件缩写在一张卡片上比如“FOLLOW 继承条件右侧整体可空”“LALR 检查归约项目是否同现”。这些卡片比反复翻 PDF 更管用。希望这些经验能帮你在刷题和实验的路上少踩几个坑祝你顺利。本文还有配套的精品资源点击获取