凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

编译原理【国防科技大学网课】【笔记】【陈火旺】 ——用于期末考试【持续更新ing】_编译原理陈火旺

作者：凡人多烦事01 | 2024-04-29 13:03:48

踩

编译原理陈火旺

期末考试复习试题
第一章：绪论
第二章：高级语言及其语法描述
第三章：词法分析
第四章：语法分析——自上而下分析
第五章：语法分析——自底向上的分析
第六章：属性文法和语法制导翻译
第七章语义分析和中间代码产生

电子书链接：

期末考试复习试题

第一章：绪论

编译器的五个工作步骤、功能、五个核心的模块、出错管理

第二章：高级语言及其语法描述

2.1 基本符号概念

在这里插入图片描述
注意：

1 . AB就是笛卡尔

2 . 自反传递闭包* 是有空串的 A^0 就是空串

在这里插入图片描述

本题注意自反传递闭包是有空串的 A^0 就是空串

2.2 上下文无关文法G是一个四元式

构造文法时，先写产生式S->ab| ϵ 然后写出四元式
ϵ 不是非终结符集里的
非终结符一般大写A，终结符小写a
右部叫做候选式

在这里插入图片描述

2.3 推导和规约、语法树（子树、直接子树）

在这里插入图片描述

2问第一个产生式不能推出d，第二个虽然有d但是S一直存在，死循环，因此不是文法的句子

2.4 二义性文法判断

在这里插入图片描述

二义性文法：某一句子可以由两颗语法树推出

2.5 短语、直接短语、句柄、素短语

在这里插入图片描述

做题方法：先画出语法树，然后根据语法树写出最右推到，再自下而上找出每一步的句柄（采用剪枝法），注意题目中是求每一步推导的句柄还是整棵语法树的句柄？

求句柄时：是求每一步推导的句柄还是整棵语法树的句柄；

一个语法树对应一个句柄，
如果求每一步推导的句柄注意写的顺序要按照推导顺序

在这里插入图片描述

注意这里求的是每一步推导的句柄，而我们分析用的是自下而上，最后要倒过来写才与推导顺序一致

2.6 化简文法

在这里插入图片描述

就是删掉死循环、没用到的产生式
删空串产生式
删A->B单产生式

在这里插入图片描述

第三章：词法分析

用户的词是不是合法的词

基础知识

3.1 右线性文法、状态转换图

在这里插入图片描述
3型文法就是正规文法、右线性文法A->aB 以及A-〉a

例题
在这里插入图片描述

解题步骤：
根据语法树知道文法结果，然后根据语法结果画出等价的状态图，然后由状态转换图写出最右线性文法（一系列产生式），注意有两种写法

圈里面的A、B并不是文法里面的A、B，这里的A、B、C你也可以写成1、2、3，只是个标号
大C是自己设的，这个状态转换图是自己构造出来的，只要可以产生an bm ck就行！
注意，在终态的写法

在这里插入图片描述

注意这里C->0A|1F|1 1F是F作为中间状态，1是F为终态

在这里插入图片描述
输入串的特征是，任意以b开头，中间任意个a，后面跟一个b，然后由a或b结尾的字符串

最后终态的ab 分开画成两个，清晰！

3.2 NFA的确定化和最小化

一、先将正规式转换成NFA
在这里插入图片描述
二、再将NFA转成DFA（子集法）

做表的过程中，关键的就是求每个状态的ϵ 闭包——从该状态出发经历ϵ 所能到达所有的状态的集合
新的终态就是包含原先终态的状态
表中的空不用记为新状态，不用新写一行

三、DFA的最小化
什么是最小化，为什么要最小化？
在这里插入图片描述
怎么做？用一个例题来讲解这篇讲的很好

什么叫不同？不属于同一个状态集合，需要再次划分；相同就是属于同一个状态集合，无需划分，最后需要合并成一个状态表示。
注意：最后还要删除多余状态

例题：考前做几道理解一下
在这里插入图片描述

考点：DFA与NFA的区别（老师强调）

