吳大非

(湖南科技學院 信息技術(shù)與教育系，湖南 永州 425199)

有關(guān)算符優(yōu)先文法及其語言的研究雖可往后追溯到Floyd于1963年所開展的工作[1]，但其影響深遠，仍然是我們分析部分上下文無關(guān)語言所采用的重要技術(shù)之一。

針對優(yōu)先語言的分析問題而被設(shè)計和引入的自動分析手段叫算符優(yōu)先分析法。該法包括分析總控程序和操作支持部件即棧兩部分。前者是固定的，不因所面對的文法的改變而改變，后者則依據(jù)分析對象間的優(yōu)先關(guān)系制約、組織著整個分析過程。因而，優(yōu)先關(guān)系一定意義上可視為算符優(yōu)先分析法的靈魂所在。因為算符優(yōu)先分析法簡潔易于實現(xiàn)，現(xiàn)已成為借助棧實施表達式處理的經(jīng)典方法。

優(yōu)先關(guān)系的實施技術(shù)主要有矩陣表示法和優(yōu)先函數(shù)兩種[1]，前者在信息刻畫方面清晰詳盡，但美中不足是空間損耗大，遠不如優(yōu)先函數(shù)帶來的優(yōu)越性能。本文深入探討優(yōu)先函數(shù)的Floyd計算方法，指出其存在的問題，并給出相應的改進辦法。

1 預備知識與背景

算符優(yōu)先文法（Operator Precedence Grammar, OPG）及其語言自Floyd提出以來，得到了廣泛關(guān)注和應用。文獻[12-14]等是早期的研究，主要致力和介紹語言分析方法的改進與應用。例如在優(yōu)先關(guān)系的實施問題上，Martin在文獻[12]基礎(chǔ)上解答了有關(guān)優(yōu)先函數(shù)計算中涉及的發(fā)現(xiàn)和存在性問題。文獻[14]又將文獻[13]涉及的布爾矩陣予以分塊，再利用數(shù)學手段在分塊陣的分步求值基礎(chǔ)上將原有運算重疊于必要的公共空間上，從而獲得物理資源利用上的性能提升。

表達式是科學研究過程中經(jīng)常碰到的數(shù)學概念，涉及表達、解讀兩個環(huán)節(jié)，一般用以刻畫研究對象間的復合、相互表征等問題。算符優(yōu)先文法除卻適合表達式的描述以外，也適合程序語言、半結(jié)構(gòu)數(shù)據(jù)的描述。如Floyd就以優(yōu)先文法刻畫、分析過ALGOL60。因為它簡潔易用，現(xiàn)也是借助棧實施表達式處理的常用方法。

文獻[2, 15-16]給出了一些新近成就。著名的VPL ( Visibly Pushdown Language)[17]是既適合描述程序分析問題又能像正規(guī)語言那樣而易于處理的確定型上下文無關(guān)語言。因為算符優(yōu)先文法可以定義 VPL, 看似無關(guān)的兩個語言又變得水乳交融起來。這為人們重新考量和關(guān)注OPG的價值、應用迎來新的契機。

本工作旨在探討OPG關(guān)鍵支撐技術(shù)即優(yōu)先函數(shù)計算方法的改進問題。為方便后續(xù)討論，先對它的基本知識與問題做一交代。

1.1 基本概念

定義1（算符文法） 一個上下文無關(guān)文法叫做算符文法，如果其任何句型中都不含兩個及以上相繼出現(xiàn)的非終結(jié)符。

定義3（算符優(yōu)先文法） 一個算符文法叫做算符優(yōu)先文法，如果其任意終結(jié)符對之間最多只能滿足上述三種優(yōu)先關(guān)系之一。

優(yōu)先關(guān)系一般用矩陣表示。以圖1所示的兩個算符優(yōu)先文法為例，它所規(guī)定的倆優(yōu)先矩陣見表1.該表界定了理解句子的一個基本原則，而憑此就可以設(shè)計實現(xiàn)一個基于棧的表達式或句子處理算法。這一方法也叫算符優(yōu)先分析法，是棧的經(jīng)典應用之一。

圖1 算符優(yōu)先文法

表1 算符優(yōu)先文法1和2的優(yōu)先矩陣

定義4（優(yōu)先函數(shù)） 給定算符優(yōu)先文法及算符優(yōu)先矩陣，如果存在滿足以下性質(zhì)的函數(shù)f、g，則說它們?yōu)橄鄳P(guān)系的優(yōu)先函數(shù)。

（1）a?b，則f(a)＞g(b)；

（2）a?b，則f(a)＜g(b)；

（3）a?b，則f(a)=g(b)。

顯然優(yōu)先函數(shù)較準確地刻畫了優(yōu)先關(guān)系，就存貯而言，可以節(jié)省大量空間。

1.2 問題與動機

