使用 Antlr 開發(fā)領(lǐng)域語言

1、頁碼，1/12使用 Antlr 開發(fā)領(lǐng)域語言簡介： Antlr 是一個基于 Java 開發(fā)的功能強大的語言識別工具，Antlr 以其簡介的語法和高速的運行效率在這類工具中出類拔萃。當你需要開發(fā)一種領(lǐng)域語言時，語言可能像 Excel 中的公式一樣復(fù)雜，也可能像本文中的例子一樣簡單（只有算術(shù)運算），這時你可以考慮使用 Antlr 來處理你的語言。發(fā)布日期： 2011 年 3 月 07 日級別： 高級Antlr 簡介1.ANTLR 語言識別的一個工具 (ANother Tool for Language Recognition ) 是一種語言工具，它提供了一個框架，可以通過包含 Java, C+,

2、或 C# 動作（action）的語法描述來構(gòu)造語言識別器，編譯器和解釋器。 計算機語言的解析已經(jīng)變成了一種非常普遍的工作，在這方面的理論和工具經(jīng)過近 40 年的發(fā)展已經(jīng)相當成熟，使用 Antlr 等識別工具來識別，解析，構(gòu)造編譯器比手工編程更加容易，同時開發(fā)的程序也更易于維護。 2.語言識別的工具有很多種，比如大名鼎鼎的 Lex 和 YACC，Linux 中有他們的開源版本，分別是 Flex 和 Bison。在 Java 社區(qū)里，除了 Antlr 外，語言識別工具還有 JavaCC 和 SableCC 等。3.和大多數(shù)語言識別工具一樣，Antlr 使用上下文無關(guān)文法描述語言。最新的 Antlr

3、 是一個基于 LL(*) 的語言識別器。在 Antlr 中通過解析用戶自定義的上下文無關(guān)文法，自動生成詞法分析器 (Lexer)、語法分析器(Parser) 和樹分析器 (Tree Parser)。 回頁首Antlr 能做什么編程語言處理識別和處理編程語言是 Antlr 的首要任務(wù)，編程語言的處理是一項繁重復(fù)雜的任務(wù)，為了簡化處理，一般的編譯技術(shù)都將語言處理工作分為前端和后端兩個部分。其中前端包括詞法分析、語法分析、語義分析、中間代碼生成等若干步驟，后端包括目標代碼生成和代碼優(yōu)化等步驟。Antlr 致力于解決編譯前端的所有工作。使用 Anltr 的語法可以定義目標語言的詞法記號和語法規(guī)則，An

4、tlr 自動生成目標語言的詞法分析器和語法分析器；此外，如果在語法規(guī)則中指定抽象語法樹的規(guī)則，在生成語法分析器的同時，Antlr 還能夠生成抽象語法樹；最終使用樹分析器遍歷抽象語法樹，完成語義分析和中間代碼生成。整個工作在 Anltr 強大的支持下，將變得非常輕松和愉快。文本處理當需要文本處理時，首先想到的是正則表達式，使用 Anltr 的詞法分析器生成器，可以很容易的完成正則表達式能夠完成的所有工作；除此之外使用 Anltr 還可以完成一些正則表達式難以完成的工作，比如識別左括號和右括號的成對匹配等。頁碼，2/12回頁首Antlr 的安裝1.Antlr 本身是使用 Java 開發(fā)的，在使用

5、Antlr 之前必須先安裝 JRE(Java Runtime Environment )。Antlr 需要 Java 1.4 或者 1.4 以上版本。然后我們在 Antlr 的主頁上下載 Antlr 的 Jar 包 antlr-3.2.jar，最新的 Jar 包可能已經(jīng)升級。把 Jar 添加到 CLASSPATH 環(huán)境變量之后，即可使用 Anltr。在 window 中，修改 CLASSPATH 為CLASSPATH = %CLASSPATH%; C:/ antlr-3.2.jar2.至此已經(jīng)可以運行 Anltr, 使用的方法為 java org.antlr.Tool XXX.g, 其中 XX

6、X.g 是我們依據(jù) Antlr 的語法規(guī)則編寫的文法文件。3.除了 Anltr 運行環(huán)境之外，還有一個輔助 Antlr 開發(fā)的工具 Antlrworks，在 Antlr 的主頁上下載另一個 Jar 包 Antlrworks-1.4.jar。在 window 中，修改 CLASSPATH 為CLASSPATH = %CLASSPATH%; C:/ Antlrworks-1.4.jar運行 java org.antlr.works.IDE，然后在 Antlrworks 的 GUI 中新建或者打開文法文件。使用 Antlrworks 可以可視化顯示文法，并可以對語法分析樹和抽象語法樹可視化。 回頁首

