王海燕，楊鶴標

（1.宿遷學(xué)院計算機科學(xué)系，江蘇 宿遷223800；2.江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江212013）

0 引言

編譯技術(shù)已廣泛應(yīng)用于編譯器構(gòu)造之外的其他領(lǐng)域，如程序分析、模型轉(zhuǎn)換、語言處理等領(lǐng)域［1］。所有這些領(lǐng)域的應(yīng)用，說明了編譯技術(shù)的普遍性和重要性。為了簡化編譯技術(shù)的處理，用戶通常將編譯處理的工作分為前端編譯和后端編譯2個部分，前端編譯完成語言源代碼的分析，同時為后端編譯提供必要的信息；后端編譯則是在前端編譯的基礎(chǔ)上，完成代碼生成及代碼優(yōu)化等工作。鑒于編譯技術(shù)應(yīng)用的普遍性和重要性，結(jié)合ANTLR構(gòu)建編譯器的優(yōu)勢，文章詳細描述了以ANTLR作為編譯器分析工具遇到的關(guān)鍵技術(shù)問題，并對此問題進行分析，給出了可行的解決方案。

1 ANTLR設(shè)計前端基礎(chǔ)

1.1 ANLTR簡介

ANTLR是語言識別器的一種，其前身是PCCTS。ANTLR接受EBNF［2］描述的規(guī)則，采用自頂向下的遞歸分析方法，是LL（＊）分析方法的一種實現(xiàn)方式［3］。用戶可以通過ANTLR提供的元語言完成各種源代碼的文法描述，進而通過ANTLR解析所描述的文法，生成各種目標語言的源代碼，如：C、C＋＋、C＃、Java、Python。目前，ANTLR是一個免費的、開放源代碼的工具，已經(jīng)在研究領(lǐng)域和商業(yè)領(lǐng)域得到了廣泛的使用，與其他編譯分析器相比，ANTLR的好處有［4］：（1）錯誤處理能力強，生成的代碼為面向?qū)ο箫L(fēng)格；（2）具有良好的可讀性、便于調(diào)試；（3）異常錯誤處理的最小粒度可以得到具體的標號；（4）可以在文法定義的任何位置設(shè)置返回值和參數(shù)。

1.2 前端的整體結(jié)構(gòu)

編譯器前端的設(shè)計包含了詞法分析和語法分析，通過詞法、語法分析可以構(gòu)造目標語言及抽象語法樹，進而為后續(xù)的程序分析、模型轉(zhuǎn)換、語言處理提供基礎(chǔ)。前端的整體結(jié)構(gòu)如圖1所示。

圖1 前端結(jié)構(gòu)

圖1中詞法規(guī)則描述、語法規(guī)則描述是ANTLR進行詞法分析和語法分析的基礎(chǔ)。顯然無論是詞法規(guī)則描述不正確，還是語法規(guī)則描述不正確，其結(jié)果都無法形成相應(yīng)的分析器；此外，即使詞法、語法各自的規(guī)則描述正確，能生成對應(yīng)的詞法分析器和語法分析器，但若是規(guī)則描述不恰當、不精簡、不明確，則生成的代碼必然存在質(zhì)量低下等問題。因此，本文提出了基于ANTLR前端編譯器的若干關(guān)鍵技術(shù)的解決方案。

2 關(guān)鍵技術(shù)

圖1中的源代碼代表了某種領(lǐng)域特定語言，即領(lǐng)域?qū)Ｓ谜Z言（domain specific language，DSL），這種語言的基本思想是“求專不求全”，不像通用目的語言那樣目標范圍涵蓋一切軟件問題，而是專門針對某一特定問題的計算機語言［5］。

對于這種語言的結(jié)構(gòu)我們可以用文法來描述，文法無論對語言的設(shè)計還是對編譯器的編寫，至少在以下3個方面起著重要的作用：（1）文法給出了易于理解的、精確的語言結(jié)構(gòu)的描述；（2）以文法為基礎(chǔ)的語言，便于增加、修改、刪除舊的語言結(jié)構(gòu)；（3）有些類別的文法，可以自動生成高效的分析器。

