抽象语法树(AST)

在本章中,我们将以第一章中开发的词法分析器为基础,为Kaleidoscope语言开发一个完整的语法解析器。搞定语法解析器之后,我们就开始定义并构造抽象语法树(AST,Abstract Syntax Tree)。

在解析Kaleidoscope的语法时,我们将综合运用递归下降解析和运算符优先级解析两种技术(后者用于解析二元表达式,前者用于其他部分)。正式开始解析之前,不妨先来看一看解析器的输出:抽象语法树。

抽象语法树的作用在于牢牢抓住程序的脉络,从而方便编译过程的后续环节(如代码生成)对程序进行解读。AST就是开发者为语言量身定制的一套模型,基本上语言中的每种结构都与一种AST对象相对应。Kaleidoscope语言中的语法结构包括表达式、函数原型和函数对象。我们不妨先从表达式入手:

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() {}
};

/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;

public:
NumberExprAST(double Val) : Val(Val) {}
};

上述代码定义了基类ExprAST和一个用于表示数值常量的子类。其中子类NumberExprAST将数值常量的值存放在成员变量中,以备编译器后续查询。

直到目前为止,我们还只搭出了AST的架子,尚未定义任何能够体现AST实用价值的成员方法。例如,只需添加一套虚方法,我们就可以轻松实现代码的格式化打印。以下定义了Kaleidoscope语言最基本的部分所要用到的其他各种表达式的AST节点:

/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;

public:
VariableExprAST(const std::string &Name) : Name(Name) {}
};

/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;

public:
BinaryExprAST(char op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
};

/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;

public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
};

我们(特意)将这几个类设计得简单明了:VariableExprAST用于保存变量名,BinaryExprAST用于保存运算符(如+),CallExprAST用于保存函数名和用作参数的表达式列表。这样设计AST有一个优势,那就是我们无须关注语法便可直接抓住语言本身的特性。注意这里还没有涉及到二元运算符的优先级和词法结构等问题。

定义完毕这几种表达式节点,就足以描述Kaleidoscope语言中的几个最基本的结构了。由于我们还没有实现条件控制流程,它还不算图灵完备;后续还会加以完善。接下来,还有两种结构需要描述,即函数的接口和函数本身:

/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;

public:
PrototypeAST(const std::string &name, std::vector<std::string> Args)
: Name(name), Args(std::move(Args)) {}

const std::string &getName() const { return Name; }
};

/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;

public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
};

在Kaleidoscope中,函数的类型是由参数的个数决定的。由于所有的值都是双精度浮点数,没有必要保存参数的类型。在更强大、更实用的语言中,ExprAST类多半还会需要一个类型字段。

有了这些作为基础,我们就可以开始解析Kaleidoscope的表达式和函数体了。