7、表達式定義文法定義我們定義一個最簡單的領(lǐng)域語言，從一個簡單的完成算術(shù)運算的例子出發(fā)，詳細說明 Antlr 的使用。首先我們需要創(chuàng)建一個 Antlr 的文法文件， 一般以 .g 為文件名后綴，命名為 Expr.g 。在這個文法文件中根據(jù) Antlr 的語法規(guī)則來定義算術(shù)表達式的文法，文件的頭部是 grammar 關(guān)鍵字，定義文法的名字：grammar Expr;為了簡單起見，假設(shè)我們的自定義語言只能輸入一個算術(shù)表達式。從而整個程序有一個語句構(gòu)成，語句有表達式或者換行符構(gòu)成。如清單 1 所示：清單 1 程序和語句prog: stat;頁碼，3/12stat: expr;在 Anltr 中，算法的優(yōu)

8、先級需要通過文法規(guī)則的嵌套定義來體現(xiàn)，加減法的優(yōu)先級低于乘除法，表達式 expr 的定義由乘除法表達式 multExpr 和加減法算符 ('+'|'-') 構(gòu)成；同理，括號的優(yōu)先級高于乘除法，乘除法表達式 multExpr 通過原子操作數(shù) atom 和乘除法算符 ('*'|'/') 構(gòu)成。整個表達的定義如清單 2 所示：清單 2 表達式Expr : multExpr ('+'|'-') multExpr)*;multExpr : atom ('*'|'/') atom

