企业官网建设流程全解析

简介：常州工学院《编译原理》试卷A是一份面向计算机专业学生的期末试题，覆盖词法分析、语法分析、中间代码生成等编译流程核心知识点，既适合考前自测、查漏补缺，也可供教师布置作业或命题时参考。资源为单个doc文档，体积仅55KB，内页排版清晰，可直接打印练习。试卷共五个大题，依次涉及正规表达式与最简DFA构造、逆波兰表示转换、文法二义性证明与语言描述、First集与Follow集计算及LL(1)预测分析表构建、if语句四元式序列翻译，并在题目标注了分值，便于规划答题时间。已有391人浏览学习，属于“试卷库”中的常用备考资料。通过完整作答这些题目，能系统梳理编译原理主干内容，理解词法规则、语法判定和中间代码生成之间的衔接，熟悉期末常见题型与解题方法。

1. 一份编译原理试卷A到底在考什么：它不是题库，是整条编译链路的地图

拿到《编译原理试卷A》的时候，很多人第一反应是找原题、背题型。但真到了考场上，你会发现丢分的地方从来不是没背过，而是没看懂这张卷子背后的脉络。编译原理这门课和别的课不一样，它把“字符串怎么变成机器码”这条完整链路切成了词法、语法、语义、中间代码、代码生成五段，而一份成型试卷的考点分布，恰恰就是这条链路的等比例压缩。只要抓住“输入串到目标代码”这条主线，题目再怎么换皮，考点都是那几个固定的节点。

这份试卷适合三类人：一是正在准备期末考试的在校生，想用一套真题摸清重点；二是准备考研或面试的工程师，需要快速梳理编译基础；三是工作中偶尔和解析器、DSL、代码生成打交道，想补上理论短板的开发者。读这一篇，不是要你把题目背下来，而是带着你从卷面倒推知识结构，再讲清楚每类题型的展开方式和踩坑点。

2. 词法与语法题：从正则到LR分析表的四类必练题型

2.1 正则表达式与自动机题：NFA、DFA、最小化，步骤别跳

词法分析在试卷A里通常占12到18分，最常见的组合是“给一个正则表达式，写出NFA，再转成DFA并最小化”。这道题看着绕，但其实是全卷性价比最高的题目，因为套路完全固定，练熟之后几乎不会丢分。

我把它拆成三步操作：

第一步：画NFA。拿到正则表达式后，先按运算符的优先级加括号，把“|”“*”“连接”拆成子表达式。然后每个子表达式画一个片段：字符用一条边，连接用串接，闭包用带回边的状态，并集用两个分支合并到一个起点和一个终点。这步的关键是不要试图一步到位画一个“看起来很简洁”的NFA，宁可多画两个空转移边，为了后续算法服务。

第二步：对NFA做子集构造得到DFA。从NFA的初态出发，对每个输入符号求ε-闭包，得到一组状态子集。每个子集就是DFA的一个状态。这个计算过程我建议老老实实写状态子集表格，列是输入符号，行是新生成的状态集，直到没有新状态出现。真正容易出事的地方在ε-闭包漏算：空转移边形成的环必须完整展开，否则后面对输入串的判定一定会错。

第三步：DFA最小化。先把终态和非终态分成两个集合，然后不断按输入符号分裂——只要同一个集合内的状态对某个符号走到了不同集合，就继续分裂，直到不动点。这步的细节是：如果某个状态对符号没有出边，不要直接丢弃，要把它视为“走入死状态”，在最小化时和死状态一起归类，否则最终得到的状态数会比正确答案少。

下面给出一个我用来自检的最小化流程，写成伪代码级别的步骤：

输入：DFA M=(Q, Σ, δ, q0, F) 1. 初始化划分 P = {F, Q-F} 2. 重复： 对 P 中每个集合 G，对每个符号 a： 若 G 中的状态经 a 到达的集合不完全相同， 则按“到达集合的归属”把 G 分裂 直到没有任何集合被分裂 3. 把同一集合内部的状态合并为一个状态 4. 包含 q0 的集合作为新初态，包含原终态的集合作为新终态

