企业官网建设流程全解析

简介：这份资料是哈尔滨工业大学编译原理课程的习题与答案解析汇总，以PDF文档形式呈现，面向计算机专业本科生、考研备考生及希望夯实编译基础的开发者，用于配套教材进行章节复习与自测。内容系统覆盖源程序与目标程序的关系、编译程序与解释程序的运行区别、典型编译系统八个组成部分的功能划分，以及C语言关键字、括号与逗号的多重用途等核心知识点。资源包共1个PDF文件，整体大小1.6MB，内容紧凑便于离线使用；目前已有1743人学习下载。除了基础习题解答，还深入涉及前后文无关文法、语法树、最左/最右推导、短语与句柄、二义性文法化简与消去等经典题目，既能辅助期末备考，也可用于考研复习时快速回顾编译原理主干难点。

1. 哈工大编译原理习题集：这份 PDF 到底能帮你拿到什么

如果你正在准备考研复试、期末考或者补考编译原理，手里缺的不是教材，而是一套能对着答案反推思路的题。哈工大这套编译原理习题集正好是这个定位：它把概念题、文法推导题、词法分析题按章节排好，每题后面跟着详细解答，其中第二章和第三章占了近七成篇幅，恰好是大多数人在考场上丢分最狠的区间。这份资料能不能用，关键看你会不会用它——直接背答案基本没用，带着“为什么这样构造文法、为什么这个句型能归约”去对解，才是正确姿势。适合两类人：一类是刚学完前四章、做题找不到入手点的初学者；另一类是考前想用最短时间把句柄、最左推导、NFA 确定化这些高频考点过一遍的冲刺党。

2. 开篇概念题：编译和解释的分界线，用一张表说清楚

2.1 五个术语的关系，考点全在这张图里

题目 1.1 问的是源程序、目标程序、翻译程序、编译程序、解释程序之间“可能有何种关系”。这题不是背定义，而是考你对“翻译程序”这个上位的理解。翻译程序是所有语言转换程序的统称，编译和解释是它的两个子类；源程序是输入，目标程序是输出。解释程序不保存翻译结果，读一条执行一条，所以它其实可以看成“翻译程序 + 执行程序”的合并体。

我复习时习惯用一张对比表把编译和解释钉死，考试时无论怎么变着问都不会绕晕：

注意一个容易翻车的点：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 | X，X → bX | Y，Y → 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 | aA，A → bA | a。S 的递归是10S0，每递归一次套一对10和0，直到换成aA；A 的递归是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 → aAcB，B → b，A → 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 | b，A → cS | ε。A 是唯一的可空符号。对S → aAS而言，右侧 A 可空，所以除了保留原产生式，还要增加去掉 A 的版本S → aS。消除后文法变成S → aAS | aS | b，A → 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 的答案相对完整，把每道题当作一次小模考用，效果比通读三遍教材好得多。希望帮到你。

本文还有配套的精品资源，点击获取