基于 LLVM 自制编译器(2)——解析器、抽象语法树

发表于 更新于 分类于 Waline：

概述

本章，我们将基于词法分析器，为 Kaleidoscope 构建一个完整的解析器（Parser）。通过解析器，我们可以定义并构造抽象语法树（Abstract Syntax Tree，AST）。

我们构造的解析器使用两种方法进行语法分析：

  • 递归下降分析法（Recursive Descent Parsing）：用于基本表达式的解析。
  • 算符优先分析法（Operator-Precedence Parsing）：用于二元表达式的解析。

在实现解析器之前，我们先来介绍一下解析器的输出——抽象语法树。

抽象语法树

抽象语法树（AST）为编译器后续的各个阶段提供了一种易于解释的表示形式，比如：代码生成。通常，我们希望编程语言中的每一种结构都有一个对应的表示对象。为了实现这种映射关系，我们使用 AST 对语言进行分析建模。

在 Kaleidoscope 的 AST 中，我们设计了三种结构，分别是：

  • 表达式
  • 原型
  • 函数

表达式

如下所示，ExprAST 是 AST 中表达式的基类定义，其包含了多种子类定义，分别用于对应不同的具体表达式。由于 Kaleidoscope 只有一种数据类型——双精度浮点类型，因此我们没有必要存储类型信息。当然，现实的编程语言通常都包含多种类型，这种情况下 ExprAST 会包含一个用于存储类型信息的字段。 

1
2
3
4
5
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
    virtual ~ExprAST() {}
};

如下所示为 ExprAST 的各种子类定义，分别是：

  • NumberExprAST：用于表示 数值表达式，其捕获字面量的数值保存于 Val 中。
  • VariableExprAST：用于表示 变量表达式，其捕获变量名保存于 Name 中。
  • BinaryExprAST：用于表示 二元表达式，其使用 Op 保存操作符，如：+。使用 LHS 和 RHS 分别保存左子表达式和右子表达式。
  • CallExprAST：用于表示 函数调用表达式，其使用 Callee 保存函数名。使用 Args 数组变量保存函数的各个参数。

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
31
32
33
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
    double Val;

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

/// 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)) {}
};

对于仅包含基本功能的编程语言而言，上述为全部的 AST 表达式节点定义。由于不包含条件控制流，因此这并不是图灵完备的；对此，我们将在后面进一步对其进行优化。

原型

如下所示，PrototypeAST 为 AST 中原型（Prototype）的定义。原型用于表示一个函数的原型，用于捕获函数的名称，各个参数的名称等。 

1
2
3
4
5
6
7
8
9
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 为 AST 中函数的定义。函数由函数原型和函数体组成，其分别使用 Proto 和 Body 进行存储。其中函数体是一个 AST 表达式结构。 

1
2
3
4
5
6
7
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)) {}
};

解析器基础

上文，我们定义了 AST 的结构，包括各种类型的节点。下面，我们来介绍如何通过解析器构建 AST。例如，对于表达式 x+y 可以通过如下方式将其解析成 AST。 

1
2
3
auto LHS = std::make_unique<VariableExprAST>("x");
auto RHS = std::make_unique<VariableExprAST>("y");
auto Result = std::make_unique<BinaryExprAST>('+', std::move(LHS), std::move(RHS));
为此，我们需要实现一些辅助函数，如下所示。我们通过 CurToken 作为词法分析器的输出 token 缓冲区。解析器内部每次调用词法分析器，输出一个 token，存储在缓冲区中。解析器则通过读取 CurToken 用于后续的解析。 
1
2
3
4
5
6
7
/// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
/// token the parser is looking at.  getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() {
    return CurTok = gettok();
}

除了处理错误，我们还定义了 LogError 函数。这里我们对于不同类型的错误处理均返回 nullptr。 

1
2
3
4
5
6
7
8
9
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
    fprintf(stderr, "LogError: %s\n", Str);
    return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
    LogError(Str);
    return nullptr;
}

表达式解析

Kaleidoscope 文法的每一个产生式，我们定义一个对应的解析函数。关于表达式的解析，其实可以分为以下几种类型：

  • 数值表达式：解析 NumberExprAST。
  • 括号表达式：解析 BinaryExprAST。
  • 标识符表达式：解析两种 AST 类型 VariableExprAST 和 CallExprAST。

下面我们分别进行介绍。

数值表达式

