OPG文法的語法分析優(yōu)化策略

文/關(guān)玉欣

語法分析方法中自上而下的分析是指從文法的開始符號(hào)出發(fā)，反復(fù)的選擇產(chǎn)生式進(jìn)行推導(dǎo)，最終推導(dǎo)出句型；自下而上分析是指從待分析的句型本身出發(fā)，逐步選擇產(chǎn)生式進(jìn)行歸約，直至歸約到文法的開始符號(hào)。這兩類分析都可以利用各種語法分析算法進(jìn)行。每種語法分析算法都有其優(yōu)勢(shì)和局限性，根據(jù)文法的類型，可以選擇最優(yōu)的語法分析算法進(jìn)行語法分析。

1 OPG文法

Chomsky將文法分為短語文法、上下文有關(guān)文法、上下文無關(guān)文法和正規(guī)文法四類。OPG文法是上下文有關(guān)文法中的一種，該文法的特殊性在于任意兩個(gè)終結(jié)符之間最多只存在<、=、>三種優(yōu)先關(guān)系中的一種優(yōu)先關(guān)系，文法的產(chǎn)生式中不會(huì)出現(xiàn)兩個(gè)相鄰的非終結(jié)符。根據(jù)文法的特性可以推論該文法的任何句型也不會(huì)含有相鄰的非終結(jié)符，這就為使用優(yōu)化的OP分析法進(jìn)行句型分析奠定了基礎(chǔ)。

2 規(guī)范歸約

歸約與推導(dǎo)是一個(gè)逆過程，規(guī)范歸約過程中一直本著最左的歸約原則，每次分析過程中首先找到句型中的句柄，句柄是句型中的最左直接短語，之后根據(jù)產(chǎn)生式規(guī)則向左歸約，用產(chǎn)生式的左部去替換產(chǎn)生式右部。例如對(duì)OPG文法G[E]：E→T|E+T T→F|T*F F→i|(E)的句型T+T*F+i的分析如表1所示。

上述句型分析中每步都是在句型中尋找最左直接短語，也就是文法中某條產(chǎn)生式的右部。進(jìn)行最左歸約實(shí)質(zhì)上就是用某條產(chǎn)生式的左部非終結(jié)符去替換產(chǎn)生式的右部符號(hào)串。根據(jù)句型的不同，歸約的步驟也會(huì)有區(qū)別，但分析成功的標(biāo)志就是歸約到OPG文法的開始符號(hào)，代表句型分析成功。在上述的規(guī)范歸約過程中，句型T+T*F+i總歸約次數(shù)為6。

3 優(yōu)化的OP分析

在自底向上的句型分析方法中，OP（Operator Priority）分析法僅考慮句型中終結(jié)符的優(yōu)先關(guān)系，從而確定每一步分析過程中的句柄。OP分析過程中也仍然采用最左歸約，但由于句柄中忽略非終結(jié)符的屬性，因而句柄的概念需要進(jìn)行精確刻畫，用最左素短語來描述歸約過程中的句柄。

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

其中：ai-1aj+1

根據(jù)OPG的特點(diǎn)，素短語中沒有多個(gè)非終結(jié)符相鄰的情況，且至少要包含一個(gè)終結(jié)符，也不能再包含其它的素短語。

由于OP分析過程中每次分析都對(duì)句型中的素短語進(jìn)行歸約，忽略了單一非終結(jié)符組成的句柄的歸約，由此可以看出，OP分析方法并不是一種規(guī)范的歸約方法。上述OPG文法的句型的分析，采用OP分析法分析過程如表2所示。

OP分析過程中，省掉了T1、F、T2三個(gè)僅由單個(gè)非終結(jié)符組成的短語的歸約，因而分析過程相對(duì)于規(guī)范的歸約少了兩個(gè)分析步驟，分析效率提高，僅需歸約4次即可完成該句型的分析。

4 OP分析算法設(shè)計(jì)

OP分析法特別適合OPG文法的句型的分析，在分析的每一步需要確定最左素短語進(jìn)行最左歸約。分析過程中需要借助于堆棧存儲(chǔ)待分析句型以及分析結(jié)果，并且分析過程中需要查找終結(jié)符之間的優(yōu)先關(guān)系。OP分析算法設(shè)計(jì)如下：

初始化：分析棧初始為#，句型棧存入待分析句型#。

分析：

（1）從左向右掃描待分析句型并逐個(gè)移入分析棧，查找優(yōu)先矩陣，直至找到滿足aj>aj+1時(shí)為止。其中aj為堆棧中棧頂?shù)姆?hào)，aj+1為句型棧中棧頂符號(hào)。

表1：規(guī)范歸約

表2：OP分析

（2）再?gòu)腶j開始往左掃描分析棧，直到滿足ai-1

（3）NiaiNi+1ai+1… NjajNj+1形式的可歸約串即為最左素短語。

結(jié)束：句型棧中只剩下#，且分析棧中僅剩下#S（S為開始符號(hào)），標(biāo)志分析成功，否則分析失敗，說明該句型不是該文法的句型。

5 結(jié)語

算符優(yōu)先分析算法相對(duì)于規(guī)范的歸約分析法來說，免去了對(duì)非終結(jié)符的分析，因而分析速度快。但它的缺點(diǎn)是對(duì)文法的要求較高，不滿足OPG文法的語法分析是不準(zhǔn)確的。因而，對(duì)于OPG文法的句型的語法分析采用算符優(yōu)先方法是最優(yōu)的。