设为首页收藏本站
开启辅助访问

编译原理 【国防科技大学网课】【笔记】【 陈火旺】

您所在的位置：网站首页 › 编译原理第三版答案陈火旺第三章 › 编译原理 【国防科技大学网课】【笔记】【 陈火旺】

编译原理 【国防科技大学网课】【笔记】【 陈火旺】

2024-07-13 20:44| 来源: 网络整理| 查看: 265

编译原理 陈火旺 期末考试复习试题第一章：绪论第二章：高级语言及其语法描述2.1 基本符号概念2.2 上下文无关文法G是一个四元式2.3 推导和规约、语法树（子树、直接子树）2.4 二义性文法判断2.5 短语、直接短语、句柄、素短语2.6 化简文法 第三章：词法分析基础知识**3.1 右线性文法、状态转换图**3.2 NFA的确定化和最小化 考点：DFA与NFA的区别（老师强调） 第四章： 语法分析——自上而下分析4.1 求First（α）首符号集 、Follow（B）后跟符号集4.2 LL（1）文法（自顶向下的分析）4.2.1非LL1文法到LL1文法的等价转换（不一定都能转换）方法一：提取左公因子方法二、消除直接左递归——背公式【注意空串e】 4.2.2 判断LL（1）文法---求相同左步产生式的Select集的交集4.2.3 LL（1）分析的实现递归下降的分析（一种写代码的思想）表驱动的 第五章： 语法分析——自底向上的分析5.1 自下而上分析法基本问题——确定可规约串求短语、直接短语和句柄的快速方法——画出语法树，从下向上找规范规约、规范推导、规范句型 5.2 算符优先分析法（不是规范规约）——根据最左素短语找可规约串**计算FIRSTVT 和 LASTVT集合****优先关系表的构造**算符优先分析——根据最左素短语找可规约串算符优先分析算法优先函数——优化 5.3 LR分析法（规范规约）——根据句柄，怎么找句柄，即保证栈里是活前缀？LR分析器的工作原理—— 三元组表示① LR（0）分析表的构造——0 代表不看后面那个方法一：LR（0）项目 -》NFA-》DFA=》LR（0）分析表方法二：拓展文法=》做闭包 =》GO函数=》DFA =》LR（0）分析表 ② SLR分析表的构造——Follow集解决冲突，Simple 简单解决③ 规范LR分析表的构造——LR（1）分析表的构造④ LALR——压缩相同展望串的LR(1)项目小结 第六章：属性文法和语法制导翻译属性文法基于属性文法的处理方法1.依赖图（有向图）2.树遍历方法（从上到下，从左到右）3.一遍扫描3.1 S属性文法自下而上的计算 S综合属性3.2 L属性文法和自顶向下的翻译 L联系成方向翻译模式（进一步说明每一个规则在什么地方算，语义规则说明怎么算）自顶向下翻译 第七章 语义分析和中间代码产生中间语言后缀式无循环有向图DAG三地址代码 赋值语句的翻译布尔表达式的翻译 电子书链接：

期末考试复习试题 第一章：绪论

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

第二章：高级语言及其语法描述 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 就是s20 状态接收E到1状态，影响的是GOTO表，GOTO0 E 就是16状态是归约状态，在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）

=》展望串分量的写法，其实就是看从哪过来的！ 在求的时候不用这么麻烦

项目集转换函数GO新定义

在这里插入图片描述 LR（1）项目集规范族构造算法（与LR（0）类似）在这里插入图片描述 LR（1）分析表的ACTION和GOTO子表的构造 在这里插入图片描述

差别就在2，把归约动作都放在展望串那一列中 LR（0） SLR呢？

LR（1）文法 在这里插入图片描述

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

举例理解： 文法 在这里插入图片描述 LR（1）项目集构造

在这里插入图片描述

注意图中S->.BB状态I0 延伸出来的I2的展望串的写法，到底是哪个B？

LR（1）分析表为 在这里插入图片描述

观察：状态7的归约动作只放在了#中，8的归约动作只放在了ab中，都是状态的展望串对应的终结符

利用表对输入串进行分析 在这里插入图片描述

④ LALR——压缩相同展望串的LR(1)项目

注意：可能导致一种新的冲突 归约——归约 冲突！因为第一分量是一样的，只有第二分量展望串可能会冲突

小结

LR分析法就是根据句柄分析，怎么找句柄，怎么样保持栈里的是活前缀？ 通过构造LR（1）、SLR、LR（0）项目集规范族=》识别活前缀的DFA=》LR分析表=》安装LR分析表去正确的移进归约！！！

第六章：属性文法和语法制导翻译

在这里插入图片描述

属性文法

两种属性

综合属性继承属性-可以来自兄弟节点 or 父节点

说明： 在这里插入图片描述 在这里插入图片描述 例： 在这里插入图片描述

基于属性文法的处理方法 1.依赖图（有向图）

在这里插入图片描述

