编译原理与实践：规范活前缀句型

如5.2.2节所述，规范归约过程的任何时刻，分析栈中呈现了规范句型的前面部分，分析栈和输入串剩余部分构成了一个完整的句型。由此，分析栈内句柄形成及形成以前的符号串的形式对于句型的识别，或者说对于句柄的归约，具有重要的意义。识别出分析栈中句型的前面部分就能够确定下一步的动作。

利用符号串前缀的概念可以描述符号串的形成。符号串的前缀是指符号串的任意首部。例如，串ab的前缀有ε、a以及ab。

定义5.6 对于文法G，若有规范推导

如果符号串δ是αγ的前缀，则δ是句型αγβ的一个活前缀。αγ称为句型αγβ的可归约前缀。

由定义可知，规范句型的活前缀是规范句型的一个前缀，并且不含句柄之后的任何符号。可归约前缀是含有句柄的活前缀。规范归约过程中，任何时刻分析栈中的符号串均为规范句型的活前缀。在活前缀右边添加终结符串（输入串剩余部分）后，则构成一个规范句型。

再次回顾例5.1的归约过程(www.xing528.com)

S⇒aAcBe⇒aAcde⇒aAbcde⇒abbcde

例5.1 分析过程中每当分析栈中呈现出当前句型的句柄时，分析栈和输入串的情形如表5-11所示。表5-11中列举了句型的活前缀，显然，ε、a、aA、aAc都不只是一个规范句型的前缀。

表5-11　例5.1的4次归约过程

LR分析法并不是直接分析文法符号栈中的符号是否形成句柄。分析的任何时刻，只要已分析过的部分，即分析栈里的文法符号X1X2…Xm，一直保持为规范句型的活前缀，就表明输入串已被分析过的部分没有语法错误。加上输入串的剩余部分，恰好就是活前缀所属的规范句型。因此，对句柄的识别实际上就是对规范句型活前缀的识别。

LR分析法利用有穷自动机识别文法所有句型的活前缀。有穷自动机的状态表示了活前缀识别过程中的不同阶段，终结符和非终结符是状态的输入符号。每当符号进入符号栈则表示识别了该符号，而进行状态转换。当识别到可归约前缀时，相当于栈中形成了句柄，到达识别的终态。对于文法G，首先需要构造一个识别G所有活前缀的有穷自动机，然后将其转变为LR分析表。