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

吳大非

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

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

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

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

1 預(yù)備知識(shí)與背景

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

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

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

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

1.1 基本概念

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

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

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

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

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

定義4（優(yōu)先函數(shù)） 給定算符優(yōu)先文法及算符優(yōu)先矩陣，如果存在滿足以下性質(zhì)的函數(shù)f、g，則說(shuō)它們?yōu)橄鄳?yīng)關(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ù)較準(zhǔn)確地刻畫了優(yōu)先關(guān)系，就存貯而言，可以節(jié)省大量空間。

1.2 問(wèn)題與動(dòng)機(jī)

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

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

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

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

2.1 Floyd方法

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

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

2.2 改進(jìn)算法與原理

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

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

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

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

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

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

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

3 例證與分析

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

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

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

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

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

4 結(jié)束語(yǔ)

優(yōu)先關(guān)系的技術(shù)實(shí)施問(wèn)題是算符優(yōu)先分析法的關(guān)鍵所在。以上分析和改進(jìn)了一直被廣泛采用的Floyd的優(yōu)先函數(shù)計(jì)算方法，取得了滿意的結(jié)果。在改進(jìn)算法基礎(chǔ)上，關(guān)系檢測(cè)操作基本做到量需進(jì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.