《两周自制脚本语言》—— 第四天（用于程序表示的对象）

笔记、源码同步在 github 上，欢迎 Star，蟹蟹～

---

语言处理器在词法分析阶段将程序分割为单词后，将开始构造抽象语法树。抽象语法树（AST，Abstract Syntax Tree）是一种用于表示程序结构的树形结构。语法分析的主要任务是分析单词之间的关系，如判断哪些单词属于同一个表达式或语句，以及处理左右括号（单词）的配对等问题。这一阶段还会检查程序中是否含有语法错误。

抽象语法树的定义展开目录

我们试着用抽象语法树来表示下面的 Stone 语言程序

13 + x * 2

只要将这个程序理解为算式 13+x*2，即 13 与（x*2）的和即可。下图是它的对象形式表示。
图中的矩形表示对象。矩形上半部分显示的是类名

BinaryExpr 对象用于表示双目运算表达式。双目运算指的是四则运算等一些通过左值和右值计算新值的运算

图中含有两个 BinaryExpr 对象，其中一个用于表示乘法运算 x*2，另一个用于表示加法运算 13 加 x*2

表达式 x*2 左侧的 x 是一个变量名，因此能用 Name 对象来表示。右侧的 2 是一个整型字面量，因此以 NumberLitera1 对象表示
抽象语法树优势可能难以理解，因此可以像上图那样改写语法树，将所有的字段都写在矩形中。这样一来，各个对象与字段的关系将更加清晰

抽象语法树是一种去除了多余信息的抽象树形结构。例如，拿

(13+x) * 2

这样一个表达式来说，它与之前的例子不同，包含了括号。这段程序的抽象语法树如下图所示。叶节点和中间的节点都不含括号

13+x 是乘法的左值，必须在做乘法计算之前算好。即图的抽象语法树中不含括号。因此，程序中的括号等信息不必出现在抽象语法树中。除了括号，句尾的分号等无关紧要的单词通常也不会出现在抽象语法树中。

下图是抽象语法树的节点类。为保持程序简洁，抽象语法树所有的节点类都是 ASTree 的子类。之后还会进一步详述。ASTLeaf 类和 ASTList 类是 AsTree 的直接子类。ASTLeaf 是叶节点（不含树枝的节点）的父类，ASTList 是含有树枝的节点对象的父类，其他的类都是 ASTList 或 ASTLeaf 类的子类。

NumberLitera1 与 Name 类用于表示叶节点，BinaryExpr 类用于表示含有树枝的节点，它们分别是上述两个类的子类。

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

ASTree 类的主要方法

此外，ASTree 类还含有 location 方法与 iterator 方法。location 方法将返回一个用于表示抽象语法树节点在程序内所处位置的字符串。iterator 方法与 children 方法功能相同，它是一个适配器，在将 ASTree 类转为 Iterable 类型时将会用到该方法

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

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

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

NumberLiteral 和 Name 类具有名为 value 及 name 的字段。在实际实现时，这些字段并非由各个类直接定义，而是通过 ASTLeaf 类的 token 字段完成这一工作。例如，NumberLitera1 含有一个表示与之对应的整型字面量的单词，这个 Token 对象实际由 ASTLeaf 类的 token 字段保存。NumberLiteral 类的 value 方法将从这个 token 字段中取得该整型字面量并返回。Name 类的实现方式也类似

BinaryExpr 类同样也有 1eft 和 right 这两个字段，不过在实际实现时，这两个字段并不直接在 BinaryExpr 类中定义，而是通过其父类 ASTList 类的 children 字段定义。如代码清单 4.6 所示，BinaryExpr 类不含 left 及 right 字段，而是提供了 1eft 与 right 方法。这些方法能够分别从 children 字段保存的 ASTree 对象中选取，并返回对应的左子节点与右子节点