逻辑上，这个流程依赖一个事实：完全等价的状态必须有完全一致的“未来行为”，也就是对任意输入串，两者要么同时接受要么同时拒绝。参数上，分裂条件只看一步转移后的集合归属，所以必须按“划分—精化”反复迭代，不能只扫一遍。你可能觉得这很像闭包计算，没错，它和求可达状态本质是同一类不动点算法。计算完成后，用原始正则里的典型串（包含空串、重复项、非法串至少各一个）去测试新DFA，能跑通，这题才叫稳了。

2.2 LL(1)与LR(1)的取舍判断：FIRST/FOLLOW和项目集的两种考法

语法分析是试卷的大头，通常能到30分以上。它一般分成两个阵营：自顶向下考LL(1)，自底向上考LR(0)/SLR(1)/LR(1)。很多同学会陷入一个误区——试图把所有文法都套进LR(1)，结果项目集规范族画到一半卷面就写不下了。试卷A里显然更偏爱“给出文法，判断能否用LL(1)，并构造预测分析表”这类题。

判断LL(1)需要走一遍标准流程：

1. 消除左递归。注意直接左递归和间接左递归都要处理。
2. 提取左公因子。
3. 对每个产生式计算FIRST集。如果某个非终结符能推出空串，还要计算FOLLOW集。
4. 检查冲突：对任意产生式 A → α | β，如果 α 和 β 的FIRST集相交，或者其中某个FIRST集包含空串而FOLLOW(A)与另一个产生式的FIRST集相交，则文法不是LL(1)。

FOLLOW集是这题的坑王。初学最容易把“开始的符号”和“跟随的符号”搞混，比如把开始符号的FOLLOW默认成空，忘了要放入结束标记$。我的习惯是：初始化时把所有文法开始符号的FOLLOW集中加入$，然后反复套三条规则直到没有新增项。

有些时候你不需要手工算，可以用一个小脚本校验。我常用下面这个极简FIRST集计算的骨架，把这个挂在本机跑一下，能快速对照手算结果：

def first_set(grammar, symbol): # grammar: dict, 非终结符 -> 产生式列表, 产生式是字符串列表 # symbol: 当前计算的符号 if symbol not in grammar: # 终结符的FIRST就是自身 return {symbol} result = set() for production in grammar[symbol]: if production == ['epsilon']: # 空产生式直接贡献空串 result.add('epsilon') continue for i, ch in enumerate(production): if ch == symbol: continue # 避免左递归死循环，实际完整版要维护访问标记 f = first_set(grammar, ch) result |= (f - {'epsilon'}) if 'epsilon' not in f: break # 这一项没有空串，后续无法继续传导 else: # 整个产生式都能推空，才贡献空串 result.add('epsilon') return result

这段脚本的逻辑：对产生式逐个符号扫描，如果某个符号的FIRST集里没有空串，就停止扫描，因为后面的符号不可能再贡献FIRST了；只有当产生式右侧全部都能推出空串，整个产生式才向FIRST集增加空串。参数上的关键是epsilon的传导处理，实际做课程练习时最好加上“已访问符号”字典，防止间接左递归让递归调用无限循环。

2.3 算符优先分析与LR分析的边界，别混着用

有的试卷会把“算符优先分析表”和“LR分析表”放在同一张卷子里，而且故意用同一份文法。这时候要特别注意：算符优先分析的基础是终结符之间的优先关系，它只看终结符，不看非终结符；LR分析的基础是项目集和状态转移。混用就会出现“等号关系”处理错误——算符优先里=表示的归约，并不是普通算术里的相等。

做题时，先判断题目要求的是“移进-归约”分析还是要构造分析表。如果要求构造算符优先表，就老老实实计算FIRSTVT、LASTVT，再根据产生式形态填关系；如果要求LR分析，就不要去算优先关系，直接写项目集规范族。这个选型判断本身就是考点，你把它走对，等于白赚一道题的分数。

3. 语义分析与中间代码：属性文法、三地址码与控制流翻译

3.1 属性文法题：综合属性与继承属性怎么分配不会乱

试卷A在语义分析部分的典型考法是给出一个小型语言的文法，问“为文法设计属性，写出语义规则，并为某语句输出带注释的语法树”。这类题表面的计算量不大，但特别容易在属性方向的定义上翻车。