算符優(yōu)先語言的分析方法通常叫做算符優(yōu)先分析法。它的句型分析原理是：以移進-歸約的自下而上分析方式，反復讀取和處理待分析的表達式或源碼，并將分析過程所得的結(jié)果保存在分析棧中；歸約原則是按最左素短語進行歸約，即依據(jù)優(yōu)先矩陣，一旦發(fā)現(xiàn)棧頂呈現(xiàn)出可稱謂最左素短語的可歸約子串，就將該子串替換為適當產(chǎn)生式的左部符號。這一分析過程周而復始，直到所有源碼處理完畢。有關(guān)更詳盡的內(nèi)容，讀者可以參見文獻[1, 4-10]。

上述分析原理表明，優(yōu)先關(guān)系控制著移進/歸約的實施過程，是算符優(yōu)先分析法的核心技術(shù)與靈魂所在。照實保存優(yōu)先矩陣不失為一種實現(xiàn)技術(shù)，但會消耗過多的存貯資源，總計可達O(n2)存貯單元。因此通常采用優(yōu)先函數(shù)作為其信息壓縮手段。這樣可將空間消耗量降至O(n)個。

給定算符優(yōu)先矩陣情形下，優(yōu)先函數(shù)既可通過人為設(shè)置也可采用Bell方法或Floyd方法來自動獲得。鑒于Floyd方法簡潔易于實現(xiàn)，一直沿用至今，以下對它深入分析，以期對其進行有效改進、提升性能。

2 優(yōu)先函數(shù)的計算

2.1 Floyd方法

Floyd方法是便捷易用的優(yōu)先函數(shù)計算方法。它與Bell方法類似,兩者均以優(yōu)先關(guān)系矩陣為基礎(chǔ)。以下是它的具體描述。由循環(huán)體可見，該算法的主要問題是數(shù)據(jù)的訪問或修正量過大，每次迭代都需進行全體優(yōu)先矩陣元素的檢測。這便值得關(guān)注，自然成為我們改進的目標。

算法1 (Floyd方法) 設(shè)G為算符優(yōu)先文法, T、P分別為終結(jié)符集和相應的優(yōu)先矩陣, 則優(yōu)先函數(shù)f、g存在情況下可按下述步驟獲得[1,5,7-10]:

2.2 改進算法與原理

算法1中fa、gb分別代表f(a)和g(b)的取值?？梢?，只要fa、gb因循環(huán)體的執(zhí)行有一小小改變就有可能引發(fā)f、g的既有計算結(jié)果的動蕩；而每一動蕩的修正、調(diào)整又會招致新一輪迭代檢測（需n2次檢測運算）。特別地，優(yōu)先矩陣某些情形下還可能是稀疏矩陣。例如假設(shè)某算符文法的終結(jié)符集為T，關(guān)于開始符S的產(chǎn)生式為S→N1a1N2a2…Nm-1am-1Nm，又設(shè)各Ni(1≤i≤m)能導出的終結(jié)符集相對獨立且一道構(gòu)成T-{a1,…,am-1}的一個劃分，則優(yōu)先矩陣即為稀疏矩陣刻畫的優(yōu)先關(guān)系R(?T×T )。鑒于此，對算法1進行了必要改進。

下面介紹改進算法的思想和所依據(jù)的數(shù)學原理?？傮w而言，我們希望做到：檢測、函數(shù)調(diào)整要有針對性，即盡量調(diào)整那些可能需要調(diào)整的fa和gb。

在給定優(yōu)先矩陣的前提下，我們將優(yōu)先關(guān)系按?、?、?分成Less、Equal和Great三組（每組中的終結(jié)符偶對間都滿足同一類優(yōu)先關(guān)系）。進而再設(shè)每一組中的優(yōu)先關(guān)系具有一定的局部秩序（依據(jù)優(yōu)先矩陣按行或列序原則組織同類優(yōu)先關(guān)系的排列），如對a ∈T而言，讓{a?b| b∈T, 且a和b之間滿足?關(guān)系}中的元素占據(jù)Less序列（滿足“?”關(guān)系的全體終結(jié)符偶對組成的序列）某連續(xù)位置區(qū)域，那么，針對優(yōu)先矩陣獲得的以下Great、Less序列為改進算法提供了有用的性質(zhì)。

Less的性質(zhì)：若Less是按行序原則排列優(yōu)先矩陣的一切“?”關(guān)系所得的序列，那么關(guān)于g函數(shù)的一個增大的變化可能會在Great中引起局部變化，但對于Less中滿足f(X)＜g(Y )的一切實例具有保向性。

Great的性質(zhì)：若Great是按列序原則排列優(yōu)先矩陣的一切“?”關(guān)系所獲得的序列，那么關(guān)于f函數(shù)的一個增大的變化可能會引起Less的局部變化，但對于Great中滿足f(X )＞g(Y )的一切實例具有保向性。

根據(jù)以上性質(zhì)，可以改進Floyd算法如下。其中FofModifiedLess表示為了滿足Less關(guān)系描述而被調(diào)整過的f的定義點；GofModifiedGreat表示為了滿足Great關(guān)系描述而被調(diào)整過的g的定義點。

