建模語言中的文本表面語法分析方法研究

摘要：通過分析三種常見文法的利弊，采用了擴展的BNF文法進行文本語法規則的描述，并通過準引用（quasiquote）和語法糖方法對該文法進行了改進和擴充，增強了文本語法的描述能力和易用性。通過準引用方法，已經被建立好的文本語法元素的抽象語法能夠被重用來構造新的語法元素。通過使用語法糖，新的語法構件能被轉換到存在的語法構件上。當元模型在實例上執行計算或編譯時，可以通過脫糖（desugar）轉換操作，建立一個新的語法類的實例。

關鍵詞：建模語言；文本表面語法；擴展的巴科斯—諾爾范式；

準引用；語法糖

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)03－0791－04

在語言工程中，需要一種語言以一種統一標準和豐富語義的方式來捕獲、描述和操作語言的所有方面，這種語言就叫做元建模[1]語言。而在廣義上，元模型[2]就是語言的模型，即表示語言工程的主要方式。它有兩個主要的區別于其他模型的特點：a)它必須捕獲被建模語言的主要特性和性質；b）一個元模型應能夠描述一個語言的抽象語法、具體語法和語義。一個元建模語言經常是以三個主要的步驟來定義：a）定義語言的概念與概念之間形式良好的關系，如詞匯表和分類法就是被抽象語法捕獲的；b）語義應以用戶清晰理解的方式來描述；c）精確的描述定義是很重要的，這是由表面語法捕獲的。表面語法是提供給程序員或建模者的具體表達模型的方式，它們是抽象語法的不同視圖。所以一個語言可以有多種表面語法或多個表面語法。抽象語法的定義已經被OMG的四層元模型體系結構標準化了，所以大多數語言規范都是以非正式的方式來描述語義和表面語法的。表面語法的定義被認為是元建模語言中最重要的一部分。表面語法的處理分為兩個階段：包含了解析語法和確保它是合法的；表面語法被用于構建抽象語法。表面語法可以多種方式被建模。模型語言的表面語法主要包括文本表面語法（如Java語言的具體語法）和圖形表明語法（如UML[3]的圖形符號），它們又被簡稱為文本語法和圖語法。

圖像語法經常被用戶顯示的實際情況所限制。元模型定義圖形具體語法已經被OMG和許多作者提出。OMG采納了一個標準來定義UML2.0 (UMLDI)的圖形交互來克服基于XMI的模型交互的缺點。雖然圖像語法用得多，也比較流行，但是文本語法是基礎，必不可少。因此本文主要集中于文本表面語法部分，采用了擴展的BNF文法描述它的文本語法規則，尤其是它與抽象語法的聯系。本文著重講述了表面語法的文本語法解析過程。

1文法

語法的結構和形式規則由文法來描述。文法用于描述具體語法的合法構造規則。本章其余部分將介紹語法的描述方法—文法，以及如何根據文法規則解析一個語法和如何用具體語法構建抽象語法模型。

1．1文法定義

定義1[4]一個上下文無關文法（CFG）G= (VT，VN，S，P)由下列四部分組成：

a)VT是有限的終極符集。

b)VN是有限的非終極符集。

c)S是初始符，S∈VN。

d)P是產生式的有限集。其產生式具有下面形式：

A→X1X2…Xn

其中：A∈VN；Xi∈(VN∪VT)，右部可空。

從定義中可以看出終極符只能出現在產生式的右部。一個正常的文法應滿足這樣的條件，即每個非終極符都至少有一個產生式，并且至少有一次出現在某個產生式中（初始符除外）。每個非終極符都能推導出終極符串（包括空串）。

1．2文法的分類

使用正式文法的一個最重要的方式是：一旦給定了一種語言的文法就應該完備地定義它。在語言中什么允許和什么不允許是一致的。這個非常有用，因為一個文中的語法描述非常模糊，就會有很多不同的解釋。

另一個好處是正式的文法是由數學而來的，可以被計算機理解。有許多程序以給定的BNF及其擴展的方式為輸入，然后自動地為給定的文法產生代碼解析。事實上，這就是產生一個編譯器的最常用的方法：通過使用所謂的compliercomplier輸入文法，然后在一些程序語言中產生解析代碼。

當然，編譯器檢查文法并且它們也產生代碼。這些并不是用BNF文法來描述的。所以compilercompiler經常來連接代碼的特殊語法。常見的文法有如下幾種。

a）BNF[5]BNF表示法是日前最常用的文法表示方法。它主要是由Peter Naur為了描述Algol60程序語言的語法引入的。其可以嚴格地表示語法規則。現在幾乎每一個編程語言都使用BNF來定義編程語言的語法規則。BNF包含的元語言符號為：