属性分成两类：

• 综合属性：节点的属性值由子节点属性计算得到，信息自底向上传递。典型代表是表达式的结果、语句中变量的类型。
• 继承属性：节点的属性值由父节点或兄弟节点传递而来，信息自顶向下或横向传递。典型代表是语句中希望传递的符号表引用、循环入口标签等。

我一般的做题顺序是：先把语法树画出来，然后从最终需要的结果反推哪一层能直接算出来——能被孩子算出的是综合属性，需要从外面传入的是继承属性。比如“声明语句的类型”通常由声明中的类型名向上综合；“变量在表达式中的类型检查”则由变量声明处向下继承。把每个非终结符所需的属性写在语法树节点旁，再逐条写语义规则，就不会漏。

里面有一个高频坑：赋值语句id := expr里，如果希望检查左部和右部类型是否一致，左部变量id的类型是从环境继承下来的属性，而不是从expr综合上来的。所以常见语义规则写法是S.type := if id.type == expr.type then id.type else error。这个规则里id.type用的是继承属性，很多人会当成综合属性来写，方向一错整个语义检查的传递链就断了。

3.2 控制流翻译题：回填技术做布尔表达式和if语句的代码布局

中间代码考得最多的是三地址码，尤其是带布尔表达式的if-else和while语句翻译。这类题最稳妥的做法是使用“回填”思路：生成跳转指令时不直接填目标地址，先挂一个待填列表，等后续确定目标后再回填。手工做题时你不需要完整模拟回填的数据结构，但我建议按下面这套顺序展开：

1. 画出语句的语法分析树。
2. 给每个语句节点标记真出口、假出口和下一个语句的入口标签。
3. 从左到右生成三地址码，遇到跳转指令先空着目标，记录这条指令的编号。
4. 当后续标签确定时，反向把编号填入。

以布尔表达式a < b or c > d为例，生成的三地址码一般长这样：

if a < b goto L_true if c > d goto L_true goto L_false L_true: ... L_false: ...

逻辑上，这里用到了短路求值——只要第一个条件成立，就不再判断第二个条件。参数上要注意：or的语义是“跳过其余条件直接走真出口”，所以前两个if的目标都是L_true；而goto L_false是两者都不满足时的兜底跳转。如果你手写的答案里把第二个条件写成了if c > d goto L_false，那一定是把短路语义理解反了。多练几个嵌套组合之后，这类题基本就是填模板。

3.3 过程调用的三地址码：形参实参、返回值和栈上临时量的处理

试卷A偶尔会考一段带函数调用的赋值语句，比如x := f(a, b)，要求写出完整的三地址码。这里很多人漏掉“实参计算”这一层。正确的展开是：先把实参表达式算出结果，存到临时量；再把临时量作为参数传入；然后调用函数；最后把返回值赋给左部变量。

一个容易丢分的点是把参数求值顺序写乱，尤其是当实参本身包含副作用的表达式时。如果题目没有特别说明求值顺序，我一般按从左到右展开，并显式注释“按PLUS语言语义，参数从左到右求值”。如果试卷明确说明求值顺序未定义，则以表达式树的自然顺序为准。这提醒我们，语义分析不只看你会不会生成指令，还看你能不能感知语义规则对代码形状的影响。

4. 运行时环境与代码生成：活动记录、寄存器分配和局部优化题

4.1 栈式存储题：活动记录与调用序列，这几个字段千万别写漏

运行环境这块的考点集中在“栈式分配”和“活动记录”。试卷里比较典型的问法是：“画出某次递归调用后的运行栈”或者“写出过程调用前后调用序列的步骤”。活动记录的字段一般是：局部变量、临时量、保存的机器状态（返回地址和旧栈指针）、参数、返回值、以及可选的访问链/控制链。

画运行栈时，我建议按下面的顺序布局，从高地址向低地址：

这里的关键不是背字段，而是看懂哪些由调用者压入、哪些由被调者填写。实参、返回地址和旧栈指针一定是调用者负责压栈的；局部变量和临时量由被调函数进入后分配。如果你画出的栈里，局部变量出现在实参上方，基本就能看出调用序列画反了。访问链是最常见的迷惑项：如果题目语言不是Pascal式嵌套过程，访问链可以不画，画了反而画蛇添足。

