3.5.1 Reductions and Handle在线视频

各位同学大家好

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

我们来看一下

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

从这节课开始

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

在自上而下的分析中

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

那么在自下而上的分析中

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

我们先来看一个例子

在自上而下分析中

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

根据这个文法

假设我们的输入是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

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

这一小节就介绍到这

谢谢大家