Sealyu

簡介
Antlr（ANother Tool for Language Recognition）是一個工具，它為我們構(gòu)造自己的識別器（recognizers）、編譯器（compiler）和轉(zhuǎn)換器 （translators）提供了一個基礎(chǔ)。通過定義自己的語言規(guī)則，Antlr可以為我們生成相應(yīng)的語言解析器，這樣便可以省卻了自己全手工打造的勞 苦。

目標(biāo)
如同程序設(shè)計語言入門大多采用“Hello World”一樣，編譯領(lǐng)域的入門往往選擇計算器。而這里邁出的第一步更為簡單：一個只能計算兩個數(shù)相加的計算器，也就是說，它可以計算“1+1”。

基礎(chǔ)知識
先來考慮一下如何下手，如果你曾經(jīng)接受過編譯原理的教育，權(quán)當(dāng)憶苦思甜了。這個計算器工作的前提是有一個需要計算的東西，不管我們是以文件的形式提供，還是手工輸入，至少我們可以讓我們的計算器知道“1+1”的存在。

有 了輸入之后，我們要先檢查輸入的正確性，只有對正確的輸入進(jìn)行計算才是有意義的。如同寫文章有形式和內(nèi)容之分，這里的檢查也要細(xì)分一下，率先完成的檢查當(dāng) 然是面子功夫——形式上的東西，看看是否有錯別字的存在，我們要做的是數(shù)值相加，結(jié)果人家給出了一個字母，這肯定不是我們希望得到的，所以我們有權(quán)力拒絕 這個不合法的東西。對于程序員來說，如果在自己的程序里寫了一個語言不接受的標(biāo)識符，比如在Java里用“123r”做標(biāo)識符，那編譯器肯定會罷工，拒絕 讓程序通過編譯的。在編譯原理里面，這個過程叫做詞法分析。在我們的計算器中，我們只接受整數(shù)和加號，其它的一概不理。這里我們說的是“整數(shù)”，而非 “1”、“2”……，對我們來說，它們代表著同一類的東西，編譯原理教導(dǎo)我們把這這種東西叫做token，那些數(shù)字對我們來說，都是一樣的token，不 同的僅僅是它們的值而已。

形式說得過去并不代表內(nèi)容就可以接受，南北朝時期許多駢體文讓我們看到了隱藏在華麗的外表下的空虛靈魂。你可以 說 “我吃飯”，如果說“飯吃我”，除非是在練習(xí)反正話的場合，否則沒有人會認(rèn)為它是有意義的，因為顯然這不是我們習(xí)慣的主謂賓結(jié)構(gòu)。只有在闖過了詞法分析的 關(guān)口，才能到達(dá)這里，在編譯原理里面，我們把這個階段叫做語法分析。如果說詞法分析階段的輸入是字符流的話，那么語法分析階段的輸入就是token流—— 詞法分析的輸出。我們這里接受的合法語法是“整數(shù) 加號 整數(shù)”。

編寫語法文件
好了，制訂好自己的語言規(guī)則之后，我們需要以Antlr的語言把它描述出來。下面便是以Antlr的語言描述的語法：
grammar Calculator;
 
expr:   INT PLUS INT;
 
PLUS  : '+' ;
INT   : ('0'..'9')+ ;

Antlr的語法文件通常會保存在一個“.g”的文件中，我們的語法文件叫做“Caculator.g”。
 
我們來看看這里的定義：
expr:   INT PLUS INT;
 
這條語句定義了expr，它等價于“:”右邊的部分，也就是說，
* 一個INT，后面跟著一個PLUS，后面再接著一個INT。
 
至于INT和PLUS，它來自后面的定義：
PLUS  : '+' ;
INT   : ('0'..'9')+ ;
 
* PLUS定義的token，就是一個單一的“+”
* INT定義的token，由從'0'到'9'之間任意的數(shù)字組成，后面的加號表示它是可以重復(fù)一次到多次
 
如 果你曾經(jīng)與Antlr 2.x有過一面之緣，你會發(fā)現(xiàn)，這個語法文件與Antlr 2.x的語法文件有著些許不同。首先，我們沒有區(qū)分詞法分析和語法分析，由上面的代碼可以看出，二者在形式上是一致的，不同的是，對于詞法分析的輸入是字 符，而語法分析的輸入是詞法分析的結(jié)果，也就是token。Antlr 2.x必須顯式的區(qū)分這二者，而在Antlr 3.0之后，Antlr會替你料理這一切。再有，這里的語法文件名必須與grammar定義的名字保持一致，對于Java程序員，這是一個順其自然的選 擇。