9、)*;atom: '(' expr ')'| INT| ID;最后需要考慮的詞法的定義，在 Antlr 中語法定義和詞法定義通過規(guī)則的第一個字符來區(qū)別， 規(guī)定語法定義符號的第一個字母小寫，而詞法定義符號的第一個字母大寫。算術(shù)表達式中用到了 4 類記號 ( 在 Antlr 中被稱為 Token)，分別是標識符 ID，表示一個變量；常量 INT，表示一個常數(shù)；換行符 NEWLINE 和空格 WS，空格字符在語言處理時將被跳過，skip() 是詞法分析器類的一個方法。如清單 3 所示：清單 3 記號定義ID : ('a'.'z' |&#

10、39;A'.'Z')+ ;INT : '0'.'9' + ;NEWLINE:'r' ? 'n' ;WS : (' ' |'t' |'n' |'r' )+ skip(); ;Antlr 支持多種目標語言，可以把生成的分析器生成為 Java，C#，C，Python，JavaScript 等多種語言，默認目標語言為 Java，通過 options language=?; 來改變目標語言。我們的例子中目標語言為 Java。運行 Antlr完成文法定義之

11、后，即可以運行 Antlr，為我們生成需要的詞法分析器和語法分析器。在命令行運行以下下命令，如清單 4 所示：清單 4 運行 Antlrjava org.antlr.Tool c:/antlr_introsrcexprExpr.g|NEWLINE頁碼，4/12成功運行Antlr之后，將為我們生成 3 個文件，Expr.tokens、ExprLexer.java和ExprParser.java。其中Expr.tokens為文法中用到的各種符號做了數(shù)字化編號，我們可以不關(guān)注這個文件。ExprLexer是Antlr生成的詞法分析器，ExprParser是Antlr 生成的語法分析器，如圖 1 所示。

12、圖 1 Antlr 生成結(jié)果表達式驗證基于 Antlr 生成的詞法分析器和語法分析器后，可以基于它們來驗證我們的輸入的表達式是否合法。我們需要調(diào)用 Antlr 的 API 完成以下 Java 程序，如清單 5 所示：清單 5 調(diào)用分析器public static void run(String expr) throws Exception ANTLRStringStream in = new ANTLRStringStream(expr);ExprLexer lexer = new ExprLexer(in);對每一個輸入的字符串，我們構(gòu)造一個 ANTLRStringStream 流 in，用

13、 in 構(gòu)造詞法分析器 lexer，詞法分析的作用是產(chǎn)生記號，用詞法分析器 lexer 構(gòu)造一個記號流 tokens，然后再使用 tokens 構(gòu)造語法分析器 parser，至此已經(jīng)完成詞法分析和語法分析的準備工作。最終調(diào)用語法分析器的規(guī)則 prog，完成對表達式的驗證。詳細的 Java 程序參考樣例代碼中的 Test.java。當輸入合法的的表達式時，分析器沒有任何輸出，表示語言被分析器接受；當輸入的表達式違反文法規(guī)則時，比如“a + (b * 3”，分析器輸出 line 0:-1 mismatched input '<EOF>' expecting ')

14、'；提示期待一個右括號卻遇到了結(jié)束符號。如圖 2 所示：圖 2 表達式驗證結(jié)果CommonTokenStream tokens = new CommonTokenStream(lexer); ExprParser parser = new ExprParser(tokens); g();頁碼，5/12文法可視化使用 Antlrworks 打開 Expr.g，Antlrworks 對每一個文法定義都做了可視化顯示。整體的文法定義如圖 3：圖 3 文法定義的可視化其中語法規(guī)則和詞法記號的定義都有對應(yīng)的圖形表示方式。比如語法規(guī)則 atom 的圖示形式如圖 4 所示：圖 4

15、 語法規(guī)則 atom 的可視化詞法記號 ID 的圖示形式如圖 5 所示：圖 5 詞法記號 ID 的可視化使用 Antlrworks 還可以對語法分析樹可視化，在 Antlrworks 的 GUI 窗口中，點擊 Run ->Debug, 在 Input Text 窗口中輸入 a+(2 + b)，Start Rule 選擇 prog, 然后完成調(diào)試，可以看到 a+(2 + b) 時的語法分析樹，如圖 6 所示：圖 6 a+(2+b) 的語法分析樹頁碼，6/12回頁首表達式求值抽象語法樹截至目前使用 Anltr 生成的詞法分析器和語法分析器，除了校驗表述式輸入合法性之外，沒有更多的用處。如果需

16、要對表達式做進一步的處理，對表達式的運算結(jié)果求值，使用 Antlr 可以有兩種選擇，第一，直接在我們之前的 Expr 文法中嵌入動作，加入 Java 代碼片段；第二，使用 Antlr 的抽象語法樹語法，在語法分析的同時將用戶輸入轉(zhuǎn)換成中間表示方式：抽象語法樹，后續(xù)在遍歷語法樹的同時完成計算。第二種方法在結(jié)構(gòu)上更為清晰，便于開發(fā)和維護，我們使用第二種方法完成表達式的求值。首先來建立抽象語法樹，Antlr 中建立抽象語法樹只需在原來文法的基礎(chǔ)上加上建樹語法即可。改寫我們的 Expr 文法，在每一個語法規(guī)則后，加上相應(yīng)的抽象語法樹語法。清單 6，展示了程序和語句規(guī)則對應(yīng)的抽象語法樹節(jié)點。其 符用于指

17、示樹的根節(jié)點，PROG 和 STAT 是我們引入的占位符號，僅僅是一個字符串，用于區(qū)別不同的節(jié)點。清單 6 程序和語句的抽象語法樹節(jié)點prog : stat -> (PROG stat);stat : expr EOF -> (STAT expr)除了可以使用占位符做根節(jié)點外，算符也可以直接作為根節(jié)點，如清單 7 所示，加減乘除 4 個算符分別作為抽象語頁碼，7/12法樹的根節(jié)點來建立樹。清單 7 表達式的抽象語法樹節(jié)點expr : multExpr ('+'|'-') multExpr)*;multExpr : atom ('*'|

18、'/') atom)*;atom : '(' expr ')' -> expr| INT -> (NUM INT)| ID -> (VAR ID);再次使用 Antlrworks 打開 Expr.g，在調(diào)試窗口輸入表達式 a+(2 + b)，完成調(diào)試可以看到 a+(2 + b) 對應(yīng)的抽象語法樹如圖 7 所示。整個表達式是一個 PROG，PROG 中包含了一個 STAT，而 STAT 是由一棵表達式構(gòu)成的。圖 7 a+(2+b) 的抽象語法樹解釋器抽象語法樹建立之后，可以使用 Antlr 的樹分析器來構(gòu)造表達式的解釋器。樹分析器

19、的語法和前面的表達式文法有所區(qū)別，創(chuàng)建一個 Eval.g 文件，文件的頭部通過 tree grammar 來標識這是一個樹分析器。tree grammar Eval;之后對抽象語法樹節(jié)點逐一加入語義動作，完成最終的解釋執(zhí)行。樹分析器會深度優(yōu)先遍歷抽象語法樹，當 PROG 節(jié)點返回時，完成整個計算，輸出計算結(jié)果。STAT 擁有一個返回值，它的值取決于表達式的值。如清單 8 所示：清單 8 程序和語句的解釋頁碼，8/12prog : (PROG s=stat) System.out.println("Compute result : " + s.value);stat retu