文法（Grammar）通?？梢员硎緸樗脑M：G（Z）＝（Vn，Vt，S，P）。其中Vn 表示非終結(jié)符（定義對象的集合，如語法成分等）；Vt表示終結(jié)符（字母表）；S是非終結(jié)符，表示文法的開始符號；P是產(chǎn)生式的有限集合，即規(guī)則集。文法識別，常采用自頂向下的LL（K）分析方法和自底向上的LR分析方法。一般認為LL（K）分析方法較LR（K）分析方法便于被人們所接受和采用［6］。ANTLR最初采用的是LL（K）遞歸下降分析法，現(xiàn)已升級為LL（＊）遞歸下降分析方法，該方法較之前的方法有了明顯的改善，但無論采用LL（K）還是采用LL（＊），遞歸下降法都是一種自上而下的分析模式，即從入口產(chǎn)生式開始分析，根據(jù)所分析的記號流表現(xiàn)形式，匹配不同的產(chǎn)生式。

2.1 左遞歸

如前所述升級版ANTLR采用的是LL（＊）分析方法，而LL分析法是不支持左遞歸文法的。為此在制作文法時，用戶首先要考慮的是怎樣避免左遞歸。接下來，我們按照左遞歸存在的2種形式——直接左遞歸和間接左遞歸，進行分別討論。

2.1.1 直接左遞歸

上式中大寫字母表示文法規(guī)則，小寫字母表示詞法符號。（1）式規(guī)則A的產(chǎn)生式有2個，分別是Aa和b。第一個產(chǎn)生式Aa，最左端包含了A，這是一個直接左遞歸；（2）式 A 產(chǎn)生bB；（3）式B產(chǎn)生aB和空集。（1）式經(jīng)化解后，轉(zhuǎn)化為（2）式和（3）式，消除了左遞歸。

2.1.2 間接左遞歸

化解步驟：

（1）首先轉(zhuǎn)化為直接左遞歸式

（2）在步驟（1）基礎(chǔ)之上，再用直接左遞歸轉(zhuǎn)化為不含遞歸的產(chǎn)生式。

（3）經(jīng)步驟（2）化解為：

間接左遞歸（4）、（5）兩式經(jīng)化解后，轉(zhuǎn)化為（7）、（8）兩式，同樣也消除了左遞歸。

經(jīng)過上述分析，無論是直接左遞歸還是間接左遞歸均可通過化解消除。我們把經(jīng)化解消除后得到的產(chǎn)生式稱之為尾遞歸（所謂尾遞歸形如：B－＞aB）。有了尾遞歸，借助ANTLR的元語言可以將其進一步改寫，得到相應(yīng)規(guī)則的文法描述。

2.2 算符的結(jié)合性

算符連接操作數(shù)構(gòu)成最基本的表達式，無論是單目算符還是多目算符，算符都有其自身的結(jié)合性，算符的結(jié)合性不外乎左結(jié)合和右結(jié)合，接下來分別討論2種結(jié)合性在ANTLR中的文法形式。

2.2.1 左結(jié)合

左結(jié)合，諸如算術(shù)運算符：＋、－、＊、／、%，關(guān)系運算符：＞、＜、＝＝、?。?。在LL識別器中，左結(jié)合算符通過指定重復(fù)匹配進行定義，形式如下：A－＞a（（op）a）＊。

2.2.2 右結(jié)合

右結(jié)合，諸如賦值運算符：＝、＋＝、%＝。a＝b＝c等價于a＝ （b＝c）。在LL識別器中，右結(jié)合算符通過尾遞歸文法進行定義，形式如下：B－＞a op B。

2.3 算符的優(yōu)先級

在LL文法識別器中，算符的優(yōu)先級要通過文法的嵌套定義來體現(xiàn)。優(yōu)先級低的算符要優(yōu)先聲明，相同優(yōu)先級的算符可以在同一個規(guī)則中描述。形式如下：

式中op1的優(yōu)先級低于op2的優(yōu)先級。

2.4 語法斷言

ANTLR通過元語言定義文法規(guī)則，在進行文法分析時，它提供了語法預(yù)測和語義預(yù)測。這兩種預(yù)測機制要求用戶要事先設(shè)定向前看的K值，以用于匹配某一產(chǎn)生式。但有的時候，用戶無法根據(jù)匹配的句子事先確定預(yù)測機制中的K值，此時用戶可以不考慮K值的定義，選用ANTLR中提供的語法斷言。ANTLR的語法斷言可以處理復(fù)雜的語言結(jié)構(gòu)，解決LL（＊）預(yù)測中最多只能向前看K個符號的問題，如：

上述產(chǎn)生式中A、B、C、D代表文法規(guī)則，a代表某種詞法符號，’＝＞’是語法斷言推導(dǎo)符號，由于無法根據(jù)K值確定某一產(chǎn)生式，故令K＝1。根據(jù)語法斷言符號（’＝＞’）之前條件表達式，可以推導(dǎo)出產(chǎn)生式A。

