抽象语法树(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的表达式和函数体了。

教程简介及词法分析器


语法分析器和AST


LLVM IR代码生成


添加JIT和优化支持


最新文章

归档