抽象语法树定义

使用抽象语法树定义下面的程序：

1
13 + x * 2

方块表示的是由词法分析得到的对象，方块的上半部分表示类别。

BinaryExpr 对象用于表示双目运算表达式。

图中含有两个 BinaryExpr 对象，其中一个用于表示乘法运算 x * 2，另一个用于表示加法运算 13 加 x * 2。加法运算的左侧是整型字面量 13，它是一个 NumberLiteral 对象。右侧是 x * 2，它是另一个BinaryExpr 对象。这样通过对象来表示运算符的左值与右值的方式能一目了然地显示各自表示的内容。

因为operator和left、right都是字段，用箭头表示不是特别清晰。
改进后的表现形式：

（这个图非常像Lisp中的S表达式。）

对于以下表达式：

1
(13 + x) * 2

抽象语法树仅用于表示语法分析的结果，因此通过词法分析得到的单词并不一定要与抽象语法树的节点一一对应。抽象语法树是一种去除了多余信息的抽象树形结构，所以括号不必包含在抽象语法树中，如下图：

设计节点类

ASTree类，抽象语法树所有节点都属于它的子类。
ASTLeaf类，是叶节点的父类，叶节点就是不含树枝的节点。
ASTList类，是含有树枝节点的父类。

NumberLiteral 与 Name 类用于表示叶节点
BinaryExpr 类用于表示含有树枝的节点

如图：

ASTree类

只要抽象语法树的节点不是叶节点，它就含有若干个树枝，并与其他节点相连。这些与树枝另一端相连的节点称为子节点（child）。

child 方法用于返回第 i 个子节点。
numChildren 方法用于返回子节点的个数。
children 方法则会返回一个 Iterator 对象，用于依次遍历所有子节点。

ASTLeaf

ASTLeaf 是叶节点对象的类，叶节点对象没有子节点，因此 numChildren 方法将始终返回 0，children 方法将返回一个与空集合关联的 Iterator 对象。

抽象语法树的叶节点不含子节点，因此 ASTLeaf 类没有 children 字段。不过它含有 token 字段。本书规定抽象语法树的叶节点必须与对应的单词关联。token 字段保存了对应
的 Token 对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package stone.ast;
import java.util.Iterator;
import java.util.ArrayList;
import stone.Token;

public class ASTLeaf extends ASTree {
    private static ArrayList<ASTree> empty = new ArrayList<ASTree>(); 
    protected Token token;
    public ASTLeaf(Token t) { token = t; }
    public ASTree child(int i) { throw new IndexOutOfBoundsException(); }
    public int numChildren() { return 0; }
    public Iterator<ASTree> children() { return empty.iterator(); }
    public String toString() { return token.getText(); }
    public String location() { return "at line " + token.getLineNumber(); }
    public Token token() { return token; }
}

ASTList

ASTList 是非叶节点对象的类，可能含有多个子节点（即 ASTree 对象）。ASTList 类含有一个 children 字段，它是一种 ArrayList 对象，用于保存子节点的集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package stone.ast;
import java.util.List;
import java.util.Iterator;

public class ASTList extends ASTree {
    protected List<ASTree> children;
    public ASTList(List<ASTree> list) { children = list; }
    public ASTree child(int i) { return children.get(i); }
    public int numChildren() { return children.size(); }
    public Iterator<ASTree> children() { return children.iterator(); }
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append('(');
        String sep = "";
        for (ASTree t: children) {
            builder.append(sep);
            sep = " ";
            builder.append(t.toString());
        }
        return builder.append(')').toString();
    }
    public String location() {
        for (ASTree t: children) {
            String s = t.location();
            if (s != null)
                return s;
        }
        return null;
    }
}

BNF

要想构造抽象语法树，语言处理器必须要知道会接收哪些单词序列，即语法的规则，比如if语句应该具有什么样的结构。

BNF即是表达语法规则的书写方式。


factor位于：号左侧，它被称为非终结符或元变量。：号右侧是规定好的符号，用于表示各种单词，例子中用的是NUMBER，它表示任意一个整形字面量单词。就是说任意的数都可以匹配成factor规则。

  • factor 能表示 NUMBER （1 个整型字面量单词），或由左括号、expression （表达式）及右括号依次排列而成的单词序列。
  • term（项）表示一种由 factor 与运算符 * 或 / 构成的序列，其中 factor 至少出现一次，运算符则必须夹在两个 factor 之间
  • expression 表示一种由 term（对 term 对应的单词序列）与运算符 + 或 - 构成的序列，其中 term 至少出现一次，运算符则必须夹在两个term 之间。

非终结符可以理解为常用模式的别称，在定义其他模式时能够引用这些非终结符。模式中包含非终结符是 BNF 的特征之一。


整个单词序列与代码清单 4.7 中的模式 expression 匹配。

该单词序列的局部与非终结符 factor 及 term 的模式匹配，整个序列则明显与模式 expression 匹配。