《编译原理》-习题复习

提示：文章写完后，目录可以自动生成，如何生成可

前言

第一章：绪论

考点1.编译过程的组成

题目描述：

解题思路：

类似题：

第二章：文法和语言

考点1.符号串

题目描述：

解题思路：

考点2.构造文法

题目描述：

解题思路：

类似题：

考点3.推导与语法树

题目描述：

知识拓展：

解题思路：

类似题

考点4.二义性文法：

题目描述：

解题思路：

类似题

考点5.短语和句柄

题目描述：

解题思路：

类似题

考点6.将文法化简

题目描述：

解题思路：

第三章：词法分析

考点1.右线型文法及状态转换图

题目1描述

解题思路：

题目2描述

解题思路：

考点2.状态转换矩阵

题目描述：

解题思路：

考点3.NFA的确定化和DFA最小化🌟🌟

题目1描述：

知识拓展：

解题思路：

题目2描述：

解题思路：

题目3描述：

解题思路：

题目4描述：

解题思路：

第四章：语法分析

考点1.消除左递归

题目描述：

解题思路：

考点2.求First集和Follow集

题目描述：

解题思路：

考点3.验证LL（1）文法

题目描述：

解题思路：

考点4.书写LL（1）文法以及构建LL（1）分析表

题目描述：

解题思路：

考点5.项目集规范族以及LR（0）分析表🌟

题目1描述：

解题思路：

题目2描述：

解题思路：

考点6.SLR（1）文法及其分析表

题目1描述：

解题思路：

题目2描述：

解题思路：

考点7.LR（1）文法及其分析表

题目描述：

解题思路：

考点8.LALR（1）文法

题目描述：

解题思路：

小总结：各个文法的判定方法

第五、六章：语法制导翻译及中间代码生成

考点1.逆波兰式（后缀表达式）

题目1描述：

解题思路：

题目2描述：

解题思路：

考点2.语法制导的翻译

题目1描述：

解题思路：

题目2描述：

解题思路：

题目3描述：

解题思路：

考点3.画注释分析树

题目1描述

解题思路

题目2描述

解题思路

第七章：运行时刻环境

考点1.参数传递

题目描述

解题思路

考点2.活动记录

题目描述

解题思路

第八章：代码生成

考点1.基本块和流图、流图中的循环、局部优化、循环优化

题目描述

解题思路

1.划分基本块

2.画流图

3.局部优化

​编辑

4.循环优化

​编辑

考点2.DAG图及其优化

题目描述

解题思路

考点3.活跃变量的计算

题目描述

解题思路

考点4.线性扫描算法

题目描述

解题思路

考点5.图着色算法

题目描述

解题思路

总结

前言

博主近期开始了编译原理这门课的复习，在大致地过了一遍基础内容后，我决定开始对于题的练习，今天看了b站上的up主“废物点心v”的题目讲解后，做出了大致的总结。本篇文章仅充当学习分享，如有谬误尽情指正。

ps：！！！！！！！！！！！！！！！！！！！！！

b站视频链接：第一章 绪论_哔哩哔哩_bilibili

我今天的主要内容就是基于上面这个视频来的。up讲的很不错，方法很明了清晰！

（如果后续博主在复习过程中发现有新的题型会尽量添加）

本篇文章大致思路如下：

12.19号更新，今天更新了后面几章的习题复习，现也将b站视频的链接给出：
【编译原理期末版】第五章 语法制导翻译（2），构造注释分析树，计算翻译结果，指出语义功能_哔哩哔哩_bilibili

第一章：绪论

考点1.编译过程的组成

题目描述：

解题思路：

这个没什么好讲的，记住图上的那几步就行，各个步骤的作用最好也要搞清楚（知道大致的就好，不用扣字眼）。

类似题：

答：

第二章：文法和语言

考点1.符号串

题目描述：

解题思路：

这里跟离散数学里的笛卡尔积道理是相通的，AB的结果是左边的元素来自A，右边的元素来自B。这里要注意一下正闭包和自反传递闭包的概念，记住正闭包加上一个空串就等于自反传递闭包就好。

关于第三问，过程如下：

考点2.构造文法

题目描述：

解题思路：

首先要明白文法是个四元组，四个元素分别是非终结符集，终结符集，产生式集，开始符号。

这一道题的意思是让我们自己来书写文法，包括要书写产生式（核心），非终结符（自己创造），终结符（从题目中读取），使得通过我们所写的文法可以推导出题目所示的语言，此题看图中up主的解法就可以了。我认为此类题需要多加练习才能熟练地写出这类文法。