編譯語法文件
如同不編譯的程序是無法發(fā)揮其威力一樣，單單語法文件對我們來說，并沒 有很大的價值。我們的工作就是使用Antlr提供工具對我們的語法文件進(jìn)行編譯，不同于日常的編譯器輸出可執(zhí)行文件，這里的輸出是程序語言的源文件。 Antlr缺省目標(biāo)語言是Java語言，它也可以支持C，C#和Python語言，其他的語言尚在開發(fā)之中，從3.0發(fā)布包結(jié)構(gòu)來看，Ruby的支持很快 就會加進(jìn)來。
 
將Antlr提供的JAR文件加入到classpath中，其中包括Antlr 2.7.7，Antlr 3.0與其runtime，stringtemplate。你沒看錯，除了3.0，這里還包含著2.7.7。原因很簡單，Antlr 3.0是基于之前版本開發(fā)的。
 
然后把語法文件的名稱作為參數(shù)傳給語法編譯器：
java org.antlr.Tool Caculator.g

在確保命令正確執(zhí)行，且語法文件編寫正確的情況下，Antlr為我們生成了幾個文件：
* CalculatorLexer.java
* CalculatorParser.java
* Calculator__.g
* Calculator.tokens

正 如前面說過的，Antlr替我們料理好了詞法分析和語法分析，其中， CalculatorLexer.java就是我們的詞法分析器，而CalculatorParser.java中包含了語法分析器，它們是我們這里關(guān)注 的主要對象。至于另外兩個文件，Calculator__.g是一個自動生成的lexer語法文件，而Calculator.tokens則是列出了我們 定義的token，我們并不會在程序中和它們直接打交道，所以，讓我們暫時忽略它們的存在。

運行程序
生成代碼之后，就是如何使用這些生成的代碼。下面就是我們的主程序，它負(fù)責(zé)將詞法分析部分（Lexer）和語法分析部分（Parser）驅(qū)動起來：
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            parser.expr();
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}
從 這段代碼中可以清晰的看出，Lexer的輸入是一個字符流，而Parser則需要Lexer的協(xié)助來完成工作，用Lexer構(gòu)造出的Token流作為其輸 入。一切就緒，我們讓它跑起來，嘗試輸入一些內(nèi)容，看它是否能夠通過驗證。事實證明，我們的程序可以輕松識別“1+1”，而對于不合法的東西，它會產(chǎn)生一 些抱怨。

計算結(jié)果
還記得我們的目標(biāo)嗎？我們的目標(biāo)是計算出“1+1”的結(jié)果，而現(xiàn)在這個程序剛剛能夠識別出“1+1”，我們還要繼續(xù)前進(jìn)。

熟 悉XML解析的朋友對于SAX和DOM一定不陌生，二者之間差別在于SAX屬于邊解析邊處理，而DOM則是把所有的內(nèi)容解析全部解析完（在內(nèi)存中形成一棵 樹）之后，再統(tǒng)一處理。Antlr也有與之類似的兩種處理方式，SAX的朋友是在Parser中加入處理動作（Action）處理將隨著解析的過程進(jìn)行， 而DOM的伙伴則是解析形成一棵抽象語法樹（Abstract Syntax Tree，簡稱AST），再對樹進(jìn)行處理。

加入Action
先來看看SAX的朋友。因為處理動作是加在expr上，其它部分保持不變。下面是修改過的expr：
expr returns [int value=0]
        : a = INT PLUS b = INT
          {
              int aValue = Integer.parseInt($a.text);
              int bValue = Integer.parseInt($b.text);
              value = aValue + bValue;
          }
        ;


看到常用的字符串轉(zhuǎn)整數(shù)的方法，熟悉Java的朋友想必已經(jīng)露出了會心的微笑。沒錯，這里定義Action的方法采用就是Java語言，因為我們生成的目標(biāo)是Java，如果你期待另辟蹊徑，那這里的代碼就要用你的目標(biāo)語言來編寫。

