由于llvm的资料比较稀缺, 所以品读官方文档就成了最佳了解llvm的方法, tutorial的整个流程目的是实现一个语法简单, 但较为完整的实现一个编译器. 而其中第一个步骤便是简单地实现一个前端parser, parser算法整个编译器流程中最为简单的一部分, 但也是整个编译器的入口(话说当时学编译原理的时候老师主要讲的就是这一部分).
tutorial中这个Parser主要分为三个部分, lexer, AST(abstract syntax tree) 与 parser主体, 代码很清晰, 我们来一部分一部分看.
lexer
enum Token {tok_eof = -1,tok_def = -2,tok_extern = -3,tok_identifier = -4,tok_number = -5}; // 返回token类型static std::string IdentifierStr;static double NumVal;// 值标记static int gettok(){// 去空格static int Lastc = ' ';while(isspace(Lastc)) Lastc = getchar();// 判断标识符if(isalpha(Lastc)) { IdentifierStr = Lastc; while(isalnum(Lastc = getchar())) IdentifierStr += Lastc; if(IdentifierStr == "def") return tok_def; if(IdentifierStr == "extern") return tok_extern; return tok_identifier; }// 判断数字if(isdigit(Lastc) || Lastc == '.') { std::string Numstr; do { Numstr += Lastc; Lastc = getchar(); }while(isdigit(Lastc) || Lastc == '.'); NumVal = strtod(Numstr.c_str(), nullptr); return tok_number; }// 判断注释if(Lastc == '#') { do Lastc = getchar(); while(Lastc != EOF || Lastc != '\n' || Lastc != '\r'); if(Lastc != EOF) return gettok(); }// 判断结尾if(Lastc == EOF) return tok_eof;// 判断特殊字符(';', '(', ')', ',')int Thischar = Lastc;Lastc = getchar();return Thischar;} 这个lexer的目的十分清楚, 识别token, 这个token可以是数字, 变量或关键字, 识别后如果是变量或数字就返回变量名或值. 其中枚举类型列举了所有返回的类型.
AST
namespace { class ExprAST { public: virtual ~ExprAST() = default; }; // 数值类 class NumberExprAST : public ExprAST{ double Val; public: NumberExprAST(double Val) : Val(Val) {} };// 简单变量类 class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &Name) : Name(Name) {} };// 运算表达式类 class BinaryExprAST { char Op; std::unique_ptr LHS, RHS; public: BinaryExprAST(char Op, std::unique_ptr LHS, std::unique_ptr RHS) : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {} }; // 数组类 class CallExprAST { std::string Callee; std::vector > Args; public: CallExprAST(std::string Callee, std::vector > Args) : Callee(Callee), Args(std::move(Args)) {} };// 函数原型类(函数名, 参数名数组) class PrototypeAST { std::string Name; std::vector Args; public: PrototypeAST(const std::string &Name, std::vector Args) : Name(Name), Args(std::move(Args)) {} const std::string &getName() const {return Name;} };// 函数类(函数原型, 函数体) class FunctionAST { std::unique_ptr Proto; std::unique_ptr Body; public: FunctionAST(std::unique_ptr Proto, std::unique_ptr Body) : Proto(std::move(Proto)), Body(std::move(Body)) {} };} 抽象语法树也比较清晰, 一个有七个类, 分别表达了从简单变量到函数的定义方法
Parser
/===---------------------------------------------------------------------------------------------===//// parser ////===---------------------------------------------------------------------------------------------===//static int CurTok;static int getNextToken() { return CurTok = gettok(); }static std::map BinopPrecedence;/* * 返回操作符优先级 * 不吞token */static int GetTokPrecedence() { if(!isascii(CurTok)) return -1; int TokPrec = BinopPrecedence[CurTok]; if(TokPrec <= 0) return -1; return TokPrec;}std::unique_ptr LogError(const char *Str) { fprintf(stderr, "Error: %s\n", Str); return nullptr;}// PrototypeAST是ExprAST上层的一个pointstd::unique_ptr LogErrorP(const char *Str) { LogError(Str); return nullptr;}static std::unique_ptr ParseExpression();/* * 最底层函数 --- 识别数字 * 1.生成返回 * 2.下一token * 3.返回 */static std::unique_ptr ParseNumberExpr() { auto Result = llvm::make_unique (NumVal); getNextToken(); return std::move(Result);}/* * 最底层函数 --- 识别括号体 * 1.eat '(' * 2.识别主体 * 3.找 ')' */static std::unique_ptr ParseParenExpr() { getNextToken(); auto V = ParseExpression(); if (!V) return nullptr; if(CurTok != ')') return LogError("expected ')'"); getNextToken(); return V;}/* * 最底层函数 --- 识别标识符 // 单个 或 数组类型 * 1.判断'(' * 2.判断')' * 3.while,push进vector * 4.判断')'与',' * 5.eat')' * 6.返回 */static std::unique_ptr ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); if(CurTok != '(') // 单标识符, 无括号 return llvm::make_unique (IdName); getNextToken(); std::vector > Args; if(CurTok != ')') { while(true) { if(auto Arg = ParseExpression()) Args.push_back(std::move(Arg)); else return nullptr; // (a,b, null if(CurTok == ')') break; if(CurTok != ',') return LogError("Expected ')' or ',' in argument list"); // 标识符支持',', 参数列表不支持',' getNextToken(); // eat ',' } } getNextToken(); return llvm::make_unique (IdName, std::move(Args));}/* * 识别主函数(一个expression的子部分): 标识符 或 数字 或 括号 * 不吞token */static std::unique_ptr 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(); }}/* * 返回当前LHS所在的完整表达式(对高优先级进行嵌套). * 1.当前优先级 * 2.与前一级比较 * 3.保存op * 4.找RHS * 5.下一个优先级 * 6.两个优先级比较 * 7.返回 */static std::unique_ptr ParseBinOpRHS(int ExprPrec, std::unique_ptr LHS) { while(true) { // 优先级 int TokPrec = GetTokPrecedence(); if(TokPrec < ExprPrec) return LHS; // 标识符 int BinOp = CurTok; getNextToken(); // RHS auto RHS = ParsePrimary(); if(!RHS) return nullptr; int NextPrec = GetTokPrecedence(); if(TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS)); if(!RHS) return nullptr; } //merge LHS/RHS LHS = llvm::make_unique (BinOp, std::move(LHS), std::move(RHS)); }}/* * 获取当前完整表达式 */static std::unique_ptr ParseExpression() { auto LHS = ParsePrimary(); if(!LHS) return nullptr; return ParseBinOpRHS(0, std::move(LHS));}/* * 获取函数名及各个参数名 * 1. 函数名 * 2. eat'(' * 3. 获取各参数名 * 4. eat')' */static std::unique_ptr ParsePrototype() { // 判断名字并存名字 if(CurTok != tok_identifier) return LogErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; // 判断( getNextToken(); // eat ( if(CurTok != '(') return LogErrorP("Expected '(' in prototype"); // 存参数 std::vector ArgNames; while(getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); //判断并eat) if(CurTok != ')') return LogErrorP("Expected ')' in prototype"); getNextToken(); // 跳 ) return llvm::make_unique (FnName, std::move(ArgNames));}/* * 函数定义 * 1. 获取函数名及参数列表(Proto) * 2. 获取函数体 */static std::unique_ptr ParseDefinition() { // 换行 getNextToken(); // 函数proto并检测 auto Proto = ParsePrototype(); if(!Proto) return nullptr; // 函数体并检测 if(auto E = ParseExpression()) return llvm::make_unique (std::move(Proto), std::move(E)); return nullptr;}/* * parse函数主体 */static std::unique_ptr ParseTopLevelExpr() { if(auto E = ParseExpression()) { auto Proto = llvm::make_unique ("__anon_expr", std::vector ()); return llvm::make_unique (std::move(Proto), std::move(E)); } return nullptr;}/* * 获取函数定义 */static std::unique_ptr ParseExtern() { getNextToken(); return ParsePrototype();}/* * 子层parse都会提前getToken(); *///===----------------------------===//// 顶层parse//===----------------------------===///* * parse定义 */static void HandleDefinition() { if(ParseDefinition()) { fprintf(stderr, "Parsed a function definition.\n"); }else{ getNextToken(); }}static void HandleExtern() { if(ParseExtern()) { fprintf(stderr, "Parsed an extern\n"); }else{ getNextToken(); }}static void HandleTopLevelExpression() { if(ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top_level expr.\n"); }else{ getNextToken(); }}/* * 判断当前token性质 * 1. EOF ---> 返回 * 2. ; ---> 下一个token * 3. def ---> HandleDefinition() * 4. extern ---> HandleExtern() */static void MainLoop() { while(true) { fprintf(stderr, "ready> "); switch(CurTok) { case tok_eof: return; case ';': getNextToken(); break; case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } }} 其中最多的,同时逻辑也较为复杂的就是这个parser
我画了一张各个函数之间的调用关系
这样一整个parser就算简单的表达出来了