OPG文法的语法分析优化策略

文/关玉欣

语法分析方法中自上而下的分析是指从文法的开始符号出发，反复的选择产生式进行推导，最终推导出句型；自下而上分析是指从待分析的句型本身出发，逐步选择产生式进行归约，直至归约到文法的开始符号。这两类分析都可以利用各种语法分析算法进行。每种语法分析算法都有其优势和局限性，根据文法的类型，可以选择最优的语法分析算法进行语法分析。

1 OPG文法

Chomsky将文法分为短语文法、上下文有关文法、上下文无关文法和正规文法四类。OPG文法是上下文有关文法中的一种，该文法的特殊性在于任意两个终结符之间最多只存在<、=、>三种优先关系中的一种优先关系，文法的产生式中不会出现两个相邻的非终结符。根据文法的特性可以推论该文法的任何句型也不会含有相邻的非终结符，这就为使用优化的OP分析法进行句型分析奠定了基础。

2 规范归约

归约与推导是一个逆过程，规范归约过程中一直本着最左的归约原则，每次分析过程中首先找到句型中的句柄，句柄是句型中的最左直接短语，之后根据产生式规则向左归约，用产生式的左部去替换产生式右部。例如对OPG文法G[E]：E→T|E+T T→F|T*F F→i|(E)的句型T+T*F+i的分析如表1所示。

上述句型分析中每步都是在句型中寻找最左直接短语，也就是文法中某条产生式的右部。进行最左归约实质上就是用某条产生式的左部非终结符去替换产生式的右部符号串。根据句型的不同，归约的步骤也会有区别，但分析成功的标志就是归约到OPG文法的开始符号，代表句型分析成功。在上述的规范归约过程中，句型T+T*F+i总归约次数为6。

3 优化的OP分析

在自底向上的句型分析方法中，OP（Operator Priority）分析法仅考虑句型中终结符的优先关系，从而确定每一步分析过程中的句柄。OP分析过程中也仍然采用最左归约，但由于句柄中忽略非终结符的属性，因而句柄的概念需要进行精确刻画，用最左素短语来描述归约过程中的句柄。

OPG的句型的一般形式为：#N1a1N2a2… Nnan# (Ni∈VN∪{ε}，ai∈VT），文 法 中 最左素短语是满足下列条件的最左子串：NiaiNi+1ai+1… NjajNj+1

其中：ai-1aj+1

根据OPG的特点，素短语中没有多个非终结符相邻的情况，且至少要包含一个终结符，也不能再包含其它的素短语。

由于OP分析过程中每次分析都对句型中的素短语进行归约，忽略了单一非终结符组成的句柄的归约，由此可以看出，OP分析方法并不是一种规范的归约方法。上述OPG文法的句型的分析，采用OP分析法分析过程如表2所示。

OP分析过程中，省掉了T1、F、T2三个仅由单个非终结符组成的短语的归约，因而分析过程相对于规范的归约少了两个分析步骤，分析效率提高，仅需归约4次即可完成该句型的分析。

4 OP分析算法设计

OP分析法特别适合OPG文法的句型的分析，在分析的每一步需要确定最左素短语进行最左归约。分析过程中需要借助于堆栈存储待分析句型以及分析结果，并且分析过程中需要查找终结符之间的优先关系。OP分析算法设计如下：

初始化：分析栈初始为#，句型栈存入待分析句型#。

分析：

（1）从左向右扫描待分析句型并逐个移入分析栈，查找优先矩阵，直至找到满足aj>aj+1时为止。其中aj为堆栈中栈顶的符号，aj+1为句型栈中栈顶符号。

表1：规范归约

表2：OP分析

（2）再从aj开始往左扫描分析栈，直到满足ai-1

（3）NiaiNi+1ai+1… NjajNj+1形式的可归约串即为最左素短语。

结束：句型栈中只剩下#，且分析栈中仅剩下#S（S为开始符号），标志分析成功，否则分析失败，说明该句型不是该文法的句型。

5 结语

算符优先分析算法相对于规范的归约分析法来说，免去了对非终结符的分析，因而分析速度快。但它的缺点是对文法的要求较高，不满足OPG文法的语法分析是不准确的。因而，对于OPG文法的句型的语法分析采用算符优先方法是最优的。