当前课程知识点:编译技术 >  第三章 语法分析 >  3.4 自下而上分析 >  3.4.1 归约句柄

返回《编译技术》慕课在线视频课程列表

3.4.1 归约句柄在线视频

下一节:3.4.2 移进归约分析过程

返回《编译技术》慕课在线视频列表

3.4.1 归约句柄课程教案、知识点、字幕

各位同学大家好

我们继续来学习语法分析部分

我们来看一下

之前我们已经学习了自上而下的分析

从这节课开始

我们来学习自下而上的分析

在自上而下的分析中

我们一直使用的是最左推导

那么在自下而上的分析中

我们是不是应该用最右推导呢?

我们先来看一个例子

在自上而下分析中

我们用最左推导来构造语法树

根据这个文法

假设我们的输入是id×id

从产生式的开始符号E开始

我们将E推导为TE'

然后T推导为FT'

我们将F推导为id

T'推导为*FT'

然后F推导为id

T'推导为ε

E'推导为ε

这样我们就完成了自上而下的语法树的构建

接下来的问题就是

我们在进行自上而下的分析中

我们可以用最右推导吗?

我们其实可以发现

我们在进行分析输入的时候

我们是从左到右来读取我们的输入符号

却要进行最右推导

这也就是说

我们每一次希望利用最左边的字符

来决定右边的符号的动作

这样其实是非常困难的

也就是说

在自上而下的分析过程中

适用的是最左推导

没法使用最右推导

但是我们在自下而上的分析中

我们发现

我们要做的是从句子开始

将它进行归结为文法的开始符号

后面我们会看到

最右推导用于自下而上的分析

对应的实际上是最右推导的逆过程

首先我们给大家介绍一个新的概念 叫做归约

归约实际上是最右推导的逆过程

也就是我们有一个输入id+id×id

我们将它归约为产生式的开始符号E

在进行自下而上分析中

我们引入两个重要的概念

一个是归约,另一个是句柄

我们首先来学习一下'归约'这个概念

归约是自下而上分析中的一个重要动作

它对应的是最右推导的逆过程

假设我们有一个文法

S可以产生aABe

A可以产生Abc或者b

B可以产生d

我们有一个输入串abbcde

这个输入串如何把它归约为我们想要的开始符号S

我们将这个符号串写在这

我们使用最右推导的逆过程

也就是归约,来完成自下而上的分析

我们首先可以看到

a没有办法进行归约

而第1个b可以归约为A

我们将它归约为A

然后我们发现Abc可以归约为A

接下来我们将d归约为B

最后我们就可以根据aABe得到S

也就是完成了自下而上的构建

我们再来完整的看一下分析的过程

实际上

我们在进行归约动作的时候

是从左到右去读取输入

发现第1个符号a 没有办法进行归约

然后我们读取到第1个b

它是一个产生式A产生b的右半部

所以这个小B可以归为A

接下来我们的符号串就变成了aAbcd

我们观察到Abc

它仍然是作为一个产生式的右部A产生Abc

所以我们将Abc归约为A

接下来我们观察到

我们的输入符号串变成了aAde

而其中的d其实是一个产生式的右部

也就是B可以产生d

d可以来进行归约

我们将d归约为B

在归约完成之后

输入的符号串就变成了aABe

那么输入的符号串aABe

仍然是作为一个产生式的右部

S可以产生aABe

所以我们将符号串归约为S

我们整个的输入串就完成了自下而上的分析

构造出了语法树 得到了开始符号S

接下来我们

来学习句柄这个概念

我们看到在归约的过程中

每一次和一个产生式右部符号

如果匹配上了

我们就可以将这个符号串变成产生式的左部

也就是把它归约过去

而实际上和一个产生式右部匹配的一个子串

我们给它一个名字叫做句柄

也就是在刚才的分析过程中

b就是句柄

因为我们将b归约为A

而在这一步Abc,我们将它归为A

所以在这一步,Abc就是句柄

而在下一步

由于d归约为B,所以d是句柄

那么在最后一步aABe归约成S

所以它是句柄

总结一下

句柄是句型的一个子串

我们把句柄归为非终结符的这一步

实际上代表的是

最右推导的逆过程

也就是这个归约的步骤

最终可以得到产生式的开始符号S

接下来我们学习一下句柄的性质

我们可以看到

对于我们之前所标注出来的

几个句柄的右侧

它只含有终结符

这是句柄本身的特点所决定的

因为句柄是用来进行归约

所以它在(产生式的)右边,肯定只含有终结符

如果文法是二义性的

那么句柄可能不唯一