起始状态：NFA的起始状态是一个集合
映射规则：DFA的转换箭头上的标签必须是字母表中的，但NFA可以有标识为ϵ 的边，NFA的状态可能有零条、一条甚至多条ϵ 边。
转换关系：DFA同一状态接受同一事件可以到达不同状态

第四章：语法分析——自上而下分析

期末复习建议直接看这里：

在这里插入图片描述

有一定基础看这个视频！理解两种推到方式

4.1 求First（α）首符号集、Follow（B）后跟符号集

定义

First（E）表示所有能表示为E的终结符串的开头符号的集合

找最左边可能出现的终结符
规则如下：

找最左边可能出现的终结符，递归地找（画一颗树理解！！）
如果要求的First集合能推出e空串，也要加到首符号集中

以例题讲解
在这里插入图片描述

求Follow（B）后跟符号集

定义

即找所有可能跟在B后面所能跟的所有终结符或结束符#，口诀 看右边

规则

开始默认 # 放入follow（S）
若 A-》αBβ，把First（β）-{e} 属于follow（B）（把右边β的首字符集删除空串e加入follow B）
若A-》αB ，或者A-》αBβ，其中β可以推出空串e（First（β）里有e），需要follow（A）加入follow（B）（也是看右边，最终都是累加到右边的B的follow集上的）

上面讲得可能还是有点乱，多读几遍，直接记忆下面这个方法！看右边！

总结：看右边，就是我们看文法右边，找我们要求的非终结符B的Follow，哪里出现了B，看B后面跟的是哪个符号？A->αBβ

如果是跟的β是终结符，直接β放入Follow(B)集（仅放入一个如 S-》Abc follow A ={b} ）；
如果是跟的β是非终结符，看Firstβ集是什么样的，如果里面有空串e（β可以推出e），一要把First β中的空串e去掉之后放入Follow(B)（如 A-》αBβ ,β->C|e 求Follow（B））；二是要左步的的followA 放进Follow（B）

下面的图示也比较清晰，只是A B 翻过来了，上面的是根据我的理解容易记忆的写法
在这里插入图片描述
例题：

4.2 LL（1）文法（自顶向下的分析）

首先LL1文法的判定只针对有两条产生式的非终结符如A->α A->β

先明确select(A->α)t选择符号集的定义

当我们拿到一个非终结符时候，遇到哪些输入符号时候可以进行推导，将这些符号成为一个产生式的select集，意为遇到这些符号时选择这一产生式！

例题：同上
在这里插入图片描述

如果=》右侧不能广义推导出空串e，就=右部的First集
如果=》右侧可以广义推到出空串e，就=右部的First集-{e} 并上 Follow A

总结select求法：

