可擴(kuò)展語言編譯器的設(shè)計

葛寒松

(商丘師范學(xué)院 信息技術(shù)學(xué)院，河南 商丘 476000)

可擴(kuò)展語言編譯器的設(shè)計

葛寒松

(商丘師范學(xué)院 信息技術(shù)學(xué)院，河南 商丘 476000)

傳統(tǒng)的編譯器設(shè)計和實現(xiàn)的方法論限制了編程語言的開放性與可擴(kuò)展性.一般在語言徹底定型后開始制作編譯器，一旦語言擴(kuò)展成新的語言，就需要重新開發(fā)一個編譯器.可擴(kuò)展語言編譯器的設(shè)計過程中，考慮語言的進(jìn)一步擴(kuò)展，編譯器開發(fā)也會為進(jìn)一步擴(kuò)展預(yù)留一定的接口.開發(fā)過程中，嚴(yán)格遵守軟件開發(fā)的基本法則，應(yīng)用軟件工程中的增量模型，進(jìn)行迭代開發(fā)，開發(fā)過程通過利用面向?qū)ο笏枷胧钩绦蚓哂懈邤U(kuò)展性，從而大大降低重新開發(fā)編譯器的風(fēng)險.

編譯器，開放性，可擴(kuò)展性，漸增式，面向?qū)ο?/p>

0 引 言

隨著計算機(jī)技術(shù)被應(yīng)用到方方面面，編程思想在不斷的進(jìn)步；同時，計算機(jī)語言也在快速的發(fā)展著.計算機(jī)語言的發(fā)展是一個不斷演化的過程.其根本的推動力就是抽象機(jī)制更高的要求以及對程序設(shè)計思想的更好的支持.具體地說，就是把機(jī)器能夠理解的語言提升到也能夠很好地模仿人類思考問題的形式.計算機(jī)語言的演化從最開始的機(jī)器語言到匯編語言再到各種結(jié)構(gòu)化高級語言，最后到支持面向?qū)ο蠹夹g(shù)的面向?qū)ο笳Z言.[1]

隨著編譯技術(shù)的發(fā)展，編譯器變得越來越復(fù)雜.但是，編程語言是在不停的演化與發(fā)展的，這給編譯器的設(shè)計與制作帶來了潛在的風(fēng)險.傳統(tǒng)的編譯器設(shè)計和實現(xiàn)的方法論限制了編程語言的開放性與可擴(kuò)展性.

新的編譯器開發(fā)方法的整體思路是，語言的特征是漸增式地添加到一系列編譯器中.編譯器的每個版本都會更多地關(guān)注可擴(kuò)展性的設(shè)計.整個開發(fā)過程會完全遵守軟件開發(fā)的基本法則，面向?qū)ο笏枷朐谲浖_發(fā)以及可擴(kuò)展設(shè)計過程中起著關(guān)鍵的作用.我們將整個過程以及由之帶來的一系列語言命名為Couplet.Couplet會為C0,C1,C2和C3這一系列語言編寫編譯器.除了初始語言C0，編寫每一個Cn的時候我們都是通過擴(kuò)展開發(fā)它的前一個版本的語言Cn-1(n>1)而來.

1 傳統(tǒng)編譯器設(shè)計與開發(fā)現(xiàn)狀

語言的演變和編譯過程的復(fù)雜性以及重要性，需要以一種合適的方式構(gòu)建編譯的過程.一方面使得編譯過程能夠簡單易學(xué)，另一方面能夠使得編譯器可以很好地應(yīng)對語言的演化.隨著編譯技術(shù)的發(fā)展，將編譯過程分解為多步，一方面能更好地分析源碼，實現(xiàn)編譯過程，另一方面也簡化了整個編譯過程理解的難度和梯度.不過，在應(yīng)對語言演化方面，一直沒有很成形的辦法，一般在語言徹底定型后開始制作編譯器，語言發(fā)生變化時就成了新的語言，最簡便的方式便是將當(dāng)前語言翻譯為與其相近的語言，但是，整個過程需要重新開發(fā)一個編譯器.

編譯的發(fā)展過程經(jīng)歷了由一步翻譯到多步分析的歷程.現(xiàn)在計算機(jī)界的語言設(shè)計以及編譯器開發(fā)都基于一個5步分析的編譯過程：詞法分析、語法分析、語義檢查和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成[2].

