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