句柄与移入-归约分析的关系

相关概念

• 移入-归约分析
  关于该分析的介绍可以查看 移入-归约分析

• 句柄
  此概念在进行移入-归约分析时很重要，能否正确识别句柄会影响到分析时所进行归约操作是否正确。

要了解句柄的定义先要了解短语和直接短语的概念。

1. 短语

一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语

2.直接短语

当子树不包含其他更小的子树时，该子树叶节点所组成的字符串就是该句型的直接短语

3. 句柄

一个句型最左边的直接短语成为句柄

移入-归约分析和句柄

在进行移入-归约分析时，需要一个栈去接受输入的字符以及归约后的文法字符。

以以下文法及句子为例进行说明

• 文法

<S> → var<IDS>:<T>
<IDS> → i
<IDS> → <IDS>,i
<T> → real|int 

显然该文法是用于命名变量的（这不是重点）

• 要分析的句子

var i:real

• 分析过程

首先需要有一个用于存放句子中移入的字符和归约后的非终结符。

下面的分析过程中会列出每一步对应句型的分析树。

当然需要说明的是在实际进行移入-归约分析时并没有分析树辅助分析工作。毕竟构造分析树与移入-归约分析的目的是一致的，即是判断句型是否符合文法。若开始便有句型对应分析树，也没必要再进行判断了因为已经知道句型符合文法。

所以下文出现的分析树的出现只是方便我们理解，句柄与移入-归约分析的关系。

整个分析过程如下所示

分析过程.png

为了方便分析将分析过程中规范句型（栈内符号串+剩余输入=规范句型）相同的情况归在一起分析，如下

规范句型.png

下面列出各个规范句型的分析树及其句柄

1. 句型 var i : real 对应的分析树

var i : real.png

2. 句型 var <IDS> : real 对应的分析树

var <IDS> : real.png

3. 句型 var <IDS> : <T> 对应的分析树

var <IDS> : <T>.png

4. 句型 <S> 对应的分析树

<S>.png

通过观察上述所列的分析树可以看出这样的规律，一旦句柄在栈顶形成就会进行归约操作。你可能会问这个规律在分析中是普遍适用的吗？如果归约的不是句柄的话能分析成功吗？带着这个问题我们来看分析稍微复杂一点的句型 var a,b : real 的例子。

看如下分析过程

分析过程.png

看见该分析最后失败了，最后栈中并没有得出所期望的<S>。当栈内的数据分析至红框里的数据时，通过观察产生式可以知道有两种归约的方式，一种是b归约成<IDS>，另外一种是<IDS>,b归约成<IDS>，显然上述分析过程中使用了前者。

下面先看句型var <IDS> , b : real的分析树

var IDS , b real分析树.png

可见<IDS>,b才是句型var <IDS>,b:real的句柄，而我们错误地将b进行归约导致了分析的失败。

正确的分析过程如下（将<IDS>,b归约）

正确的分析过程.png

可见只有当栈中的形成当前规范句型对应分析树的句柄时才能进行归约，但问题是实际进行移入-归约分析时并没有分析树以供判断栈是否已经形成句柄，为此我们需要LR分析。

LR分析法中多了一个栈存储栈中当前的状态，利用栈中状态和输入符结合进行判断，避免了进行错误的归约。