可擴展語言編譯器的設計

葛寒松

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

可擴展語言編譯器的設計

葛寒松

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

傳統的編譯器設計和實現的方法論限制了編程語言的開放性與可擴展性.一般在語言徹底定型后開始制作編譯器，一旦語言擴展成新的語言，就需要重新開發一個編譯器.可擴展語言編譯器的設計過程中，考慮語言的進一步擴展，編譯器開發也會為進一步擴展預留一定的接口.開發過程中，嚴格遵守軟件開發的基本法則，應用軟件工程中的增量模型，進行迭代開發，開發過程通過利用面向對象思想使程序具有高擴展性，從而大大降低重新開發編譯器的風險.

編譯器，開放性，可擴展性，漸增式，面向對象

0 引 言

隨著計算機技術被應用到方方面面，編程思想在不斷的進步；同時，計算機語言也在快速的發展著.計算機語言的發展是一個不斷演化的過程.其根本的推動力就是抽象機制更高的要求以及對程序設計思想的更好的支持.具體地說，就是把機器能夠理解的語言提升到也能夠很好地模仿人類思考問題的形式.計算機語言的演化從最開始的機器語言到匯編語言再到各種結構化高級語言，最后到支持面向對象技術的面向對象語言.[1]

隨著編譯技術的發展，編譯器變得越來越復雜.但是，編程語言是在不停的演化與發展的，這給編譯器的設計與制作帶來了潛在的風險.傳統的編譯器設計和實現的方法論限制了編程語言的開放性與可擴展性.

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

1 傳統編譯器設計與開發現狀

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

編譯的發展過程經歷了由一步翻譯到多步分析的歷程.現在計算機界的語言設計以及編譯器開發都基于一個5步分析的編譯過程：詞法分析、語法分析、語義檢查和中間代碼生成、代碼優化、目標代碼生成[2].

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

2 可擴展語言編譯器設計原理

可擴展語言編譯器的設計過程中，語言定義將不再一步到位，而是將語言特性逐漸地加入到語言中.每次語言的定義以及編譯器的實現過程中，都會考慮語言的進一步擴展，編譯器開發也會為進一步擴展預留一定的接口.

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

開發過程中，嚴格遵守軟件開發的基本法則，應用軟件工程中的增量模型[3]，進行迭代開發，開發過程通過利用面向對象思想使程序具有高擴展性.

3 可擴展語言及編譯器的擴展設計

語言的擴展按照C0，C1，C2……的擴展原則，編譯器設計也會為進一步擴展預留一定的接口.

3.1 基本擴展思路

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

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

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

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

即將建立的couplet.c2包開始出現針對C2的實現，通常的類應當形如代碼：

package couplet.c2;

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

// ......

}

而其中的方法，有些無需擴展的，繼承后自然實現，有些可能需要補充，形如代碼：

@Override

public void method(Object parameter) {

super.method(parameter);

// ......}

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

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

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

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

3.2 Couplet頂層接口設置

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

3.3 擴展中的問題及解決辦法

3.3.1 關于數據結構類型的擴展

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

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

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

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);

}

}

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

3.3.3 操作類的擴展

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

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

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

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

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

4 可擴展語言編譯器設計的意義

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

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

[1]李源．計算機語言發展的歷史、現狀和未來[J]．數碼世界，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]張海藩．軟件工程導論[M]．北京：清華大學出版社，1999．

[4]王翔．設計模式——基于C#的工程化實現及擴展[M]．北京：電子工業出版社，2008．

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

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

[責任編輯：王 軍]

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

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

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

TP313

A

1672-3600(2017)06-0053-04