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 $