【IT168技术文档】在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 )
...
;

赋值的次序很重要，因为第二个可选产生式是第一个可选产生式的“子集”.

语义断言
语义断言在可选产生式的开始，仅仅同可选的断言表达式合成一体，就像合成一个正规文法。语义断言在产生式的中间，当它断言失败时，也会像正规文法一样抛出异常。 4312736love