ANTLR樹(shù)分析器
                本章翻譯人 CowNew開(kāi)源團(tuán)隊(duì) 周曉

曾經(jīng)的SORCERER

在ANTLR 2.xx版本中，只要增加一些樹(shù)操作符,就可以幫助你建立一種中間形式的樹(shù)結(jié)構(gòu)(抽象語(yǔ)法樹(shù)) 來(lái)重寫(xiě)語(yǔ)法規(guī)則和語(yǔ)義動(dòng)作。ANTLR同樣允許你去指定AST樹(shù)的文法結(jié)構(gòu)，因此，可以通過(guò)操作或簡(jiǎn)單遍歷樹(shù)結(jié)點(diǎn)的方式來(lái)進(jìn)行文法翻譯。

以前，樹(shù)分析器用一個(gè)單獨(dú)的工具SORCERER來(lái)生成，但是ANTLR已經(jīng)取代了它的功能。ANTLR現(xiàn)在可以為字符流，記號(hào)流，以及樹(shù)節(jié)點(diǎn)來(lái)建立識(shí)別器。

什么是樹(shù)分析器？

分析是決定一個(gè)記號(hào)串是否能由一個(gè)文法產(chǎn)生的過(guò)程。ANTLR在這方面比大多數(shù)工具考慮的都要深，它把一個(gè)二維樹(shù)結(jié)構(gòu)看作是一串節(jié)點(diǎn)。這樣，在ANTLR中，對(duì)記號(hào)流分析和樹(shù)分析的代碼生成過(guò)程來(lái)說(shuō)，真正僅有的區(qū)別就變成了對(duì)超前掃描，規(guī)則方法定義頭部的檢測(cè)，以及對(duì)二維樹(shù)結(jié)構(gòu)代碼生成模板的指定上。

可以分析什么類(lèi)型的樹(shù)？

ANTLR樹(shù)分析器可以遍歷實(shí)現(xiàn)了AST接口的任何樹(shù)。AST接口是一種基于類(lèi)似兒子-兄弟結(jié)點(diǎn)的樹(shù)通用結(jié)構(gòu)，有如下重要的制導(dǎo)方法：

• getFirstChild: 返回第一個(gè)子結(jié)點(diǎn)的引用.
• getNextSibling: 返回下一個(gè)兄弟結(jié)點(diǎn)的引用.

每一個(gè)AST結(jié)點(diǎn)有一個(gè)子女列表，一些文本和一個(gè)"記號(hào)類(lèi)型"。每個(gè)樹(shù)的結(jié)點(diǎn)都是一棵樹(shù)，因此我們說(shuō)樹(shù)是自相似的。AST接口的完整定義如下：

/** 最小AST結(jié)點(diǎn)接口用于ANTLR的AST成生
*	和樹(shù)遍歷
*/
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); 如果沒(méi)有子結(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)類(lèi)型 */
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)類(lèi)型 */
public void setType(int ttype);
public String toString();
public String toStringList();
public String toStringTree();
}

樹(shù)的語(yǔ)法規(guī)則

正如PCCTS1.33的SORCERER工具和ANTLR記號(hào)語(yǔ)法中所看到的，樹(shù)語(yǔ)法是一個(gè)嵌入語(yǔ)義動(dòng)作，語(yǔ)義斷言和句法斷言的EBNF規(guī)則的集合。

規(guī)則:	可選產(chǎn)生式1
|	可選產(chǎn)生式2
...
|	可選產(chǎn)生式n
;

每一個(gè)可選的產(chǎn)生式都是由一個(gè)元素列表所組成的，列表中的元素是加入了樹(shù)模式的ANTLR正規(guī)語(yǔ)法中的一個(gè)，有如下的形式：

#( 根結(jié)點(diǎn) 子結(jié)點(diǎn)1 子結(jié)點(diǎn)2 ... 子結(jié)點(diǎn)n )

例如：下列的樹(shù)模式匹配一個(gè)以PLUS為根結(jié)點(diǎn)，并有兩個(gè)INT子結(jié)點(diǎn)簡(jiǎn)單樹(shù)結(jié)構(gòu)：

#( PLUS INT INT )

