Parsing binary expressions

In this recipe, you will learn how to parse a binary expression.

Getting ready

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.

How to do it…

To parse a binary expression, proceed with the following code flow:

  1. Open the toy.cpp file as follows:
    $ vi toy.cpp
  2. Declare a 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 -< + < / < *.

  3. A function to initialize precedence—that is, to store precedence value in 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;
}
  4. A helper function to return precedence of binary operator can be defined as follows:
    static int getBinOpPrecedence() {
  if(!isascii(Current_token))
return -1;
  
  int TokPrec = Operator_Precedence[Current_token];
  if(TokPrec <= 0) return -1;
  return TokPrec;
}
  5. Now, the 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.

  6. A 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;
}
  7. Some top-level functions acting as wrappers around these 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();
  }
}

See also

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.145.52.188