二元表达式解析

二元表达式的解析过程相对复杂，因为二元表达式会有二义性。比如，当出现x+yz，解析器可以选择(x+y)z或者x+(yz)两种解析顺序。在数学定义中，我们期望后一种解析方式，因为比+有更高的优先级。

面对优先级问题，我们可用的处理方法有很多，不过论最优雅最高效的还是要数远算符优先级分析法（Operator-Precedence Parsing）。这种解析方法借助运算符优先级来选择解析顺序，所以，起初需要一个一个优先级表格：

/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
 
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;
 
  // Make sure it's a declared binop.
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0) return -1;
  return TokPrec;
}
 
int main() {
  // Install standard binary operators.
  // 1 is lowest precedence.
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40;  // highest.
  ...
}

现在我们可以开始着手解析二元表达式了，最核心的思想方法是将可能出现二义性的表达式分解成多个部分。想一下，比如表达式a+b+(c+d)ef+g。解析器将这个字符串看做一串由二元运算符分隔的基本表达式。因此，它将先解析第一个基本表达式a，接着将解析到成对出现的[+, b] [+, (c+d)] [, e] [, f]和 [+, g]。因为括号也是基础表达式，不用担心解析器会对(c+d)出现困惑。

开始解析第一步，表达式是由第一个基础表达式和之后的一连串[运算符, 基础表达式]组成。

/// expression
///   ::= primary binoprhs
///
static ExprAST *ParseExpression() {
  ExprAST *LHS = ParsePrimary();
  if (!LHS) return 0;
 
  return ParseBinOpRHS(0, LHS);
}

ParseBinOpRHS是为我们解析运算符-表达式对的函数。它记录优先级和已解析部分的指针。

优先级数值被传入ParseBinOpRHS，凡是比这个优先级值低的运算符都不能被使用。比如如果当前的解析的是[+, x]，且目前传入的优先级值为40，那么函数就不会消耗任何token（因为"+"优先级值仅20）。因此我们函数应该这样写：

/// binoprhs
    ///   ::= ('+' primary)*
    static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
      // If this is a binop, find its precedence.
      while (1) {
        int TokPrec = GetTokPrecedence();
 
        // If this is a binop that binds at least as tightly as the current binop,
        // consume it, otherwise we are done.
        if (TokPrec < ExprPrec)
          return LHS;

这部分代码获取了当前的token的优先级值，与传入的优先级进行比较。若当前的token已经不是运算符时，我们会获得一个无效的优先级值-1，它比任何一个运算符的优先级都小，我们可以借助它来获知二元表达式已经结束。若当前的token是运算符，我们继续：

// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken();  // eat binop
 
// Parse the primary expression after the binary operator.
ExprAST *RHS = ParsePrimary();
if (!RHS) return 0;

就这样，这段代码消耗了（并记住了）二元运算符然后解析接下来的基本表达式。我们用[+, b]以及后续的运算符-表达式对作为示例来完成接下来的代码。

现在我们已知左侧的表达式和右侧的一组运算符-表达式对，我们必须决定用他们的关系是什么。比如我们可能会遇到"(a + b) 未知运算符"或者"a + (b 未知运算符)"这样的关系。为了决定这个关系，我们要依靠下一个运算符并与当前运算符优先级（在这个例子中是"+"）进行比较：

// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {

如果右侧的运算符优先级小于等于当前的运算符，我们就可以知道当前运算符的顺序是"(a + b) 运算符 …"。在我们例子里，当前的运算符是"+"且下一个运算符是"+"，我们知道他们的优先级是一样的。因此，我们为"a + b"创建AST节点，接着，继续解析：

  ... if body omitted ...
    }
 
    // Merge LHS/RHS.
    LHS = new BinaryExprAST(BinOp, LHS, RHS);
  }  // loop around to the top of the while loop.
}

在我们上面的例子里，将会将"a + b +"作为"a + b"并且进入下一个循环，处理下一个"+"。这些代码将消耗，记录，并将"(c + d)"作为基本表达式进行解析，即解析[+, (c + d)]。这时将进入上方的if语句，并比较"+"和""的优先级，因为这里的""优先级高于"+"，所以if语句将进入true分支。

现在一个关键的问题来了，那就是“上方的if语句如何完整解析剩余部分”？我们继续用上面的例子建立正确的AST树，所以我们需要得到右侧“(c + d) e f”表达式的指针。这部分代码相当简单（上面代码if的部分）：

// If BinOp binds less tightly with RHS than the operator after RHS, let
    // the pending operator take RHS as its LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec+1, RHS);
      if (RHS == 0) return 0;
    }
    // Merge LHS/RHS.
    LHS = new BinaryExprAST(BinOp, LHS, RHS);
  }  // loop around to the top of the while loop.
}

至此，我们知道右侧的二元运算符优先级应当高于当前的运算符。所以，任意拥有比“+”更高优先级的运算符-表达式对应当作为RHS变量返回。因此我们递归调用ParseBinOpRHS函数，并特别地将当前的优先级值加一，即"TokPrec + 1"。在我们以上的例子中，“(c+d)ef”将作为AST节点返回到RHS。

最后，在最后一个循环中解析完毕"+ g"部分。至此，我们用这一点点代码（14行不记空行和注视的代码）成功地以一种优雅的方式解析完了整个二元表达式。由于篇幅有限，也许有一些部分你还存在不解，我希望你能对这些代码多进行一下实验，以便熟悉它的工作原理，扫清困惑。

目前，我们仅仅完成对表达式的解析，下一步我们要进一步完善语法。