王海燕，楊鶴標(biāo)

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

0 引言

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

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

1.1 ANLTR簡(jiǎn)介

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

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

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

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

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

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

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

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

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

2.1 左遞歸

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

2.1.1 直接左遞歸

上式中大寫(xiě)字母表示文法規(guī)則，小寫(xiě)字母表示詞法符號(hào)。（1）式規(guī)則A的產(chǎn)生式有2個(gè)，分別是Aa和b。第一個(gè)產(chǎn)生式Aa，最左端包含了A，這是一個(gè)直接左遞歸；（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)過(guò)上述分析，無(wú)論是直接左遞歸還是間接左遞歸均可通過(guò)化解消除。我們把經(jīng)化解消除后得到的產(chǎn)生式稱(chēng)之為尾遞歸（所謂尾遞歸形如：B－＞aB）。有了尾遞歸，借助ANTLR的元語(yǔ)言可以將其進(jìn)一步改寫(xiě)，得到相應(yīng)規(guī)則的文法描述。

2.2 算符的結(jié)合性

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

2.2.1 左結(jié)合

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

2.2.2 右結(jié)合

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

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

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

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

2.4 語(yǔ)法斷言

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

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

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

3 實(shí)例分析

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

表1 規(guī)則的描述

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

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

4 結(jié)語(yǔ)

在研究分析器自動(dòng)生成工具ANTLR的基礎(chǔ)上，構(gòu)建編譯器的前端設(shè)計(jì)，通過(guò)關(guān)鍵技術(shù)的研究，解決了ANTLR作為編譯器前端設(shè)計(jì)的若干關(guān)鍵技術(shù)問(wèn)題。本文創(chuàng)新點(diǎn)：以ANTLR作為工具分析編譯器的構(gòu)造，解決了相關(guān)技術(shù)問(wèn)題；在語(yǔ)法分析過(guò)程中以Java語(yǔ)言作為目標(biāo)語(yǔ)言，該設(shè)計(jì)操作簡(jiǎn)單，具有良好的擴(kuò)展性和實(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］劉三獻(xiàn).基于ANTLR的Gaussian詞法分析器和語(yǔ)法分析器的分析與設(shè)計(jì)［D］.蘭州：蘭州大學(xué)，2009.10－15.

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

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