（a)〈〉語法成分被放在一對尖括號內；

（b)∷＝或者→表示左邊的語法成分由右邊的語法成分組成（或者定義）；

（c)∣表示具有相同的坐部的產生規則。

例如：〈number〉 ∷＝〈digit〉∣〈number〉〈digit〉

b)EBNF[6]EBNF(extend BNF)，這種表示法是在BNF表示基礎上發展起來的，稱為擴展的BNF。它與BNF具有相同的表達能力，且結構上更簡單和清晰。

EBNF在原來BNF的基礎上又引入了以下三對符號作為元語言符號使用。即：

(a){t}mn表示字符串的任意多次出現（包括0次）。其中：下角標n表示串t重復的最小次數；上角標m表示字符串t重復的最大次數。如：

number：：=digit{digit}

(b)()表示提取產生式中的公共因子，簡化產生式的表示。如有文法規則：

U ∷＝xa︱xb∣…∣xz

引入圓括號提取公共字符串x后有

U ∷＝x(a∣b∣…∣z)

(c)[t]表示字符串t可有可無。

〈條件語句〉∷＝〈如果子句〉[else〈語句〉]

1．3XBNF[7]

XBNF(extreme BNF)，本文中采用另外一種擴展的EBNF文法XBNF。具體定義如下：

a)文法字句的形式 NAME ∷＝ RULE。其中：NAME為規則字句名稱；RULE定義如何識別輸入字符的序列；終止符采用單引號修飾；非終止符采用一個字符序列表達。

如一個計算器的文法規則，它是以“＝”結束的，如下：

Calc ::= Mult ′=′.

Mult::=n1=Add(′*′n2=Mult{n1*n2}|′/′ n2=Mult{n1/n2} |{n1}).

Add ::=n1=Int(′+′n2=Add{n1+n2}| ′-′n2=Add{n1-n2}|{n1}).

b)括號的功能與EBNF相同。如Mult規則的解析結果有以下三種可能：

(a)輸入流滿足規則Add*Mult；

(b)輸入流滿足規則Add/Mult；

(c)輸入流滿足規則Add。

c){ }被用于表示解析過程中執行的語句塊，如{n1*n2}上面解析的成功后執行的動作，這個用于構造具體語法的抽象語法模型，后面將詳細介紹。

d)用星號*代替{}表達符號的0次或多次出現。

如：String∷＝Char*，字符串由0或多個字符組成。

e)[ ]與EBNF相同。

f)每個文法規則以實心句點‘.’結束。

一個文本語言是以文法定義的形式來定義的；文法定義了與語言匹配的字符的合法序列。一旦被定義，文法被提供給解析器并與輸入連接。分析文本輸入和決定它是否合法的過程叫做解析。

在本文中，定義文法的語言叫做XBNF。XBNF是基于EBNF的，它是計算機處理方面表達語言文法的一種標準方式，其功能比EBNF更強大。除了表達控制語言識別的規則外，XBNF支持在解析過程中用來分析數值的動作。

2使用XBNF來構建一個文本語言

XBNF擴展了EBNF。可以用來管理多個文法：(a)必須將文法放在一些地方，以便在需要時能夠使用它；(b)有必要定義一個給定的ASCII流，其文法能夠理解這個文本流。

為了構造一個最小的文本語言，筆者定義一個域模型來描述如何使用XBNF來解析文本程序。假定是從一個領域模型[8]來定義語言，而不是一個逆向工程。

如建立一個文法，這個文法能解析HelloWorld程序：

@HelloWorldModel

hello Andy

hello James

hello Tony

hello Sheila

hello Lili

end;

其文本解析定義如下：

context 〈HelloWorldModel〉

@Grammar

HelloWorldModel ::=h=HelloWorld*

{HelloWorldModel [helloWorlds=h]}.

HelloWorld ::= ′hello′ t=Name

{HelloWorld::HelloWorld [text=t]}.

end

這個文法規則嵌入在@Grammar和end中。@為文法切換符號，用于切換當前的文法到另一個文法，以便解析器能夠通用解析不同的文法規則。

文法的定義由兩部分文法規則組成。在XBNF中，文法規則由文法模式后面跟著一個action組成，這個action放在花括號中。在這個例子中，第一個規則處理HelloWorldModel的解析。它期望解析一個HelloWorld規則序列，這個規則中定義了變量h。它的action構建了一個HelloWorleModel類的實例，并設置helloWorlds屬性給h。注意[]僅僅是一個為了定義變量值的簡單的構造器符號。第二個規則處理HelloWorld的解析。它期待名字‘hello’后跟著另外一個name。它被賦值給變量t。它的action建立一個HelloWorld class的實例，并賦值它的text屬性為變量t。

