LLVM学习入门(2):实现解析器 Parser 和语法树 AST

此篇主要是承接上篇 Kaleidoscope语言及词法分析内容，实现整个解析器，从而最终输出构建构建语法树 AST。

Parser 主要分为两部分，分别为 Recursive descent parser 和 Operator-precedence parser。

Operator-precedence parser: 运算符优先级解析器，主要是用来二进制表示。

Recursive descent parser: 递归下降解析器，用于其他所有内容。

接下来，我们先介绍一下语法分析树 AST：

2.1 The Abstract Syntax Tree (AST): 语法抽象树

AST 可以捕捉程序的行为，以及方便后续的编译。AST 对编成语言的每一个构造建立相应的对象，下面来定义 AST Node：

// ExprAST - 所有表达式的基类
class ExprAST {
public:
  virtual ~ExprAST() {}
};

// NumberExprAST - 数字表达式
class NumberExprAST : public ExprAST {
public:
    NumberExprAST(double Val) : NumVal(Val) {}
private:
    double NumVal;
};

// VariableExprAST - 变量表达式，类似可以表达变量'x'
class VariableExprAST : public ExprAST {
public:
    VariableExprAST(const std::string &Name) : Name(Name) {}
private:
    // 变量名字
    std::string Name;
};

// BinaryExprAST - 二元运算符表达式,例如'+'
// 这里没有讨论二元运算符的优先级
class BinaryExprAST : public ExprAST {
public:
    // op 代表操作符，LHS 代表运算符左边的表达式，RHS 代表右边的表达式
    BinaryExprAST(char op, std::unique_ptr<ExprAST> LHS,
                std::unique_ptr<ExprAST> RHS)
    : Op(op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
private:
    char Op;
    std::unique_ptr<ExprAST> LHS, RHS;
};

// CallExprAST - 函数调用表达式
class CallExprAST : public ExprAST {
public:
    CallExprAST(const std::string &Callee,
              std::vector<std::unique_ptr<ExprAST>> Args)
    : Callee(Callee), Args(std::move(Args)) {}
private:
    std::string Callee;
    std::vector<std::unique_ptr<ExprAST>> 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
34
35
36
37
38
39
40
41
42
43
44
45
46

为了便于学习理解，我们将条件表达式放到后边实现，接下来定义函数的声明和函数的 AST Node：

// PrototypeAST - 函数原型，表面形式
// 获取函数名字, 以及参数的数量
class PrototypeAST {
public:
    PrototypeAST(const std::string &name, std::vector<std::string> Args)
    : Name(name), Args(std::move(Args)) {}
  