对于数值表达式，我们定义如下解析函数。 

1
2
3
4
5
6
7
/// 文法产生式
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
    auto Result = std::make_unique<NumberExprAST>(NumVal);
    getNextToken(); // consume the number
    return std::move(Result);
}
当词法分析器分析当前 token 的类型为 tok_number 时，解析器会调用 ParseNumberExpr 解析函数，读取全局变量 NumVal，从而获取数值，最终创建并返回一个 NumberExprAST 节点。

在 ParseNumberExpr 解析函数中，它将读取所有与产生式相关的 token，并将下一个 token 写入词法分析器缓存 CurTok 中，以用于后续的分析。这其实是递归下降分析的标准方式，即 预测分析——提前读取下一个 token 进行分析，避免深度优先搜索带来回溯开销。

括号表达式

对于括号表达式，我们定义如下解析函数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
/// 文法产生式
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
  getNextToken(); // eat (.
  auto V = ParseExpression();
  if (!V)
    return nullptr;

  if (CurTok != ')')
    return LogError("expected ')'");
  getNextToken(); // eat ).
  return V;
}
在 ParseParenExpr 解析函数中，我们可以看到对于 LogError 的使用。当调用 LogError 时，表示当前 token 是 (，在解析完子表达式之后，发现并没有与之匹配的 )。比如，当我们使用 (4 x 替代 (4) 作为输入，解析器就会调用 LogError 进行报错处理。

除此之外，我们还可以发现内部递归调用了 ParseExpression 解析函数（后面我们会提到该函数）。通过递归调用，解析器能够处理递归语法，从而简化每一个文法产生式，最终返创建并返回一个 BinaryExprAST 节点。

注意，括号并不会构建 AST 节点，其最大的作用是辅助解析器进行分组。当 AST 构建完毕，括号也就不需要了。

标识符表达式

对于标识符表达式，我们定义如下解析函数。 

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
31
32
33
34
35
36
/// 文法表达式
/// identifierexpr
///   ::= identifier
///   ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;

  getNextToken();  // eat identifier.

  if (CurTok != '(') // Simple variable ref.
    return std::make_unique<VariableExprAST>(IdName);

  // Call.
  getNextToken();  // eat (
  std::vector<std::unique_ptr<ExprAST>> Args;
  if (CurTok != ')') {
    while (1) {
      if (auto Arg = ParseExpression())
        Args.push_back(std::move(Arg));
      else
        return nullptr;

      if (CurTok == ')')
        break;

      if (CurTok != ',')
        return LogError("Expected ')' or ',' in argument list");
      getNextToken();
    }
  }

  // Eat the ')'.
  getNextToken();

  return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
解析器会在当前 token 类型为 tok_identifier 时调用 ParseIdentifierExpr 解析函数。其内部同样实现了递归分析和错处处理，并且通过预测分析的方式来判断当前的标识符是变量引用表达式还是函数调用表达式，从而分别进行处理。这里的预测分析是通过判断当前 token 下一个 token 是否是 ( 实现的，从而分别构建 VariableExprAST 节点和 CallExprAST 节点。

主表达式

我们将四种类型的表达式统称为 主表达式（Primary Expression）。 为了方便外部对各种类型的表达式进行解析，我们提供一个主表达式解析函数，对外隐藏细节，对内提供实现，该解析方法如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// 文法产生式
/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case tok_identifier:
    return ParseIdentifierExpr();
  case tok_number:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  }
}

ParsePrimary 解析函数的实现逻辑非常清晰，即通过读取 CurTok 进行预测分析，判断 token 类型，并调用对应解析函数，从而构建 AST。

二元表达式解析

二元表达式是表达式的一种，相比于其他三种表达式，二元表达式（Binary Expression）解析会更加复杂，因为它们通常具有二义性。比如，当我们输入字符串 x+y*z，解析器可以解析成 (x+y)*z 或 x+(y*z)。基于数学定义，我们期望解析器能将其解析为后者，因为乘法 * 的优先级是高于加法 + 的。

处理二义性的方式很多，其中一种优雅且高效的方式是 算符优先分析法。这种分析技术通过为操作符定义优先级来辅助递归分析。比如，我们可以通过如下方式来定义优先级。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // Make sure it's a declared binop.
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0) return -1;
  return TokPrec;
}

