Graduation Project——用于表示程序的对象
语言处理器在词法分析阶段将程序分割为单词后，将开始构造抽象语法树。抽象语法树AST是一种用于表示程序结构的树形结构。抽象语法树的构造过程称为语法分析，依然属于语言粗利器的前半段。因为经过词法分析后，程序已经被分解为一个个单词，语法分析的主要任务是分析单词之间的关系。比如判断哪些单词属于同一个表达式或语句，以及处理左右括号（单词）的配对等问题。语法分析的结果能够通过抽象语法树来表示，这个阶段还会检查程序中是否包含有语法错误。
抽象语法树的定义
已经得到token流的我们，再通过语法分析就能得到如图所示的对象形式表示的树形结构。
BinaryExpr对象用于表示双目运算表达式，譬如1+2，1*2等等。NumberLiteral对象是一个整型字面量。Name对象表示变量名。
当然可以简化为如下的形式：
设计节点类
为了保持简洁，所有节点类都是ASTree的子类。ASTLeaf类和ASTList类是ASTree的直接子类。ASTLeaf是节点的父类，ASTList是非叶节点的父类。
其他类都是它俩的子类。
下面来看看代码：
package stone.ast;
import java.util.Iterator;
public abstract class ASTree implements Iterable<ASTree>{
public abstract ASTree child(int i);//返回第i个子节点
public abstract int numChildren();//返回子节点的个数（叶子节点返回0）
public abstract Iterator<ASTree> children();//（子节点iterator）
public abstract String location();//返回AST节点在程序内所处位置的字符串
public Iterator<ASTree> iterator(){//适配器，把ASTree类转为Iterable类型
return children();
}
}
其他代码略。
BNF
要构造抽象语法树，语言处理器首先要知道将会接收哪些单词序列，并确定希望构造出怎样的抽象语法树。通常，这些设定由程序设计语言的语法决定。
语法规定了单词的组合规则，例如，双目运算表达式应该由哪些单词构成，或者if语句应该具有怎么样的结构等等。而程序设计语言的语法通常会包含诸如if语句的执行方式，或者通过extends继承类时将执行哪些处理等规则。不过，这里讨论的语法不含那些程序设计语言范畴的内容，仅考虑如何处理词法分析器传来的单词序列。
举例来讲，我们看一下一条仅包含整型字面量与四则运算的表达式。代码采用BNF（Backus-Naur Form，巴克斯范式）的书写方式。
BNF中用到的元符号：
-
{pat}：模式pat至少重复0次 -
[pat]：与重复出现0次或1次的模式pat匹配 -
pat1|pat2：与pat1或者pat2匹配 -
()：将括号内视为一个完整的模式
通过BNF来表示语法的例子：
- factor:NUMBER|"(“expresion”)"
- term:factor{("*"|"/")factor}
- expression:term{("+"|"-")term}
:左侧写的内容能够用于表示在:右侧写的模式相匹配的单词序列。所以左侧出现的诸如factor这样的符号称为非终结符。而终结符是一些实现规定好的符号，表示各种单词，即右侧的诸如NUMBER，以及双引号"括起来的诸如"("就是终结符号。另一方面，右侧也含有expression这样的非终结符。
理解：
factor表示NUMBER或者由左右括号括起来的expression的单词序列。
term是由factor与运算符*或/构成的序列，其中factor至少出现一次，并且运算符必须夹在两个factor之间（因为{}括起来的模式可以出现0次或多次，因此term的规则很容易理解）。
expression是由term与运算符+、-构成的序列。
我们其实可以猜测出来，上面就是一个运算表达式的表示。
我们继续13+4*2的例子，它经由词法分析后的结果是：NUMBER "+" NUMBER "*" NUMBER
形象的说就是：
语法分析与抽象语法树
图的左上方是语法分析的结果，右下方是构造的抽象语法树，正好上下颠倒：