类似题：

考点3.推导与语法树

题目描述：

知识拓展：

最左（右）推导与最右（左）归约互为逆过程，其中，最右推导和最左归约分别称为规范推导和规范规约，在答题时尽量采取这两种方式。

解题思路：

最左推导和最右推导还是比较好理解的，不断替换最左边（最右边）的非终结符（大写字母）就可以了。

第一问没啥好讲的，第二问up主的思路是先看串的最后一位（d），再回过头去看文法，发现没有哪个产生式的末尾能产生d，所以判断出其不是该文法句子。

类似题

考点4.二义性文法：

题目描述：

解题思路：

1. 画语法树
2. 通过树来找出特例来证明二义性

二义性的直接判断方法是判断某个句子是否有两颗语法树。

博主画语法树的流程是先将所有的S作为根，再依次往下面画。

通过两个S的语法树可以判断出二者均可以产生abc这个句子，故其具有二义性。

类似题

考点5.短语和句柄

题目描述：

解题思路：

up主第二问的答案有部分问题，我在下面会给出修正。

最右推导的过程就不讲了，这里着重说一下如何通过语法树来判断短语，直接短语，句柄：

ps：树相关的定义看上面考点三的知识拓展部分👆

类似题

考点6.将文法化简

题目描述：

解题思路：

核心：如果一个非终结符不能推出终结符，那么就把含有它的式子删掉

第三章：词法分析

考点1.右线型文法及状态转换图

题目1描述

解题思路：

首先注意右线型文法，其特点是非终结符只能在右边，终结符在左边，正规文法包含右线型文法。

只有右线型文法才有状态转换图。画图时将终结符放在线上面，终点用两层圈。

等价：设计另外一个文法，使得最后推出的句子与原来相同

up的流程：

• 把原来的文法的语法树画出来
• 观察叶子，发现最终句子的组成是,所以以此为基础，开始构造新的文法
• 先画状态转换图再写右线型文法（这样更简单）
• up没有讲为什么状态转化图要那么画，我的理解是直接背，如果想构造出的话就像图上那样就行
• 写右线型文法时，将箭头上的放左边，箭头指向的放右边

题目2描述

解题思路：

与上一题思路相同，需要注意的如下：

• 找最短输入串就看初态A到终态E或F哪条路是最短的。
• 接受就是从A开始走能到终态，拒绝就是不能到

考点2.状态转换矩阵

题目描述：

解题思路：

这道题整体比较简单，只是需要注意：

• 状态转换矩阵上面的是终结符，左边的是非终结符，像图中第一个非终结符A的“坐标”为 （S，a）就说明S可以通过a到A（语言描述起来很抽象，看看up的解题答案应该就好理解了）。
• 3型文法即为正规文法，包含右线型文法，所以这里其实就是让根据状态转换图写右线型文法

考点3.NFA的确定化和DFA最小化🌟🌟

大部分题型都在这个考点下

题目1描述：

知识拓展：

NFA（非确定性有限自动机）的确定化就是将其转换为等价的确定性有限自动机（DFA）的过程。所以这个考点也叫做NFA与DFA的转化。

最小化是指将DFA（确定性有限自动机）中的状态数目减少到最小的过程。说白了就是化简DFA的图。

所以确定化是针对NFA的，最小化是针对DFA的

解题思路：

上面是up主给出的流程，下面我将针对题给出解释：

up主的答案

 若可合并，则将二者视为一个，在表中删除一行再画表。比如上述第二题中q1和q3不可区分，则二者可合并，可以选择在表中删除q3那一行（也可以选q1），最后就只剩下q0,q1,q2三个状态，再接着画图。

注意：终态集和非终态集都要进行是否可区分的检测。

题目2描述：

解题思路：

这题跟上面的唯一区别就是含有空串，注意closure的定义即可，剩余操作与上面一样，这里没有让最小化，所以画出表了之后就可以画状态转换图了。

题目3描述：

解题思路：

第一步：先进行化简，化简的依据是看某个状态是否在之前出现过。图中被划掉的就是化简之后不要的状态，比如状态4，在它上面的行没有出现过状态4，所以将其划掉。

第二步：跟上面几道题最小化的步骤一样，先划分出终态集和非终态集，然后去找两个集中是否有不可区分的状态，有的话就要合并

第三步：画图

题目4描述：

解题思路：

这道题跟之前的不太一样，原因是涉及到了正规文法，接下来我将针对up的解法给出我的解释：