從以上關(guān)鍵技術(shù)的研究可以看出：本文提出的解決方案，統(tǒng)一了文法的制作思想，無論應(yīng)用于何種領(lǐng)域語言，該技術(shù)的研究都可以幫助用戶快速有效地制作文法，實現(xiàn)基于ANTLR的編譯器制作。接下來我們將此研究應(yīng)用于實際領(lǐng)域語言，并以Java語言作為目標代碼，實現(xiàn)了一次開發(fā)處處使用的便利。

3 實例分析

通過上述對編譯器若干關(guān)鍵技術(shù)的研究，我們以類C為領(lǐng)域語言，Java為目標語言進行分析，抽取出部分類C語言的文法，如表1所示。

表1 規(guī)則的描述

表1較多地給出了語法產(chǎn)生式，詞法產(chǎn)生式僅給出了一個。這樣做的原因是：語法分析是編譯程序的核心部分，它是以識別符號序列是否為給定的句子為目的的。接下來一一說明表中的含義：序號為1第1行的產(chǎn)生式是詞法產(chǎn)生式，變量（IDENTIFIER）規(guī)則的定義有效地避免了左遞歸；序號為2第2行的產(chǎn)生式（external＿declaration）指出了類C包含了函數(shù)定義與函數(shù)聲明2個部分，在該產(chǎn)生式的后面緊跟著K 值的設(shè)置（K＝1），external＿declaration產(chǎn)生式可以推導(dǎo)出函數(shù)定義和函數(shù)聲明2種路徑，利用ANTLR的語法斷言有效地解決了輸入語句匹配哪一條路徑的問題，提高了設(shè)置K值的靈活性；序號為3第3行的產(chǎn)生式指出了函數(shù)定義（function＿definition）包含了：函數(shù)存儲類別，函數(shù)名，函數(shù)的參數(shù)及復(fù)合語句組成等；序號為4第4行的產(chǎn)生式指出了參數(shù)列表（paramDeclList）可以有0個或多個參數(shù)組成，從參數(shù)的定義可以看出：函數(shù)的參數(shù)是左結(jié)合順序，即求值順序是自左向右；序號為5第5行包含了2個產(chǎn)生式：equalityExpr和comparisonExpr，產(chǎn)生式comparisonExpr被嵌套在equalityExpr產(chǎn)生式之中，解決了關(guān)系運算符優(yōu)先級的問題。通過分析可以看出類C程序由若干函數(shù)聲明和函數(shù)定義組成。

依據(jù)上述文法定義，借助antlrwork工具，最終生成了詞法、語法分析器，形成了目標語言代碼。當然還可以借助ANTLR提供的樹編譯器形成抽象語法樹，即本文的研究不僅是構(gòu)造編譯器前端的基礎(chǔ)，也為程序分析（如代碼相似度檢測）、模型轉(zhuǎn)換、語言處理提供了一種新途徑。

4 結(jié)語

在研究分析器自動生成工具ANTLR的基礎(chǔ)上，構(gòu)建編譯器的前端設(shè)計，通過關(guān)鍵技術(shù)的研究，解決了ANTLR作為編譯器前端設(shè)計的若干關(guān)鍵技術(shù)問題。本文創(chuàng)新點：以ANTLR作為工具分析編譯器的構(gòu)造，解決了相關(guān)技術(shù)問題；在語法分析過程中以Java語言作為目標語言，該設(shè)計操作簡單，具有良好的擴展性和實用性。

［1］Alfred V Aho，Monica S Lam，Ravi Sethi，et al.Compilers：Principles，Techniques，and Tools［M］.2nd Edition.Lodon：Pearson Education，Inc，2006.

［2］Lars Marius Garshol.BNF and EBNF：What are they and how do they work［OL］.http：／／www.garshol.priv.no／download／text／bnf.html，2008－08－22.

［3］Terence Parr.ANTLR history［OL］.http：／／www.antlr.org／history.html，2012－11－15.

［4］劉三獻.基于ANTLR的Gaussian詞法分析器和語法分析器的分析與設(shè)計［D］.蘭州：蘭州大學(xué)，2009.10－15.

［5］黃華.多領(lǐng)域統(tǒng)一建模語言分析器研究與實現(xiàn)［D］.武漢：華中科技大學(xué)，2005.20－25.

［6］潘旭，康慕寧.基于ANTLR的試卷識別和導(dǎo)入系統(tǒng)的研究［J］.電子設(shè)計工程，2011，19（7）：45－49.