4.2 代码生成与优化题：寄存器描述符和变量地址描述符的双向追踪

代码生成题的典型考法是用基本块给你一段中间代码，让你用寄存器描述符和变量地址描述符模拟寄存器分配。考试时逐行维护两张表很繁琐，但它是把“寄存器里的值”和“内存里的值”这个状态追踪清楚的最好手段。

表结构大概是这样的：

代码生成时，每个用到变量的指令，先去寄存器表查是否命中；如果命中且内容有效，直接生成寄存器引用指令；否则生成内存加载指令。赋值给变量时，优先写入寄存器，同时更新两张表。到基本块结束，需要把仍然只存在于寄存器中的变量保存回内存。

很多同学会在“何时写回内存”这里栽跟头。规则很简单：如果变量在寄存器里被修改过，且后续块还可能读取它，那么在本块结尾必须保存；如果本块内它是最后使用，后面不再引用，就不必保存。做题时只要记住“寄存器只是缓存，内存才是最终归宿”，就不会漏掉store指令。

4.3 循环优化三件套：代码外提、强度削减和归纳变量删除

试卷的优化大题如果出到“对下列循环进行优化”，基本是在考这三件事。我给出一段极简的中间代码来演示一下：

L: i := 0 t1 := 4 * i t2 := arr[t1] if t2 < 100 goto L_end i := i + 1 goto L L_end:

第一步，代码外提：循环体内如果出现“不随迭代改变”的表达式，把它移到循环前。上面的4*i其实随i变化，不能外提。要找一个真正不依赖循环变量的，比如c := 2 * p这种，其中p在循环内不变。外提的判断标准是：表达式里每个操作数在循环内所有赋值点之后都没有被重新定义。

第二步，强度削减：4 * i这种乘法可以用每次递增4的加法替代。引入一个临时变量，比如让t = 4 * i在循环入口初始化，循环体内每次t := t + 4。这样乘法变成加法，指令代价明显下降。

第三步，归纳变量删除：如果i只在循环计数和数组寻址时使用，而且t完全由i推导而来，那i可能被删除，直接用t做循环判断。这一步要谨慎，删除的前提是i在循环外没有被引用，否则你删掉的不是一个变量，而是一个对外接口。

优化题的坑在于顺序。考试时很多人先做归纳变量删除，再做强度削减，结果两边互相干扰。我的习惯是先外提、再削减、最后删归纳变量，这个顺序和你实际做优化的编译器流程也一致。

5. 从试卷A的常见丢分点聊开去：五个踩坑记录

5.1 FOLLOW集合算出来的结果比标准答案少了$

现象：手算FOLLOW(开始符号)时，只写了过程体里的跟随符号，把结束标记丢了；或者用上面那段Python脚本时发现结果集和预期不一致。

原因：FOLLOW集的定义要求开始符号的FOLLOW元素包含输入结束符。多数教材把这条作为初始化规则，而不作为推导规则，如果自主计算时只套用产生式推导，就会漏掉$。

解决：算FOLLOW前先写好三类初始化——开始符号加$；对形如A → αB的产生式，把FOLLOW(A)全部并入FOLLOW(B)；对A → αBβ的产生式，把FIRST(β)中除空串外的符号并入FOLLOW(B)，若FIRST(β)含空串，则还要并入FOLLOW(A)。把这个流程写成检查清单，逐条核对。

5.2 LR项目集规范族出现凭空多出来的搜索符

现象：构造LR(1)项目集时，某些项目的搜索符来自初始项目传递，但闭包过程中忽略了上下文，导致多加了搜索符，最终SLR(1)和LR(1)分析表混在一起。

原因：很多教材在引入LR(1)时会强调“搜索符比SLR更精确”，于是有人把SLR的FOLLOW集直接搬到LR(1)的搜索符上。但LR(1)搜索符来自产生式右侧的FIRST计算，不是FOLLOW全集。二者在简单文法上结果可能一样，在复杂文法上就会不同。