对于明显右部以明确的终结符开头+ *，如F-》（E）指的是F遇到(采用该产生式进行推导，意为遇到这些符号时选择这一产生式！所以就是 {（}
其他的还是记公式吧！！！

下面是LL1型文法的定义

L表明自顶向下分析是从左向右扫描输入串
第2个L表明分析过程中将用最左到推倒,
1表明只需向右看一个符号便可决定如何推倒即选择哪个产生式(规则)进行推导,类似也可以有LL(k)文法,也就是需要向前查看k个符号才能确定选用哪个产生式

LL1型文法的判定

首先文法无左递归
只看含相同左部的产生式（如 E->+E|e），可选集合select的交集，均为空集合（拆成E->+E 和 E->e），则文法为LL1文法

4.2.1非LL1文法到LL1文法的等价转换（不一定都能转换）

方法一：提取左公因子

在这里插入图片描述

方法二、消除直接左递归——背公式【注意空串e】

我们只学消除直接左递归；注意空串
在这里插入图片描述

例题
在这里插入图片描述

4.2.2 判断LL（1）文法—求相同左步产生式的Select集的交集

下面还有一种判断方法，其实就是同一个意思，用select方法方便理解，虽然挺浪费时间。。。。建议掌握下面的
在这里插入图片描述

4.2.3 LL（1）分析的实现

递归下降的分析（一种写代码的思想）

在这里插入图片描述
举例分析41.55秒

注意如果能推出空串e的，不会有报错处理，因为如果不匹配指针后移1个，可以为空e，可能下一个就匹配了呀比如+

伪代码如下
在这里插入图片描述

表驱动的

在这里插入图片描述

表中一项没有两个，没有冲突项，也可以说明是LL 1文法

写到这里突然发现自己对基本知识还不够理解，于是又去恶补了视频，从基础开始写

第五章：语法分析——自底向上的分析

在这里插入图片描述

5.1 自下而上分析法基本问题——确定可规约串

基本思想
在这里插入图片描述
移进——规约

关键问题是识别可规约串，有好几种选择选哪个规约？——用句柄来规约

基本概念：
短语、直接短语、句柄
在这里插入图片描述

短语：=》是某个非终结符一步或多部推到出的句子
β能够规约成非终结符A，一步获多步规约为A，构成一个语法单位
而且这个语法的单位能和上文和下文规约为S，即拼起来是一棵树

直接短语：是某个非终结符一步推到出的句子
β一步规约为A，
短语是可能的要规约的目标
直接短语是可能的马上要规约的目标，一步就到非终结符

句柄：
最左的直接短语，规约的抓手！
就是那个马上要规约的对象，因为我们是从左到右分析，
句柄可能是非终结符、终结符，因为短语只说了是叶子！！

求短语、直接短语和句柄的快速方法——画出语法树，从下向上找

这篇

在这里插入图片描述

所有子树的末端，保证了A=》+ β
而短语的第一个条件要求S=》αAβ，即把这子树切掉还是一颗树

在这里插入图片描述
此时利用句柄进行规约就不会出现刚才有好几种选择的情况了

规范规约、规范推导、规范句型

在这里插入图片描述

每次都是用句柄进行规约，是规范规约，因此得到的分析树跟语法树一定是一致的

在这里插入图片描述
符号栈的使用

这中间的每一步，栈内的内容和输入串剩下的内容拼起来一定是一个句型，一定是一个规范句型，可以画出拼成的语法树来理解，一但栈顶出现句柄就进行规约！

那么具体怎么确定可规约串，肯定不能画出语法树找句柄，下面讲找。。。。。。。。。

5.2 算符优先分析法（不是规范规约）——根据最左素短语找可规约串

优先关系定义
在这里插入图片描述
算符文法（没有+*这种形式）

算符优先文法

计算FIRSTVT 和 LASTVT集合

先介绍FIRSTVT集和LASTVT集
在这里插入图片描述

FISTVT（P）表示从左向右看，第一次出现的终结符a，或者Qa形式，就把a放入集合；（直接看出来的）
如果有P-》Q。。。，要把FISTVT Q 加入FISTVT P中；（要全部进去）
每次把所有的产生式扫描完了后，如果矩阵有变化就重新扫描所有产生式一次；直到最后没有变化（一遍遍的扫描，不要着急反）

LASTVT P 表示从左向右看，出现以终结符a结尾，或aQ结尾，把a放入集合；
如果有P-》。。Q 要把LASTVT Q 加入 LASTVT P
每次把所有的产生式扫描完了后，如果矩阵有变化就重新扫描所有产生式一次；直到最后没有变化；（反复查看）

构造FISTVT、LASTVT集合的算法——利用二维bool矩阵手算也推荐
在这里插入图片描述

优先关系表的构造

现在已经求出FISTVT 和LASTVT集合，构造优先关系表
在这里插入图片描述

如果考虑# 符号，只用考虑#S# 句型

构造优先关系表的算法
在这里插入图片描述

解释：
在构造优先关系表时每个产生式只从左到右扫描1遍，但每次扫描，都要检查所有可能的模式= 《》！
如果出现两个连续的终结符 ± ，关系为 =
如果两个终结符中间只有一个非终结符 +E- ，说明两边的终结符的优先级是相等的，关系为 =
如果 +E形式，对于FIRSTVT E 中每一个a 都有 + 《a a要先规约
如果 E+ 形式，对于LASTVT E 中每一个a 都有 a》+ a要先规约

例题：
在这里插入图片描述

算符优先分析——根据最左素短语找可规约串

概念回顾：
可归约串：自底向下分析的核心就是找可规约串
句型：文法开始符号所能推出的某种串
短语：语法树末端
直接短语、句柄：短语的特例
规范规约：每次都对句柄进行规约，这个规约就是规范规约，规范规约的结果一定是语法树

素短语：在算法分析方法中要规约的对象

首先是短语，然后至少有一个终结符，但内部不能再有包含终结符的短语，即不含有更小的素短语

最左素短语：在句型最左边的那个素短语，之所以找最左，因为我们规约就是从左向右的，最左素短语就是我们要规约的

例题：
在这里插入图片描述

怎么找最短素短语？找满足如下条件的子串
在这里插入图片描述

在这里插入图片描述

中间部分即是最左素短语

算符优先分析算法

在这里插入图片描述

算符优先分析算法解释：

如果栈顶s【k】是终结符Vt，把位置k（栈顶）赋给j，如果是非终结符，置为k-1 次栈顶（栈顶-1下面那个）=》这样j指向了栈里面最上方的终结符
如果栈顶的终结符s【j】比刚刚读入的a高的话，已经发现了最左素短语的尾部；头在栈里，往下找，找到头尾之间的短语就是最短素短语；
Q是上面的终结符，s【j】是下面的终结符，直到上面大下面小就退出；说明找到了
把s【j+1】-s【k】规约为某个N，不一定要跟某个候选式完全一样，只要有一个对应关系即可

体现在分析树上就是比语法树短了好几节，直接对应上去的。跳过了一些简单的规约
规约后，可能栈顶还是一个最左素短语，持续规约，直到栈顶终结符a与栈里是 = 》关系；继续扫描，直到句子结束a=#
如果出现j-1后《=0 说明输入串出错，翻到最后也没找到，最后栈里形式为#S#
发现非终结符好像没有影响，可以不进栈，但有时候会错

优缺点
算符优先分析一般不是规范规约，跳过了一些简单的规约，速度更快了
在这里插入图片描述

优先函数——优化

在这里插入图片描述
优先函数不一定存在

优先函数如果存在，是无穷多的，可以加减常数
如果优先函数存在，三步构造优先函数

检查很重要！检查f g值关系和符号表的对应关系是否一致

例题
在这里插入图片描述

5.3 LR分析法（规范规约）——根据句柄，怎么找句柄，即保证栈里是活前缀？

问题：
我们要用句柄来确定可规约串，但语法分析的目的就是为了得到语法树，语法分析没有完哪来的句柄？——LR分析器

思想：
在这里插入图片描述

LR分析表

LR分析器的工作原理—— 三元组表示

在这里插入图片描述

LR分析器工作原理例题：讲得很棒理解过程44：00

LR文法、 LR（k）文法

LR文法不是二义文法

因此文法是LR文法是文法无二义性的充分条件

① LR（0）分析表的构造——0 代表不看后面那个

基本概念：字的前缀、活前缀
在这里插入图片描述

解释
活前缀保证不会出现句柄+句柄之后的符号出现在栈中，只会有三种情况，句柄在栈顶，句柄一部分在栈顶一部分在栈外，句柄全在栈外

问题是：怎么样构造DFA识别活前缀
在这里插入图片描述

方法一：LR（0）项目 -》NFA-》DFA=》LR（0）分析表

LR（0）项目
在这里插入图片描述

解释
移进项目：现在α已经在栈中，我希望见到终结符a，将来把β移进，最后规约到A
待约项目：等待着把B先归约
其实这里的。可以理解为当前用户输入到哪了？

在这里插入图片描述
构成识别活前缀的NFA方法

解释
2. 等待A形成，到了状态A直接跳到A->γ上去，希望下面的输入符号能沿向右移动，形成γ最后形成A，回到状态i

在这里插入图片描述

终结态是*在最后的状态，也是句柄识别态，是规约项目

子集法确定化DFA
在这里插入图片描述

任何一个状态都是活前缀的识别态
LR分析表实际上把DFA识别活前缀的能力转换到表里了，前进后退
图里所有项目集合构成了LR（0）项目集规范族

方法二：拓展文法=》做闭包 =》GO函数=》DFA =》LR（0）分析表

有效项目
在这里插入图片描述

代表的格局是：A在形成过程中，β1已经形成，希望形成β2这样一个项目对于活前缀αβ1是有效的；
也就是说识别了αβ1后，A的前部分已经识别，后一部分β2等待着识别，*后是我们希望识别的部分
项目集中的项目都是对这个活前缀有效的项目

一个结论

在这里插入图片描述
项目对于活前缀是有效的例子理解：

定义几个概念：拓广文法、闭包运算、GO函数
在这里插入图片描述

解释：
这里求闭包与之前类似：

在画识别活前缀NFA时，两个项目通过e弧连接
前面NFA确定化时候，一个状态集的e闭包代表的是，从该状态出发，识别到若干个e所能到达的点也放进来

GO函数
在这里插入图片描述

解释：

J求法是把所有*在X前，放在X后
前面NFA确定化时候

识别了γ活前缀后到达了I这个项目集，I项目集里所有项目都是对γ有效的，再沿弧X走一步就是GO（I，X），也就是说GO（I，X）对于γX有效

例题理解：
在这里插入图片描述
LR（0）项目集规范族的算法

构造过程举例：

LR（0）分析表的构造
LR（0）文法定义

把DFA 识别活前缀的能力转换到LR分析表中去
LR（0）分析表的ACTION和GOTT子表的构造方法
在这里插入图片描述
例子：
文法

识别活前缀的DFA 、项目集规范族

转变为分析表

检查：

0 状态接收a到2状态，影响的是ACTION表，ACTION0 a 就是s2
0 状态接收E到1状态，影响的是GOTO表，GOTO0 E 就是1
6状态是归约状态，在6行所有列都有用产生式1来进行归约r1

在这里插入图片描述

对应到DFA识别活前缀的过程，接收、退出

② SLR分析表的构造——Follow集解决冲突，Simple 简单解决

LR文法会有冲突: 移进归约冲突、归约归约冲突，（没有移进移进冲突！！！）

检查非终结符的Follow集合，有选择地把归约动作放在某些列中去，而不是每一列

在这里插入图片描述
推广

蓝色是所有移进项目，绿色是归约项目
S small 有一点点展望 FollowA 告诉我们非终结符A后面可能跟哪些符号
1 代表向前看1个

SLR（1）分析表的ACTION和GOTO子表构造
在这里插入图片描述

与LR0区别在:放的时候看终结符是不是FollowA里可能的后跟符号

在这里插入图片描述

又是一个判断无二义文法的充分条件

例题理解：
在这里插入图片描述
项目集规范族，通过GO函数连成DFA

其中1 2 9 都有冲突

SLR冲突消解存在的问题
在这里插入图片描述

我们应该要在某种特定状态才能follow！

举例解释：

在这里插入图片描述

③ 规范LR分析表的构造——LR（1）分析表的构造

展望信息关联到每一个具体的状态上，不再关联到follow集合上了

LR（k）项目、展望串新定义 在这里插入图片描述

在这里插入图片描述

对比：

LR（0）项目代表的格局是在识别活前缀过程中、在分析句子过程中，α已经识别、出现在栈顶，马上要做归约；
SLR 要检查当前的输入符号是不是A的Follow集合再归约
但这都不够，只有当前输入符号α以及后面连续的k个符号正好是a1–ak，即跟展望串一样时候，才能把栈顶的α归约成A，展望串是跟项目的状态关联而不是A

第二分量代表是只有遇到这种情况，才进行前面的动作

LR（1）项目集规范族的构造
做项目集闭包的方法
在这里插入图片描述
其中：与前面LR（0）项目求闭包不同之处

理解：
b是怎么来的？

说明α已经有了，下面希望形成B再形成β，当β出现的时候我希望碰到a，然后一起归约成A，因此格局应该转到B的识别

希望通过识别kesi来归约为B，但是有一个上下文条件！
B的下文是β，如果β不空，把kesi归约成B面临的终结符即展望的单词要是β的开头！
如果β为空，展望的单词就是a（比如a是# 如果β为空，说明是空串，后面只会跟#）
=》合起来就是b属于FIRST（βa）