這個編譯過程的特點是，編譯器開發(fā)開始必須在語言設(shè)計完成之后.編譯器開發(fā)過程每一步的開始都必須在上一步完全完成之后.在整個開發(fā)過程中，無法得到有完整功能的編譯器，只有開發(fā)完全完成的時候，編譯器才能第一次試用.這種開發(fā)方法需要在語言定義較為固定、無重大變化的前提下,可是卻無法面對語言設(shè)計上可能出現(xiàn)的改變或功能上的擴(kuò)充,雖然穩(wěn)定可靠，卻缺乏一定的可擴(kuò)展性.

2 可擴(kuò)展語言編譯器設(shè)計原理

可擴(kuò)展語言編譯器的設(shè)計過程中，語言定義將不再一步到位，而是將語言特性逐漸地加入到語言中.每次語言的定義以及編譯器的實現(xiàn)過程中，都會考慮語言的進(jìn)一步擴(kuò)展，編譯器開發(fā)也會為進(jìn)一步擴(kuò)展預(yù)留一定的接口.

把設(shè)計過程中定義的語言命名為Couplet，Couplet分為幾個版本，分別是C0，C1，C2，C3；并分別定義了每個版本語言的特征，每一個高級版本的語言都是在擴(kuò)展低級版本的語言特性后得來的.設(shè)計過程中為每一個版本的語言編寫編譯器.除了初始語言C0，編寫每一個Cn的時候都是通過擴(kuò)展開發(fā)它的前一個版本的語言Cn-1(n>1)而來.

開發(fā)過程中，嚴(yán)格遵守軟件開發(fā)的基本法則，應(yīng)用軟件工程中的增量模型[3]，進(jìn)行迭代開發(fā)，開發(fā)過程通過利用面向?qū)ο笏枷胧钩绦蚓哂懈邤U(kuò)展性.

3 可擴(kuò)展語言及編譯器的擴(kuò)展設(shè)計

語言的擴(kuò)展按照C0，C1，C2……的擴(kuò)展原則，編譯器設(shè)計也會為進(jìn)一步擴(kuò)展預(yù)留一定的接口.

3.1 基本擴(kuò)展思路

首先從目錄結(jié)構(gòu)進(jìn)行解釋.在根目錄(trunk)下分設(shè)1.0、2.0等分目錄依次對應(yīng)于C1、C2等，然后每個分目錄是一個單獨的eclipse項目，它們分別都包含src、.settings等文件夾.

以下由C1擴(kuò)展到C2說明擴(kuò)展過程.擴(kuò)展后，2.0目錄下的C2項目需要將C1項目生成的.jar包含進(jìn)Referenced Libraries，然后就可以繼承其中的各個類了.C1的代碼已經(jīng)寫好，生成的.jar包不再更改，C2在此基礎(chǔ)上擴(kuò)展.

在C1生成.jar包的時侯首先的任務(wù)是在C1下增加一組回歸測試，找些典型的、覆蓋面廣的源程序給c1編譯，以后一旦更改了C1代碼，通過這些測試用例可以基本保證原有的正確性.

在C2中，包結(jié)構(gòu)應(yīng)該保持類似.couplet頂層包中的類原則上不需要改動，它們約定了最基本的“概念”；也就是說，C2中的couplet包是空的(當(dāng)然couplet的物理目錄中還有子目錄).C1為其后Cx“預(yù)留”或是“定義”的接口，全部體現(xiàn)在這里.依靠這套接口的封裝，理論上應(yīng)該可以實現(xiàn)整體替換，實際中可能還需根據(jù)C2進(jìn)行調(diào)整.

即將建立的couplet.c2包開始出現(xiàn)針對C2的實現(xiàn)，通常的類應(yīng)當(dāng)形如代碼：

package couplet.c2;

public class Lexer extends couplet.c1.Lexer implements couplet.Lexer {

// ......

}

而其中的方法，有些無需擴(kuò)展的，繼承后自然實現(xiàn)，有些可能需要補(bǔ)充，形如代碼：

@Override