解决：做LR(1)闭包时，用“当前项目后紧跟的符号串的FIRST”作为新项目的搜索符，不要直接用FOLLOW。简单校验方法：分析表的ACTION表里，如果某个状态对同一个终结符同时出现移进和归约，说明这里很可能混用了SLR的风格。考试时如果时间紧张，宁愿先做SLR(1)，也别为了追求LR(1)把搜索符写成一锅粥。

5.3 属性文法里的类型信息方向写反

现象：语义规则写了S.type := id.type，结果题目给的文法里id是在产生式左侧定义的，明明应该从环境继承类型，却写成了子节点向父节点传值。

原因：想当然地把所有属性都当成综合属性。实际上，符号表里的变量类型、循环深度、嵌套层级这些信息，都是从上下文环境获取的，天然是继承属性。只有表达式结果、语句生成代码序列这类由自身计算出来的值，才是综合属性。

解决：写上每个属性之前先问自己：这个值是从哪里知道的？如果它来自“声明处”或“外面传入的环境”，就是继承属性；如果它来自“子节点算完给我的”，才是综合属性。考试时拿不准，就在属性名前写inh或syn，让阅卷老师看到你的意识，至少不会整个方向都废掉。

5.4 中间代码生成时跳转目标乱填，回填之后对不上

现象：写if语句的三地址码，goto后面先填了一个占位编号，后来回填时发现编号少于实际条数，跳到了错误位置。

原因：手工做题时，还没有确定生成顺序就先写跳转，导致指令条数变动后编号对不上。

解决：我建议按“先框架后填充”的顺序——先写出带空跳转的完整指令列表，用L_true、L_false这类符号代替实际编号，而不是真的先写数字。全部框架落定后，再为每个标签分配唯一编号并替换。这样即使中间插入若干临时量指令，跳转目标也不会错位。这个习惯在考场上能省下大量改错时间。

5.5 代码生成的最终指令忘记保存寄存器中的变量

现象：基本块末尾生成的汇编指令里，只有计算指令，没有store指令，导致结果在后续基本块读不到。

原因：模拟寄存器分配时只关注了当前指令，忽略了“基本块边界是寄存器状态的同步点”这一原则。

解决：每次一个基本块结束时，把所有“寄存器中有且已修改但内存未更新”的变量全部生成store指令，然后清空寄存器描述符。这一步做完再进下一个基本块，状态干净，不会带着上一个块的脏数据进入新块。把这个“基本块结尾清脏”的动作作为一个默认步骤，所有代码生成题都不会漏。

6. 用试卷A做复习闭环：把错题变成一张可复用的考点映射表

这可能是整篇笔记里对你最有用的一个技巧。拿到试卷A，别急着整套做，也别急着对答案，而是先给它做一次考点拆解，每道题对应到知识模块和具体算法。做完后按下面这个模板整理：

把所有错题往里填，一个星期后你会得到一张属于你自己的漏洞分布图。这个方法的厉害之处在于，它不针对某一次考试，而让你看清自己容易在哪个环节翻车。

这套方法的来源说起来也简单。我认识一位已毕业的同行，当年复习时把近三年的卷子全部按上面的方式做映射，结果发现他所有的丢分几乎都集中在“继承属性和LR(1)搜索符”两个点上。第二次复习时直接把这两个点作为主攻方向，最终成绩显著提升。后来我带新人学编译时也一直用这个思路——不管手头拿的是哪一份试卷，先不要做，先拆结构，把考点归位，等结构清楚了再做题，事半功倍。

如果你想偷懒一点，还有一个更省力的做法：把卷子里的中大型题（比如LR分析、三地址码生成、循环优化）单独抽出来，不按原卷顺序做，而是按“词法→语法→语义→优化”的流程重排，从前往后自己当老师讲一遍。能流畅讲出来，就说明你已经站在出题人的角度思考问题了。考试时遇到改编变体也不会慌，因为你掌握的是框架，不是答案模板。

这是我最想分享的一个备考习惯，也是我自己的血泪经验——别把试卷当题库，把它当训练集。训练集的价值不在于刷完，而在于每次迭代都在修正模型参数。希望帮到你。

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