雪一梦 2019-06-27
由于llvm的资料比较稀缺, 所以品读官方文档就成了最佳了解llvm的方法, tutorial的整个流程目的是实现一个语法简单, 但较为完整的实现一个编译器. 而其中第一个步骤便是简单地实现一个前端parser, parser算法整个编译器流程中最为简单的一部分, 但也是整个编译器的入口(话说当时学编译原理的时候老师主要讲的就是这一部分).
tutorial中这个Parser主要分为三个部分, lexer, AST(abstract syntax tree) 与 parser主体, 代码很清晰, 我们来一部分一部分看.
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可以是数字, 变量或关键字, 识别后如果是变量或数字就返回变量名或值. 其中枚举类型列举了所有返回的类型.
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<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)) {} }; // 数组类 class CallExprAST { std::string Callee; std::vector<std::unique_ptr<ExprAST>> Args; public: CallExprAST(std::string Callee, std::vector<std::unique_ptr<ExprAST>> Args) : Callee(Callee), Args(std::move(Args)) {} }; // 函数原型类(函数名, 参数名数组) 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;} }; // 函数类(函数原型, 函数体) 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)) {} }; }
抽象语法树也比较清晰, 一个有七个类, 分别表达了从简单变量到函数的定义方法
/===---------------------------------------------------------------------------------------------===// // parser // //===---------------------------------------------------------------------------------------------===// static int CurTok; static int getNextToken() { return CurTok = gettok(); } static std::map<char,int> BinopPrecedence; /* * 返回操作符优先级 * 不吞token */ static int GetTokPrecedence() { if(!isascii(CurTok)) return -1; int TokPrec = BinopPrecedence[CurTok]; if(TokPrec <= 0) return -1; return TokPrec; } std::unique_ptr<ExprAST> LogError(const char *Str) { fprintf(stderr, "Error: %s\n", Str); return nullptr; } // PrototypeAST是ExprAST上层的一个point std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) { LogError(Str); return nullptr; } static std::unique_ptr<ExprAST> ParseExpression(); /* * 最底层函数 --- 识别数字 * 1.生成返回 * 2.下一token * 3.返回 */ static std::unique_ptr<ExprAST> ParseNumberExpr() { auto Result = llvm::make_unique<NumberExprAST>(NumVal); getNextToken(); return std::move(Result); } /* * 最底层函数 --- 识别括号体 * 1.eat '(' * 2.识别主体 * 3.找 ')' */ static std::unique_ptr<ExprAST> 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<ExprAST> ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); if(CurTok != '(') // 单标识符, 无括号 return llvm::make_unique<VariableExprAST>(IdName); getNextToken(); std::vector<std::unique_ptr<ExprAST>> 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<CallExprAST>(IdName, std::move(Args)); } /* * 识别主函数(一个expression的子部分): 标识符 或 数字 或 括号 * 不吞token */ 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(); } } /* * 返回当前LHS所在的完整表达式(对高优先级进行嵌套). * 1.当前优先级 * 2.与前一级比较 * 3.保存op * 4.找RHS * 5.下一个优先级 * 6.两个优先级比较 * 7.返回 */ static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, std::unique_ptr<ExprAST> 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<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS)); } } /* * 获取当前完整表达式 */ static std::unique_ptr<ExprAST> ParseExpression() { auto LHS = ParsePrimary(); if(!LHS) return nullptr; return ParseBinOpRHS(0, std::move(LHS)); } /* * 获取函数名及各个参数名 * 1. 函数名 * 2. eat'(' * 3. 获取各参数名 * 4. eat')' */ static std::unique_ptr<PrototypeAST> 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<std::string> ArgNames; while(getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); //判断并eat) if(CurTok != ')') return LogErrorP("Expected ')' in prototype"); getNextToken(); // 跳 ) return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames)); } /* * 函数定义 * 1. 获取函数名及参数列表(Proto) * 2. 获取函数体 */ static std::unique_ptr<FunctionAST> ParseDefinition() { // 换行 getNextToken(); // 函数proto并检测 auto Proto = ParsePrototype(); if(!Proto) return nullptr; // 函数体并检测 if(auto E = ParseExpression()) return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); return nullptr; } /* * parse函数主体 */ static std::unique_ptr<FunctionAST> ParseTopLevelExpr() { if(auto E = ParseExpression()) { auto Proto = llvm::make_unique<PrototypeAST>("__anon_expr", std::vector<std::string>()); return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); } return nullptr; } /* * 获取函数定义 */ static std::unique_ptr<PrototypeAST> 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就算简单的表达出来了