第4天 用于表示程序的对象

程序分割为单词后，接下来是构造抽象语法树。

4.1 抽象语法树的定义

抽象语法树（AST，Abstract Syntax Tree）是一种用于表示程序结构的树形结构。

词法分析 （分割单词）-> 语法分析（构造抽象语法树）

file

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

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

file

4.2 设计节点类

抽象语法树的节点类

抽象语法树的所有节点都是ASTree的子类

ASTLeaf类是叶节点（不含树枝的节点）的父类
ASTList是含有树枝的节点对象的父类
其他类都是ASTList或ASTLeaf类的子类

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

ASTree类的主要方法

ASTLeaf child(int i) //返回第i个子节点
int numChildren() //返回子节点的个数（如果没有子节点则返回0）
Iterator<ASTree> children() //返回一个用于遍历子节点的iterator

file file

BinaryExpr类同样也有left和right这两个字段
这两个字段并不直接在BinaryExpr类中定义，而是通过其父类ASTList类的children字段定义。
如代码清单4.6所示，BinaryExpr类不含left及right字段，而是提供了left与right方法。这些方法能够分别从children字段保存的ASTree对象中选取，并返回对应的左子节点与右子节点。
BinaryExpr类也没有图4.1与图4.2中出现的用于保存运算符的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.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; }
}

代码清单 4.3 ASTList.java

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;
    }
}

代码清单 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> c) { super(c); }
    public ASTree left() { return child(0); }
    public String operator() {
        return ((ASTLeaf)child(1)).token().getText();
    }
    public ASTree right() { return child(2); }
}

4.3 BNF

BNF(Backus-NaurForm, 巴科斯范式)
EBNF(Extended BNF,  扩展巴科斯范式)

BNF能用于表达语言学领域中的Noam Chomsky 上下文无关文法（BNF与上下文无关文法等价）

BNF中用到的元符号

{ pat }            模式pat至少重复0次

[ pat ]            与重复出现0次或1次的模式pat匹配

pat1 | pat2        与pat1或pat2匹配

{}                 将括号内视为一个完整的模式

file

factor: 因子

term：项

expression：表达式

file

只看概念有点难理解 书上的例子比较清楚

file

4.4 语法分析与抽象语法树

file

慢慢开始有难度了，先按计划看完吧。有些地方可能确实还得在理解理解