BinaryExpr 类也没有用于保存运算符的 operator 字段。运算符本身是独立的节点（ASTLeaf 对象），作为 BinaryExpr 对象的子节点存在。也就是说，BinaryExpr 对象含有左值、右值及运算符这三种子节点。虽然 BinaryExpr 类没有 operator 字段，却提供了 operator 方法。该方法将从与运算符对应的 ASTLeaf 对象中获取单词，并返回其中的字符串。

代码清单 4.1 ASTree.java

package Stone.ast;

import java.util.Iterator;

public abstract class ASTree implements Iterable<ASTree> {
    public abstract ASTree child(int i);

    public abstract int numChildren();

    public abstract Iterator<ASTree> children();

    public abstract String location();

    public Iterator<ASTree> iterator() {
        return children();
    }
}

代码清单 4.2 ASTLeaf.java

package Stone.ast;

import java.util.ArrayList;
import java.util.Iterator;

import Stone.Token;

public class ASTLeaf extends ASTree {
    private static ArrayList<ASTree> empty = new ArrayList<ASTree>();
    protected Token token;

    public ASTLeaf(Token token) {
        this.token = token;
    }

    @Override
    public ASTree child(int i) {
        throw new IndexOutOfBoundsException();
    }

    @Override
    public int numChildren() {
        return 0;
    }

    @Override
    public Iterator<ASTree> children() {
        return empty.iterator();
    }

    public String toString() {
        return token.getText();
    }

    @Override
    public String location() {
        return "at line " + token.getLineNumber();
    }

    public Token token() {
        return token;
    }
}

代码清单 4.3 ASTList.java

package Stone.ast;

import java.util.Iterator;
import java.util.List;

public class ASTList extends ASTree {
    protected List<ASTree> children;

    public ASTList(List<ASTree> t) {
        children = t;
    }

    @Override
    public ASTree child(int i) {
        return children.get(i);
    }

    @Override
    public int numChildren() {
        return children.size();
    }

    @Override
    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();
    }
    
    @Override
    public String location() {
        for(ASTree t : children) {
            String s = t.location();
            if (s != null)
                return s;
        }
        return null;
    }

}

代码清单 4.4 NumberLiteral.java

package Stone.ast;

import Stone.Token;

public class NumberLiteral extends ASTLeaf {

    public NumberLiteral(Token t) {
        super(t);
    }

    public int value() {
        return token().getNumber();
    }
}

代码清单 4.5 Name.java

package Stone.ast;

import Stone.Token;

public class Name extends ASTLeaf {

    public Name(Token t) {
        super(t);
    }

    public String name() {
        return token().getText();
    }
}

代码清单 4.6 BinaryExpr.java

package Stone.ast;

import java.util.List;

public class BinaryExpr extends ASTList {
    public BinaryExpr(List<ASTree> t) {
        super(t);
    }

    public ASTree left() {
        return child(0);
    }

    public String operator() {
        return ((ASTLeaf) child(1)).token().getText();
    }
    
    public ASTree right() {
        return child(2);
    }
}

BNF展开目录

代码清单 4.7 通过 BNF 来表示语法的例子

factor:     NUMBER | "(" expression ")"
term:       factor { ("*" | "/") factor }
expression: term { ("+" | "-") term }

要构造抽象语法树，语言处理器首先要知道将会接收哪些单词序列，并确定希望构造出怎样的抽象语法树。通常，这些设定由程序设计语言的语法决定

语法规定了单词的组合规则，例如，双目运算表达式应该由哪些单词组成，或是 if 语句应该具有怎样的结构等。而程序设计语言的语法通常会包含诸如 if 语句的执行方式，或通过 extends 继承类时将执行哪些处理等规则。不过，这里仅会判断语句从哪个单词开始，中途能够出现哪些单词，又是由哪个单词结束

举例来讲，我们来看一下一条仅包含整型字面量与四则运算的表达式。代码清单 4.7 采用了一种名为 BNF（Backus-Naur Form，巴科斯范式）的书写方式