int main() {
  // Install standard binary operators.
  // 1 is lowest precedence.
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40;  // highest.
  ...
}
我们以二元运算符为键，优先级为值存储于哈希表中，便于进行扩展。在 Kaleidoscope 中，我们仅支持 4 种二元运算符。GetTokPrecedence 函数根据当前 token 从哈希表中读取对应的优先级，如果 token 不是二元运算符，则返回 -1。

算符优先分析法的基本思想是：将具有二义性二元运算符的表达式分解为多个片段，依次进行解析。比如，对于表达式 a+b+(c+d)*e*f+g。算符优先分析法会将其视为一系列由二元运算符分隔的主表达式。因此，解析器会首先分析头部的主表达式 a，然后依次分析 [+, b]，[+, (c+d)]，[*, e]，[*, f]，[+, g]。由于括号表达式也是主表达式，因此二元表达式的解析并不需要关注类似 (c+d) 这样的嵌套子表达式。

下面，我们来看一下具体的实现。

首先，我们将表达式分解为 一个主表达式+多个[binop, primaryexpr] 的形式，对应的解析函数如下所示。

1
2
3
4
5
6
7
8
9
10
11
/// 文法产生式
/// expression
///   ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParsePrimary();
  if (!LHS)
    return nullptr;

  return ParseBinOpRHS(0, std::move(LHS));
}

ParseBinOpRHS 函数用于解析 [binop, primaryexpr] 序列，其入参包含两个：优先级、已解析的表达式指针。值得注意的是，表达式 x 其实也是一个有效的表达式，在这种文法表达式 binoprhs 为空的情况下，ParseBinOpRHS 解析函数会将传入的已解析的表达式指针直接返回。

ParseBinOpRHS 函数的优先级的参数表示 最小算符优先级（Minimal Operator Precedence），即函数能够允许读取的运算符。比如，如果当前的分析内容是 [+, x]，而传入 ParseBinOpRHS 函数的优先级为 40，那么函数不会读取任何 token，因为 + 的优先级为 20。

ParseBinOpRHS 函数的具体定义如下所示。 

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
31
32
33
34
35
36
37
/// 文法产生式
/// binoprhs
///   ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // If this is a binop, find its precedence.
  while (true) {
    int TokPrec = GetTokPrecedence();

    // If this is a binop that binds at least as tightly as the current binop,
    // consume it, otherwise we are done.
    if (TokPrec < ExprPrec)
      return LHS;

    // Okay, we know this is a binop.
    int BinOp = CurTok;
    getNextToken(); // eat binop

    // Parse the primary expression after the binary operator.
    auto RHS = ParsePrimary();
    if (!RHS)
      return nullptr;

    // If BinOp binds less tightly with RHS than the operator after RHS, let
    // the pending operator take RHS as its LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
      if (!RHS)
        return nullptr;
    }

    // Merge LHS/RHS.
    LHS =
        std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
  }
}
在 ParseBinOpRHS 函数内部，它会首先读取当前 token 的优先级。如果优先级低于设定 ExprPrec，则直接返回传入的已解析的表达式 LHS。如果优先级符合设定，那么将解析操作符之后的主表达式。

此时，我们已经解析了表达式的左部以及 RHS 序列的一个分段。接下来，我们需要决定如何关联表达式。比如，这里有两种关联方式：(a+b) binop <未解析部分> 或 a + (b binop <未解析部分>)。为此，我们通过预测分析的方式，继续向前读取一个运算符的优先级，并与 BinOp 的优先级进行比较（例子中是 +）。

如果 RHS 右边的运算符的优先级小于或等于当前操作符，那么我们选择 (a+b) binop <未解析部分> 的关联方式。在例子中，当前的运算符和下一个运算符都是 +，具有相同的优先级。

在例子中，解析函数会将 a+b+ 解析为 (a+b)，并在下一次循环中继续执行。接下来，它会将 (c+d) 作为主表达式进行解析，即直接解析 [+, (c+d)]。继续解析，则会遇到 * 运算符。由于 * 的优先级大于 +，因此将执行 if 语句的内部逻辑。其内部逻辑会对高优先级的部分作为进行整体解析，然后将其作为低优先级运算符右部。为此，我们递归地调用 ParseBinOpRHS 函数，并指定最低优先级为 TokPrec+1。在例子中，会将 (c+d)*e*f 作为 + 的 RHS。

最后，[+, g] 会在下一次循环中被解析。