3建立抽象語法

上一步已經建立了文本語法，下一步就是建立抽象語法。由XBNF所采取的步驟如圖1所示。

由圖1可知，XBNF的文本語法首先通過解析產生抽象語法，抽象語法再通過計算產生了抽象語法模型。在圖1中，有兩種類型的抽象語法和一個具體語法給一個抽象語法到另外一個抽象語法的計算步驟。這是基于XBNF機制的通用性，XBNF能被用在一個更加方便的解析器上下文中，如文本輸入5+5計算出結果等于10。這個文法首先產生了5+5的抽象語法，然后這個求值程序計算出這個抽象語法產生值10。在這個基于語言的模型的定義中，來自這個計算器的值是基于抽象語法的模型。在這種情況下，文法規則首先產生XMF的等價于基于抽象語法模型的值的抽象語法。為了避免混淆，抽象語法即為抽象語法，抽象語法模型叫做抽象語法值。

原始的抽象語法可以根據文法規則來定義，可是這樣定義既冗長又浪費時間。一種改進的方法就是使用一個工具，它可以使這個定義的過程簡化并且可讀性好。該工具是根據所需的抽象語法用一個已存在的基于具體語法來表示而設計的。這個工具叫做準引用（quasiquotes）[9]，允許新的具體語法[10]用舊的具體語法來表示。因為大部分語言傾向于從已有的語言中建立，而且quasiquotes表達式能被用于構建語法模板，通過留出抽象語法占位符，在那里具體語法變量能被嵌入。這樣的quasiquotes能被用于捕捉語法模式。

3．1準引用

當設計語言和構建語言時，準引用通常被用來構建文法。文法可以執行它們動作中的任何命令，尤其是可以構建和返回類的實例。合并語法的文法的特征之一是它們能從相對簡單的構件映射到相對復雜語法樹的映射。語法來自于兩種主要格式：抽象語法和具體語法。抽象語法面向機器，主要是機器代表的數據結構；具體語法面向人類是基于字符的。如下是具體語法：

X+1

與它相等的抽象語法是：

