抽象语法树（AST）

原文出自：http://blog.csdn.net/zhouhuozhi/archive/2009/06/07/4250258.aspx
抽象语法树（AST）
最近在做一个类JAVA语言的编译器，整个开发过程，用抽象语法树（Abstract SyntaxTree,AST）作为程序的一种中间表示，所以首先就要学会建立相对应源代码的AST和访问AST。Eclipse AST是Eclipse JDT的一个重要组成部分，定义在包org.eclipse.jdt.core.dom中，用来表示JAVA语言中的所有语法结构。
Eclipse AST的总体结构
1、org.eclipse.jdt.core.dom.AST（AST节点类）
Eclipse AST的工厂类，用于创建表示各种语法结构的节点。

2、org.eclipse.jdt.core.dom.ASTNode及其派生类（AST类）
用于表示JAVA语言中的所有语法结构，在实际使用中常作为AST上的节点出现。

3、org.eclipse.jdt.core.dom.ASTVisitor（ASTVisitor类）
Eclipse AST的访问者类，定义了统一的访问AST中各个节点的方法。
详细介绍：
一、AST节点类
整体结构包括CompilationUnit类(编译单元）、TypeDeclaration类（类型声明）、MethodDeclaration类（方法声明）；
语句包括Block类（语句块）、ExpressionStatement类（表达式）、IfStatement(if语句）、WhileStatement类（while语句）、EmptyStatement类（空语句）、BreakStatement类和ContinueStatement类；
表达式包括MethodInvocation类（方法调用）、Assignment类（赋值表达式）（“=”、“+=”、“-=”、“*=”、“/=”）、InfixExpression类（中缀表达式）（“+”、“-”、“*”、“/”、“%”、“==”、“！=”、“<"、“<=”、“>=”、“&&”、“||”。）、 PrefixExpression类（前缀表达式）（“+”PLUS  “-”MINUS  “！”NOT）、ParenthesizedExpression类（带括号的表达式）、NumberLiteral类（整数）、Name类（simple）、MethodInvocation类（方法调用）。
二、AST类
关键是创建编译单元节点，创建类AST的实例。
AST ast = AST.newAST(JLS3);
三、ASTVisitor类
它提供与节点类有关的visit()方法和endVisit()法，与节点类无关的preVisit()方法和postVisit()方法。
boolean  visit( T node):这类方法如果返回true，则接着访问子节点。如果返回false，则不再访问子节点。
void endVisit(T node):这类方法在节点node的子节点已经被访问或者是在visit(node)返回false后调用。
void preVisit():这类方法在visit(node)之前被调用。
void postVisit():这类方法在endVisit(node)之后被调用。
在做简单解释器过程中，分析句子时我主要用到了上面的visit()和endVisit()方法，其中visit()方法是比较好理解的，主要是endVisit()方法在没有特定语法分析树的情况下分析是比较抽象的，所以下面我举几个例子分析。
endVisit（）在node的子节点已被访问后调用型：
a、赋值语句分析为例：

i1 = 1;
i4 = i1;
它们对应语法树结构：
Expressionstatement

Assignment


simplename
numberLiteral




Expressionstatement
Assignment





simplename
simplename



实现程序：
int rightis_num = 1;
visit(Assignment n){
return true;
}
public void endVisit(Assignment n)//访问完所有的节点后，rightis_num已经能够确定
    {
        Expression string = n.getLeftHandSide();//返回表达式左部
        String simplename =((SimpleName) string).getIdentifier();//将变量串赋给simplename
        try
        { 
           if(rightis_num == 1)
           {
               Expression data1 = n.getRightHandSide();//返回表达式右部
               System.out.println(simplename);
               hm.put(simplename,new Integer(((NumberLiteral) data1).getToken()));//将变量及值加入hashmap
               System.out.println(hm.get(simplename));
        }
           else//右部为标识符
           { 
               Expression data2 = n.getRightHandSide();//返回表达式右部
               String rightname = ((SimpleName) data2).getIdentifier();
               hm.put(simplename,hm.get(rightname));
               System.out.println(hm.get(simplename));             
           }
        }
        catch(Exception e)
        {}
    }



对应源程序AST的建立
           
class Program{
static void main(){
    i = 10;
    }
}

/************实现方法************/

AST ast = AST.newAST(JLS3);

CompilationUnit cu = ast.newCompilationUnit();//CompilationUnit实例中包含一个TypeDeclaration

TypeDeclaration type = ast.newTypeDeclaration();//TypeDeclaration实例表示程序中的类
type.setName(ast.newSimpleName("Program"));

MethodDeclaration method = ast.newMethodDeclaration();//TypeDeclaration实例中添加类Program中的方法main();
method.setName(ast.newSimpleName("main"));
type.bodyDeclarations().add(method);
method.modifiers().add(
    ast.newModifier(Modifier.ModifierKeyword.STATIC_KEYWORD));//设置方法main()的modifier修饰语为static
method.setReturnType2(ast.newPrimitiveType(PrimitiveType.VOID));//设置方法main()的返回类型为void

Block mainBody = ast.newBlock();
method.setBody(mainBody);//构造main函数的函数体mainBody

//向方法main函数体mainBody中添加语句
Assignment.assign = ast.newAssignment();//构建赋值表达式
assign.setLeftHandSide(ast.newSimpleName("i"));//设置赋值表达式的左值为i
assign.setOperator(Assignment.Operator.ASSIGN);//设置赋值表达式的赋值算符为=
assign.setRightHandSide(ast.newNumberLiteral("10"));//设置赋值表达式的右值为数字10

ExpressionStatement statement = ast.newExpressionStatement(assign);
mainBody.statements().add(statement);//由赋值表达式构建语句，并把这个语句加入方法Main()的函数体。

             

访问方法

在Eclipse AST中，结合AST节点的accept()方法和ASTVisitor实例，假设待访问的AST树的根节点为root，则调用root.accept()就可以启动对这棵AST树的遍历。

总结：做这个简单解释器的主要目的是熟悉程序源代码对应AST的映射，创建对应的AST方法都比较的固定，问题不大。难主是难在遍历树上，分析不同的语句结构，需要重写Visit()方法，同时要适当利用endVisit()方法增加一些控制变量，以决定应该解释句子的哪一分支。到现在对preVisit()和postVisit()方法仍然不怎么了解，在接下来的编译器开发中仍需慢慢摸索。熟悉了AST相关知识，后续工作可以展开了。