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

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

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

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

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

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

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

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

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

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

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

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

12、圖 1 Antlr 生成結(jié)果表達(dá)式驗(yàn)證基于 Antlr 生成的詞法分析器和語(yǔ)法分析器后，可以基于它們來(lái)驗(yàn)證我們的輸入的表達(dá)式是否合法。我們需要調(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);對(duì)每一個(gè)輸入的字符串，我們構(gòu)造一個(gè) ANTLRStringStream 流 in，用

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

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

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

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

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

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

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

20、rnsInteger value: (STAT e=expr) $value = e.value;表達(dá)式同樣擁有返回值，算術(shù)運(yùn)算的求值只需用左子節(jié)點(diǎn)的值和右子節(jié)點(diǎn)的值完成對(duì)應(yīng)的運(yùn)算即可；葉子節(jié)點(diǎn)atom，如果輸入是一個(gè)常量，直接求出常量代表的值；如果輸入是一個(gè)變量，簡(jiǎn)單起見(jiàn)，我們用一個(gè)隨機(jī)數(shù)來(lái)為其賦值，如清單 9 所示。實(shí)際應(yīng)用中，可以替換為從數(shù)據(jù)庫(kù)中或者從文件中讀入變量的值。清單 9 表達(dá)式的解釋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 的編輯之后，再次運(yùn)行 Antlr.java org.antlr.Tool c:/ antlr_introsrcintepreterEval.gAntlr 生成了樹(shù)分析器 Eval.java。使用 Antlr 的 API 完成以下 java 代碼，如清單 10 所示。至此完成了對(duì)輸入表達(dá)式的解釋求值。清單 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();頁(yè)碼，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í)行相比，需要依賴于特定的目標(biāo)機(jī)器，而解釋執(zhí)行不需要。表達(dá)式求值的語(yǔ)義不是十分復(fù)雜，在這里我們假設(shè)有一臺(tái)這樣機(jī)器，它用堆棧進(jìn)行運(yùn)算，支持以下 7 種指令，如表 1 所示：表 1 抽象機(jī)的 7 條指令指令 說(shuō)明 操作數(shù)個(gè)數(shù)變量入棧 LDV Load Variable 1LDC Load Constant1ADD Add 0SUB SubtractMUL Mul

25、tiplyDIV DivideRET Return 0 0 0 0 語(yǔ)義 常量入棧 棧頂兩個(gè)元素出棧，求和后入棧棧頂兩個(gè)元素出棧，求差后入棧棧頂兩個(gè)元素出棧，求積后入棧棧頂兩個(gè)元素出棧，求商后入棧棧頂一個(gè)元素出棧，計(jì)算結(jié)束和之前的解釋器類似，創(chuàng)建一個(gè) Compiler.g 樹(shù)分析器文件，其中各個(gè)表達(dá)式的編譯方案如清單 11 所示：清單 11 表達(dá)式的編譯prog : (PROG s=stat) System.out.println("RET");stat: (STAT e=expr);頁(yè)碼，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 的編輯之后，再次運(yùn)行 Antlr.java org.antlr.Tool c:/ antlr_introsrcCompilerCompiler.gAntlr 生成了樹(shù)分析器 Compiler.java。使用Antlr的 API 完成以下java代碼，如清單 12 所示。至此完成了把表達(dá)式編譯為抽象機(jī)的指令。清單 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