BinExp(Var(\"x\"，\"＋\"，IntExp(1))

為了描述給出抽象語法值的抽象語法，準引用能夠給出能被解析的具體語法的抽象語法。其表示如下：

[︱…︱]

例如，需要建立下面這樣的一個文本表面語法：

＠Operation test(x)

@Check(\"X must be less than 100\") x < 100 end

end

那么，通過準引用獲得它的抽象語法構造：

@Class Check

@Grammar extends OCL∷OCL.grammar

[|

if not 〈e〉 then

self.error(〈StrExp(s)〉)

else

true

end

| ]

end

通常準引用返回的抽象語法并不是所需要的抽象語法，而是需要有值能被嵌入這個已經被解析的抽象語法部分并且被文法規則存儲。在語法上需要被嵌入的被放在〈〉中。在合并的文法動作中，用抽象語法表達實例表達式非常麻煩。實例表達式將變得非常龐大，而且使用者必須記住所有的構件參數。準引用化允許在構造可執行實例時使用具體語法工作。但是，無論是使用2．1節的準引用機制或者直接建立抽象語法，其缺點就是原始的具體語法的丟失，原因是轉換不記錄原始的具體語法的細節。有時這個原始具體語法的細節，在從抽象語法到具體語法的轉換過程中也是有用的，特別是在調試一個模型的過程中。為了支持這個功能，引入了一個方法，叫做語法糖[11]。

3．2語法糖

本文改造語法糖解決無法保留語法轉換前的源語法的問題。對于直接構造抽象語法規則，語法糖采用間接構造抽象語法規則，通過實例化sugar類型的類，采用脫糖方法建立抽象語法并提供方法作保留具體語法。

通過改造語法糖能夠提供這個能力。語法糖最初是由P. J. Landin給出的一個名詞，為計算機語言添加的，其主要是不影響語言的表達而對于人類使用更加“有甜頭”。語法糖給程序員一個使用編碼的可選方式，即或變得更加簡潔，或編程符號看起來更加熟悉。語法糖能很容易地被轉換，產生一個用更簡單的核語法編寫的程序。一些編程語言，如LISP、ML和scheme被明確地設計為一個基本構件的語言核，其他特征能被脫糖（desugar）到這個語言核。這樣可以采用語法糖來實現語法到其他語法的轉換。

Sugar通常被用于新語法構件，通過反應到存在的語法構件來實現。這個轉換經常被稱為desugaring（脫糖）。它是建立一個新的語法類型實例的方法。

一個sugar的例子如下：

@When passengers > 63 do

format( stdout，\" Too many people on the bus.~%\")

end

這個條件語句被作為一個語法類來實現，desugar操作產生等效if表達式。

@Class When extends Sugar

@Property guard : Performable end

@Property body : Performable end

@Constructor(guard，body) end

@Operation desugar():Performable

[| if 〈guard〉

then 〈body〉

else \" guard fail\"

end

|]

end

end

任何擴展sugar的類必須重載抽象的脫糖操作desugar()返回抽象語法。附加的的方法如pprint（）被用于給出一個來自抽象語法的原始的具體語法。在上面的例子中，文本@Whendoend被送到輸出流。

@Operation pprint(out:OutputChannel，indent:Integer)

format(out，\"When \");

guard.pprint(out，indent);

format(out，\" do~%~V\"， Seq{indent+2});

body.pprint(out，indent+2);

format(out，\"~%~Vend\"，Seq{indent})

end

end

構建sugar類的文法規則如下：

@context When

@Grammar extends OCL::OCL.grammar

When ::=guard=Exp ′do′ body=Exp {

When(guard，body)

}.

end

通過語法糖，新的語法構件能被轉換到存在的語法構件實現。這個脫糖的轉換desugar操作建立一個新的語法類的實例，然后當xMOF在實例上執行計算或編譯時，執行desugar。通過脫糖步驟到最后時刻，原始語法構件結構能盡可能長的時間保留。

4結束語

表面語法是提供給建模者的具體表達模型的方式。在可執行元模型中，元建模語言可以擁有文本表面語法和圖形表面語法。在本文中主要分析了文本表面語法，介紹了三種主要的文法：BNF、EBNF、XBNF，并且采用了XBNF文法來描述模型的文本表面語法。此外，針對XBNF使用中存在的使用復雜、易用性差等問題，研究了基于已有的文本語法獲得它們的抽象語法的準引用方法，通過準引用方法，已經被建立好的文本語法元素的抽象語法能夠被重用來構造新的語法元素，并通過使用語法糖來解決表面語法到抽象語法轉換中原始的表面語法的丟失問題。

參考文獻：

［1］BERKI E，GEORGIADOU E，HOLCOMBE M.Requrirements engineering and process modeling in software quality managementtowards a generic process metamodel[J].Software Qulity Control，2004，12(3):265－283.

[2]VOLTER M，BETTIN J.Patterns for modeldriven softwaredevelopment[C]//Proc of the 9th European Conference on Pattern Languages of Programs.Irsee:[s.n.]，2004:18－24.

[3]TARIQ N A，AKHTER N.Comparison of model driven architecture (MDA) based tools[D].Stockholm:Department of Computer and Systems Science， Royal Institute of Technology(KTH)，2005:613.

[4]金成植.編譯程序構造原理和實現技術[M].北京:高等教育出版社，2000:63－64.

[5]SLONNEGER K，KURTZ B L.Formal syntax and semantics of programming languages:a laboratory based approch[M].United States:AddisonWesley Publishing Company，1995:18－46.

[6]GARGANTINI A，RICCOBENE E，SCANDURRA P.Deriving a textual notation from a metamodel: an experience on bridging model ware and grammarware[C]//SINDEREN M van.European Workshop on Milestones，Models and Mappings for Modeldriven Architecture: CITI Workshop Proceedings Series.Netherland:[s.n]，2006:41－54.

[7]FRANKEL D S.MDA journal[EB/OL].(200410).http://www.davidfrankelconsulting.com/MDAJournal.htm.

[8]BATORY D，LOFASO B，SMARAGDAKIS Y.JTS:tools for implementing domainspecific languages[C]//Proc of the 5th International Conference on Software Reuse.Washington DC:IEEE Computer Society，1998:143153.

[9]CLARK T，EVANS A，SAMMUT P，et al.Applied meta modelling:a foundation for language driven development[EB/OL].(200410).http://www.xactium.com.

[10]VISSER E.Metaprogramming with concrete object syntax[C]//Proc of the 1st ACM SIGPLAN/SIGSOFT Conference.2002:299－315.

[11]LAAN KV Der.Syntactic sugar[C]//Proc of the 1993 Annual Meeting.Aston，VK:[s.n.]，1993:310－318.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”