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