优先关系表及算符分析的实践

算符之间的优先关系可由表格直观表示。算符优先关系表的垂直维度表示位于左侧的算符，水平维度是位于右侧的算符，表项的内容是两者的优先关系。例如，算术表达式文法的算符优先关系表如表5-4所示，其中空白格表示相应终结符对之间没有优先关系。通过扩展表达式文法增加产生式E→#E#，可以将句子的起始和终止符作为终结符对待。

表5-4　算术表达式文法的算符优先关系表

E→#E#

E→E+T|T

T→T*F|F

F→P↑F|P

P→(E)|i

1.FIRSTVT集

依据优先关系的定义，为了找出所有满足关系的终结符对，需要明确非终结符能够推导出的符号串中的第一个终结符。文法每个非终结符P的FIRSTVT集定义为

FIRSTVT集

注意，符号串的第一个终结符不一定是其第一个符号，也可能是第二个符号，前面可以存在一个非终结符。

依据下面两条规则可以构造非终结符P的FIRSTVT集：

（1）若有产生式P→a…或P→Qa…，则a∈FIRSTVT（P）；

（2）若a∈FIRSTVT（Q），且有产生式P→Q…，则a∈FIRSTVT（P）。

规则（1）可以通过直接扫描产生式实现。规则（2）可以利用一个布尔数组F[P，a]实现，当且仅当a∈FIRSTVT（P）时F[P，a]取值为真。依据规则（1）对数组F[P，a]的每个元素赋初值。然后，利用一个栈结构，将所有初值为真的数组元素F[P，a]的符号对（P，a）压入分析栈。如果栈不空，则弹出栈顶，记作（Q，a）。对每个形如P→Q…的产生式，若F[P，a]为假，则将其值设为真，并将（P，a）压栈。重复上述过程，直至栈空为止。构造FIRSTVT（P）集的过程如算法5.1所示。

算法5.1 构造文法的FIRSTVT集合。

(www.xing528.com)

2.LASTVT集

为了找出所有满足关系·＞的终结符对，需要明确非终结符能够推导出的符号串中的最后一个终结符。文法每个非终结符P的LASTVT集定义为

LASTVT集的构造算法与FIRSTVT集的构造算法类似。依据下面两条规则可以构造非终结符P的LASTVT集：

（1）若有产生式P→…a或P→…aQ，则a∈LASTVT（P）；

（2）若a∈LASTVT（Q），且有产生式P→…Q，则a∈LASTVT（P）。

3.优先关系表的构造

依据定义，通过检查文法的每个产生式的每个候选式，可找出所有满足ab关系的终结符对。利用非终结符P的FIRSTVT（P）集，通过检查每个产生式的候选式，就可以确定满足关系的所有终结符对。若有形如…aP…的产生式，那么任何b∈FIRSTVT（P），则ab。利用非终结符P的LASTVT（P）集，通过检查每个产生式的候选式，就可以确定满足·＞关系的所有终结符对。若有形如…Pb…的产生式，那么任何a∈LASTVT（P），则a·＞b。算符文法优先关系表的构造方法如算法5.2所示。

LASTVT集

算法5.2 构造文法的优先表。

例5.4 构造算术表达式文法的算符优先关系表。

首先，构造每个非终结符的FIRSTVT集和LASTVT集。

然后，扫描产生式可得

最后，构造文法的优先关系表如表5-4所示。从中可以看出，任意终结符号对之间至多只有一种优先关系成立，因此算术表达式的文法是算符优先文法。