樹(shù)模式的根必須是一個(gè)記號(hào)引用，但是子結(jié)點(diǎn)元素不限于此，它甚至可以是子規(guī)則。例如，一種常見(jiàn)結(jié)構(gòu)是if-then-else樹(shù)結(jié)構(gòu)，其中的else子句聲明子樹(shù)是可選的：

#( IF expr stat (stat)? )
    

值得一提的是，當(dāng)指定樹(shù)模式和樹(shù)語(yǔ)法后，通常，會(huì)進(jìn)行滿足條件的匹配而不是精確的匹配。一旦樹(shù)滿足給定的模式，不管剩下多少?zèng)]有分析，都會(huì)報(bào)告一次匹配。例如，#( A B )，對(duì)于像#( A #(B C) D)這樣有相同結(jié)構(gòu)的樹(shù)，不管有多長(zhǎng)，都會(huì)報(bào)告一次匹配。

句法斷言

ANTLR樹(shù)分析器在工作時(shí)僅使用一個(gè)單獨(dú)的超前掃描符號(hào)，這在通常情況下不是一個(gè)問(wèn)題，因?yàn)檫@種中間形式被明確設(shè)計(jì)成利于遍歷的結(jié)構(gòu)。然而，偶爾也需要區(qū)別出相似的樹(shù)結(jié)構(gòu)。句法斷言就是被用來(lái)克服有限確定的超前掃描所帶來(lái)的限制。例如：在區(qū)分一元和二元減號(hào)時(shí)，可以為每一種類(lèi)型的減號(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)生式的“子集”.

語(yǔ)義斷言

語(yǔ)義斷言在可選產(chǎn)生式的開(kāi)始，僅僅同可選的斷言表達(dá)式合成一體，就像合成一個(gè)正規(guī)文法。語(yǔ)義斷言在產(chǎn)生式的中間，當(dāng)它斷言失敗時(shí)，也會(huì)像正規(guī)文法一樣拋出異常。

一個(gè)樹(shù)遍歷器的例子

考慮一下如何去建立一個(gè)計(jì)算器。一個(gè)方法是建立一個(gè)分析器，這個(gè)分析器識(shí)別輸入并計(jì)算表達(dá)式的值。按照這種方法，我們將會(huì)建立一個(gè)分析器來(lái)為輸入的表達(dá)式創(chuàng)建一棵樹(shù)，把表達(dá)式以這種中間形式表示，然后樹(shù)分析器遍歷這個(gè)樹(shù)，并計(jì)算出結(jié)果。

我們的識(shí)別器, CalcParser, 通過(guò)如下的代碼來(lái)定義：

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)是操作符，因此把它們作為子樹(shù)的根結(jié)點(diǎn)，在它們后面注釋上字符'^'。SEMI記號(hào)后綴有字符'!'，這指出了它不應(yīng)該被加入到樹(shù)中。

這個(gè)計(jì)算器的詞法分析定義如下：

class CalcLexer extends Lexer;
WS	:	(' '
|	'\t'
|	'\n'
|	'\r')
{ _ttype = Token.SKIP; }
;
LPAREN:	'('
;
RPAREN:	')'
;
STAR:	'*'
;
PLUS:	'+'
;
SEMI:	';'
;
INT	:	('0'..'9')+
;
    

識(shí)別器生成的樹(shù)是一棵簡(jiǎn)單的表達(dá)式樹(shù)。例如，輸入"3*4+5"所產(chǎn)生的樹(shù)的形式為#( + ( * 3 4 ) 5 )。為了給這種形式的樹(shù)建立樹(shù)遍歷器，你必須要為ANTLR遞歸的描述樹(shù)的結(jié)構(gòu)：

class CalcTreeWalker extends TreeParser;
expr	:	#(PLUS expr expr)
|	#(STAR expr expr)
|	INT
;

