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文法的句型的語法分析采用算符優先方法是最優的。