public void method(Object parameter) {

super.method(parameter);

// ......}

以上都是最理想的情況，可能不易達(dá)到，有些方法需要完全重寫，即上述代碼中不再調(diào)用super的對應(yīng)方法，而是從頭編寫.如上過程需要更改c1代碼的，自行處理即可，C1中的protected方法應(yīng)該是重寫的主要單元.

諸如scan()、parse()這些實現(xiàn)頂層接口的public方法可被完整重用，因為它們是對整體流程的高層描述，各個Cx本質(zhì)相同.而各個Cx不同的部分，應(yīng)該作為protected方法單獨抽象出來，不斷重寫，以實現(xiàn)擴(kuò)展.這也就意味著，c1中減小public方法的粒度，分割出小的protected方法以便于重用.在設(shè)計時明確哪些是該重用的、哪些是該重寫的.

把main方法寫在couplet.cx.Compiler類中，couplet頂層包的Compiler是一個類.這個類在compile()方法中基于同級別的其他接口構(gòu)造起主流程；構(gòu)造方法參數(shù)不再留空，而是那些Lexer、Parser、TCGenerator、TCEmitter等接口.[4]這樣，下層各個Cx包中的main方法只要將本Cx的各個實現(xiàn)類對象傳入Compiler的構(gòu)造方法，就可以調(diào)用compile()方法完成編譯，這樣就完成了完美抽象.

再下一層目錄，像couplet.c1.ast包中，原有的大部分類理論上不需要被繼承.這層的“擴(kuò)展”，更多的不是通過繼承，而是通過加入并列的新的類，如新補(bǔ)的token、ast節(jié)點等.相應(yīng)地，這層中那些需要被繼承的類，部分可以考慮調(diào)到上一層(但不一定，比如有些父ast節(jié)點在各Cx中有不同子類，這樣的繼承就不意味著應(yīng)上調(diào)).

3.2 Couplet頂層接口設(shè)置

與其他編譯器不同，為了方便擴(kuò)展，設(shè)計過程中設(shè)置了頂層的接口.將編譯器的一般邏輯設(shè)計成通用接口，再在各級語言中實現(xiàn)這個接口.這樣，就為重用提供了可能.基本編譯器的整體思路都是相同的，包括詞法分析、語法分析等.假設(shè)語言的擴(kuò)展中，需要加入新的語法允許的元素，而token并不需要改變，那么設(shè)計過程中至少可以重用的內(nèi)容有頂層的基本邏輯和詞法分析器.頂層邏輯是相同的，所以類型的申明不需要改變，需要做的只需要寫一個新的入口函數(shù)，申請和原來相同的編譯器類，但是傳參數(shù)的時候，只需要傳入需要改變的類.比如語法分析器需要改變，那么只需要重新編寫語法分析器，并傳入到編譯器類中.

3.3 擴(kuò)展中的問題及解決辦法

3.3.1 關(guān)于數(shù)據(jù)結(jié)構(gòu)類型的擴(kuò)展

這里的數(shù)據(jù)結(jié)構(gòu)指的是存儲Token、AST、IC、TC的類.語言擴(kuò)展后，Token、AST、IC、TC的結(jié)構(gòu)一般也會相應(yīng)的擴(kuò)展，新的數(shù)據(jù)結(jié)構(gòu)直接依據(jù)其與原有數(shù)據(jù)結(jié)構(gòu)類的關(guān)系向下繼承即可.但是，現(xiàn)在的問題是，為了方便地識別一個數(shù)據(jù)結(jié)構(gòu)的類型(例如某個AST是IfStatement還是Identifier)，我們之前采用了整型常量作為類型編碼，這些常量定義在 C1語言相應(yīng)數(shù)據(jù)結(jié)構(gòu)的基類中(如ASTNode)，現(xiàn)在數(shù)據(jù)結(jié)構(gòu)擴(kuò)展了，相應(yīng)的類型編碼也要擴(kuò)展，那么這些新的常量應(yīng)該定義在哪里？如果C2語言的所有AST 能夠有一個基類，那么這些常量可以定義在這個基類中，但是現(xiàn)在不可能；如果各自定義在新的數(shù)據(jù)結(jié)構(gòu)類本身中，無法通過一種方便、統(tǒng)一的手段訪問到.

現(xiàn)在有兩種解決方案：第一種方案是根本不使用類型編碼.一種觀點認(rèn)為可以不要有類型編碼和獲得類型的方法，直接使用instance of進(jìn)行判斷.現(xiàn)在看來，在許多情況下，這個getXXXType的方法作用不大(在AST、IC、TC中)，只有個別地方需要根據(jù)類型進(jìn)行不同的操作.但是對于Token來說，這個編碼還是發(fā)揮了至關(guān)重要的作用(在語法分析中經(jīng)常需要根據(jù)下一個Token的類型來選擇操作)，更重要的是，Token的類型層次和TokenType的類型編碼是不對應(yīng)的(例如Token的類型層只劃分到Punctuation、Keyword等，但是語法分析器要用到的類型是精確到具體哪個標(biāo)點、哪個關(guān)鍵字來進(jìn)行判斷的).這樣，如果一定不使用類型編碼的話，要么選擇擴(kuò)展Token的類型層次(例如Punctuation下派生出Semi、Equal、Plus等)，否則語法分析器中的判斷代碼就會很復(fù)雜.不使用類型編碼后，原有一些case結(jié)構(gòu)的語句更改為if...else if...的形式，可讀性稍有影響，但也不算很大的問題.第二種方案是創(chuàng)建一個單獨的類(可以抽象類或者接口)維護(hù)類型編碼.例如，創(chuàng)建一個ASTType的類，里面只是聲明了一組表示AST類型編碼的常量，C2中還可以有一個這樣的類，繼承于C1的ASTType，里面聲明新的類型編碼常量，這樣C2的ASTType可以訪問到所有C1、C2的類型編碼.但是，維護(hù)常量類型編碼這種方法本身也是存在一定缺陷的，例如，編碼的值需要人工編碼，并且一定不能重復(fù)，這當(dāng)存在繼承的時候還是有一定不可靠性的(需要回頭去看父類的編到幾號，然后按順序繼續(xù)，可能會出現(xiàn)錯誤，并且很難查出)，還有另一方法是用一個累加計數(shù)器來維護(hù)類型編碼[5]，但是這相當(dāng)于把常量變成變量了，這種類型的編碼雖然還是有final修飾符，但是不能用在case語句中了.其實本來在這里使用Enum是很理想的，但是可惜Enum不支持繼承，無法滿足我們擴(kuò)展的需要.

這兩種方案的利弊大抵相當(dāng)，采用哪種都無妨，雖然有點小瑕疵，但不算很嚴(yán)重的缺陷.

3.3.2 訪問者模式的問題

這個問題目前采用思路的具體代碼可以這樣寫：

class B extends A {

@Override

void accept(VisitorA visitor) {

if (visitor instanceof VisitorB) {

accept((VisitorB)visitor);

}

void accept(VisitorB visitor) {

visitor.visit(this);

}

}

這有點類似于適配器模式的思想，相當(dāng)于需要accept(VisitorA visitor)方法，而實際功能在accept(VisitorB visitor)方法，于是在accept(VisitorA visitor)方法中將其適配到accept(VisitorB visitor).[6]這種方法存在一定的重復(fù)性代碼，好在C2中新增類型的accept(VisitorA visitor)方法中的內(nèi)容完全相同，可以通過復(fù)制粘貼快速完成(實際上訪問者模式的accept方法本身就是完全雷同的).

3.3.3 操作類的擴(kuò)展

這里的操作類指的是Compiler、Lexer、Parser、ICGenerator、TCGenerator等進(jìn)行具體操作的類.下面逐個考慮.

Compiler類中的內(nèi)容其實很簡單(不考慮我們用于輸出中間結(jié)果的main方法)，不論Cx語言，其大體結(jié)構(gòu)是相似的.但是這里涉及一個問題，這些操作類中的成員變量是否都使用頂層接口的類型(例如C1的Compiler中的lexer這個成員的類型是couplet.c1.Lexer這個類型還是couplet.Lexer這個類型).我們認(rèn)為，應(yīng)該盡可能地使用頂層接口進(jìn)行操作(最好能全都使用).但這里又涉及了另一個問題——訪問者模式的accept方法，這個方法不適合放在頂層接口中，那么在需要調(diào)用accept方法的時候，又要將其強(qiáng)制轉(zhuǎn)換為具體的Cx的某個類，這樣在一定程度上降低了抽象性，對于擴(kuò)展以后的復(fù)用也不利(例如C1要轉(zhuǎn)成C1的類，C2要轉(zhuǎn)成C2的類，這種語句在一個方法中一旦出現(xiàn)一次，就可能導(dǎo)致整個方法需要在子類中重寫，即使其它部分的內(nèi)容是完全相同的).總地來說使用頂層接口進(jìn)行操作還是利大于弊的，使用頂層接口以后，可能只需要在子類的構(gòu)造方法中實例化不同語言的具體類，其它操作代碼可以不改動(當(dāng)然也有可能改動，比如C1沒有類型檢查，C2加上了類型檢查，這樣compile這個方法還是要重寫的，但是C2到C3如果沒有再增加什么中間步驟的話，comile這個方法就可以復(fù)用).

Lexer類的改動也不大，區(qū)別主要在于關(guān)鍵字和操作符.關(guān)鍵字只要在子類的靜態(tài)方法中添加到reserved這個Map中即可(但是使用Map的這種方法是否合適還保留一點疑問，包括后來在Lexer中使用的terminalMap)，操作符的識別需要重寫recognizeOperator這個方法.

Parser類主要隨產(chǎn)生式的變化而變化.設(shè)計的總體思想就是，產(chǎn)生式中一個非終極符對應(yīng)Parser中的一個方法.這樣新增的非終極符對應(yīng)于一個新增的方法，原有的非終極符如果新增了可推導(dǎo)出的產(chǎn)生式，則原有的方法也要重寫(這樣可能會重復(fù)寫一大部分原有的代碼，只是新增了一條case而已，但是目前沒有更好的解決方案).

ICGenerator類和TCGenerator類這兩個類的情況類似，也比較好處理.例如，C2的ICGenerator繼承C1的ICGenerator ，實現(xiàn)C2的ASTVisitor，這樣實現(xiàn)ASTVisitor中的這些方法即可完成對新的AST的翻譯處理，原有的AST的處理如果確有改變，則重寫父類的方法.

4 可擴(kuò)展語言編譯器設(shè)計的意義

從理論價值看，可擴(kuò)展語言編譯器的設(shè)計將軟件開發(fā)模式引用到編譯原理中，希望通過模式的改變進(jìn)一步優(yōu)化和改進(jìn)編程語言的設(shè)計思想和編譯器的開發(fā)流程.傳統(tǒng)的編譯方式一直局限于瀑布模型，缺乏迭代與反饋，不能很好地適應(yīng)編程語言的進(jìn)一步發(fā)展與擴(kuò)充.本設(shè)計希望在語言設(shè)計以及編譯過程中引入增量模型的思想，做以下嘗試：在語言設(shè)計時考慮進(jìn)一步擴(kuò)充的可能和方向，在編譯器開發(fā)時，為語言的改變和進(jìn)一步擴(kuò)充預(yù)留接口，并做充分的準(zhǔn)備.每一步都為進(jìn)一步的開發(fā)做基礎(chǔ)和鋪墊.

從實際價值看，隨著語言以及編譯技術(shù)的發(fā)展，語言設(shè)計更加復(fù)雜，編譯器的功能也更加強(qiáng)大.然而這快速的發(fā)展卻帶來了一種限制與風(fēng)險.由于編譯器的開發(fā)需要在語言完全定義好之后，而且基本應(yīng)用瀑布模型，無法根據(jù)語言定義的擴(kuò)展而作相應(yīng)的擴(kuò)展.一旦語言有擴(kuò)展或者改變的需要，編譯器就可能需要重新開發(fā)，上個版本只能提供少量的思想，卻不能做到大量的設(shè)計和代碼上的重用.這樣的現(xiàn)象，一方面限制了語言的進(jìn)一步擴(kuò)展和發(fā)展，另一方面也給編譯器的開發(fā)帶來了一定的風(fēng)險.通過這次設(shè)計，希望可以減少編程語言進(jìn)一步擴(kuò)展上的限制，降低編譯器在語言擴(kuò)展后需要重新開發(fā)的風(fēng)險.

[1]李源．計算機(jī)語言發(fā)展的歷史、現(xiàn)狀和未來[J]．?dāng)?shù)碼世界，2008(12):20-21．