代码清单 4.7 第 1 行的规则中，factor（因子）意指与右侧模式匹配的单词序列。: 左侧出现的诸如 factor 这样的符号称为非终结符或元变量

与非终结符相对的是终结符，它们是一些事先规定好的符号，表示各种单词。在代码清单 4.7 中，NUMBER 这种由大写字母组成的名称，以及由双引号 " 括起的诸如 (的符号就是终结符。NUMBER 表示任意一个整型字面量单词，(表示一个内容为左括号的单词

在代码清单 4.7 第 1 行的规则中，factor 能表示 NUMBER（1 个整型字面量单词），或由左括号、expression（表达式）及右括号依次排列而成的单词序列。expression 是一个非终结符，第 3 行对其下了定义。因此，由左括号、与 expression 匹配的单词序列，及右括号这些单词组成的单词序列能与 factor 模式匹配

如果：右侧的模式中仅含有终结符，BNF 与正则表达式没有什么区别。此时，两者唯一的不同仅在于具体是以单词为单位检查匹配还是以字符为单位检查

另一方面，如果右侧含有类似于 expression 这样的非终结符，与该部分匹配的单词序列必须与另外定义的 expression 模式匹配。

代码清单 4.7 第 2 行中的 term（项）表示一种由 factor 与运算符 * 或 / 构成的序列，其中 factor 至少出现一次，运算符则必须夹在两个 factor 之间。由于 {} 括起来的模式将至少重复出现 0 次，因此，第 2 行的规则直译过来就是：与模式 term 匹配的内容，或是一个与 factor 相匹配的单词序列，或是在一个与 factor 相匹配的单词序列之后，由运算符 * 或 / 以及 factor 构成的组合再重复若干次得到的序列。

第 3 行的规则也是类似。expression 表示一种由 term（对 term 对应的单词序列）与运算符 + 或 - 构成的序列，其中 term 至少出现一次，运算符则必须夹在两个 term 之间。结合所有这些规则，可以发现与模式 expression 匹配的就是通常的四则运算表达式，只不过单词的排列顺序做了修改。也就是说，与该模式匹配的单词序列就是一个 expression。反之，如果单词序列与模式 expression 不匹配，则会发生语法错误（syntax error）

下图与代码清单 4.7 表示的是相同的语法。图中的圆圈表示终结符，矩形表示非终结符。箭头的分支与合并表示模式的循环出现或 “or” 的含义

那么接下来看一个具体的例子

13 + 4 * 2

在经过词法分析后将得到如下的单词序列

NUMBER "+" NUMBER "*" NUMBER

如下图所示，该单词序列的局部与非终结符 factor 及 term 的模式匹配，整个序列则明显与模式 expression 匹配。整型字面量 13 与 factor 匹配的同时也与 term 匹配。根据语法规则，单独的整型字面量单词能与 factor 匹配，单个 factor 又能与 term 匹配

下面这个包含括号的表达式也能与模式 expression 匹配

(13 + 4) * 2

根据语法规则，括号中的 13+4 与模式 expression 匹配，括号括起的 (13+4) 与模式 factor 匹配。因此，整个乘法表达式与模式 term 匹配。一个 term 又与模式 expression 匹配

语法分析与抽象语法树展开目录

语法分析用于查找与模式匹配的单词序列。查找得到的单词序列是一个具有特定含义的单词组。分组后的单词能继续与其他单词组一起做模式匹配，组成更大的分组

下图是根据代码清单 4.7 中的四则运算规则，对 13+4*2 进行语法分析后得到的结果，以及根据该结果构造的抽象语法树。图的左上方是语法分析的结果，右下方是构造的抽象语法树，正好上下颠倒。抽象语法树中的 13 或 + 等节点表示与相应单词对应的叶节点。可以看到，语法规则中出现的终结符都是抽象语法树的叶节点。非终结符 term 与 factor 也是抽象语法树的节点

第四天的思维导图展开目录