简介南京信息工程大学2021—2022学年编译原理期末试卷B卷及参考答案对应凌妙根老师所授课程覆盖词法分析、语法分析、错误处理、非递归预测分析、语法制导翻译、SLR分析、代码优化及自动机理论等要点适合计算机专业本科生期末复习、考研复试和自学编译器知识。试卷包含选择题、画图题、计算分析题和综合题可用于检验对最左推导与语法树、DAG优化、FIRST/FOLLOW集、预测分析表及NFA/DFA构造的掌握情况。题目设置由浅入深既有基本概念辨析也有“75”SLR语法分析、基本块DAG重写和最小化DFA等综合性求解实例方便对照答案反推每一步规则。压缩包共1个docx文件大小约1.11MB内容完整、便于打印练习已有1021人学习下载是考前查漏补缺的高质量模拟材料。1. 为什么一份带答案的期末卷是复习编译原理的最短路径编译原理这门课难点不在于某一个算法有多深而在于整条链路太长。词法、语法、语义、中间代码生成、优化、目标代码生成每一步都是上一阶段的输出作为下一阶段的输入。绝大多数教材把这些环节拆成独立章节学生学完词法忘了语法学完语法忘了文法变换到了期末复习时手忙脚乱。南京信息工程大学凌妙根老师的这份2021-2022学年第1学期《编译原理》期末试卷B卷恰好把这条链路上的关键节点全部串了一遍选择题覆盖编译器构成、错误处理策略、语法制导翻译的基本假设画图题考查最左推导、语法树、DAG优化计算分析题涉及消除左递归、FIRST/FOLLOW集合、预测分析表综合题则要求构造SLR分析表并手推移进-规约过程以及正则表达式到最小化DFA的完整转换。这份试卷适合两类人一是正在备考的本科生用来做自测和查漏二是已经工作、想快速唤醒编译原理知识体系的工程师用它做一次低成本的能力盘点。带答案的版本尤其有价值因为考试题本身就是从大量经典习题里筛出来的答案是别人踩过坑之后留下的比从头啃教材效率高得多。2. 选择题里被反复问到的几处关键概念辨析2.1 编译器的组成边界设备管理程序为什么不是编译器的组成部分选择题第一题问“哪一个不是编译程序的组成部分”答案C是设备管理程序。这个题目本身不难但它划定了一条很容易被忽视的边界编译器是一个纯软件层面的翻译系统它处理的是源代码到目标代码的转换不负责与硬件资源打交道。词法分析程序负责把字符流切割成token序列语法分析程序负责根据文法构建语法树代码生成程序负责把中间表示转换成目标机器指令。设备管理属于操作系统内核的功能范畴与编译器的职责完全无关。如果把这个边界再往外推一步在实际的编译实现里一个完整的编译器前端项目通常会包含词法分析器、语法分析器、语义分析器、中间代码生成器四个部分。很多人在github上搜“编译原理词法分析实验”项目时会发现有些工程把符号表、错误报告模块也单独划出来这属于实现层面的组织方式不是理论层面的必要组成。我见过不少学生把错误处理机制误以为是编译器之外的模块实际上错误处理是贯穿所有阶段的基础设施任何阶段都可能产出错误信息但它不是编译器的“组成部分”而是各组成部分运行时调用的公共机制。2.2 错误处理策略立即停止编译是最差的选择第二题和第二题之后的第三题都在讲错误处理。题目问“在编译过程中遇到错误应该怎么办”四个选项里“立即停止编译”是错误答案。编译器的设计原则是尽可能多地发现错误而不是遇到第一个错误就中断。常见的做法是在局部范围内对错误进行纠正然后跳过出错所在的语法单位继续分析。这里有一个实操层面的细节值得展开在递归下降分析器里实现错误恢复时有一个叫synchronizing token的技巧。当语法分析器发现当前输入符号与期望符号不匹配时不是直接报错终止而是丢弃输入符号直到遇到一个同步符号比如分号或}再尝试恢复分析。这个做法对应试卷第三题的选项C“跳过错误所在的语法单位继续分析下去”。我实现过一个小型C语言子集的语法分析器实际的错误处理策略比理论课讲的要更细化分为panic mode恐慌模式、phrase-level recovery短语级恢复和error productions错误产生式三个层次panic mode虽然在恢复质量上最粗糙但因为实现简单、不会引入二次错误反而是工业编译器里最常用的策略。// 递归下降分析器中的错误恢复示例 void parse_block() { expect({); while (!check(}) !check(TOKEN_EOF)) { if (!check_sync_token()) { // 不在同步符号集合中则跳过 advance(); continue; } parse_statement(); } expect(}); }上述代码的逻辑是check_sync_token()会在当前token不是分号、右大括号这些可以安全恢复的符号时返回false此时不断advance()直到遇到同步符号。这个策略的好处是不会因为一次错误就放弃整个块的分析。这套实现思路在期末复习中不算得分点但面试时经常被追问。2.3 非递归预测分析中的属性计算时机第四题和第五题围绕属性文法与语法制导翻译的两个认识误区展开。第一处误区在继承属性与综合属性的计算时机非终结符A的继承属性在A出现之前就可以计算答案D是错误说法因为继承属性是从父节点或左兄弟节点的属性值计算出来的所以必须在进入A之前先算好作为参数传给A的语义规则综合属性相反它是由A自身的产生式右部各符号的属性计算出来的因此在A完全展开之后才得到结果。第二处误区在语法制导翻译方案的适用方法。第五题的说法A“语法制导翻译方案只限自底向上的分析方法”是错的L-SDD和S-SDD分别对应自顶向下和自底向上的全流程。在自顶向下的LL(1)分析中嵌入语义动作需要扩展语法分析栈把继承属性和综合属性分开放置在栈记录的不同字段里。这里有一个底层认知语义动作本质上是在语法分析的过程中插桩每执行一个产生式就触发一次对应的属性计算代码。我在做表达式求值的小型计算器时就是按这个模式做的遇到数字就压栈数值遇到运算符就弹两个操作数做运算再压回结果。代入式synthesized attribute的计算顺序问题可以用下面的表做一个直观对照属性类型计算时机依赖方向在非递归预测分析中存放位置继承属性inherited产生式左部符号展开之前自顶向下传递对应符号的栈记录传入字段综合属性synthesized产生式右部符号全部处理完成后自底向上汇聚对应符号的栈记录传出字段这张表在实际做实现部署时非常有用尤其是写递归下降翻译器时继承属性通常作为函数的入参综合属性作为函数的返回值两者在接口设计上天然分离。期末答题时只要把这层关系说清楚选择题不会丢掉分数。3. 画图题中的语法树、句柄识别与DAG优化实战3.1 最左推导和语法树如何保证每一步都落在最左边试卷第一道画图题给出文法G(S)要求对句子(a,(a,a))做最左推导并画出语法树。这里最左推导的定义是每步都把当前句型中最左边的非终结符替换为某个产生式的右部。做这种题的关键是控制推导顺序不能跳步。以这类题目常见的文法为例如果文法包含S → ( T ) | a和T → S | T, S最左推导的过程是S ⇒ ( T ) ⇒ ( S ) ⇒ ( a )但这个式子不够复杂。“句子(a,(a,a))”在视觉上是一个嵌套的括号结构推导时要先处理最外层的括号成对匹配再处理内部的逗号分隔。第二个小问“给出句型((T,S),a)的短语、直接短语和句柄”先张成语法树短语对应语法树中任意子树的叶子序列直接短语是那些不能再往下一层退的直接子树叶子序列句柄是最左边那个直接短语。识别句柄有一个工程上的实用技巧在做LR分析时句柄恰好对应即将被规约的那个串。所以我一般会把树画出来后先用肉眼找最左边的那颗深度最小的子树它的叶子一定就是句柄。这个判断方法在考试够用在设计LR分析器时也会反复用到。文法演示用 S → ( L ) | a L → S | L , S画语法树时节点的孩子顺序严格对应产生式右部符号顺序。这个考点对应试者来说很友好但隐含了一个能力要求能在给定的推导序列里快速定位“当前句型的句柄”也就是最左直接短语。3.2 基本块DAG构建与优化后的三地址指令第二道画图题给了一个含多条三地址代码的基本块要求画DAG并做优化。题目给的答案是经过优化后的MF20这是个典型结果说明其背后应该发生了以下几种优化中的某几种公共子表达式消除前者计算A-C的结果在后面的TA-C里被重复计算可以合并。常量折叠与复制传播G2*S这类乘法若S是已知常量可以算成常量。代数化简F*E这类节点如果在DAG中与其他节点结构完全相同就去掉冗余计算。死代码消除题中说“基本块出口时只有M还被引用”所以其它非M计算依赖链上的结果都可以被清理掉。构造DAG的标准步骤是逐一处理每条三地址指令对每个子表达式建立一个内部节点已有相同左右操作数的节点直接复用不新建节点。处理完以后从M作为根节点反向往回追溯凡是M不依赖的节点在优化后的代码里就可以删掉。这样得到的最简序列就是类似DA-C; EA*C; FD*E; MF20这样的结构如果D和E恰好也没有其它引用还能继续简化。这里给一个更小例子来演示DAG节点合并(1) t1 a b (2) t2 a b // 公共子表达式与t1相同的运算 (3) t3 t1 * t2 // 此时t3可直接写为 t1 * t1合并之后第(2)条指令可以被删除因为对t2的赋值不影响任何后续结果假设t2不作为出口活跃变量。DAG优化在期末里是拿分题动手做一遍比背理论要实用得多。很多讲义上讲某道题都会标注“答案写的MF20”意思是本块里前面所有变量只在块内使用编译器根据活跃变量信息把其它赋值全部删掉。提示做这类题时务必先看最后一句“哪个变量还在被引用”再决定保留哪些计算这是决定优化力度的关键。4. 消除左递归、FIRST/FOLLOW集合与LL(1)预测分析表4.1 消除左递归直接左递归和间接左递归的处理方式计算分析题里要求“写一个文法使其语言为……”以及“消除左递归并构造预测分析表”这两项都属于LL(1)文法分析的看家本事。直接左递归的产生式形如A → Aα | β消除时引入新的非终结符A原文法 A → Aα | β 消除后 A → βA A → αA | ε一个常见练习题是E → ET | T消除后变为E → TE和E → TE | ε。间接左递归的处理更繁琐一些需要先对非终结符排序逐层代入后再消除。这里需要区分“提左因子”和“消左递归”前者解决的是FIRST集合冲突后者解决的是无限递归问题两者不是一回事。考场上最常见的失分点是把两者混为一谈直接用提左因子替代消除左递归。4.2 FIRST集合与FOLLOW集合的计算规则构造FIRST集合的规则可以浓缩为三条。第一如果X是终结符那么FIRST(X) {X}第二如果X → ε是一个产生式那么ε加入FIRST(X)第三如果X → Y1Y2...Yn那么把FIRST(Y1)中的非ε元素加入FIRST(X)若FIRST(Y1)含ε再顺延处理Y2直到某个Yi的FIRST不含ε或Y1...Yn全部可推导出ε。FOLLOW集合这边先把$加入FOLLOW(S)S为开始符号然后对每个形如A → αBβ的产生式把FIRST(β)中除ε之外的全部元素加入FOLLOW(B)如果FIRST(β)包含ε或β能推导出ε那么把FOLLOW(A)的全部元素加入FOLLOW(B)。为了便于做题时快速对照我把FIRST和FOLLOW在计算时的差异整理成下面这张表要点FIRST集合FOLLOW集合作用对象产生式右部的符号串非终结符含ε吗可以含ε不含ε初始条件逐个扫描产生式开始符号先放入$核心规则右部首个符号的FIRST加入左部右部某非终结符后紧跟的终结符或FOLLOW(左部)迭代终止条件各集合不再变化各集合不再变化动手做题时用“迭代直到集合不再扩大”的办法比套公式更不容易出错。先初始化再逐条产生式扫描一次次扩充直到某一轮没有任何新增元素计算完成。很多考生直接背诵定义但考场上稍复杂的文法包含间接ε产生式就会算错所以建议至少手算三套习题再上考场。4.3 预测分析表驱动的LL(1)分析何时填移进、何时填规约第三小题构造预测分析表规则也相对固定。对每个产生式A → α先计算FIRST(α)。对FIRST(α)中的每一个终结符a把A → α填入表M[A, a]。如果ε属于FIRST(α)则再对FOLLOW(A)中的每一个符号b把该产生式填入M[A, b]。最后把没有被任何产生式填到的空白格标记为error。设计LL(1)分析器时有一个容易被忽略的点是同一个非终结符在同一个终结符输入下若对应多条产生式就说明文法不是LL(1)。比如对文法E → T E和E → T E | ε当输入为时E对应的两产生式的FIRST集分别是{}和FOLLOW(E)中的元素通常是)或$两者不相交所以表格不会发生冲突。这里也可以顺带理解为什么FIRST集合里要排除ε、为什么要单独用FOLLOW来补位就是为了保证表格每个格子最多只有一个候选产生式。拿到一个不是LL(1)的文法时第一步是尝试左因子提取再检查能不能消除左递归最后再看两个集合是否冲突。全部走完仍然冲突那么这种文法本质上就不是LL(1)文法得考虑改用LR方法分析。这条判断顺序也是面试里经常考察的分析思路。5. SLR分析表构造与正则语言的最小化DFA验证5.1 手推SLR项集族和分析表的完整流程综合题第一部分要求对表达式文法构造SLR自动机的项集族和语法分析表并模拟输入串的处理过程。构造SLR的步骤通常会被简化成五步拓广文法加S → S对每个状态做闭包对每个文法符号做转移根据得到的项集族构造ACTION和GOTO表再检测是否存在移进-规约冲突。这里要特别说明闭包计算的一个极其容易出错的环节当点号出现在非终结符B之前时要把B的所有产生式都加入当前项集在每个产生式前加一个点这就是CLOSURE操作的递归本质。初学的时候容易漏掉嵌套的非终结符比如项E → E . T中的点后面有TT又有自己的产生式这些都要全部展开。对表达式文法E → ET | T、T → T*F | F、F → (E) | id做SLR表时有一个值得注意的现象在某些状态下同一个项集里会出现“点号后跟终结符的移进项”和“点号在末尾的规约项”这时就要用FOLLOW集合来判断是否冲突。如果输入符号在规约项左部的FOLLOW集合里就执行规约如果既是移进符号又是FOLLOW元素就说明该文法不是SLR。计算75的整个分析栈栈顶变化序列时需要关注几个关键节点先在状态0遇到id做移进接着遇到根据ACTION表规约然后GOTO图中的状态迁移链会自动决定E → ET何时触发。这里“何时规约”完全不靠人工直觉而是表格驱动来决定。5.2 正则表达式到NFA再到最小化DFA的标准化推演第二小题是经典正则语言问题由0和1组成、倒数第二个字符为1的所有字符串。这种语言用正则表达式写是(0|1)*1(0|1)。构造识别它的NFA也很直接中间有一条主干路径依次经过三个状态(0|1)*部分在起始状态上用自环最后一个字符走得是双路分支。得到NFA后使用子集构造法确定化为DFA再用划分法最小化。子集构造法的核心不是“模拟NFA”而是对每个状态子集打上表看新读入的每个输入符号会迁移到哪些NFA状态的集合然后不断重复。最小化有一个很实用的小技巧去掉所有不可达状态把终态和非终态分成两个不同组对每个组里的状态观察它们在每个输入符号下迁移到的组是否一致不一致则拆分该组反复执行直到分组稳定。# 用划分法最小化DFA的伪代码框架核心逻辑 states [non_accept, accept] # 初始划分为非终态组和终态组 while changed: changed False new_groups [] for group in states: split {} for state in group: # 以「每个输入符号迁移到的组编号」作为分组键 key tuple(move[state][c] for c in alphabet) split.setdefault(key, []).append(state) if len(split) 1: changed True new_groups.extend(split.values()) states new_groups这段伪代码的逻辑是把DFA的每个状态按转移目标组的编号做一次哈希分组同一组的任意两个状态必须在所有输入符号下落到同一个组里否则再次拆分。这个划分过程是可验证的因为每一步拆分依据都是可观测的转移关系。实际考试里最小化后的DFA通常只剩三个或四个状态终态集里所有状态都可以合并因为它们在任意输入下的转移目标在等价意义上完全一致。做完最小化可以用几个边界字符串验证DFA是否正确“1”应该被接收因为倒数第二位为1时最后一位隐式地可以是空字符不按经典定义倒数第二个字符为1那么字符串长度至少为2所以“1”不应被接受。这个边界条件在考试里很容易被忽略很多复习者以为1也应该被接受实际上长度为1的字符串不存在“倒数第二个字符”所以必须有个初始状态无法直接到达终态。用这个边界用例去检验最小化结果能够立即暴露输入串长度判断上的错误。5.3 用试卷答案去反向验证自己的实现是否正确试卷带有答案这本身就是对复习最有价值的资产。建议把答案盖住先按上述流程独立推一遍再对照答案。对照时不要只看“最后结果对不对”要逐步检查每个状态的项目集闭包是否完整每个FIRST/FOLLOW集合的迭代次数是否足够还有一个最容易丢分的地方是FOLLOW集合中是否忘了把$加入开始符号。另一个值得注意的地方是SLR分析表构造时要确认每个规约动作是否严格使用了FOLLOW集合而不是凭感觉填上reduce。手推SLR表确实很繁琐但正是这种繁琐能把“预测分析”和“LR分析”的机制差异变得具体。预测分析靠一张二维表格加一个栈就能完成语法分析而SLR分析虽然同样依赖表和栈但表的构造过程更复杂——它要处理的是整个项集族表格信息里既包含移进动作又包含规约动作而且必须借助FOLLOW集合来排除部分规约冲突。把这些点串起来之后期末复习和面试准备基本就能形成一个闭环了。本文还有配套的精品资源点击获取