简介这份资料是哈尔滨工业大学编译原理课程的习题与答案解析汇总以PDF文档形式呈现面向计算机专业本科生、考研备考生及希望夯实编译基础的开发者用于配套教材进行章节复习与自测。内容系统覆盖源程序与目标程序的关系、编译程序与解释程序的运行区别、典型编译系统八个组成部分的功能划分以及C语言关键字、括号与逗号的多重用途等核心知识点。资源包共1个PDF文件整体大小1.6MB内容紧凑便于离线使用目前已有1743人学习下载。除了基础习题解答还深入涉及前后文无关文法、语法树、最左/最右推导、短语与句柄、二义性文法化简与消去等经典题目既能辅助期末备考也可用于考研复习时快速回顾编译原理主干难点。1. 哈工大编译原理习题集这份 PDF 到底能帮你拿到什么如果你正在准备考研复试、期末考或者补考编译原理手里缺的不是教材而是一套能对着答案反推思路的题。哈工大这套编译原理习题集正好是这个定位它把概念题、文法推导题、词法分析题按章节排好每题后面跟着详细解答其中第二章和第三章占了近七成篇幅恰好是大多数人在考场上丢分最狠的区间。这份资料能不能用关键看你会不会用它——直接背答案基本没用带着“为什么这样构造文法、为什么这个句型能归约”去对解才是正确姿势。适合两类人一类是刚学完前四章、做题找不到入手点的初学者另一类是考前想用最短时间把句柄、最左推导、NFA 确定化这些高频考点过一遍的冲刺党。2. 开篇概念题编译和解释的分界线用一张表说清楚2.1 五个术语的关系考点全在这张图里题目 1.1 问的是源程序、目标程序、翻译程序、编译程序、解释程序之间“可能有何种关系”。这题不是背定义而是考你对“翻译程序”这个上位的理解。翻译程序是所有语言转换程序的统称编译和解释是它的两个子类源程序是输入目标程序是输出。解释程序不保存翻译结果读一条执行一条所以它其实可以看成“翻译程序 执行程序”的合并体。我复习时习惯用一张对比表把编译和解释钉死考试时无论怎么变着问都不会绕晕对比维度编译程序解释程序翻译时机先整体翻译生成目标代码保存逐句翻译逐句执行目标代码保存到指定空间可重复运行不保存翻译结果执行完即弃执行方式先翻译后执行两阶段分离边翻译边执行翻译和执行交错错误发现时机编译期集中发现语法、语义错误运行到出错语句才发现典型代表GCC、ClangPython 解释器、旧式 BASIC注意一个容易翻车的点Java 先编译成字节码再用 JVM 解释执行这算编译还是解释严格说它两个都沾但大多数教材里归为“编译解释”混合型。考试遇到这种题别一口咬死要把“编译成中间表示”和“运行时逐条解释”两层分开说。2.2 编译系统的八个组成部分怎么记才不忘题目 1.2 要求列出编译系统的组成部分。标准答案是八个词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、信息表管理、错误检查处理。这个顺序不是随便排的它本身就是一条流水线词法把字符流切成 token语法把 token 串成语法树语义检查类型和声明然后生成中间代码优化后落到目标代码。我自己的记忆方法是把它压缩成“六个阶段 两个伴随”。六个阶段是从词法到目标代码的六步两个伴随是信息表管理和错误处理它们贯穿整个编译过程。信息表管理维护符号表、常量表、保留字表错误检查处理在每一阶段都可能触发比如词法阶段的非法字符、语法阶段的括号不匹配、语义阶段的类型不一致。题目里还埋了一个坑它问“各部分的主要功能是什么”。答这道题不能只写名字至少要写一句功能。词法分析负责识别单词符号语法分析负责按文法规则检查句子结构语义分析负责检查静态语义并生成中间代码的语义信息。尤其要区分语法和语义语法只管形式对不对语义管意思通不通。比如int x abc语法上没错语义上类型不匹配。2.3 为什么这章适合拿来检验“是否真懂”1.1 到 1.4 看起来是概念题实际是后面所有章节的地基。1.3 让你上机验证 C 的关键字是否为保留字这题直接指向一个考试常考细节保留字是“不允许用户重新定义”的关键字但不同语言策略不同。C 语言的关键字全部是保留字而 FORTRAN 早期版本允许关键字当变量名这就是两门语言在词法设计上的差异。1.4 关于 C 语言括号和逗号的用途是词法分析章节“单词分类”的前置练习。逗号在 C 里既是分隔符又是运算符优先级最低运算结果是逗号表达式最后一个子表达式的值。这些细节在第三章构造 LEX 正规式时会反复用到所以别急着跳过。3. 文法与语言题构造文法、描述语言、找句柄三道硬菜3.1 构造文法从集合表达式到产生式的三步套路第二章的 2.2 题要求为六种语言构造文法这是编译原理考试必考题型。做题顺序有固定的三步先看语言集合的形状再决定用左递归还是右递归最后套模板。第一问{aⁿbⁿ | n ≥ 0}是经典的同数量配对结构。解法是右递归S → ε | aSb。为什么用右递归因为 a 在前 b 在后每推导一次在最外层套一对 a、b推导方向从左到右恰好对应“生成一个 a递归生成中间的最后补一个 b”。注意 n ≥ 0所以空串 ε 必须能推导出来。第二问{aⁿbᵐcᵖ | n, m, p ≥ 0}是三个互不干扰的段。解法是三个非终结符接力S → aS | XX → bX | YY → cY | ε。这里要理解一个问题为什么不写成S → aS | bS | cS | ε因为那样会生成a b c打乱顺序的串比如abc里 b 和 c 相邻没问题但acb也会被错误接受。三个非终结符接力本质是用推导路径强制了顺序先产生全部 a再产生全部 b最后产生全部 c。第四问{w#wʳ# | w ∈ {0,1}*}是回文串构造方式比较隐蔽S → W#W → 0W0 | 1W1 | #。推导01#10#时先用W → 0W0套最外层 0再W → 1W1套 1最后W → #收尾。这里的核心设计是用同一个非终结符在左右两侧同步扩展保证逆序关系。第五问“不以 0 打头的奇数”考察的是对首字符的约束J产生 1、3、5、7、9 作为个位I产生 2、4、6、8 作为非零首位的补充B 产生中间任意串包括空串。这道题的要点是非零首位和奇数末位分开控制。3.2 描述语言特点反向做题考的是读文法能力2.3 题给文法让你描述语言和 2.2 正好相反。这种题的难点在于看不出产生式之间的递归模式我用一个通用办法先看有哪些非终结符再找哪些产生式是递归的最后把递归结构翻译成自然语言。看第(1)问S → 10S0 | aAA → bA | a。S 的递归是10S0每递归一次套一对10和0直到换成aAA 的递归是bA每递归一次多一个 b最后以 a 收尾。组合起来语言就是L(G) {(10)ⁿ a bᵐ a 0ⁿ | n, m ≥ 0}。这道题容易漏掉的是最内层aA产生的a...a结构很多人只看到外层循环把中间的aa结构忽略掉。第(5)问S → aSS | a比较有迷惑性。展开推导会发现无论怎么推最终 a 的个数永远是奇数S a 1 个S aSS a a a 3 个继续推导每次把 S 替换成 aSS相当于在当前串里增加两个 a所以总数从奇数加偶数还是奇数。答案是L(G) {a^(2n-1) | n ≥ 1}。这类题要写出推导两步看规律而不是盯着产生式发呆。3.3 最左推导、最右推导和句柄卷二大题的主战场2.6 和 2.7 要求的推导题是考研卷面最常见的题型。最左推导就是每次替换最左边的非终结符最右推导反之。题目往往要求你同时给出两种推导和语法树用来验证文法是否有二义性。以 2.7(1) 的句子aacb为例文法含S → aAcBB → bA → a。最左推导是S aAcB aacB aacb最右推导是S aAcB aAcb aacb。两道推导看着差不多但在复杂文法里最右推导每步被替换的非终结符位置不同归约时对应的句柄也不同。自底向上分析用最右推导的逆过程所以句柄的定义是“最右推导中每一步直接推导中被替换的那个非终结符和它当前推导出的串”。找句柄有个实用技巧从最右推导的倒数第一步看起最后一步替换了哪个非终结符那一步替换产生的符号串就是最终句型的句柄。顺序是从后往前推。2.7 里有一串“不是句子”的判断这里容易踩坑。第(4)问aacabcbcccaacdca不是句子因为文法里d后面必须跟a而题干串里出现dc相邻直接违反产生式约束。第(5)问aacabcbcccaacbca也不是因为c后面不可能跟非终结符推导出的aacb序列文法里终结符c之后只能出现A或空不能出现S的推导结果。这类题在考场上没有捷径只能老老实实从最左推导逐个尝试推不动就说明不是句子。4. 文法变换与自动机化简、消 ε、NFA 确定化的实操顺序4.1 文法化简先删无用产生式再删不可达2.13 的化简题有标准顺序先删不可达的非终结符再删不能推导出终结符串的非终结符。顺序反了会出问题——如果你先删“非生成”的符号可能把一个本来可达但依赖已删符号的非终结符留在文法里导致后面步骤混乱。我的操作顺序固定如下第一步标注所有能推导出终结符串的非终结符。A → a这样的直接满足B → bC且 C 已满足则 B 也满足。反复迭代直到标注集不再变化。第二步删除所有未标注的非终结符及其相关产生式。第三步在剩余文法里找出所有从开始符号 S 出发可达的非终结符删除不可达的。以 2.13(1) 为例初始文法包含S → aABS | bCACd、A → bAB | cSA | cCC、B → bAB | cSB、C → cSC | c。先判断生成性C 能推出 c所以 C 是生成的S 能推出bCACd其中 C 生成、A 待定按迭代可以全部确定。删除非生成符号后原文法里的S → aABS和A → bAB等产生式因为引用了已删符号需要一起处理最后化简为S → bCACd、A → cSA | cCC、C → cS | c。化简完建议反向验证用化简后的文法重新推导一遍题干给出的句子确认生成的语言范围没变。4.2 消除 ε 产生式只删 ε别改变语言2.14 要求消 ε 产生式。标准做法是先找可空非终结符——能推导出 ε 的非终结符集合然后对每个产生式凡是右侧包含可空符号的位置生成“去掉该符号”的变体。看 2.14(1) 文法S → aAS | bA → cS | ε。A 是唯一的可空符号。对S → aAS而言右侧 A 可空所以除了保留原产生式还要增加去掉 A 的版本S → aS。消除后文法变成S → aAS | aS | bA → cS。这里最容易被忽略的是如果产生式右侧有两个可空符号比如X → AB且 A、B 都可空那么要分别生成去掉 A、去掉 B、去掉 A 和 B 三种变体共 2 的 n 次方减 1 种新产生式。另外消 ε 之后原语言里的空串能不能保留教材里通常分两套要么允许空串作为句子单独存在从开始符号额外加一条S → ε要么完全禁掉。考试看题目要求题目说“消去 ε 产生式”但没说禁掉空串就别乱加。4.3 NFA 确定化和 DFA 最小化按算法走别跳步3.12 到 3.14 是词法分析的高频题。NFA 确定化用子集构造法从初态的 ε 闭包开始对每个输入符号求转移后的 ε 闭包形成新的状态子集。这里常见的失误是忘记对每个新子集再求一次 ε 闭包导致转移表缺行。DFA 最小化用划分法。初始把终态和非终态分成两组然后反复检查对每个输入符号当前组内状态是否都转移到同一组。只要有一个符号的转移目标跨组就把该组再拆。停止条件是所有组在任何输入符号下都不再分裂。3.14 题里初态 S0、终态 S1/S2/S6/S7 的矩阵比较典型用划分法拆到最后发现 S3 和 S4 因转移目标不同被拆开。最小化做完后每个状态组内状态两两等价可以合并为一个状态转移表同步压缩。注意合并后要检查是否出现“死状态”——没有任何路径能到达终态的状态考试题上下文里出现了就删。这部分是整份 PDF 里最像“工程算法”的内容不要靠肉眼猜按子集构造法和划分法的四步流程走每一步都写下当前状态集合既方便检查也不会漏状态。5. 避坑记录六个最容易踩的编译原理题坑5.1 句柄识别错误现象给出最右推导的中间句型要求指出句柄总是把整个可直接归约的短语当句柄比如把ba当作句柄而不是其中更短的a。原因句柄是“最右推导中当前步被替换的非终结符所对应的符号串”它是直接短语但不一定是句型里最长的可归约串。自底向上归约时句柄是栈顶可归约的那个不是随意选的子串。解决做 2.11 这类题时先写出完整的最右推导从最后一步往前数每一步被替换的非终结符展开后的串就是该句型唯一的句柄。对比几个例句型会发现句柄必然出现在句型“最左边”的可归约位置这是算符优先分析和 LR 分析的共同直觉。5.2 描述文法语言时漏掉空串现象对{aⁿbⁿ | n ≥ 0}这类语言描述成“若干个 a 后跟若干个 b”把 n ≥ 0 的空串情况丢掉。原因题干里集合表达式明确写了 n ≥ 0但读文法时忽略了开始符号能直接推导出 ε 的路径。比如S → aaS | εε 是合法句子必须写进语言描述。解决描述语言前先检查每个非终结符是否可空特别是开始符号。若S ⇒* ε语言集合就要显式包含 ε。2.3 的第(2)问里S → 1A0和A → 1A0 | ε组合ε 是否在语言里取决于是否有路径让整个 S 推导为空——此题没有但要养成检查的习惯。5.3 最左推导和最右推导不标注替换位置现象做题时只写推导序列不标注每一步替换了哪个非终结符或者二义性题里两个不同语法树对应的推导序列写得一模一样。原因推导序列里S AS aS ab如果不说明第二步替换的是哪个 A 或 S别人无法判断是否合法也无法用它判断二义性。二义性定义是“存在某个句子对应两个不同的语法树”而不是“有两个不同的推导序列”。解决写推导时用下划线或高亮标出每一步被替换的非终结符。再做一个额外验证画出语法树看两棵树形状是否真的不同。2.10 证二义性用的句子abc就有两棵不同语法树而不是两条写法不同的推导。5.4 消 ε 产生式时丢失产生式变体现象对S → aAS | b、A → cS | ε只保留S → aAS加上S → aS结果用原文法能生成的句子a cS b在新文法里推不出来。原因S → aAS中 A 可空去掉 A 得到aS但如果同时还有其他可空符号组合每个组合都需要一条变体。缺失一个组合就丢一种句子。解决把产生式右侧每个可空符号的所有组合逐一列出。两个可空符号按二进制枚举四种情况删去全空的那一种就是三条新产生式。做完用原语言里的一个代表性长句子反向验证确保新文法能完整推导出来。5.5 NFA 确定化时忽略 ε 闭包现象子集构造法求转移时只取直接能读某符号到达的状态没求这些状态的 ε 闭包导致得到的 DFA 状态少且多个终结符的句子识别不出来。原因ε 转移不消耗输入字符是“免费移动”。NFA 读一个符号后实际能停住的状态包含所有可通过 ε 边到达的状态必须一并纳入当前子集。解决定一个固定动作每步转移后马上对目标集合求 ε 闭包再写进转移表。子集构造法的正式定义是move(subset, symbol)后接ε-closure()两步缺一不可。3.13 题的 NFA 含多条 ε 边做完后可以挑一个含 ε 边的路径手工走一遍验证。5.6 文法化简顺序颠倒导致删错符号现象先删不可达符号再删非生成符号结果把一条本应保留的产生式连带删掉。原因不可达和非生成两个性质会相互影响。某些非终结符虽然从 S 可达但它引用了非生成符号导致自身间接非生成反过来有的非生成符号可能是某个生成路径的一部分。顺序错了结果就不一样。解决按标准顺序来先删非生成、再删不可达。每次删除后要重新检查剩余文法的生成性和可达性因为删除会产生新的不可达符号。用 2.13(1) 练习时按这个顺序得出的化简文法是S → bCACd、A → cSA | cCC、C → cS | c先做生成性标记再删不可达两次检查都能对上。6. 拿着 PDF 做自测用 LEX 题和推导验证来验收6.1 用 3.27 题的 LEX 正规划当试金石第三章最后的 LEX 题是这份资料里最有“落地感”的部分。3.27 要求写出匹配 C 语言无符号整数的 LEX 正规式包含十进制、八进制0123、十六进制0X89ab、字符常量Z、\t、\012多种形式。一个能覆盖大部分情况的写法是分段匹配0[xX][0-9a-fA-F] { /* 十六进制整数 */ } 0[0-7] { /* 八进制整数 */ } [1-9][0-9]* { /* 非零开头的十进制整数 */ } 0 { /* 单独的零 */ } (\\.|[^\\\n]) { /* 字符常量处理转义 */ }逻辑说明前四条规则按前缀特征把数字切成十六进制、八进制、十进制和零四类优先级从高到低排列。LEX 匹配时取最长匹配但0[xX]前缀能确保十六进制优先。第五条字符常量用\\.匹配转义序列如\t、\012用[^\\\n]匹配普通字符排除了换行和未转义引号。参数说明里最容易忽视的是规则顺序如果把0[0-7]放在十六进制规则前0x89会被截成0和x89两段这是经典错误。6.2 用“反向验证法”验收推导题做完每道推导题我都建议做一个反向归约验证。从最终句子开始按最右推导的逆过程逐步归约看每步归约的子串是不是对应文法中某个产生式的右部。句柄就是这一步归约的子串。这个方法不依赖语法树特别适合考试时快速自查。我自己的复习习惯是每章先限时做题做完直接用 PDF 答案对不对的地方不看解析先自己返工一次。第二章的文法构造题最值得这么做——构造错了不返工下一题还会错。从那以后每逢推导题我强制自己做完最右推导立刻反向归约一遍花不了半分钟但能挡住一半低级失误。这份 PDF 的答案相对完整把每道题当作一次小模考用效果比通读三遍教材好得多。希望帮到你。本文还有配套的精品资源点击获取