2. 万花筒：实现解析器和 AST¶
2.1. 第 2 章 简介¶
欢迎来到“使用 LLVM 实现语言”教程的第 2 章。本章将向您展示如何使用在第 1 章中构建的词法分析器，为我们的万花筒语言构建一个完整的解析器。一旦我们有了解析器，我们将定义并构建一个抽象语法树 (AST)。
我们将构建的解析器使用递归下降解析和运算符优先级解析的组合来解析万花筒语言（后者用于二元表达式，前者用于其他所有内容）。但在我们开始解析之前，让我们先谈谈解析器的输出：抽象语法树。
2.2. 抽象语法树 (AST)¶
程序的 AST 以一种易于编译器后续阶段（例如代码生成）解释的方式捕获其行为。我们基本上希望为语言中的每个构造创建一个对象，并且 AST 应该与语言紧密建模。在万花筒中，我们有表达式、原型和函数对象。我们先从表达式开始
/// 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，所以它们没有任何有用的访问器方法。例如，添加一个虚拟方法来漂亮地打印代码是非常容易的。以下是我们将在万花筒语言的基本形式中使用的其他表达式 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)) {}
};
在万花筒中，函数的类型仅与其参数的数量相关。由于所有值都是双精度浮点数，因此每个参数的类型不需要存储在任何地方。在一个更积极和现实的语言中，“ExprAST”类可能会有一个类型字段。
有了这个脚手架，我们现在就可以讨论在万花筒中解析表达式和函数体了。
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
/// ::= 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.
...
}
对于万花筒的基本形式，我们只支持 4 个二元运算符（当然，您可以扩展它，我们勇敢而无畏的读者）。 GetTokPrecedence 函数返回当前标记的优先级，如果标记不是二元运算符，则返回 -1。使用映射可以轻松添加新运算符，并清楚地表明算法不依赖于所涉及的特定运算符，但可以很容易地消除映射并在 GetTokPrecedence 函数中进行比较。（或者只使用固定大小的数组）。
在定义了上述辅助函数后，我们现在可以开始解析二元表达式了。操作符优先级解析的基本思想是将可能包含歧义二元操作符的表达式分解成多个部分。例如，考虑表达式“a+b+(c+d)*e*f+g”。操作符优先级解析将其视为由二元操作符分隔的一系列基本表达式。因此，它将首先解析最前面的基本表达式“a”，然后它将看到对 [+, b] [+, (c+d)] [*, e] [*, f] 和 [+, g]。请注意，因为括号是基本表达式，所以二元表达式解析器根本不需要担心像 (c+d) 这样的嵌套子表达式。
首先，表达式是一个基本表达式，后面可能跟着一系列 [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;
因此，此代码“消耗”（并记住）二元操作符，然后解析其后的基本表达式。这构建了整个对，第一个对对于正在运行的示例是 [+, b]。
现在我们已经解析了表达式的左侧和 RHS 序列的一对，我们必须决定表达式的结合方式。特别是，我们可能有“(a+b) binop 未解析”或“a + (b binop 未解析)”。为了确定这一点，我们向前查看“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)”作为基本表达式，这使得当前对等于 [+, (c+d)]。然后，它将使用“*”作为“primary”右侧的 binop 来评估上面的“if”条件。在这种情况下，“*”的优先级高于“+”的优先级，因此将进入“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.
}
此时，我们知道基本表达式 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;
}