LLVM极简教程：第⼆章实现语法分析器和AST
第⼆章实现语法分析器和AST
原⽂:Implementing a Parr and AST
本章简介
欢迎进⼊“⽤LLVM开发新语⾔”教程的第⼆章。在本章中，我们将以第⼀章中开发的词法分析器为基础，为Kaleidoscope语⾔开发⼀个完整的语法解析器。搞定语法解析器之后，我们就开始定义并构造抽象语法树（AST，Abstract Syntax Tree）。
在解析Kaleidoscope的语法时，我们将综合运⽤递归下降解析和运算符优先级解析两种技术（后者⽤于解析⼆元表达式，前者⽤于其他部分）。正式开始解析之前，不妨先来看⼀看解析器的输出：抽象语法树。
抽象语法树（AST）
抽象语法树的作⽤在于牢牢抓住程序的脉络，从⽽⽅便编译过程的后续环节（如代码⽣成）对程序进⾏解读。AST就是开发者为语⾔量⾝定制的⼀套模型，基本上语⾔中的每种结构都与⼀种AST对象相对应。Kaleidoscope语⾔中的语法结构包括表达式、函数原型和函数对象。我们不妨先从表达式⼊⼿：
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Par Tree)
//===----------------------------------------------------------------------===//
/// ExprAST - Ba 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;
ExprAST *LHS, *RHS;
public:
BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
: Op(op), LHS(lhs), RHS(rhs) {}
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<ExprAST*> Args;
public:
CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
: Callee(callee), Args(args) {}
};
我们（特意）将这⼏个类设计得简单明了：VariableExprAST⽤于保存变量名，BinaryExprAST⽤于保存运算符
（如“+”），CallExprAST⽤于保存函数名和⽤作参数的表达式列表。这样设计AST有⼀个优势，那就是我们⽆须关注语法便可直接抓住语⾔本⾝的特性。注意这⾥还没有涉及到⼆元运算符的优先级和词法结构等问题。
定义完毕这⼏种表达式节点，就⾜以描述Kaleidoscope语⾔中的⼏个最基本的结构了。由于我们还没有实现条件控制流程，它还不算图灵完备；后续还会加以完善。接下来，还有两种结构需要描述，即函数的接⼝和函数本⾝：
/// PrototypeAST - This class reprents 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, const std::vector<std::string> &args)
: Name(name), Args(args) {}
};
/// FunctionAST - This class reprents a function definition itlf.
class FunctionAST {
PrototypeAST *Proto;
ExprAST *Body;
public:
FunctionAST(PrototypeAST *proto, ExprAST *body)
: Proto(proto), Body(body) {}
};
在Kaleidoscope中，函数的类型是由参数的个数决定的。由于所有的值都是双精度浮点数，没有必要保存参数的类型。在更强⼤、更实⽤的语⾔中，ExprAST类多半还会需要⼀个类型字段。
有了这些作为基础，我们就可以开始解析Kaleidoscope的表达式和函数体了。
语法解析器基础
开始构造AST之前，先要准备好⽤于构造AST的语法解析器。说⽩了，就是要利⽤语法解析器把“x+y”这样的输⼊（由词法分析器返回的三个语元）分解成由下列代码⽣成的AST：
ExprAST *X = new VariableExprAST("x");
ExprAST *Y = new VariableExprAST("y");
ExprAST *Result = new BinaryExprAST('+', X, Y);
为此，我们先定义⼏个辅助函数：
wps替换
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parr 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视作当前待解析的语元。
/// Error* - The are little helper functions for error handling.
ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
这三个⽤于报错的辅助函数也很简单，我们的语法解析器将⽤它们来处理解析过程中发⽣的错误。这⾥采⽤的错误恢复策略并不妥当，对⽤户也不怎么友好，但对于教程⽽⾔也就够⽤了。⽰例代码中各个函数的返回值类型各不相同，有了这⼏个函数，错误处理就简单了：它们的返回值统统是NULL。
准备好这⼏个辅助函数之后，我们就开始实现第⼀条语法规则：数值常量。
解析基本表达式
之所以先从数值常量下⼿，是因为它最简单。Kaleidoscope语法中的每⼀条⽣成规则（production），都需要⼀个对应的解析函数。对于数值常量，就是：
/// numberexpr ::= number
static ExprAST *ParNumberExpr() {
ExprAST *Result = new NumberExprAST(NumVal);
getNextToken(); // consume the number
return Result;
}
这个函数很简单：调⽤它的时候，当前待解析语元只能是tok_number。该函数⽤刚解析出的数值构造出了⼀个NumberExprAST节点，然后令词法分析器继续读取下⼀个语元，最后返回构造的AST节点。
这⾥有⼏处很有意思，其中最显著的便是该函数的⾏为，它不仅消化了所有与当前⽣成规则相关的所有语元，还把下⼀个待解析的语元放进了词法分析器的语元缓冲（该语元与当前的⽣成规则⽆关）。这是⾮常标准的递归下降解析器的⾏为。下⾯这个括号运算符的例⼦更能说明问题：
/// parenexpr ::= '(' expression ')'
static ExprAST *ParParenExpr() {
getNextToken(); // eat (.
ExprAST *V = ParExpression();
if (!V) return 0;
if (CurTok != ')')
return Error("expected ')'");
getNextToken(); // eat ).
return V;
}
该函数体现了这个语法解析器的⼏个特点：
1. 它展⽰了Error函数的⽤法。调⽤该函数时，待解析的语元只能是“(”，然⽽解析完⼦表达式之后，紧跟着的语元却不⼀定是“)”。
⽐如，要是⽤户输⼊的是“(4 x”⽽不是“(4)”，语法解析器就应该报错。既然错误时有发⽣，语法解析器就必须提供⼀条报告错误的途径：就这个语法解析器⽽⾔，应对之道就是返回NULL。
2. 该函数的另⼀特点在于递归调⽤了ParExpression（很快我们就会看到ParExpression还会反过来调⽤ParParenExpr）。这种⼿
法简化了递归语法的处理，每⼀条⽣成规则的实现都得以变得⾮常简洁。需要注意的是，我们没有必要为括号构造AST节点。虽然这么做也没错，但括号的作⽤主要还是对表达式进⾏分组进⽽引导语法解析过程。当语法解析器构造完AST之后，括号就没⽤了。
下⼀条⽣成规则也很简单，它负责处理变量引⽤和函数调⽤：
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static ExprAST *ParIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return new VariableExprAST(IdName);
// Call.
getNextToken(); // eat (沟通的名词解释
虽有嘉肴std::vector<ExprAST*> Args;
if (CurTok != ')') {
while (1) {
ExprAST *Arg = ParExpression();
二年级乘法口诀表
if (!Arg) return 0;
Args.push_back(Arg);
if (CurTok == ')') break;
if (CurTok != ',')
return Error("Expected ')' or ',' in argument list");
getNextToken();
}
}
该函数与其它函数的风格别⽆⼆致。（调⽤该函数时当前语元必须是tok_identifier。）前⽂提到的有关递归和错误处理的特点它统统具备。有意思的是这⾥采⽤了预读（lookahead）的⼿段来试探当前标识符的类型，判断它究竟是个独⽴的变量引⽤还是个函数调⽤。只要检查紧跟标识符之后的语元是不是“(”，它就能知道到底应该构造VariableExprAST节点还是CallExprAST节点。
现在，解析各种表达式的代码都已经完成，不妨再添加⼀个辅助函数，为它们梳理⼀个统⼀的⼊⼝。我们将上述表达式称为主表达式（primary expression），具体原因参见本教程的后续章节。在解析各种主表达式时，我们⾸先要判定待解析表达式的类别：
/// primary
/// ::= identifierexpr
/// ::= numberexpr
字典英语
/// ::= parenexpr
static ExprAST *ParPrimary() {
switch (CurTok) {
default: return Error("unknown token when expecting an expression");
ca tok_identifier: return ParIdentifierExpr();
ca tok_number: return ParNumberExpr();
遮瑕膏哪个牌子好ca '(': return ParParenExpr();
}
}
看完这个函数的定义，你就能明⽩为什么先前的各个函数能够放⼼⼤胆地对CurTok的取值作出假设了。这⾥预读了下⼀个语元，预先对待解析表达式的类型作出了判断，然后才调⽤相应的函数进⾏解析。
基本表达式全都搞定了，下⾯开始开始着⼿解析更为复杂的⼆元表达式。
解析⼆元表达式
⼆元表达式的解析难度要⼤得多，因为它们往往具有⼆义性。例如，给定字符串“x+y*z”，语法解析器既可以将之解析为“(x+y)*z”，也可以将之解析为“x+(y*z)”。按照通常的数学定义，我们期望解析成后者，因为“*”（乘法）的优先级要⾼于“+”（加法）。
基业长青读后感这个问题的解法很多，其中属运算符优先级解析最为优雅和⾼效。这是⼀种利⽤⼆元运算符的优先级来引导递归调⽤⾛向的解析技术。⾸先，我们需要制定⼀张优先级表：