算法2（改進方法）：設(shè)Less為按行存放的優(yōu)先矩陣中具有“?”關(guān)系的偶對序列，Great為按列存放的優(yōu)先矩陣中具有“?”關(guān)系的偶對序列，Equal是優(yōu)先矩陣中一切具有“?”關(guān)系的偶對序列，且初始FofModifiedLess= {a | a?b ∈ Less}，GofModifiedGreat= {b | a?b ∈ Great}，則優(yōu)先函數(shù)f、g存在情況下可按下述改進方法獲得。

3 例證與分析

為比較和了解兩個算法的迭代過程，我們以表1所示的兩個優(yōu)先矩陣為例來檢證以上算法。Floyd方法與改進算法的執(zhí)行對比分別見表2和表3。

表2 針對優(yōu)先矩陣1的迭代過程

表3 針對優(yōu)先矩陣2的迭代過程

Floyd算法1 1 1 1 1 1 0 0 1 1 1 1 1 1 2 2 2/3 2/3 1一切終結(jié)符偶對 36 2 2 2 2 3 3 2一切終結(jié)符偶對 36 4 4 4同上取值 3一切終結(jié)符偶對 36 同上取值改進算法1 1 1 1 1 1 0 0 1 1 1 1 1 1 2 2 2 2 1實際有效終結(jié)符偶對 23 2/3 2/3 2/3 2 3 3 3 3 2a，、/，、），、，，、, a、, /、, (、（）、## 9 4 4 4同上取值 3 （）、## 2 同上取值

由表2和3可見，兩個算法的迭代結(jié)果完全一樣，但改進算法每次迭代中基本只對需要調(diào)整的函數(shù)定義進行必要的修正或訪問，因而提高了處理性能。就文法1和2的分析（不計初始化）而言，原方法的迭代執(zhí)行對終結(jié)符偶對一共進行了3*36=108次的檢測操作或訪問，改進方法則對終結(jié)符偶對分別進行約53次和34次檢測或訪問。

4 結(jié)束語

優(yōu)先關(guān)系的技術(shù)實施問題是算符優(yōu)先分析法的關(guān)鍵所在。以上分析和改進了一直被廣泛采用的Floyd的優(yōu)先函數(shù)計算方法，取得了滿意的結(jié)果。在改進算法基礎(chǔ)上，關(guān)系檢測操作基本做到量需進行，因而成倍減少了冗余的比較等操作。

[1]R.W.Floyd.Syntactic Analysis and Operator Precedence[J].J.Assoc.Comput.Mach,1963,10(3):316-333.

[2]Alessandro Barenghi,Stefano Crespi Reghizzi,Dino Mandrioli,Matteo Pradella.Parallel parsing of operator precedence grammars[J].Information Processing Letters, 2013,1-11.

[3]D.Grune and C.J.Jacobs.Parsing Techniques: A Practical Guide[M].Springer,2008.

[4]Michael Main,Walter Savitch, Data Structures and Other Objects Using C++ (4thEdition) [M].Pearson Education Asia Limited and Tsinghua University Press,2012.

[5]He Yan-xiang,Wu Chun-xiang,Wang han-fei.Compiler Principle[M].Beijing: China Machine Press, 2010.

[6]Chen Huo-wang, Liu Chun-lin, Tan Qing-ping, et al.Programming Language:Compiler Principle (3rdEdition) [M].Beijing:National Defence Industry Press,2009.

[7]Chen Ying,Chen Shuo-ying,Ji Wei-xing.Compiler Principle[M].Beijing: Tsinghua University Press,2009.

[8]Liu Ming, Xu Lan-fang, Luo Ting.Compiler Principle (3rdEdition)[M].Beijing: Publishing House of Electronic Industry, 2011.

[9]Zhang Jing.Compiler Principle[M].Harbin: Harbin Engineering University Press,2011.

[10]Jiang Li-yuan,Kang Mu-Ning.Compiler Principle (3rdEdition)[M].Xi An: Northwestern University Press,2005.

[11]Yan Wei-min,Wu Wei-min.Data Structure Using C[M].Beijng:Tsinghua University Press,2012.

[12]J.R.Bell.A New Method for Determining Linear Precedence Functions for Precedence Grammars.CACM,1969,12:567-569.

[13]D.E.Martin.A Boolean Matrix Method for the Computation of Linear Precedence Functions.CACM,1972,15:448-454.

[14]C.Duong-Kien, H.J.Hoffman, D.Muth[J].A improvement to Martin's algorithm for computation of linear precedence functions,CACM, 1976,19(10): 576-577.

[15]Violetta Lonati,Dino Mandrioli,and Matteo Pradella.Precedence Automata and Languages[J].CSR 2011,LNCS 6651,2011,291-304.

[16]Stefano Crespi Reghizzi, Dino Mandrioli.Operator Precedence and the Visibly Pushdown Automata[J].J.Computer and System Sciences, 2012,78:1837-1867.

[17]Rajeev Alur,P.Madhusudan.Visibly Pushdown Language[M].In STOC: ACM Symposium on Theory of Computing, STOC 2004.