[2]Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D.Ullman.Compilers Principles, Techniques, & Tools.Second Edition.[M]．Addison-Wesley, 2006．

[3]張海藩．軟件工程導(dǎo)論[M]．北京：清華大學(xué)出版社，1999．

[4]王翔．設(shè)計模式——基于C#的工程化實現(xiàn)及擴(kuò)展[M]．北京：電子工業(yè)出版社，2008．

[5]張昱，陳意云.編譯原理實驗教程[M]．北京：高等教育出版社，2009．

[6]莫勇騰．深入淺出設(shè)計模式(C#/Java版)[M]．北京：清華大學(xué)出版社，2006．

[責(zé)任編輯：王 軍]

On the design of extensible language compiler

GE Hansong

(College of Information Technology, Shangqiu Normal University, Shangqiu 476000，China)

The traditional methodology on the design and implementation of compiler imposes restriction on the openness and extensibility of programming language.Compiler is usually made after the complete fix of language, so if the language is extended into a new one, a new complier is needed to develop.In the designing process of the extensible language complier, the language extensibility is taken into consideration, and some connectors are reserved for language extensibility.In development, the basic laws on software designing are strictly followed; the incremental model in software engineering is applied for iterative development, and the design is based on the thought of object-oriented, which can make the program get high extensibility, so as to reduce the risk of compiler redevelopment to the least point.

compiler; openness; extensibility; incremental; object-oriented

2016-09-14

商丘師范學(xué)院校級骨干教師項目(2016GGJS14)

葛寒松(1978—)，男，河南虞城人，商丘師范學(xué)院講師，碩士，主要從事編譯原理及數(shù)據(jù)庫理論的研究.

TP313

A

1672-3600(2017)06-0053-04