编译原理期末试卷B卷：词法分析、语法分析、SLR建表与DAG优化考点全解析

简介南京信息工程大学2021-2022学年编译原理期末试卷B卷含答案由凌妙根老师任课适合正在学习编译原理或准备期末考试的本科生使用。试卷覆盖词法分析、语法分析、错误处理、语法制导翻译、代码优化、正则表达式与自动机等核心专题题型包括选择题、画图题、计算分析题和综合题能较全面地检测学生对编译器设计与实现的理解程度。资源为单个docx文档大小约1.11MB内容为试卷题目与参考答案排版清晰方便直接打开阅读或打印练习。已有1022人学习下载尤其适用于南京信息工程大学计算机相关专业学生对照复习也可作为其他高校编译原理课程的补充练习。借助其中的非递归预测分析、SLR分析器、DAG优化、NFA/DFA构造等题目读者可进一步巩固关键知识点查漏补缺。1. 编译原理期末试卷这份带答案的B卷能把考点一次对齐期末复习最怕的不是题难而是整本书都翻了却不知道考试真正愿意考什么。编译原理期末试卷就是这种「平时不觉得值钱、考前才想找后悔药」的资源——这份某高校2021—2022学年第1学期的编译原理课程期末试卷B卷含参考答案覆盖面相当标准词法分析、语法分析、错误处理、语法制导翻译、SLR建表、DAG优化、正则语言转DFA全是课程大纲里的硬骨头。适合两类人一类是考前两天想快速定位盲区的学生另一类是需要按考纲出模拟题或验收考点的老师。卷子题量不大但选择题陷阱密度很高五道题几乎全在考「你以为的定义」和「教科书定义」之间的偏差。下面拆开讲。2. 选择题里的四个高频考点从编译器组成到语法制导的时机陷阱2.1 编译器组成部分设备管理为什么是个干扰项第一题问「哪个不是编译程序的组成部分」选项里有词法分析程序、代码生成程序、设备管理程序、语法分析程序。答案C——设备管理程序。这种题在期末卷里出现率极高因为它考的不是记忆而是你对「编译程序边界」有没有清醒认识。编译器从功能上切标准分法是前端和后端词法分析把字符流切成token语法分析按文法构建语法树语义分析做类型检查和属性计算中间代码生成、代码优化、目标代码生成属于后端。设备管理涉及CPU调度、I/O队列、内存分配这些属于操作系统课程的内容和「把高级语言翻译成机器代码」这条主线没有直接关系。我一般建议考生用排除法时先问自己一个问题去掉某个程序编译还能不能完成去掉词法分析token都切不出来去掉语法分析结构对不上去掉设备管理编译器照样翻译——它只是运行在操作系统之上并不是编译器的内部构成。2.2 错误处理策略为什么「立即停止编译」不是主流做法第三题考编译过程中遇到错误怎么办给了四个选项局部纠正、在局部范围内纠正并继续分析、跳过错误所在语法单位继续分析、立即停止编译等用户改完再继续。答案C跳过出错的那个语法单位继续往下分析。这个知识点容易被直觉带偏——很多学生觉得「程序都错了还继续编译干嘛」但编译器设计的真实目标是「一次编译能报告尽可能多的错误」。立即停止意味着每一轮编译只能暴露一个错误用户改完再跑一遍效率极低。工程上常见的做法是错误恢复策略选跳过当前语法单位让分析器回到一个相对安全的状态继续扫描后面的代码。注意这里和解释器有差别。解释器逐行执行遇到错误停止是合理的编译器是批处理模型错误恢复的核心准则是「补偿但不掩盖」——跳过的单位应该是局部独立的不能因为跳过导致符号表信息错乱。考试里如果换成「词法错误、语法错误、语义错误分别在哪个阶段发现」这种变体思路也是一样的错误恢复策略要对应到具体分析阶段的处理机制。2.3 非递归预测分析与语法制导翻译继承属性和综合属性的时机陷阱第四题和第五题串起来看考的是一个完整的知识点带非递归预测分析过程中做翻译栈结构怎么扩展、属性什么时候算。题目里答案D说不正确的是「综合属性在A出现之前就可以计算」。先理清两条属性链。继承属性是父节点在展开非终结符A之前把信息算好下传给A的——所以它一定在A出现之前就有了方向是自顶向下。综合属性是A的子树归约完成后把结果向上返回给父节点的——也就是说A还没归约完综合属性根本不可能算出来。第四题D选项说「综合属性在A出现之前计算」方向完全反了。工程实现上非递归预测分析用的是显式栈栈里存的是文法符号加上每个符号对应的属性记录。继承属性在符号入栈前就要压进记录里综合属性要等符号出栈时才算出并写入记录这就解释了为什么必须扩展语法分析栈而不能只存终结符和非终结符。考试如果改问「栈里除了文法符号还要存什么」答案就是符号对应的属性记录。第五题说的是L-SDDL属性语法制导定义和LR分析的结合。很多人记死了一条「语法制导翻译只限自底向上分析」——这是错的。给定一个LL文法基础上的L-SDD可以修改文法在LR语法分析过程中计算这个新文法上的SDD。具体做法是把内嵌的语义动作替换成标记非终结符MM对应一个空产生式该产生式带一段语义子程序子程序的任务就是执行被替换的那个动作。这样处理后LR分析器遇到M时触发归约语义动作就按预定顺序执行了。这个技巧在自底向上分析器里非常实用因为LR分析的归约点比LL的展开点更容易插入副作用。3. 语法分析大题最左推导、句柄判定与预测分析表一条线3.1 最左推导和语法树按「产生式展开」顺序逐层画画图题第一题给的文法G(S)是典型的括号列表文法S→(T)|aT→T,S|S。这种文法描述的就是「括号包裹的、逗号分隔的元素序列」在表达式列表、参数列表的场景里随处可见。要求给句子(a,(a,a))做最左推导。最左推导的意思是每一步都展开当前句型最左边的非终结符。推导过程我习惯这样写每一行注明用了哪条产生式步骤1: S 步骤2: (T) S→(T) 步骤3: (T,S) T→T,S 步骤4: (S,S) 最左的T→S 步骤5: (a,S) S→a 步骤6: (a,(T)) S→(T) 步骤7: (a,(T,S)) T→T,S 步骤8: (a,(S,S)) 最左的T→S 步骤9: (a,(a,S)) S→a 步骤10: (a,(a,a)) S→a画语法树的时候把推导过程反过来看每个产生式对应一个内部结点产生式左部是父结点右部各符号按顺序是孩子。步骤4中T→S产生的「S」是一个单孩子结点画的时候注意别漏。这一类推导题有一个检查技巧推导完成后把最左推导序列的每一步按「用了哪条产生式」标出最终树的高度和分支就完全确定了。考试时先写推导再画树能避免画完树才发现句子推不出来。3.2 短语、直接短语、句柄三步判定法题目第二问给句型((T,S),a)要求找短语、直接短语和句柄。这是LR分析前最重要的概念题也是丢分重灾区因为「句柄是最左直接短语」这句话背下来没用关键要会看语法树。三步判定法我常用第一步画出该句型对应的语法分析树找所有子树。第二步每棵子树的叶子序列接在一起就是一个相对于该子树根结点的短语。第三步判断哪些短语是由某个产生式一步导出的——也就是说子树根结点的产生式右部恰好就是这串叶子这算直接短语所有直接短语里位置最靠左的那个就是句柄。对句型((T,S),a)语法树里有两棵子树值得注意。最外层S的子树的叶子序列是((T,S),a)这是整句对应的短语。往内看T→(T)这个结点下面叶子序列是(T,S)它是由产生式T→T,S一步导出的所以(T,S)是直接短语。最右边的S→a叶子就是aa也是直接短语。两个直接短语里靠左的是(T,S)所以句柄是(T,S)。注意这题坑很多学生的点是只看到a是直接短语认为句柄就是a忽略了(T,S)位置更靠左。为什么句柄非取最左因为自底向上分析时每一次归约都发生在当前句型的句柄处句柄是「下一次最优先被归约的串」。若句柄判断错后面所有归约步骤全乱。3.3 消除左递归与FIRST/FOLLOW集合以表达式文法为例计算分析题第二题是经典套路消除左递归、求FIRST和FOLLOW、构造预测分析表。我以期末考试最常用的算术表达式文法为例说明这个例子改改覆盖级就能通用。原文法E → E T | T T → T * F | F F → (E) | iE和T都存在直接左递归。消除直接左递归的标准做法是把「A→Aα|β」改写成「A→βA、A→αA|ε」。代入E → T E E → T E | ε T → F T T → * F T | ε F → (E) | iFIRST集合的计算有固定顺序先处理只以终结符开头的产生式再处理引入ε的产生式最后处理非终结符开头的情况。算下来FIRST(F) { (, i }FIRST(T) { *, ε }FIRST(T) FIRST(F) { (, i }FIRST(E) { , ε }FIRST(E) FIRST(T) { (, i }FOLLOW集合的计算规则三条缺一不可。规则一A→αBβ把FIRST(β)去掉ε后加入FOLLOW(B)。规则二A→αB把FOLLOW(A)加入FOLLOW(B)。规则三A→αBβ且β能推出ε把FOLLOW(A)也加入FOLLOW(B)。实际推导FOLLOW(E)初始为{$}又F→(E)使得E后面跟)所以FOLLOW(E){$,)}FOLLOW(E)FOLLOW(E){$,)}因为E在E→TE尾部FOLLOW(T)E→TE中T后跟EFIRST(E)去掉ε是{}再加FOLLOW(E)所以FOLLOW(T){,$,)}FOLLOW(T)FOLLOW(T){,$,)}FOLLOW(F)T→FT中F后跟FIRST(T)去掉ε即{}再加FOLLOW(T)最后FOLLOW(F){,,$,)}这里最容易漏的是FOLLOW(T)里少了「)」——原因是用规则一时只注意了忘了ε传播也要把FOLLOW(E)并进来。这类题失分几乎都发生在ε的处理上。3.4 预测分析表的构造冲突意味着什么有了FIRST和FOLLOW预测分析表是机械填充。行是非终结符列是终结符加$。填表规则两条对每个产生式A→α把α的FIRST集合里每个终结符a对应的格子填上这条产生式。如果α能推出ε再把FOLLOW(A)里每个终结符b对应的格子填上A→α。按这个规则填出来的表里若某个格子出现两条产生式就叫冲突意味着这个文法不是LL(1)文法。考试中常见的冲突位置就在E、T两行——若前面FOLLOW算错这里就会出现错误的多重定义。预测分析表和LR分析表完全不同预测分析表靠「看下一个token选产生式」驱动是自顶向下LR分析表靠「状态转移动作」驱动是自底向上。做综合题时先分清楚表类型避免把SLR的移进归约概念套到预测分析表上。4. DAG优化与SLR建表两道综合题的拆解套路4.1 基本块DAG构造公共子表达式与常量折叠怎么合画图题第二题给了一个基本块语句有十几条要求画DAG并优化。先看原语句序列D A - C E A * C F D * E S 2 T A - C Q A * C G 2 * S J T * Q K G * 5 L K J M LDAG构造的顺序规则我一般按三步走。第一步每个变量名对应一个叶子或内部结点赋值语句右侧的操作数先从已有节点里找找不到再新建。第二步相同运算且操作数相同的表达式直接复用已有节点不再新建把新的目标变量名挂到该节点上去。第三步遇到常量表达式立刻计算结果作为常量节点。按这个规则扫一遍A-C第一次出现建节点标上DAC建节点标EDE建节点标F。S2是常量节点。第5条TA-C操作数A和C、运算符减号都对应已有节点所以T直接挂到那个减号节点上。Q同理挂到乘号节点。G2SS是常量2224常量折叠成4。JTQT对应减号节点、Q对应乘号节点TQ就是那个DE节点上的结果所以J也挂到该节点。KG5G是常量44*520直接折叠成常量20。LKJ就是20加F节点的值。DAG的图画出来后节点表大概是操作节点代表挂载变量A-C减号节点1D, TA*C乘号节点2E, QD*E乘号节点3F, J2常量节点S4常量节点(2*2)G20常量节点(4*5)KF20加法节点L, M4.2 优化后三地址代码只有M活着的约束题目额外给了一个条件基本块出口时只有M还被引用。这意味着优化后的三地址指令序列里那些只服务于死变量的语句可以直接删掉。DAG里已经能看出所有公共子表达式都合并了D和T是同一个值E和Q是同一个值J和F是同一个值。S、G、K这些中间变量在出口处不再被引用所以它们的赋值语句不生成代码。KG*5折叠成20之后K本身没用了但20要留下来参与L的运算。LKJ就是20FML也是同一个值最终出口要的是M所以只需要一条加法指令把F加20赋给M。优化后的三地址指令序列就是卷子答案里那四条D A - C E A * C F D * E M F 20注意输出顺序有讲究D、E、F的赋值必须保留因为M的计算依赖FF依赖D和ED和E依赖A和C。DAG生成代码的顺序本质上是拓扑序——一个节点的值在被引用之前必须先计算出来。如果DAG里有节点不被任何活跃变量引用直接跳过它这对应死代码消除。4.3 SLR项集族与语法分析表从文法到表的一步步怎么走综合题第一题给了一个带L属性文法的算术表达式文法要求用SLR自动机做自底向上的分析构造项集族和语法分析表还要对输入串75画出语法制导翻译的栈过程。SLR分析表的构造流程非常机械考的就是流程完整性。先给文法做增广比如E→ET|T、T→(E)|i这类文法增广产生式S→E。然后从初始项[S→·E]开始闭包逐步构造LR(0)项集族。每个项集看遇到什么符号转移再对归约项求FOLLOW集合来判断归约的时机。SLR分析表的填表规则对每个移进项写shift到对应项集对每个归约项A→α在FOLLOW(A)里的每个终结符列上写归约动作对接受项在$列写acc。如果同一格子既有移进又有归约说明存在移进-归约冲突。SLR解决冲突的方式就是查FOLLOW集合冲突项若在FOLLOW里没有对应终结符这个冲突可以消除如果FOLLOW也覆盖了就得换LALR或调整文法。输入串75的语法制导翻译栈过程考察的是行动执行顺序。栈里除了状态号和文法符号还要挂属性值。分析器每次移进一个终结符时把token的lex值压入属性栈归约到非终结符时按产生式对应的语义动作计算综合属性。比如数字7被归约为T再归约为E时值7一层层向上传遇到号触发E的产生式时执行加法并生成中间代码或计算结果。画栈过程图时行与行之间标注清楚当前输入指针位置和动作类型表头分别是步骤、状态栈、符号栈、输入串、动作。这类综合题分值高但套路固定。只要项集族画对、FOLLOW集算对、表填对动作模拟按表格一步步走得分率其实比选择题高得多。5. 避坑指南这套卷子里最容易翻车的五个细节5.1 句柄选错把任意直接短语当句柄现象句柄判断时选了句子中最右边的直接短语或者选了最长短语丢分后才发现与标准答案不一致。原因背诵时把「句柄是最左直接短语」记成了「句柄是直接短语」忽略了最左限定。自底向上分析中句柄决定当前归约位置选错直接导致归约路径错乱。解决每道句柄题都固定走三步——先画树再列全部子树叶子串作为候选短语然后标出哪些是由单条产生式一步导出的直接短语最后在所有直接短语里取位置最左边的。宁可多写两句判定过程不要只写一个答案。从那以后我做句柄题都强制自己列出全部直接短语再选。5.2 FOLLOW集合漏掉ε传播现象算FOLLOW(T)时只写了「」漏了「)」导致预测分析表T行缺项后面LR分析也跟着错。原因规则三使用不熟。A→αBβ且β能推出ε时FOLLOW(A)要并入FOLLOW(B)。很多人算完FIRST就开始机械套规则一忽略了「β可空」这个前提条件要逐个检查。解决算FOLLOW前先列一个「可空非终结符清单」把所有能推出ε的非终结符圈出来。然后每一步应用规则三时先问β是否在这个清单里。考试时间允许的话用依赖图的形式把FOLLOW的传递关系画出来能直观看到谁传给谁。5.3 DAG合并时忽略变量被重新赋值现象DAG构造时看到TA-C和DA-C就合并节点结果题目里后续又有新的赋值覆盖了D优化后的代码引用了错误的值。原因DAG合并的前提是操作数在当前点仍然有效。如果某个变量在两条语句之间被重新赋值原节点代表的旧值已经失效不能再挂新的目标变量名。解决按语句顺序逐个处理每次合并前检查操作数对应的变量定义点是否被覆盖过。遇到变量重新赋值必须先让该变量指向新节点再考虑复用。这道题没这个坑但很多改造题专门在这里设陷阱。5.4 SLR表出现移进-归约冲突时不知怎么办现象构造SLR分析表时某个项集里归约项和移进项指向同一格子直接把表判定为不可构造。原因SLR本身就是为了消除部分冲突才用FOLLOW集合做判断。冲突出现时要看归约项左部的FOLLOW集合是否包含移进符号不包含冲突成立这个文法不是SLR(1)文法。解决先列冲突项再列出归约左部非终结符的FOLLOW集合逐一比对。若FOLLOW和移进符号不相交说明前面FOLLOW算错了回头检查计算过程若相交说明该文法确实不满足SLR条件再考虑优先级或改写文法。5.5 NFA转DFA后没删不可达状态就最小化现象最小化DFA得到的状态数总比标准答案多对不上。原因把NFA确定化得到的DFA直接拿去做划分没有先删除从初态不可达的状态。DFA里有些状态在NFA确定化时产生但从初始状态没有任何路径能到达它们它们参与划分会干扰等价类的合并。解决确定化之后先做一步可达性标记——从初态出发BFS标记所有可达状态删除不可达状态然后再做状态等价类划分。这步虽然只有几分钟工作量但直接影响最终最小化结果。6. 把这套卷子复刷三遍从限时自测到反向出题拿到一套带答案的期末卷只做一遍就放下信息利用率大概只有三成。我把这套卷子的正确用法拆成三遍每一遍的侧重点完全不同。第一遍是限时自测。严格按120分钟闭卷做选择题也闭卷蒙不翻书不查资料。做完先不对答案把每道题旁边写上「我当时为什么这么选」再对照参考答案。这一步的目的不是得分而是把「我以为我会」和「我真的会」之间的差距暴露出来。画图题和综合题如果卡住别直接看答案先标记卡点位置——是点集族不会构造还是FOLLOW算到一半断了。这张卷子做下来你的知识盲区基本全在题目旁边标注清楚了。第二遍是按考点归类。把错题对应的考点整理成一张表考点对应题型易错位置复习动作错误处理策略选择题跳过与停止的取舍重读错误恢复章节属性计算时机选择题综合/继承属性方向手写一遍SDT栈过程句柄判定画图题直接短语与最左限定再造三个句型练判定FIRST/FOLLOW计算题ε传播与FOLLOW传递独立重算全部集合DAG合并画图题常量折叠与死变量删除换数据重新构图SLR建表综合题归约动作的FOLLOW判定重写项集族第三遍是反向出题。把卷子里的文法、基本块、正则语言描述换一组数据自己出一份变体卷。句子(a,(a,a))换成(b,((b,b),b))表达式文法E→ET|T换成E→E*T|TDAG里的常量2换成3或4。然后不看答案按第二遍的解题流程重做。这遍做完你才算真正掌握了这套卷子里所有题型的可迁移方法。有一次我拿到一套旧卷直接背答案结果考试时把句子换了个括号嵌套层级我就卡住了——因为背的是那一道题的推导过程不是推导方法。从那以后我每次拿到带答案的卷子都强制自己先闭卷做一遍、再按考点归类、再改一组数据重做一遍直到这三遍走完才敢说这份卷子真的吞透了。这套流程同样推荐给你希望帮到你。本文还有配套的精品资源点击获取