首先，明白正规式的特点就是非终结符由·   *  ｜这三种符号连接的，而我们要做的，就是针对由这三种连接符号连接的式子进行不同的分裂，分裂的方法up主已经给出，就是图中的序号圈123。

图画出来之后就只需要进行按照之前的办法进行常规的确定化和最小化了，这个过程我就不写了。

第四章：语法分析

重点内容一览：

LL分析和LR分析是考察重点，注意LR(1)包含LALR（1）包含SLR（1）包含LR（0），所以，如果一个文法是LR（0）文法，那么它就也是LR(1)，LALR（1），SLR（1）文法。

考点1.消除左递归

题目描述：

解题思路：

套up主圈出来的公式就行

考点2.求First集和Follow集

题目描述：

解题思路：

up主的求解办法：

在这里分享一个我之前学习基础知识的时候了解到的方法：

如果在求follow集的时候发现非终结符的右边啥也没有，那它的follow集就等于该产生式箭头左边那个元素的follow集。

考点3.验证LL（1）文法

题目描述：

解题思路：

注意：终结符的first集是其本身，终结符和非终结符组合放在一起，如果终结符在前面，那这个组合的first集也是这个终结符。所以在up主给出的第一个题中，fD的first集是放在前面的f，f的first集是其本身，二者有交集，故不为LL（1）文法。

考点4.书写LL（1）文法以及构建LL（1）分析表

题目描述：

解题思路：

第一问：原本的文法容易发现是有左递归的，要想构成LL（1）文法，那就消除左递归就行，所以按照之前教的消除左递归的公示来重新构造就行了。

第二问：

up列的步骤大概够清晰了，需要注意的是什么时候需要求follow集：当左边的式子推出空串时，别的就是需要注意一下first集和follow集的求法，特别是注意求first集和follow集的对象都是产生式右边的式子。

这里有一篇别人的博客，可以参考参考，讲的也比较清楚。

编译原理LL(1)预测分析表的构造_编译原理预测分析表怎么画的-CSDN博客

考点5.项目集规范族以及LR（0）分析表🌟

这里很重要，后面的题几乎都会用到这个考点的知识！

题目1描述：

解题思路：

第一步：先写出拓广文法（加个S'）

第二步：列出项目集族

第三步：写出LR（0）分析表，也叫action-goto表

以下是我对于过程的部分解释：

我的过程并不完整，完整内容参照up的给出的答案。

同样，由于篇幅受限，我只给出了部分核心过程的解释。

除此之外，注意LR（0）文法的特征是不含冲突（怎么样叫含有冲突下面会讲）。此处的文法不含冲突，所以它是LR（0）文法。

什么叫不含冲突呢？

如果你在一个项目集（同一个I里面）中发现同时含有移进产生式和规约产生式（移进-归约冲突），或者含有两个不同的归约产生式（归约-归约冲突），那么这就叫含有冲突。

题目2描述：

解题思路：

核心方法同上，验证不含冲突即可。

考点6.SLR（1）文法及其分析表

题目1描述：

解题思路：

构造规范集规范族的基本思路都是跟LR（0）差不多的。

若移进与归约冲突项目的左边的follow集有交集，那么它就是SLR（1）文法。

此外，此题并未体现SLR（1）文法构造分析表的方法，有想知道的可以看看下面这篇博客：
构造SLR(1)分析表_slr分析表-CSDN博客

题目2描述：

解题思路：

注意一下LL（1）文法和SLR（1）文法的判断方法即可。

考点7.LR（1）文法及其分析表

题目描述：

解题思路：

下面我将解释部分向前搜索符是如何确定的：

 此处展示了I0中向前搜索符是如何确定的，其余的项目集方法相同。

修正：这里有个地方写错了，右边部分倒数第二行应该是求A#的first集

LR（1）只会出现归约-归约冲突。

分析表跟之前的分支表制作方法是一样的。

分析过程在考试的时候一般不会要求写。

考点8.LALR（1）文法

题目描述：

解题思路：

注意判断LALR（1）文法的方法：在LR（1）得到的项目集族中合并同心集后没有归约-归约冲突。

什么是同心集？

（所有）产生式相同，向前搜索符不同的项目集

怎样合并？

取并集，向前搜索符取多的那一个

小总结：各个文法的判定方法

四种文法的包含关系：

相关博客： 

编译原理之LL(1) 、LR(0)、SLR、LR(1)、LALR文法的对比_lr0和lr1的区别-CSDN博客