语义规则中没有返回值，需要添加一个虚拟的综合属性节点

构造依赖图的算法： 在这里插入图片描述 举例 在这里插入图片描述 良定义的属性文法 在这里插入图片描述

属性的计算次序 在这里插入图片描述 例子：需要多遍扫描 在这里插入图片描述

2.树遍历方法（从上到下，从左到右）

算法理解：

在这里插入图片描述

从上到下，从左到右，能算的继承属性先算出来，不断VisitNode，扫过一遍，算一下根节点N的综合属性

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

3.一遍扫描

AST 抽象语法树 中间代码 在这里插入图片描述 建立抽象语法树 在这里插入图片描述 例子：构造抽象语法树，从左到右，从上到下，一遍 在这里插入图片描述

起主导的是语法分析，所以叫语法制导

3.1 S属性文法自下而上的计算 S综合属性

概念介绍： 在这里插入图片描述

在这里插入图片描述

把栈变成三元组 每个规则有相应的代码段

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

3.2 L属性文法和自顶向下的翻译 L联系成方向

L属性文法 在这里插入图片描述 区分：下面的Q依赖于右兄弟1节点的综合属性，不属于L属性文法 在这里插入图片描述

翻译模式（进一步说明每一个规则在什么地方算，语义规则说明怎么算）

把产生式对应的语义规则打上{} ，变成语义动作，放到正确的位置上，保证用一个属性时，他有定义有值

在这里插入图片描述 例子：把中缀表达式翻译为后缀表达式 在这里插入图片描述

打印出 9 5 - 2 +

建立翻译模式=》保证在用到一个属性时候已经计算好了在这里插入图片描述

只有综合属性，当所有子节点都匹配成功，自动执行他，L属性保证了这点

在这里插入图片描述

要放在非终结符前面，当碰到非终结符要往下扩展时候，因为子节点要引用非终结符的继承属性，如果{}放在后面，在扩展时候可能会用到！ 在这里插入图片描述

改进，把所有的{}都放在后面，改写加e，第七章会详细讲 在这里插入图片描述 在这里插入图片描述

自顶向下翻译

首先自顶向下翻译会遇到左递归，先要消除左递归，要进行文法、属性计算的改造 在这里插入图片描述 消除左递归，构建新的翻译模式（学完第七章再来重新理解） 在这里插入图片描述

在这里插入图片描述

例子： 在这里插入图片描述 推广：带左递归的翻译模式的改造方法

在这里插入图片描述

A推出的是X开头YYYY串，消除左递归，用R来产生YYYY串，注意e空串结束 牢记：用之前必须有值

例子 在这里插入图片描述 例2 构造抽象语法树 在这里插入图片描述

第七章 语义分析和中间代码产生

静态语言检查 在这里插入图片描述

中间语言

常用的中间语言：

![在这里插入图片描述](https://img-blog.csdnimg.cn/01

后缀式

定义: 比较复杂，看书，或者不看 优点： 在这里插入图片描述 以后缀式为中间语言构造翻译模式来分析和翻译输入串 在这里插入图片描述

无循环有向图DAG

定义： 在这里插入图片描述 DAG与抽象语法树对比（省略箭头，其实有向，DAG是压缩过的、优化） 在这里插入图片描述

三地址代码

种类： 在这里插入图片描述

**四元式：**容易优化，删除调整顺序方便 在这里插入图片描述

在这里插入图片描述

**三元式：**不去显示运算的单元，引用计算该值的位置来引用结果 在这里插入图片描述其他情况 在这里插入图片描述

间接三元式：方便优化，节省空间存储效率高 在这里插入图片描述 间接码表表示计算的顺序，要调整顺序、删除就去操作间接码表 在这里插入图片描述

赋值语句的翻译

在这里插入图片描述 产生赋值语句的三地址代码的S属性文法（先用属性文法描述语义） 在这里插入图片描述 在这里插入图片描述

产生赋值语句的三地址代码翻译模式（语义规则在什么时候计算，构造翻译模式，语义动作）

把属性文法和分析过程结合起来，得到语义动作，得到翻译模式

在这里插入图片描述

说明： lookup是查看一下标志符是否有定义，返回其在符号表中的入口地址 emit是发送到输出文件中去，与gen差不多 这个翻译模式适合和自下而上的分析器结合在一起，当用某个产生式规约时，就执行其后面的语义动作

在这里插入图片描述

d 数组元素地址的计算 在这里插入图片描述

程序每翻译一个赋值语句，当碰到一个数组元素时候，我们只要去生成红色可变部分的代码，与不变部分蓝色相加即可得到数组元素的地址

方便计算地址，改写文法 在这里插入图片描述

在这里插入图片描述 带数组元素引用的赋值语句翻译模式 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

带类型转换的赋值语句 在这里插入图片描述

布尔表达式的翻译

太复杂了，考试不考



【本文地址】


今日新闻

推荐新闻

CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3