    const std::string &getName() const { return Name; }
private:
    std::string Name;
    std::vector<std::string> Args;
};

// FunctionAST - 定义函数的本身
class FunctionAST {
public:
  FunctionAST(std::unique_ptr<PrototypeAST> Proto,
              std::unique_ptr<ExprAST> Body)
    : Proto(std::move(Proto)), Body(std::move(Body)) {}
private:
    std::unique_ptr<PrototypeAST> Proto;
    std::unique_ptr<ExprAST> Body;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.2 Parser Basics: 基本的解析器

我们已经构建了 AST，现在我们需要 Parse 来构建 AST。例如 "x + y"这个二元表达式，生成三个 token 到 AST，产生如下结果：

// LHS 左边的表达式
auto LHS = std::make_unique<VariableExprAST>("x");
// RHS 右边的表达式
auto RHS = std::make_unique<VariableExprAST>("y");
// op 为 '+'
auto Result = std::make_unique<BinaryExprAST>('+', std::move(LHS),
                                              std::move(RHS));
1
2
3
4
5
6
7

在实现 Paeser 前，我们先定义如下函数，方便后续处理：

// CurTok/getNextToken - 提供一个 token 的 buffer.  
// CurTok 是当前 parser 正在寻找的。
// getNextToken 是从词法分析器中读取另一个 token，同时更新 CurTok
// parser 都是处理的 CurTok
static int CurTok;
static int getNextToken() {
  return CurTok = gettok();
}
1
2
3
4
5
6
7
8

下面是一个基本 helper function，用来处理一些 errors，但是多数情况会返回 null。所以没有多大作用，就是一个基本的helper 啦！

// 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;
}
1
2
3
4
5
6
7
8
9

2.3 Basic Expression Parsing: 基本表达式解析

首先，我们处理最简单的数字文本：

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
  auto Result = std::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // consume the number
  return std::move(Result);
}
1
2
3
4
5
6

上述代码意思是当前 Token 为 TOKEN_NUMBER 时，使用 g_number_val，并且创建 umberExprAST Node，然后 lexer 到下一个 Token，并且返回数值。这也是一个很好的递归下降解析器的例子：每次用完一个 Token，然后调用下一个 Token。下面利用利用括号运算来举例：

// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
    // eat (，忽略左边的括号
    GetNextToken(); 
    auto V = ParseExpression();
    // 如果表达式为空
    if (!V)
        return nullptr;
    // 如果没有右括号，报错
    if (CurTok != ')')
        return LogError("expected ')'");
    getNextToken(); // eat ).
    return V;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码注释已经讲明了代码的含义，我们这边的 LogError 函数为了简单一般就是返回 NULL。

注意，括号不会导致 AST 本身的构造，括号最重要的作用是引导解析器并且提供分组。一旦解析器构造了 AST，就不需要括号了。

接下来的例子是变量引用和函数调用：

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

通过利用是否有‘(’来判断是否是函数还是变量表达式，来构造 VariableExprAST，或者是 ExprAST。

上述已经完成了所有的简单表达式内容，接下来定义一个辅助函数，方便封装和调用，我们将此类表达式称为“基本”表达式。首先，为了解析任意表达式，我们需要确认是哪一种表达式:

// primary
//   ::= identifierexpr 关键字
//   ::= numberexpr     数字表达式
//   ::= parenexpr      括号表达式
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case TOKEN_IDENTIFIER:
    return ParseIdentifierExpr();
  case TOKEN_NUMBER:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.4 Binary Expression Parsing 解析二元表达式

二元表达式通常很难确定其表达意义，例如 :
$$x+y\times z$$
可以被解析为：
$$(x+y)\times z$$
也可以被解析为：
$$x+(y\times z)$$
显然，我们希望的表达式解析为前者。为了方便，Kaleidoscope 只支持 4 种二元操作符，分别为 ‘<’，‘+’，‘-’，‘*’。

我们利用 Operator-Precedence Parsing 使用二元运算符的优先级来选择运算顺序，首先我们先构建一个优先级表：

// BinopPrecedence - This holds the precedence for each binary operator that is
// defined.
// 利用 map 映射，确定优先级表
static std::map<char, int> BinopPrecedence;

// GetTokPrecedence - Get the precedence of the pending binary operator token.
// 得到每个二元操作符优先级
static int GetTokPrecedence() {
  // 保证 CurTok 是 ASCII 码
  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.
  ...
}
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

接下来，我们开始分析二元表达式。运算符优先级解析的基本思想是将具有歧义的二元运算符的表达式分解为多个部分。

例如表达式：a + b + (c + d) * e * f + g ,运算符优先级解析将其视为由二元运算符分隔的主表达式流。首先解析前导主表达式 a，然后将看到对 [+, b] [+, (c + d) ] [ *, e], [ *, f] 和 [+, g ]。请注意，因为括号是基础表达式，所以二元表达式解析器根本不需要担心像（c + d）这样的嵌套子表达式。

首先，一个表达式是一个主表达式，其后可能是[binop，primaryexpr]对的序列,像[+, (c + d) ]这样的对：

// expression
//   ::= primary binoprhs
//
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParsePrimary();
  if (!LHS)
    return nullptr;

  return ParseBinOpRHS(0, std::move(LHS));
}
1
2
3
4
5
6
7
8
9
10

ParseBinOpRHS 是为我们解析配对的函数，它具有一个优先级参数和一个指向当前已解析的部分的表达式的指针。注意，例如 x 这个表达式，只有一个 x，所以 **binoprhs **允许为空，将会直接返回它的表达式。在 a + b + (c + d) * e * f + g 这个例子中，代码将 a 的表达式传递到其中的 ParseBinOpRHS，当前标记为 +。

传递的优先级值 ParseBinOpRHS指示允许该函数使用的最小运算符优先级。如果当前二元运算符对是 [+ , x] ，并且 ParseBinOpRHS 以 40 的优先级传递，则它将不会删去任何 token（因为 ‘+’ 的优先级仅为20）。考虑到这一点，ParseBinOpRHS 从一下内容开始：

// binoprhs: ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // If this is a binop, find its precedence.
  // 如果是二元操作符，去查找它的优先级
  while (1) {
    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;
1
2
3
4
5
6
7
8
9
10
11
12

上述代码获取当前 token 的优先级，并与传入的优先级进行比较。因为我们将无效 token 的优先级定义为 -1，它比任何一个运算符的优先级都小，我们可以借助它来获取二元表达式结束。

若当前的 token 是运算符，我们继续：

    // 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;
1
2
3
4
5
6
7
8

BinOp 是当前二元运算符，然后解析随后的主表达式，这样就构成了整个对，例如上述 a + b + (c + d) * e * f + g 中的第一对 [+, b]。

现在，我们解析了表达式的左侧和一对 RHS 序列，现在我们必须确定表达式关联的方式。特别是，我们可以设置为 (a + b) binop unparsed 或 a + (b binop unparsed)。为了确定这一点，我们先看 binop 以确定其优先级，并将其与之前 binop 的优先级（在本例中为 +）进行比较：

    // 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) {
1
2
3
4

如果 RHS 右侧的binop的优先级低于或者等于当前运算符的优先级，则我们知道括号关联为 (a + b) binop unparsed 。在a + b + (c + d) * e * f + g 这个例子中，当前运算符 +，下一个运算符为 +，它们具有相同的优先级。在这种情况下，我们将为 a + b创建 AST 节点，然后继续解析：

            ... if body omitted ...
    }