我们可以来看一个例子

比如说有一个文法

E可以产生E+E或者E×E或者(E)或者id

我们有一个输入id1×id2+id3

我们在进行推导的过程中

假设使用最右推导

我们会观察到

这两种情况

第1种情况

我们首先将E推导为E×E

然后按照最右推导的原则

我们将右边的E推导为E+E

然后再将最右侧的E推导为id3

我们观察到在这一步

E推导为id3,所以id3是句柄

而在右边的情况中

E 我们首先将它展开为E+E

我们将最右侧的E推导为id3

然后下一步

再将左边的E推导为E×E

所以在这一步当中

仍然是E×E+id3这个串

而此时它的句柄变为E×E

这个问题的原因是

由于这个文法本身是有二义性的

所以在进行推导的过程中

句柄可能不唯一

接下来我们看一下

句柄的非形式化定义

对一个句型的句柄

是指我们在一个和产生式的右部相匹配的一个字符串

我们观察一下

对于这个文法来说

在最右推导的过程中

可能和产生式的右部相匹配的串有哪些呢?

其实也就是产生式的右部的串有哪些?

也就包括aABe、Abc、b和d

也就是所有产生式的右部都是可以和它相匹配的串

接下来我们来学习

句柄的精确定义

假设有一个右句型γ

它的句柄是一个产生式的右部β

而β在用A进行替换γ中的句柄β之后

我们得到的是最右推导的前一个句型

首先我们来明确一下右句型的含义

右句型是指我们在进行最右推导过程中

所有可能出现的句型

我们可以假设

产生式的开始符号是S

从S开始推导,我们得到了一个右句型γ

然后我们把γ表示为αβω

那么其中γ可以通过产生式A产生β来归约为右句型αAω

也就是说

我们从S进行推导得到γ

我们将γ表示为αAω

然后我们将其中的A推导为β

这个情况下β就是句柄

我们仍然来观察之前的文法

输入的符号是abbcde

我们在进行第1步的归约之后

得到了一个串aAbcde

那么这个b是不是句柄呢?

如果b是句柄,

一定意味着存在这样的一步:aAAcde是一个右句型

而aAAcde我们没有办法继续进行最右推导的逆过程

也就是没有办法继续进行归约,最终得到产生式的开始符号S

所以aAAcde并不是文法的右句型

所以这个b它不是句柄

我们再来看一下句柄形式化的定义

S我们将它推导为αXω

X推导为β

在这种情况下β是句柄

β是αXω的句柄

在移进归约的分析过程中

我们每一次移进或者归约

其实是取决于是否出现了句柄

也就是句柄始终出现在栈底

自下而上的分析中

基于这个句柄是不是能识别出来

如果一个句柄出现,我们就进行归约

如果句柄没有出现,我们就继续移进

我们来看一个例子

假设有一个文法

S可以产生aAcBe

A可以产生b

A可以产生Ab

B可以产生d

我们对这个输入abbcde,使用移进归约分析器来分析它

我们画了一个栈

首先这是输入

我们将a移进栈,输入这边就去掉了a

然后我们来判断是不是出现了句柄

如果出现了句柄,要进行归约

而此时没有出现句柄,所以继续进行移进

我们将输入的b移进栈

移进栈之后

仍然需要去判断是否出现了句柄

第2条产生式A可以产生b

所以我们认为这个b是句柄

我们将b归约为A

归约完成之后

仍然需要去判断栈里是不是出现了句柄

此时我们发现栈里不含有句柄

那么我们就继续进行移进的动作

我们将b移到栈里

这时候仍然需要去判断是不是出现了句柄

我们发现

bA它是一个产生式的右部

也就是第3个产生式A可以产生Ab

如果出现了句柄,我们就进行归约

将它归约为A

然后接下来判断栈里是不是出现了句柄

如果没有出现句柄,继续将输入的c移进栈中

在将C移入栈中之后

继续去判定是否出现了句柄

没有出现句柄

我们就继续将输入的d移入到栈中

继续判断是不是出现了句柄

没有出现句柄,我们就继续移进

如果出现了句柄,我们就来进行归约

d可以根据第4个产生式来进行归约成B

然后我们判断栈里边是不是出现了句柄

如果没有出现句柄

我们继续将输入的e移入到栈里边

这个时候栈里边是第1个产生式的右部

也就是出现了一个句柄

我们将它归为产生式的开始符号S

这个移进归约过程就结束了

这一小节就介绍到这

谢谢大家

编译技术课程列表:

第一章 绪论

-1.1 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

3.4.1 归约句柄笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。