2. Kaleidoscope: 实现解析器和 AST¶
2.1. 第 2 章 介绍¶
欢迎来到“使用 LLVM 实现语言”教程的第 2 章。本章向您展示如何使用在第 1 章中构建的词法分析器，为我们的 Kaleidoscope 语言构建完整的解析器。一旦我们有了解析器，我们将定义并构建一个抽象语法树 (AST)。
我们将构建的解析器使用递归下降解析和运算符优先级解析的组合来解析 Kaleidoscope 语言（后者用于二元表达式，前者用于所有其他内容）。但在我们开始解析之前，让我们先讨论解析器的输出：抽象语法树。
2.2. 抽象语法树 (AST)¶
程序的 AST 以一种易于编译器后续阶段（例如，代码生成）解释的方式捕获其行为。我们基本上希望语言中的每个构造都有一个对象，并且 AST 应该紧密地模拟该语言。在 Kaleidoscope 中，我们有表达式、原型和函数对象。我们将首先从表达式开始
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
};
上面的代码显示了基类 ExprAST 和一个子类（我们用于数字字面量）的定义。关于这段代码，需要注意的重要一点是 NumberExprAST 类将字面量的数值捕获为实例变量。这允许编译器的后续阶段知道存储的数值是多少。
现在我们只创建 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)) {}
};
这一切都（有意地）相当简单：变量捕获变量名，二元运算符捕获其操作码（例如“+”），函数调用捕获函数名以及任何参数表达式的列表。关于我们的 AST，一件很棒的事情是它在不谈论语言语法的情况下捕获了语言特性。请注意，没有讨论二元运算符的优先级、词法结构等。
对于我们的基本语言，这些是我们将定义的所有表达式节点。因为它没有条件控制流，所以它不是图灵完备的；我们将在以后的版本中修复这个问题。接下来我们需要做的两件事是讨论函数的接口的方式，以及讨论函数本身的方式
/// 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 中解析表达式和函数体。
2.3. 解析器基础知识¶
现在我们有了一个要构建的 AST，我们需要定义解析器代码来构建它。这里的想法是，我们想将类似“x+y”（词法分析器将其作为三个标记返回）的内容解析为可以使用如下调用生成的 AST
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));
为了做到这一点，我们将首先定义一些基本辅助例程
/// 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();
}
这实现了围绕词法分析器的简单标记缓冲区。这允许我们向前看一个标记，了解词法分析器返回的内容。我们解析器中的每个函数都将假定 CurTok 是需要解析的当前标记。
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
LogError 例程是简单的辅助例程，我们的解析器将使用它们来处理错误。我们的解析器中的错误恢复不会是最好的，也不是特别用户友好，但对于我们的教程来说已经足够了。这些例程使得在具有各种返回类型的例程中处理错误变得更容易：它们总是返回 null。
有了这些基本辅助函数，我们可以实现我们语法的第一个部分：数字字面量。
2.4. 基本表达式解析¶
我们从数字字面量开始，因为它们是最容易处理的。对于我们语法中的每个产生式，我们将定义一个解析该产生式的函数。对于数字字面量，我们有
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
这个例程非常简单：它期望在当前标记是 tok_number 标记时被调用。它获取当前数字值，创建一个 NumberExprAST 节点，将词法分析器前进到下一个标记，最后返回。
这里有一些有趣的方面。最重要的一点是，这个例程会消耗与产生式对应的所有标记，并返回词法分析器缓冲区，其中包含下一个标记（不属于语法产生式），准备就绪。这对于递归下降解析器来说是一种相当标准的方法。为了更好地示例，括号运算符定义如下
/// 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;
}
此函数说明了解析器的一些有趣之处
1) 它展示了我们如何使用 LogError 例程。当调用时，此函数期望当前标记是“（”标记，但在解析子表达式后，可能没有“）”在等待。例如，如果用户输入“(4 x”而不是“(4)”，则解析器应发出错误。由于可能会发生错误，因此解析器需要一种指示错误发生的方式：在我们的解析器中，我们在错误时返回 null。
2) 此函数的另一个有趣方面是它通过调用 ParseExpression 来使用递归（我们很快就会看到 ParseExpression 可以调用 ParseParenExpr）。这很强大，因为它允许我们处理递归语法，并使每个产生式都非常简单。请注意，括号本身不会导致 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 (true) {
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));
}
此例程遵循与其他例程相同的样式。（它期望在当前标记是 tok_identifier 标记时被调用）。它还具有递归和错误处理。其中一个有趣的方面是它使用前瞻来确定当前标识符是独立的变量引用还是函数调用表达式。它通过检查标识符之后的标记是否为“（”标记来处理此问题，并根据需要构造 VariableExprAST 或 CallExprAST 节点。
现在我们已经完成了所有简单的表达式解析逻辑，我们可以定义一个辅助函数将其包装在一起成为一个入口点。我们将这类表达式称为“primary”表达式，原因将在本教程的后面变得更加清楚。为了解析任意 primary 表达式，我们需要确定它是什么类型的表达式
/// 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();
}
}
现在您看到了此函数的定义，就更清楚为什么我们可以假设各种函数中 CurTok 的状态。这使用前瞻来确定正在检查的表达式类型，然后使用函数调用对其进行解析。
现在基本表达式已处理完毕，我们需要处理二元表达式。它们有点复杂。
2.5. 二元表达式解析¶
二元表达式的解析难度明显更高，因为它们通常是模棱两可的。例如，给定字符串“x+y*z”，解析器可以选择将其解析为“(x+y)*z”或“x+(y*z)”。根据数学中的常用定义，我们期望后一种解析，因为“*”（乘法）的优先级高于“+”（加法）。
有很多方法可以处理这个问题，但一种优雅而有效的方法是使用运算符优先级解析。这种解析技术使用二元运算符的优先级来指导递归。首先，我们需要一个优先级表
/// 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 函数返回当前标记的优先级，如果标记不是二元运算符，则返回 -1。拥有一个映射可以轻松添加新运算符，并清楚地表明该算法不依赖于所涉及的特定运算符，但是消除映射并在 GetTokPrecedence 函数中进行比较也很容易。（或者只是使用固定大小的数组）。
定义了上面的助手后，我们现在可以开始解析二元表达式。运算符优先级解析的基本思想是将具有潜在歧义的二元运算符的表达式分解为多个部分。例如，考虑表达式“a+b+(c+d)*e*f+g”。运算符优先级解析将其视为由二元运算符分隔的 primary 表达式流。因此，它将首先解析前导 primary 表达式“a”，然后它将看到 [+, b] [+, (c+d)] [*, e] [*, f] 和 [+, g] 对。请注意，由于括号是 primary 表达式，因此二元表达式解析器根本不需要担心像 (c+d) 这样的嵌套子表达式。
首先，表达式是一个 primary 表达式，可能后跟一系列 [binop,primaryexpr] 对
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
ParseBinOpRHS 是为我们解析对序列的函数。它接受一个优先级和一个指向表达式的指针，该表达式指向到目前为止已解析的部分。请注意，“x”是一个完全有效的表达式：因此，“binoprhs”可以为空，在这种情况下，它返回传递给它的表达式。在上面的示例中，代码将“a”的表达式传递给 ParseBinOpRHS，当前标记为“+”。
传递到 ParseBinOpRHS 的优先级值指示函数允许消耗的最小运算符优先级。例如，如果当前对流是 [+, x] 并且 ParseBinOpRHS 以优先级 40 传递，它将不消耗任何标记（因为“+”的优先级仅为 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 (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;
这段代码获取当前标记的优先级，并检查它是否太低。由于我们将无效标记定义为优先级为 -1，因此此检查隐式地知道当标记流用完二元运算符时，对流结束。如果此检查成功，我们知道该标记是二元运算符，并且它将包含在此表达式中
// 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;
因此，这段代码消耗（并记住）二元运算符，然后解析随后的 primary 表达式。这构建了整个对，第一个对是运行示例的 [+, 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) {
如果“RHS”右侧的 binop 的优先级低于或等于我们当前运算符的优先级，那么我们知道括号关联为“(a+b) binop …”。在我们的示例中，当前运算符是“+”，下一个运算符是“+”，我们知道它们的优先级相同。在这种情况下，我们将为“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.
}
在上面的示例中，这将把“a+b+”变成“(a+b)”，并执行循环的下一次迭代，其中“+”作为当前标记。上面的代码将消耗、记住并解析“(c+d)”作为 primary 表达式，这使得当前对等于 [+, (c+d)]。然后，它将评估上面的“if”条件，其中“*”作为 primary 右侧的 binop。在这种情况下，“*”的优先级高于“+”的优先级，因此将输入 if 条件。
这里剩下的关键问题是“if 条件如何完整地解析右侧”？特别是，为了为我们的示例正确构建 AST，它需要获取“(c+d)*e*f”的所有内容作为 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.
}
此时，我们知道 primary 的 RHS 的二元运算符的优先级高于我们当前正在解析的 binop。因此，我们知道任何运算符优先级都高于“+”的对序列都应一起解析并作为“RHS”返回。为此，我们递归调用 ParseBinOpRHS 函数，指定“TokPrec+1”作为它继续所需的最小优先级。在上面的示例中，这将导致它返回“(c+d)*e*f”的 AST 节点作为 RHS，然后将其设置为“+”表达式的 RHS。
最后，在 while 循环的下一次迭代中，解析“+g”部分并将其添加到 AST。有了这段少量的代码（14 行非平凡的代码），我们就以非常优雅的方式正确处理了完全通用的二元表达式解析。这是对这段代码的旋风式巡视，它有点微妙。我建议通过一些棘手的示例来运行它，以了解它的工作原理。
这结束了表达式的处理。此时，我们可以将解析器指向任意标记流，并从中构建表达式，在第一个不属于表达式的标记处停止。接下来我们需要处理函数定义等。
2.6. 解析剩余部分¶
接下来缺少的是函数原型的处理。在 Kaleidoscope 中，这些既用于“extern”函数声明，也用于函数体定义。执行此操作的代码很简单，而且不是很令人感兴趣（一旦您经历了表达式）
/// 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));
}
鉴于此，函数定义非常简单，只是一个原型加上一个实现主体的表达式
/// 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”来声明诸如“sin”和“cos”之类的函数，以及支持用户函数的前向声明。这些“extern”只是没有主体的原型
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
最后，我们还将允许用户键入任意顶级表达式并动态评估它们。我们将通过为它们定义匿名零元（零参数）函数来处理这个问题
/// 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;
}
现在我们有了所有部分，让我们构建一个小驱动程序，让我们可以实际执行我们构建的这段代码！
2.7. 驱动程序¶
此驱动程序只是使用顶级分发循环调用所有解析部分。这里没有太多有趣的东西，所以我只包括顶级循环。有关完整代码，请参见下面的“顶级解析”部分。
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
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;”，解析器将知道您已完成。
2.8. 结论¶
仅用不到 400 行注释代码（240 行非注释、非空白代码），我们就完全定义了我们的最小语言，包括词法分析器、解析器和 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
$
这里有很多扩展空间。您可以定义新的 AST 节点，以多种方式扩展语言等等。在下一部分中，我们将描述如何从 AST 生成 LLVM 中间表示 (IR)。
2.9. 完整代码清单¶
这是我们运行示例的完整代码清单。
# Compile
clang++ -g -O3 toy.cpp
# Run
./a.out
这是代码
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>
//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
tok_eof = -1,
// commands
tok_def = -2,
tok_extern = -3,
// primary
tok_identifier = -4,
tok_number = -5
};
static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal; // Filled in if tok_number
/// gettok - Return the next token from standard input.
static int gettok() {
static int LastChar = ' ';
// Skip any whitespace.
while (isspace(LastChar))
LastChar = getchar();
if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
IdentifierStr = LastChar;
while (isalnum((LastChar = getchar())))
IdentifierStr += LastChar;
if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
return tok_identifier;
}
if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
std::string NumStr;
do {
NumStr += LastChar;
LastChar = getchar();
} while (isdigit(LastChar) || LastChar == '.');
NumVal = strtod(NumStr.c_str(), nullptr);
return tok_number;
}
if (LastChar == '#') {
// Comment until end of line.
do
LastChar = getchar();
while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
}
// Check for end of file. Don't eat the EOF.
if (LastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
int ThisChar = LastChar;
LastChar = getchar();
return ThisChar;
}
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//
namespace {
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
};
/// 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)) {}
};
/// 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)) {}
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//
/// 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(); }
/// 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;
}
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
static std::unique_ptr<ExprAST> ParseExpression();
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
/// 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;
}
/// 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 (true) {
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));
}
/// 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();
}
}
/// 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));
}
}
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
/// 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");
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));
}
/// 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;
}
/// 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;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
//===----------------------------------------------------------------------===//
// Top-Level parsing
//===----------------------------------------------------------------------===//
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 (true) {
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;
}
}
}
//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
// Prime the first token.
fprintf(stderr, "ready> ");
getNextToken();
// Run the main "interpreter loop" now.
MainLoop();
return 0;
}