ANTLR樹分析器
本章翻譯人 CowNew開源團(tuán)隊 周曉
曾經(jīng)的SORCERER
在ANTLR 2.xx版本中，只要增加一些樹操作符,就可以幫助你建立一種中間形式的樹結(jié)構(gòu)(抽象語法樹) 來重寫語法規(guī)則和語義動作。ANTLR同樣允許你去指定AST樹的文法結(jié)構(gòu)，因此，可以通過操作或簡單遍歷樹結(jié)點(diǎn)的方式來進(jìn)行文法翻譯。
以前，樹分析器用一個單獨(dú)的工具SORCERER來生成，但是ANTLR已經(jīng)取代了它的功能。ANTLR現(xiàn)在可以為字符流，記號流，以及樹節(jié)點(diǎn)來建立識別器。
分析是決定一個記號串是否能由一個文法產(chǎn)生的過程。ANTLR在這方面比大多數(shù)工具考慮的都要深，它把一個二維樹結(jié)構(gòu)看作是一串節(jié)點(diǎn)。這樣，在ANTLR中，對記號流分析和樹分析的代碼生成過程來說，真正僅有的區(qū)別就變成了對超前掃描，規(guī)則方法定義頭部的檢測，以及對二維樹結(jié)構(gòu)代碼生成模板的指定上。
ANTLR樹分析器可以遍歷實(shí)現(xiàn)了AST接口的任何樹。AST接口是一種基于類似兒子-兄弟結(jié)點(diǎn)的樹通用結(jié)構(gòu)，有如下重要的制導(dǎo)方法：
- getFirstChild: 返回第一個子結(jié)點(diǎn)的引用.
- getNextSibling: 返回下一個兄弟結(jié)點(diǎn)的引用.
每一個AST結(jié)點(diǎn)有一個子女列表，一些文本和一個"記號類型"。每個樹的結(jié)點(diǎn)都是一棵樹，因此我們說樹是自相似的。AST接口的完整定義如下：
/** 最小AST結(jié)點(diǎn)接口用于ANTLR的AST成生
* 和樹遍歷
*/
public interface AST {
/** 添加一個子結(jié)點(diǎn)到最右邊 */
public void addChild(AST c);
public boolean equals(AST t);
public boolean equalsList(AST t);
public boolean equalsListPartial(AST t);
public boolean equalsTree(AST t);
public boolean equalsTreePartial(AST t);
public ASTEnumeration findAll(AST tree);
public ASTEnumeration findAllPartial(AST subtree);
/** 得到第一個子結(jié)點(diǎn); 如果沒有子結(jié)點(diǎn)則返回null */
public AST getFirstChild();
/** 得到本結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn) */
public AST getNextSibling();
/** 得到本結(jié)點(diǎn)的記號文本 */
public String getText();
/** 得到本結(jié)點(diǎn)的記號類型 */
public int getType();
/** 得到本結(jié)點(diǎn)的子結(jié)點(diǎn)總數(shù); 如果是葉子結(jié)點(diǎn), 返回0 */
public int getNumberOfChildren();
public void initialize(int t, String txt);
public void initialize(AST t);
public void initialize(Token t);
/** 設(shè)置第一個子結(jié)點(diǎn). */
public void setFirstChild(AST c);
/** 設(shè)置下一個兄弟結(jié)點(diǎn). */
public void setNextSibling(AST n);
/** 設(shè)置本結(jié)點(diǎn)的記號文本 */
public void setText(String text);
/** 設(shè)置本結(jié)點(diǎn)的記號類型 */
public void setType(int ttype);
public String toString();
public String toStringList();
public String toStringTree();
}
正如PCCTS1.33的SORCERER工具和ANTLR記號語法中所看到的，樹語法是一個嵌入語義動作，語義斷言和句法斷言的EBNF規(guī)則的集合。
規(guī)則: 可選產(chǎn)生式1
| 可選產(chǎn)生式2
...
| 可選產(chǎn)生式n
;
每一個可選的產(chǎn)生式都是由一個元素列表所組成的，列表中的元素是加入了樹模式的ANTLR正規(guī)語法中的一個，有如下的形式：
#( 根結(jié)點(diǎn) 子結(jié)點(diǎn)1 子結(jié)點(diǎn)2 ... 子結(jié)點(diǎn)n )
例如：下列的樹模式匹配一個以PLUS為根結(jié)點(diǎn)，并有兩個INT子結(jié)點(diǎn)簡單樹結(jié)構(gòu)：
#( PLUS INT INT )
樹模式的根必須是一個記號引用，但是子結(jié)點(diǎn)元素不限于此，它甚至可以是子規(guī)則。例如，一種常見結(jié)構(gòu)是if-then-else樹結(jié)構(gòu)，其中的else子句聲明子樹是可選的：
#( IF expr stat (stat)? )
值得一提的是，當(dāng)指定樹模式和樹語法后，通常，會進(jìn)行滿足條件的匹配而不是精確的匹配。一旦樹滿足給定的模式，不管剩下多少沒有分析，都會報告一次匹配。例如，#( A B )，對于像#( A #(B C) D)這樣有相同結(jié)構(gòu)的樹，不管有多長，都會報告一次匹配。
ANTLR樹分析器在工作時僅使用一個單獨(dú)的超前掃描符號，這在通常情況下不是一個問題，因為這種中間形式被明確設(shè)計成利于遍歷的結(jié)構(gòu)。然而，偶爾也需要區(qū)別出相似的樹結(jié)構(gòu)。句法斷言就是被用來克服有限確定的超前掃描所帶來的限制。例如：在區(qū)分一元和二元減號時，可以為每一種類型的減號都創(chuàng)建操作結(jié)點(diǎn)，這樣的做法可以工作的很好。但對于一個相同的根結(jié)點(diǎn)，使用句法斷言可以區(qū)分以下結(jié)構(gòu)：
expr: ( #(MINUS expr expr) )=> #( MINUS expr expr )
| #( MINUS expr )
...
;
賦值的次序很重要，因為第二個可選產(chǎn)生式是第一個可選產(chǎn)生式的“子集”.
語義斷言在可選產(chǎn)生式的開始，僅僅同可選的斷言表達(dá)式合成一體，就像合成一個正規(guī)文法。語義斷言在產(chǎn)生式的中間，當(dāng)它斷言失敗時，也會像正規(guī)文法一樣拋出異常。
考慮一下如何去建立一個計算器。一個方法是建立一個分析器，這個分析器識別輸入并計算表達(dá)式的值。按照這種方法，我們將會建立一個分析器來為輸入的表達(dá)式創(chuàng)建一棵樹，把表達(dá)式以這種中間形式表示，然后樹分析器遍歷這個樹，并計算出結(jié)果。
我們的識別器, CalcParser, 通過如下的代碼來定義：
class CalcParser extends Parser;
options {
buildAST = true; // // 默認(rèn)使用 CommonAST
}
expr: mexpr (PLUS^ mexpr)* SEMI!
;
mexpr
: atom (STAR^ atom)*
;
atom: INT
;
PLUS和STAR記號是操作符，因此把它們作為子樹的根結(jié)點(diǎn)，在它們后面注釋上字符'^'。SEMI記號后綴有字符'!'，這指出了它不應(yīng)該被加入到樹中。
這個計算器的詞法分析定義如下：
class CalcLexer extends Lexer;
WS : (' '
| '\t'
| '\n'
| '\r')
{ _ttype = Token.SKIP; }
;
LPAREN: '('
;
RPAREN: ')'
;
STAR: '*'
;
PLUS: '+'
;
SEMI: ';'
;
INT : ('0'..'9')+
;
識別器生成的樹是一棵簡單的表達(dá)式樹。例如，輸入"3*4+5"所產(chǎn)生的樹的形式為#( + ( * 3 4 ) 5 )。為了給這種形式的樹建立樹遍歷器，你必須要為ANTLR遞歸的描述樹的結(jié)構(gòu)：
class CalcTreeWalker extends TreeParser;
expr : #(PLUS expr expr)
| #(STAR expr expr)
| INT
;
一旦指定結(jié)構(gòu)，就可以自由的嵌入語義動作去計算出結(jié)果。一個簡單的實(shí)現(xiàn)辦法就是使expr規(guī)則返回一個整型的值，然后使每一條可選產(chǎn)生式計算每個子樹的值。下面的樹文法和動作達(dá)到了我們期望的效果：
class CalcTreeWalker extends TreeParser;
expr returns [int r]
{
int a,b;
r=0;
}
: #(PLUS a=expr b=expr) {r = a+b;}
| #(STAR a=expr b=expr) {r = a*b;}
| i:INT {r = Integer.parseInt(i.getText());}
;
注意到當(dāng)計算表達(dá)式值得時候，沒有必要指定優(yōu)先級，因為它已經(jīng)隱含在樹的結(jié)構(gòu)中了。這也解釋了為什么在以中間樹形式表示的時候，要比它的輸入要多很多。輸入的符號確實(shí)作為結(jié)點(diǎn)儲存在樹結(jié)構(gòu)中，而且這種結(jié)構(gòu)隱含了結(jié)點(diǎn)之間的關(guān)系。
要想執(zhí)行分析器和樹遍歷器，還需要以下的代碼：
import java.io.*;
import antlr.CommonAST;
import antlr.collections.AST;
class Calc {
public static void main(String[] args) {
try {
CalcLexer lexer =
new CalcLexer(new DataInputStream(System.in));
CalcParser parser = new CalcParser(lexer);
// 分析輸入的表達(dá)式
parser.expr();
CommonAST t = (CommonAST)parser.getAST();
// 以LISP符號的形式輸出樹
System.out.println(t.toStringList());
CalcTreeWalker walker = new CalcTreeWalker();
// 遍歷由分析器建立的樹
int r = walker.expr(t);
System.out.println("value is "+r);
} catch(Exception e) {
System.err.println("exception: "+e);
}
}
}
樹分析器對檢查樹或者從一棵樹產(chǎn)生輸出來說是很有用的，但必須要為它們添加處理樹轉(zhuǎn)換的代碼。就像正則分析器一樣，ANTLR樹分析器支持buildAST選項，這類似于SORCERER的翻譯模式。程序員不去修改代碼，樹分析器自動把輸入樹拷貝到作為結(jié)果的樹。每一個規(guī)則都隱含(自動定義的)一個結(jié)果樹。通過getAST 方法，我們可以從樹分析器中獲得此樹的開始符號。如果要一些可選產(chǎn)生式和文法元素不被自動添加到輸入的樹上，它們后面要注釋上"!"。子樹可以被部分的或者全部重寫。
嵌入到規(guī)則中的語義動作可以根據(jù)測試和樹結(jié)構(gòu)來對結(jié)果樹進(jìn)行設(shè)置。參考文法動作翻譯章節(jié).
再來看一下上面提到的簡單計算器的例子，我們可以執(zhí)行樹翻譯來代替計算表達(dá)式的值。下面樹文法的動作優(yōu)化了加法的恒等運(yùn)算(加0)。
class CalcTreeWalker extends TreeParser;
options{
buildAST = true; // "翻譯"模式
}
expr:! #(PLUS left:expr right:expr)
// '!'關(guān)閉自動翻譯
{
// x+0 = x
if ( #right.getType()==INT &&
Integer.parseInt(#right.getText())==0 )
{
#expr = #left;
}
// 0+x = x
else if ( #left.getType()==INT &&
Integer.parseInt(#left.getText())==0 )
{
#expr = #right;
}
// x+y
else {
#expr = #(PLUS, left, right);
}
}
| #(STAR expr expr) // 使用自動翻譯
| i:INT
;
執(zhí)行分析器和樹翻譯器的代碼如下：
import java.io.*;
import antlr.CommonAST;
import antlr.collections.AST;
class Calc {
public static void main(String[] args) {
try {
CalcLexer lexer =
new CalcLexer(new DataInputStream(System.in));
CalcParser parser = new CalcParser(lexer);
// 分析輸入的表達(dá)式
parser.expr();
CommonAST t = (CommonAST)parser.getAST();
// 以LISP符號的形式輸出樹
System.out.println(t.toLispString());
CalcTreeWalker walker = new CalcTreeWalker();
// 遍歷由分析器建立的樹
walker.expr(t);
// 遍歷，并得到結(jié)果
t = (CommonAST)walker.getAST();
System.out.println(t.toLispString());
} catch(Exception e) {
System.err.println("exception: "+e);
}
}
}
}
當(dāng)開發(fā)樹分析器的時候，經(jīng)常會得到分析錯誤。不幸的是，你的樹通常異乎尋常的大，使得很難去確定AST結(jié)構(gòu)錯誤到底在哪里。針對這種情況(當(dāng)創(chuàng)建Java樹分析器的時候,我發(fā)現(xiàn)它非常有用),，我創(chuàng)建了一個ASTFrame類(一個JFrame)，這樣，你就可以用Swing樹視圖來查看你的AST。它沒有拷貝這棵樹，而是用了一個TreeModel。以應(yīng)用程序方式運(yùn)行antlr.debug.misc.ASTFrame去或者看看Java代碼Main.java。就像不確定如何去調(diào)試一樣,我不確定它們在相同的包下,總之,將會在以后的ANTLR版本中給出。這里有一個簡單的使用例子：
public static void main(String args[]) {
// 創(chuàng)建樹結(jié)點(diǎn)
ASTFactory factory = new ASTFactory();
CommonAST r = (CommonAST)factory.create(0, "ROOT");
r.addChild((CommonAST)factory.create(0, "C1"));
r.addChild((CommonAST)factory.create(0, "C2"));
r.addChild((CommonAST)factory.create(0, "C3"));
ASTFrame frame = new ASTFrame("AST JTree Example", r);
frame.setVisible(true);
}
Version: $Id: //depot/code/org.antlr/release/antlr-2.7.6/doc/sor.html#1 $