一旦指定結(jié)構(gòu)，就可以自由的嵌入語(yǔ)義動(dòng)作去計(jì)算出結(jié)果。一個(gè)簡(jiǎn)單的實(shí)現(xiàn)辦法就是使expr規(guī)則返回一個(gè)整型的值，然后使每一條可選產(chǎn)生式計(jì)算每個(gè)子樹(shù)的值。下面的樹(shù)文法和動(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í)候，沒(méi)有必要指定優(yōu)先級(jí)，因?yàn)樗呀?jīng)隱含在樹(shù)的結(jié)構(gòu)中了。這也解釋了為什么在以中間樹(shù)形式表示的時(shí)候，要比它的輸入要多很多。輸入的符號(hào)確實(shí)作為結(jié)點(diǎn)儲(chǔ)存在樹(shù)結(jié)構(gòu)中，而且這種結(jié)構(gòu)隱含了結(jié)點(diǎn)之間的關(guān)系。

要想執(zhí)行分析器和樹(shù)遍歷器，還需要以下的代碼：

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)的形式輸出樹(shù)
System.out.println(t.toStringList());
CalcTreeWalker walker = new CalcTreeWalker();
// 遍歷由分析器建立的樹(shù)
int r = walker.expr(t);
System.out.println("value is "+r);
} catch(Exception e) {
System.err.println("exception: "+e);
}
}
}
    

翻譯

樹(shù)分析器對(duì)檢查樹(shù)或者從一棵樹(shù)產(chǎn)生輸出來(lái)說(shuō)是很有用的，但必須要為它們添加處理樹(shù)轉(zhuǎn)換的代碼。就像正則分析器一樣，ANTLR樹(shù)分析器支持buildAST選項(xiàng)，這類(lèi)似于SORCERER的翻譯模式。程序員不去修改代碼，樹(shù)分析器自動(dòng)把輸入樹(shù)拷貝到作為結(jié)果的樹(shù)。每一個(gè)規(guī)則都隱含(自動(dòng)定義的)一個(gè)結(jié)果樹(shù)。通過(guò)getAST 方法，我們可以從樹(shù)分析器中獲得此樹(shù)的開(kāi)始符號(hào)。如果要一些可選產(chǎn)生式和文法元素不被自動(dòng)添加到輸入的樹(shù)上，它們后面要注釋上"!"。子樹(shù)可以被部分的或者全部重寫(xiě)。

嵌入到規(guī)則中的語(yǔ)義動(dòng)作可以根據(jù)測(cè)試和樹(shù)結(jié)構(gòu)來(lái)對(duì)結(jié)果樹(shù)進(jìn)行設(shè)置。參考文法動(dòng)作翻譯章節(jié).

一個(gè)樹(shù)翻譯的例子

再來(lái)看一下上面提到的簡(jiǎn)單計(jì)算器的例子，我們可以執(zhí)行樹(shù)翻譯來(lái)代替計(jì)算表達(dá)式的值。下面樹(shù)文法的動(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í)行分析器和樹(shù)翻譯器的代碼如下：

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)的形式輸出樹(shù)
System.out.println(t.toLispString());
CalcTreeWalker walker = new CalcTreeWalker();
// 遍歷由分析器建立的樹(shù)
walker.expr(t);
// 遍歷，并得到結(jié)果
t = (CommonAST)walker.getAST();
System.out.println(t.toLispString());
} catch(Exception e) {
System.err.println("exception: "+e);
}
}
}
}

檢查/調(diào)試AST

當(dāng)開(kāi)發(fā)樹(shù)分析器的時(shí)候，經(jīng)常會(huì)得到分析錯(cuò)誤。不幸的是，你的樹(shù)通常異乎尋常的大，使得很難去確定AST結(jié)構(gòu)錯(cuò)誤到底在哪里。針對(duì)這種情況(當(dāng)創(chuàng)建Java樹(shù)分析器的時(shí)候,我發(fā)現(xiàn)它非常有用),，我創(chuàng)建了一個(gè)ASTFrame類(lèi)(一個(gè)JFrame)，這樣，你就可以用Swing樹(shù)視圖來(lái)查看你的AST。它沒(méi)有拷貝這棵樹(shù)，而是用了一個(gè)TreeModel。以應(yīng)用程序方式運(yùn)行antlr.debug.misc.ASTFrame去或者看看Java代碼Main.java。就像不確定如何去調(diào)試一樣,我不確定它們?cè)谙嗤陌?總之,將會(huì)在以后的ANTLR版本中給出。這里有一個(gè)簡(jiǎn)單的使用例子：

public static void main(String args[]) {
// 創(chuàng)建樹(shù)結(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 $