    // Merge LHS/RHS.
    LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS),
                                           std::move(RHS));
  }  // loop around to the top of the while loop.
}
1
2
3
4
5
6
7
8

在上面的示例中，这会将 a + b + 变成 (a + b) 并执行循环的下一个迭代，并以 + 作为当前标记。上面的代码记录下来。接下来解析 (c + d) 作为基础表达式，这使得当前对为 [+ , (c + d)] 。然后，它将使用 ***** 作为主要对象右侧的 binop 评估上面的 if 条件，显然 ***** 的优先级高于 + 的优先级，因此将进入 if 条件语句执行。

接下来剩下的问题是，“if 语句条件下，如何完全解析右侧表达式？”特别是，要为我们示例正确构建 AST，需要将所有 (c + d) * e * f + g 作为 RHS 表达变量。

做到这一点代码如下

    // 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));
  }  // loop around to the top of the while loop.
}
1
2
3
4
5
6
7
8
9
10
11
12
13

至此，我们知道 RHS 的二进制运算符的优先级高于我们正在解析的 binop。因此，我们知道运算符优先级均高于 + 的任何对序列都应该一起解析，并作为 RHS 返回。为此，我们递归调用 ParseBinOpRHS 指定 TokPrec+1 的函数作为继续运行所需的最低优先级。在上面的示例中，这将导致它返回 (c + d) * e * f 的 AST 节点作为 RHS，然后将其设置为 + 表达式的 RHS。

最后，在 while 循环的下一次迭代中，+ g 段被解析并且添加到 AST 中，有了这段精妙代码，我们就可以正确处理了完全通用的二进制表达式的解析。

以上结束了对二元表达式的处理，此时，我们可以将解析器指向任意的 token 流，并根据 token 流构建一个表达式，并在不属于该表达式的第一个 token 处停止。

接下来，我们需要处理函数定义等。

2.5 Parsing the Rest 解析其他部分

接下来缺少的是函数处理原型。在 Kaleidoscope 中，这些用于“外部”函数声明以及函数主体定义。

执行此操作的代码简单明了：

// prototype
//   ::= id '(' id* ')'
// 函数原型
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  if (CurTok != TOKEN_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() == TOKEN_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
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

鉴于此，函数定义非常简单，只需要一个原型以及一个用于实现主体的表达式即可：

// definition ::= 'def' prototype expression
// def 定义的函数
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;
}
1
2
3
4
5
6
7
8
9
10
11

另外，我们支持 extern 来声明诸如 sin 和 cos 之类的函数，并支持用户函数的正向声明。这些 extern 只是没有主体的原型：

// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
  getNextToken();  // eat extern.
  // 函数原型
  return ParsePrototype();
}

1
2
3
4
5
6
7

最后，我们将让用户输入任意的外层表达式 (top-level expressions)，在运行的同时会计算出表达式结果。为此，我们需要处理无参数函数：

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

现在我们已经完成了所有的工作，接下来我们构建一个小驱动程序，它将使我们能够实际执行我们目前为止已经构建的代码。

2.6 The Driver 驱动程序

该驱动程序仅通过顶级调度循环调用所有解析块。这里没有什么注意的，所以我只包括顶级循环。请参考**LLVM学习入门(2)**完整代码的 “top-level expressions” 部分中的完整代码。

// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (1) {
    fprintf(stderr, "ready> ");
    switch (CurTok) {
    case TOKEN_DEF:
      return;
    case ';': // ignore top-level semicolons.
      getNextToken();
      break;
    case TOKEN_DEF:
      HandleDefinition();
      break;
    case TOKEN_EXTERN:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最有趣的部分是我们忽略了顶级分号。根本原因是，如果你在命令行键入 4 + 5 ，则解析器将不知道这是否是你想要输入的内容的结尾。例如，在下一行中，你可以输入 def foo ，在这种情况下 4 + 5 是顶级表达式的结尾。或者，你可以输入 *** 6** ,这个将继续表达式内容。使用分号可以让你知道完成输入，4 + 5; 代表完成输入。

2.7 Conclusions 小结

此篇通过不到400行的代码，我们完全定义了最简单语言，包括词法分析器，解析器和 AST 构建器。完成次操作后，可执行文件将验证 Kaleidoscope 代码，并告诉我们其语法是否无效。

例如下面的交互示例：

$ ./a.out
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> ^D
$
1
2
3
4
5
6
7
8
9
10
11
12
13

这里有很多扩展空间。我们可以定义新的 AST 节点，以多种方式扩展语言等。在下一篇：LLVM学习入门(3):生成 LLVM 中间代码 IR 中，我们将描述如果从 AST 生成 LLVM 中间表示 IR。