In this recipe, you will learn how to parse a binary expression.
We must have the custom-defined language—that is, the toy language in this case—and also stream of tokens generated by lexer. The binary expression parser requires precedence of binary operators for determining LHS and RHS in order. An STL map can be used to define precedence of binary operators.
To parse a binary expression, proceed with the following code flow:
toy.cpp
file as follows:$ vi toy.cpp
map
for operator precedence to store the precedence at global scope in the toy.cpp
file as follows:static std::map<char, int>Operator_Precedence;
The TOY language for demonstration has 4 operators where precedence of operators is defined as -
< +
< /
< *
.
map
—can be defined in global scope in the toy.cpp
file as follows:static void init_precedence() { Operator_Precedence['-'] = 1; Operator_Precedence['+'] = 2; Operator_Precedence['/'] = 3; Operator_Precedence['*'] = 4; }
static int getBinOpPrecedence() { if(!isascii(Current_token)) return -1; int TokPrec = Operator_Precedence[Current_token]; if(TokPrec <= 0) return -1; return TokPrec; }
binary
operator parser can be defined as follows:static BaseAST* binary_op_parser(int Old_Prec, BaseAST *LHS) { while(1) { int Operator_Prec = getBinOpPrecedence(); if(Operator_Prec < Old_Prec) return LHS; int BinOp = Current_token; next_token(); BaseAST* RHS = Base_Parser(); if(!RHS) return 0; int Next_Prec = getBinOpPrecedence(); if(Operator_Prec < Next_Prec) { RHS = binary_op_parser(Operator_Prec+1, RHS); if(RHS == 0) return 0; } LHS = new BinaryAST(std::to_string(BinOp), LHS, RHS); } }
Here, precedence of current operator is checked with the precedence of old operator, and the outcome is decided according to LHS and RHS of binary operators. Note that the binary operator parser is recursively called since the RHS can be an expression and not just a single identifier.
parser
function for parenthesis can be defined as follows:static BaseAST* paran_parser() { next_token(); BaseAST* V = expression_parser(); if (!V) return 0; if(Current_token != ')') return 0; return V; }
parser
functions can be defined as follows:static void HandleDefn() { if (FunctionDefnAST *F = func_defn_parser()) { if(Function* LF = F->Codegen()) { } } else { next_token(); } } static void HandleTopExpression() { if(FunctionDefnAST *F = top_level_parser()) { if(Function *LF = F->Codegen()) { } } else { next_token(); } }
18.188.218.226