求解優(yōu)先函數(shù)的改進型Floyd方法

吳大非

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

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

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

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

1 預備知識與背景

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

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

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

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

1.1 基本概念

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

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

優(yōu)先關系一般用矩陣表示。以圖1所示的兩個算符優(yōu)先文法為例，它所規(guī)定的倆優(yōu)先矩陣見表1.該表界定了理解句子的一個基本原則，而憑此就可以設計實現(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系的優(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)先關系，就存貯而言，可以節(jié)省大量空間。

1.2 問題與動機

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

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

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

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

2.1 Floyd方法

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

算法1 (Floyd方法) 設G為算符優(yōu)先文法, T、P分別為終結符集和相應的優(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的既有計算結果的動蕩；而每一動蕩的修正、調(diào)整又會招致新一輪迭代檢測（需n2次檢測運算）。特別地，優(yōu)先矩陣某些情形下還可能是稀疏矩陣。例如假設某算符文法的終結符集為T，關于開始符S的產(chǎn)生式為S→N1a1N2a2…Nm-1am-1Nm，又設各Ni(1≤i≤m)能導出的終結符集相對獨立且一道構成T-{a1,…,am-1}的一個劃分，則優(yōu)先矩陣即為稀疏矩陣刻畫的優(yōu)先關系R(?T×T )。鑒于此，對算法1進行了必要改進。

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

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

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

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

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

算法2（改進方法）：設Less為按行存放的優(yōu)先矩陣中具有“?”關系的偶對序列，Great為按列存放的優(yōu)先矩陣中具有“?”關系的偶對序列，Equal是優(yōu)先矩陣中一切具有“?”關系的偶對序列，且初始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一切終結符偶對 36 2 2 2 2 3 3 2一切終結符偶對 36 4 4 4同上取值 3一切終結符偶對 36 同上取值改進算法1 1 1 1 1 1 0 0 1 1 1 1 1 1 2 2 2 2 1實際有效終結符偶對 23 2/3 2/3 2/3 2 3 3 3 3 2a，、/，、），、，，、, a、, /、, (、（）、## 9 4 4 4同上取值 3 （）、## 2 同上取值

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

4 結束語

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

[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.