编译原理与实践：短语的条件与推导过程

规范归约的句柄实际上是最右推导过程中的每一步被推导出的某个产生式的右部。因此，通过描述句型推导过程中能够被推导出的串可以刻画句柄，这样的串称为句型的短语。

定义5.2 设文法G，S是其开始符号。假定αβδ是G的一个句型，如果有

则称β是句型αβγ相对于非终结符A的短语。特别是，如果A⇒β，则称β是句型αβγ相对于A的直接短语。

注意，作为短语的两个条件均是不可缺少的。仅有A⇒+β未必意味着β是句型αβδ的一个短语，还必须要有S⇒*αAγ这一条件。句子的语法树能够展示出句子推导过程中经历的所有句型，非常有助于判断输入串的短语。

例5.2 判定如下算术表达式文法的句子i1*i2+i3的短语。

句子i1*i2+i3的语法分析树如图5-2（a）所示。从语法树可以看出i1、i2和i3是句子中通过直接推导产生的串，因此均为直接短语。此外，i1*i2是句型T+i3中由T推导出的，也是句子i1*i2+i3的短语。最特殊的，i1*i2+i3是由开始符号E推导出的，也是短语。但是，尽管有E⇒*i2+i3，而i2+i3并不是句子i1*i2+i3的短语，因为不存在从文法开始符号E到i1*E的推导。

假设给定另一个句型E+T*F+i，语法分析树如图5-2（b）所示。可以看出，句型的短语包括T*F、i、E+T*F和E+T*F+i。其中，T*F和i为直接短语。

(www.xing528.com)

图5-2　例5.2示意图

E→E+T|T

T→T*F|F

F→(E)|i

语法分析树需要一层一层构造，因此句柄一定是直接短语。此外，规范归约从最左侧分支开始构造语法分析树，因此最左直接短语构成了规范句型的句柄。例5.2中，i1是句子i1*i2+i3的最左直接短语，即句柄；T*F是句型E+T*F+i的句柄。

句柄的“最左”特征对于移进-归约来说非常重要。规范归约过程中，如果栈中没有呈现出句柄，则从左至右将下一个输入符号移入栈中。一旦在移入过程中，栈顶呈现句柄则进行归约。因此，规范句型句柄的尾部一定是栈顶符号，而且句柄的右侧一定是终结符，即下一个输入符号。在分析的任一时刻，分析栈和符号串中剩余的部分，组成了一个完整的规范句型。

短语-直接短语-句柄关系