20、rnsInteger value: (STAT e=expr) $value = e.value;表達式同樣擁有返回值，算術(shù)運算的求值只需用左子節(jié)點的值和右子節(jié)點的值完成對應(yīng)的運算即可；葉子節(jié)點atom，如果輸入是一個常量，直接求出常量代表的值；如果輸入是一個變量，簡單起見，我們用一個隨機數(shù)來為其賦值，如清單 9 所示。實際應(yīng)用中，可以替換為從數(shù)據(jù)庫中或者從文件中讀入變量的值。清單 9 表達式的解釋expr returnsInteger value: ('+' e1=expr e2=expr) $value = e1.value + e2.value;| ('-'

21、; e1=expr e2=expr) $value = e1.value - e2.value;| ('*' e1=expr e2=expr) $value = e1.value * e2.value;| ('/' e1=expr e2=expr) $value = e1.value / e2.value;| a=atom $value = a.value;atom returnsInteger value: (NUM i=INT) $value = Integer.parseInt(i.getText();| (VAR v=ID) Random rand =

22、new Random(); $value = rand.nextInt(10); ;完成 Eval.g 的編輯之后，再次運行 Antlr.java org.antlr.Tool c:/ antlr_introsrcintepreterEval.gAntlr 生成了樹分析器 Eval.java。使用 Antlr 的 API 完成以下 java 代碼，如清單 10 所示。至此完成了對輸入表達式的解釋求值。清單 10 調(diào)用解釋器public static void run(String expr) throws Exception ANTLRStringStream in = new ANTLRSt

23、ringStream(expr);ExprLexer lexer = new ExprLexer(in); CommonTokenStream tokens = new CommonTokenStream(lexer); ExprParser parser = new ExprParser(tokens); ExprPg_return ret = g(); CommonTree t = (CommonTree)ret.getTree();頁碼，9/12解釋器執(zhí)行結(jié)果如圖 8 所示：圖 8 解釋的輸出結(jié)果 Eval e_walker = new Eval(n

24、odes); e_g();CommonTreeNodeStream nodes = new CommonTreeNodeStream(t); nodes.setTokenStream(tokens);編譯器編譯執(zhí)行和解釋執(zhí)行相比，需要依賴于特定的目標機器，而解釋執(zhí)行不需要。表達式求值的語義不是十分復(fù)雜，在這里我們假設(shè)有一臺這樣機器，它用堆棧進行運算，支持以下 7 種指令，如表 1 所示：表 1 抽象機的 7 條指令指令 說明 操作數(shù)個數(shù)變量入棧 LDV Load Variable 1LDC Load Constant1ADD Add 0SUB SubtractMUL Mul

25、tiplyDIV DivideRET Return 0 0 0 0 語義 常量入棧 棧頂兩個元素出棧，求和后入棧棧頂兩個元素出棧，求差后入棧棧頂兩個元素出棧，求積后入棧棧頂兩個元素出棧，求商后入棧棧頂一個元素出棧，計算結(jié)束和之前的解釋器類似，創(chuàng)建一個 Compiler.g 樹分析器文件，其中各個表達式的編譯方案如清單 11 所示：清單 11 表達式的編譯prog : (PROG s=stat) System.out.println("RET");stat: (STAT e=expr);頁碼，10/12expr: ('+' e1=expr e2=expr) S

26、ystem.out.println("ADD");| ('-' e1=expr e2=expr) System.out.println("SUB");| ('*' e1=expr e2=expr) System.out.println("MUL");atom: (NUM i=INT) System.out.println("LDC "+i.getText();| (VAR v=ID) System.out.println("LDV "+v.getText();完成

27、 Compiler.g 的編輯之后，再次運行 Antlr.java org.antlr.Tool c:/ antlr_introsrcCompilerCompiler.gAntlr 生成了樹分析器 Compiler.java。使用Antlr的 API 完成以下java代碼，如清單 12 所示。至此完成了把表達式編譯為抽象機的指令。清單 12 調(diào)用編譯器public static void run(String expr) throws Exception ANTLRStringStream in = new ANTLRStringStream(expr); Compiler c_walker = new Compiler(nodes); c_g(); Exp