• LR（0）：不含冲突（移进-归约，归约-归约），换句话说它不能解决冲突，所以是范围最小的一个。
• SLR：不存在归约-归约冲突，有可能存在移进-归约冲突，但是如果可以用 follow集解决则是 SLR文法。

• LALR（1）：合并同心集不会产生新的移进-归约冲突，但是会产生新的归约-归约冲突，如果没产生冲突就是 LALR 文法，反之不是。
• LR（1）：因为 LR(1)文法的范围比较大，所以文法几乎都是 LR(1)的，现在知道的只有当合并同心集产生了归约-归约冲突时才只属于LR(1)文法，而不属于其他文法。

第五、六章：语法制导翻译及中间代码生成

考点1.逆波兰式（后缀表达式）

题目1描述：

解题思路：

跟着up的公示套就行，这里需要注意的是转移操作符：

补充一种更为保险的方法

题目2描述：

解题思路：

方法与上面一样，只不过是倒着来。 

考点2.语法制导的翻译

题目1描述：

解题思路：

注意up主给出的四元式序列的定义即可。这道题比较好理解，最常考的是下面的几种题。

三地址码：

题目2描述：

解题思路：

先明确jnz和j这两个四元式序列的含义。

在写四元式最后一项的时候，只有第一个真出口和第一个假出口是可以确定的（也就是第2，3式子的第四项的两个0，表示如果A为假，那么整个式子都为假了，可以直接跳出，后面都不用判断了；如果B为真，那么后面的也不用判断了，必定全真，故也可以直接跳出。），其余式子的第四项要写完最后一个序列后从后往前推，方法是真出口与真出口相连，假出口与假出口相连。

如果觉得语言难以直接理解的话可以再看看视频。

题目3描述：

解题思路：

这道题就需要用到上面那道题布尔表达式中的第二个四元组序列了。

注意操作符的表达方式：J+操作符

考点3.画注释分析树

题目1描述

解题思路

 从最下面开始，将综合属性往上面推就可以了。

题目2描述

解题思路

 先根据属性文法将能填的的综合属性都填了，再根据相应的计算方法算出各自的综合属性和继承属性。

第七章：运行时刻环境

考点1.参数传递

题目描述

解题思路

考点2.活动记录

看这篇文章：编译原理【运行时环境】—什么是活动记录、 活动记录与汇编代码的关系_编译原理活动记录-CSDN博客

题目描述

解题思路

活动记录的组成

第八章：代码生成

考点1.基本块和流图、流图中的循环、局部优化、循环优化

视频链接：中间代码优化习题讲解_哔哩哔哩_bilibili

题目描述

解题思路

1.划分基本块

划分原则 ：

• 代码第一条是一个基本块的入口，如图中标红的L1
• 条件/无条件跳转语句的目标语句是一个入口，如图中标红的L4，L17，L2
• 条件跳转语句的下一条语句是个入口，如图中标红的L3（它是L2的下一条语句）

2.画流图

画法：

按着跳转的逻辑走画箭头就行，注意条件跳转块应该有两个出口。

3.局部优化

删除公共子表达式：相同的表达式用之前出现过的字母代替

复写传播：代替之后别的地方的名字也要改

死代码删除：代替的那一句可以删掉了

4.循环优化

代码外提

 没必要参与循环的提到外面去

强度削弱

乘法变加法

 归纳变量（i）删除

考点2.DAG图及其优化

参考博客链接：

《编译原理》画 DAG 图与求优化后的 4 元式代码- 例题解析_编译原理dag图-CSDN博客

参考视频链接：

【ErikTse】编译原理 | 基本块转化DAG及其优化后的三元代码序列_哔哩哔哩_bilibili

题目描述

解题思路

考点3.活跃变量的计算

题目描述

解题思路

考点4.线性扫描算法

题目描述

解题思路

建议看这篇文章：寄存器分配——线性扫描(linear scan) - 知乎

1.写出各个变量生存周期 （活跃区间）（从开始赋值到最后一次引用）。

2.每次溢出最晚结束的那一个变量

考点5.图着色算法

题目描述

解题思路

看这篇：https://www.cnblogs.com/AANA/p/16315859.html

总结

本篇文章适合看了up主视频的伙伴用来进行复习

再贴一次up的视频：第一章 绪论_哔哩哔哩_bilibili

之后的几个知识点博主还未来得及放上一些类似题，如果后面找到了会进行一些推荐。

希望这篇文章对你有用的。

12.19号更新了后面几章的习题内容，参阅了不同的资料，均已指明引用。文章来源地址https://www.toymoban.com/news/detail-771485.html

到了这里，关于《编译原理》-习题复习的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！