编译原理：算符优先分析算法

1.算符优先分析过程

构造出文法的算符优先关系表后，就可以依据算符之间的优先关系，进行文法语句的识别。如果分析栈栈顶的终结符优先级别低于下一输入符号，或与之优先级别相同，则应将下一输入符号移进分析栈，等待归约；否则，表明栈中形成了当前优先级别最高的串，应进行归约动作。例如，依据表5-4所示的表达式文法的算符优先关系表，对输入串i+i*i进行算符优先分析的过程如表5-5所示。注意，算符优先分析并不关心归约后的非终结符的名称，可以统一由某一个大写字母表示。

表5-5　i+i*i的算符优先分析过程

2.最左素短语

算符优先分析方法是通过比较相邻终结符间的优先关系来进行分析的，一般并不等价于规范归约，无法使用句柄的概念。以算术表达式的句型T1+i+T2*F为例，进行规范归约时句型的短语包括T1、i、T1+i、T2*F和T1+i+T2*F，其中T1是句柄，如图5-4（a）所示。但是，依据算符优先分析，语法分析树将呈现为图5-4（b）所示的形式。可以看出，由于算符优先分析并未对非终结符定义优先关系，所以无法发现由单个非终结符组成的可归约串，构造的语法树去掉了单个非终结符的归约过程，例如T→F。

图5-4　句型T1+i+T2*F的语法分析树

分析树VS语法树

为了描述算符优先分析的可归约串引入素短语的概念。素短语是至少包含一个终结符的短语，并且除其自身外不再包含任何更小的素短语。素短语通过不包含其他素短语保证了素短语进行归约的直接性，并且能够依据包含的相邻算符决定优先级别。由于算符优先分析采用从左至右扫描输入串，因此其可归约串是位于句型最左边的素短语，称为最左素短语。(www.xing528.com)

算符优先分析法是依据最左素短语的性质，判断算符优先文法句型的可归约串。一个算符优先文法句型的最左素短语Njaj…NiaiNi+1是满足如下条件

的最左子串。也就是，最左素短语是当前分析栈中包含的终结符优先级别最高的符号串。

3.算符优先分析法

算符优先分析算法依据算符的优先关系，不断移入优先级别较高或相同的下一输入符，寻找当前句型最左素短语末尾的终结符。然后，通过向左搜索寻找左侧优先级别低的算符，确定最左素短语的首字符。语法结构正确的语句在分析结束时，分析栈将呈现为#N，输入符号仅剩#。算符优先分析过程如算法5.3所示。

算符优先分析法

算法5.3 算符优先分析程序。

算符优先分析跳过了所有单非产生式所对应的归约步骤，显然比规范归约要快得多。这既是算符优先分析的优点，同时也是它的缺点。因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致将本来不是句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。