仔 細(xì)看一下不難發(fā)現(xiàn)，action完全是在原有的規(guī)則基礎(chǔ)上改造的來。首先用returns定義了這個Action的返回值，它將返回value這個變量的 值，其類型是int，我們還順便定義這個變量的初始值——“0”。接下來，我們用a、b拿住了兩個token的值，我們前面說過，在檢查的過程中，我們并 不關(guān)心每個token具體的內(nèi)容，只要token的類型滿足需要即可，但在action中，我們要計算結(jié)果，那必須使用token具體的內(nèi)容，所以，我們 用變量拿住了token。這里我們用$a.text獲取這個token的具體值。剩下的動作就很簡單了，把文本轉(zhuǎn)換為數(shù)字，進(jìn)行加法運算。
 
再 給舊版本一些憶苦思甜的時間，Antlr 2.x寫法有一些細(xì)微差別。首先，Antlr 2.x用“a : INT”將一個Token賦給一個變量，而這里用的是“a = INT”。再有，我們用$a.text獲取token的值，而在Antlr 2.x中，我們會用a.getText()，當(dāng)然，在Antlr 3.0中，我們也可以這么寫，不過，a.getText()這種寫法顯然太過于Java。
 
是不是對我們的計算器有些迫不及待了，那就揮動工具生成全新的Parser。不過，在新的體驗之前，我們還要稍微修改一下主程序，以體現(xiàn)我們的勞動成果。
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            System.out.println(parser.expr());
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}

好了，讓這個計算器來為我們求證“1+1”吧！

AST
SAX的朋友表演完了，下面就是DOM的伙伴登場了。

建立AST的方式很簡單，只要我們加上一個AST的選項即可，不過，同DOM的處理方式一樣，前面的解析只是為了后面的處理做準(zhǔn)備，所以，這里我們要修改一下之前編寫的語法文件，下面就是我們的新語法文件：
grammar Calculator;
 
options {
    output=AST;
    ASTLabelType=CommonTree;
}
 
expr : INT PLUS^ INT;
 
PLUS  : '+' ;
INT   : ('0'..'9')+ ;

稍微有些不同的地方是，我們加上了兩個選項，告訴Antlr，我們要輸出的是一個普通的AST。再有，在PLUS上面的“^”，這個符號用來告訴Antlr創(chuàng)建一個節(jié)點，以此作為當(dāng)前樹的根節(jié)點。

你也許會有些疑問，怎么沒看到計算的加法的地方？正如前面所說，這里只描述了語法結(jié)構(gòu)，這是為了后面的處理在做準(zhǔn)備，那么后面如何處理呢？別急，大戲要壓軸。下面登場的是Antlr整個故事最后一個大角，TreeParser：
tree grammar CalculatorTreeParser;
 
options {
  tokenVocab=Calculator;
  ASTLabelType=CommonTree;
}
 
expr returns [int value]
    : ^(PLUS a=INT b=INT)  
      {
          int aValue = Integer.parseInt($a.text);
          int bValue = Integer.parseInt($b.text);
          value = aValue + bValue;
      }
    ;
 
Antlr 可以接受三種類型語法規(guī)范——Lexer、Parser和Tree-Parser。如果說Lexer處理的是字符流、Parser處理的是Token流， 那么TreeParser處理的則是AST。前面Action的處理方式中，我們看到，規(guī)則同處理放到了一起，顯得有些混亂，而采用了AST的處理方式， 規(guī)則同處理就完全分離了：在Parser中定義規(guī)則，在TreeParser中定義處理，如果我們需要對同樣的語法進(jìn)行另外的處理，我們只要重新 TreeParser，而不必在規(guī)則與Action混合的世界中苦苦掙扎。

有了前面Action的基礎(chǔ)，再來看TreeParser也就簡單許多，需要說明的就是：
^(PLUS a=INT b=INT)
除去變量的說明，簡化一下這段代碼
^(PLUS INT INT)
第一個符號PLUS對應(yīng)了表示著根節(jié)點，兩個INT則分別代表了兩棵子樹，這樣剛好與前面生成的語法樹對應(yīng)上。

再來看看重新打造的主程序：
public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);
 
        try {
            CommonTree t = (CommonTree)parser.expr().getTree();
            CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
            CalculatorTreeParser walker = new CalculatorTreeParser(nodes);
            System.out.println(walker.expr());
        } catch (RecognitionException e) {
            System.err.println(e);
        }
    }
}

結(jié)語
體驗過最簡單的Antlr程序，我們就有了讓它更為豐富的基礎(chǔ)，接下來便是自己動手的時間了。

參考資料
《ANTLR入門》 2004年第三期《程序員》
《ANTLR Reference Manual》
《The Definitive ANTLR Reference》

探索Antlr（Antlr 3.0更新版）