此时，我们可以使用解析器对任意 token 序列进行解析并构建表达式。当检测到不属于表达式的 token 时停止解析。

函数相关解析

关于函数相关的解析，其实可以分为几种类型：

  • 函数原型
  • 函数定义
  • 外部原型

函数原型

对于函数原型，我们定义如下解析函数。 

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
/// 文法产生式
/// prototype
///   ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  if (CurTok != tok_identifier)
    return LogErrorP("Expected function name in prototype");

  std::string FnName = IdentifierStr;
  getNextToken();

  if (CurTok != '(')
    return LogErrorP("Expected '(' in prototype");

  // Read the list of argument names.
  std::vector<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return LogErrorP("Expected ')' in prototype");

  // success.
  getNextToken();  // eat ')'.

  return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}

函数定义

对于函数定义，我们定义如下解析函数。其本质上就是函数原型与普通表达式的组合，后者用于表示函数体，如下图所示。 

1
2
3
4
5
6
7
8
9
10
11
/// 文法产生式
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
  getNextToken();  // eat def.
  auto Proto = ParsePrototype();
  if (!Proto) return nullptr;

  if (auto E = ParseExpression())
    return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  return nullptr;
}

外部原型

对于外部原型，我们定义如下解析函数。其本质上就是 extern 关键字与函数原型的组合。 

1
2
3
4
5
6
/// 文法产生式
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
  getNextToken();  // eat extern.
  return ParsePrototype();
}

顶层表达式解析

为了允许用户输入任意的顶层表达式，并支持解析。我们定义一个匿名空值（零参数）函数来进行解析，如下所示。 

1
2
3
4
5
6
7
8
9
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
  if (auto E = ParseExpression()) {
    // Make an anonymous proto.
    auto Proto = std::make_unique<PrototypeAST>("__anon_expr", std::vector<std::string>());
    return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  }
  return nullptr;
}

ParseTopLevelExpr 解析函数会通过调用 ParseExpression 解析函数进行解析。当解析得到 BinaryExprAST 节点后，创建一个 PrototypeAST 节点，并使用 FunctionAST 节点将两者封装成一个匿名函数，最终返回 FunctionAST 节点。

至此，我们介绍了各种类型的表达式的解析，下面我们通过实现一个驱动器来对实际的代码进行解析。

驱动器

驱动器（Driver）的实现如下所示，其仅仅是在一个顶层的循环中调用所有类型的表达式解析函数。 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static void HandleDefinition() {
  if (ParseDefinition()) {
    fprintf(stderr, "Parsed a function definition.\n");
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

static void HandleExtern() {
  if (ParseExtern()) {
    fprintf(stderr, "Parsed an extern\n");
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (ParseTopLevelExpr()) {
    fprintf(stderr, "Parsed a top-level expr\n");
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

/// 文法产生式
/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (1) {
    fprintf(stderr, "ready> ");
    switch (CurTok) {
    case tok_eof:
      return;
    case ';': // ignore top-level semicolons.
      getNextToken();
      break;
    case tok_def:
      HandleDefinition();
      break;
    case tok_extern:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}
值得注意的是，这里我们对顶层的分号进行了忽略处理。原因是，如果我们在命令行中输入 4 + 5，解析器并不是我们输入的内容是否结束。例如，我们可以在下一行输入 def foo...，在这种情况下，4 + 5 是顶层表达式的结尾，或者，我们可以输入 * 6 来续写表达式。对此，使用顶层分号，对应 4 + 5; 表达式，解析器才能知道表达式已经输入完成。

总结

通过 400 多行代码，我们定义了一门简单的语言，包括词法分析器、解析器和 AST 构造器。完成之后，我们可以通过可执行文件来验证 Kaleidoscope 代码，从而判断代码是否存储语法语义错误。

如下所示，为验证步骤及其结果。 

1
2
3
4
5
6
7
8
9
10
11
12
ready> def foo(x y) x+foo(y, 4.0);
Parsed a function definition.
ready> def foo(x y) x+y y;
Parsed a function definition.
Parsed a top-level expr
ready> def foo(x y) x+y );
Parsed a function definition.
Error: unknown token when expecting an expression
ready> extern sin(a);
ready> Parsed an extern
ready> ^C
$

当然，代码仍然具有很大的扩展空间。我们可以定义新的 AST 节点，并以多种方式对语言进行扩展等。下一章，我们将介绍如何从 AST 生成 LLVM 中间表示 IR。