LLVMによるプログラミング言語の実装チュートリアル日本語訳
第2章 万華鏡: 構文解析器とASTの実装
第5節 二項演算式（binary expression）の構文解析

訳注: 以前も同じような事を書いたが、binary expressionはコンパイラ界隈では結構一般的な用語だと思うけど、適当な日本語訳が無いっぽいので、ここではとりあえず（二項演算子 binary operatorと区別するためにも）二項演算式と訳す。

二項演算式は構文解析するのがかなり難しい。
なぜなら、二項演算式はしばしば複数の意味を持つからである。
例えば、”x+y*z”という文字列が与えられたとき、構文解析器は”(x+y)*z”と”x+(y*z)”のどちらかとして解釈することが出来る。
一般的な数学の定義から、我々は後者として解釈されることを期待する。
なぜなら”*”（掛け算）は”+”（足し算）より高い優先度を持つからである。

これを処理する方法はいくつかあるが、効率的でエレガントなのは演算子順位構文解析法（Operator-Precedence Parsing）を用いることである。
この構文解析法は、再帰的にうまく処理するために、二項演算子の優先順位を用いる。
これを実装するために、まず優先順位のテーブルが必要となる。

/// BinopPrecedence - 定義された各二項演算子の優先順位を保持する。
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - 処理中の二項演算子トークンの優先順位を得る。
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // 定義済みの二項演算子でなければ-1を返す。
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0) return -1;
  return TokPrec;
}

int main() {
  // 標準的な二項演算子を登録する。
  // 1が一番低い優先順位である。
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40;  // 優先度 高.
  ...
}

万華鏡の原型として、4つの二項演算子のみをサポートする。
（勇敢かつ大胆な読者なら、もちろんこれ拡張することが出来る。）
GetTokPrecedence関数は現在のトークンの優先順位を返す。もしくは現在のトークンが二項演算子でなければ-1を返す。
マップ（BinopPrecedence変数）を持つことによって、新しい演算子を追加するのが楽になるし、アルゴリズムが特定の演算子に依存しない事が明らかになる。
しかし、マップを使わずにGetTokPrecedence関数の中で比較を行うのは十分に簡単である。（あるいは固定サイズの配列を使用するとか。）

上で定義したヘルパー関数によって、二項演算式の構文解析を開始出来るようになった。
演算子順位構文解析法の基本的なアイデアは、潜在的に複数の意味を持つ二項演算子をバラバラに分割する事である。
例えば、“a+b+(c+d)*e*f+g”という式について考えていこう。
演算子順位構文解析法ではこれを、二項演算子で区切られたプライマリ式の連なりとして考える。
そうすると、まず先頭のプライマリ式である”a”が解析される。
そしたら残りは[+, b]と[+, (c+d)]と[*, e]と[*, f]と[+, g]のペアとなる。
丸括弧はプライマリ式なので、構文解析器は(c+d)のような入れ子になった副次式について全く心配する必要がない事に注意。

まず式は、プライマリ式ではじまりその後に[二項演算子, プライマリ式]（[binop, primaryexpr]）のペアが連なってるものである。

/// 式
///   ::= primary binoprhs
///
static ExprAST *ParseExpression() {
  ExprAST *LHS = ParsePrimary();
  if (!LHS) return 0;

  return ParseBinOpRHS(0, LHS);
}

ParseBinOpRHSは、二項演算子とプライマリ式のペアを解析するための関数である。
優先順位と、それまで解析された部分式へのポインタを引数として受け取る。
“x”単体でも完全に正しい式であるので、”binoprhs”は空である場合もある事に注意。
そのような場合、ParseBinOpRHSは渡された式をそのまま返す。
上の例では、ParseBinOpRHSには”a”を表す式が渡され、現在のトークンは”+”となる。

ParseBinOpRHSに渡される優先順位は、解析すべき演算子の最小優先順位を表す。
例えば、現在のペアが[+, x]の場合で、ParseBinOpRHSに優先順位40が渡されたら、どのトークンも消費されない。（なぜなら”+”の優先順位は20しかないから。）
こんな感じで、ParseBinOpRHSは以下のようなコードで始まる。

/// binoprhs
///   ::= ('+' プライマリ式)*
static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
  // 二項演算子ならその優先順位を得る。
  while (1) {
    int TokPrec = GetTokPrecedence();

    // 演算子の優先順位がExprPrecより大きければ処理し、
    // そうでなければ終了する。
    if (TokPrec < ExprPrec)
      return LHS;

このコードによって、現在のトークンの優先順位を得て、それが低すぎないかのチェックが行われる。
無効なトークンは優先順位-1になるようにしてるので、トークンの連なりが二項演算子を通り越したら、ペアストリーム（二項演算子とプライマリ式のペアの連なり）が終わった事をこのチェック処理は暗黙的に知ることが出来る。
このチェックが成功したら、そのトークンがこの式に含まれる二項演算子であることを我々は知ることが出来る。

// チェック処理を通ったということは, CurTokは二項演算子である。
int BinOp = CurTok;
getNextToken();  // 二項演算子を消費。

// 二項演算子の後のプライマリ式を解析する。
ExprAST *RHS = ParsePrimary();
if (!RHS) return 0;

このようにして、このコードは二項演算子を取り込み（そして一時的に保持し）、その後に続くプライマリ式を解析する。
こうして全てのペア（例で言うと最初のペアは[+, b]）を処理する。

さてこれで、我々は式の左手側（left-hand side）と右手側のペアの連なりのひとつを解析したことになるが、次に我々は、式の関連付けの方法について決定しなければならない。
“(a + b) binop unparsed”と見なすか”a + (b binop unparsed)”と見なすか。
訳注: aが左手側のプライマリ式、+ bが右手側のペアの連なりのさいしょのひとつ、binop unparsedはまだ解析してない残りの右手側ペアを表す。
これを決めるため、次の二項演算子を見てその優先順位を決定し、BinOpの優先順位と比較する。（この場合の比較対象は”+, (c+d)”の”+”となる。）

// BinOpの優先順位がRHS（右手側）の後の二項演算子より低いなら、
// 処理中の演算子はRHSをそのLHS（左手側）として受け取る。
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {

もし”RHS”（右手側）の右の二項演算子の優先順位が、現在の演算子の優先順位より小さいか等しい場合、丸括弧によって”(a + b) binop unparsed”として関連付けられなければならないことが分かる。
我々の例では、現在の演算子は”+”であり、次の演算子も”+”であり、もちろん両方とも同じ優先度である。
この場合、”a+b”を表すASTノードが生成され、構文解析は続く。
訳注: bの後の二項演算子が、bの前の二項演算子より優先順位が低いか等しいならば、bの前の二項演算子を優先すべきなので(a + b)となる。

      ... if文の中身は省略 ...
    }

    // LHSとRHSをマージする。
    LHS = new BinaryExprAST(BinOp, LHS, RHS);
  }  // ParseBinOpRHS関数のトップレベルのwhileループを繰り返す。
}

我々の例では、これによって”a+b+”は”(a+b)”となり”+”（bの後のほう）を現在のトークンとして次のループが実行されるだろう。
上記のコードは、取り込み、保持して、”(c+d)”をプライマリ式として解析するだろう。
それは現在のペアが[+, (c+d)]となる事を意味する。
そしたら、上記のif文の条件をプライマリ式の右にある二項演算子”*”をもって評価する。
この場合、”*”の優先順位は”+”の優先順位より高いので、if文の中が実行される。

ここに残る重大な疑問点は、”どうやってif文の中で完全に右手側を解析するか？”である。
特に、我々の例においてASTを正しく構築する事は、“(c+d)*e*f”全てをRHSの式として得る事を必要とする。
これを実現するためのコードは驚くほどシンプルである。（以下のコードは上記2つのコードと同じ部分である。if文の中身を追加しただけ。）

    // BinOpの優先順位がRHS（右手側）の後の二項演算子より低いなら、
    // 処理中の演算子はRHSをそのLHS（左手側）として受け取る。
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec+1, RHS);
      if (RHS == 0) return 0;
    }
    // LHSとRHSをマージする。
    LHS = new BinaryExprAST(BinOp, LHS, RHS);
  }  // ParseBinOpRHS関数のトップレベルのwhileループを繰り返す。
}

この時点で、我々のプライマリ式のRHSに対する二項演算子は、現在解析中の二項演算子より高い優先順位を持つということを我々は知っている。
なので、”+”より優先順位が高い全てのペアが、共に解析されRHSとして返されるべきである。
これを行うために、ParseBinOpRHS関数に最小優先順位として”TokPrec+1″を渡し、再帰的に呼び出している。
我々の例では、これによって“(c+d)*e*f”を表すASTノードがRHSとして返される。
そしてそれは、”+”演算子のRHSとしてセットされる。

最後に、次のループによって、”+g”が解析されASTに追加される。
このちょっとしたコード（しかしその14行は凄い）によって、一般的な二項演算式の解析をとてもエレガントなやり方で十分に正しく処理出来る。
これはこのコードについてかなり端折った、しかもいくらか微妙な説明である。
いくつかの例を用いて、このコードがどうやって動くか確認することをおすすめする。

これで式の処理がまとまった。
これによって我々の構文解析器は、任意のトークンの連なりを指し示し、そこから式を構築出来るようになった。
最初のトークンで止めることは、式の一部ではない。（stopping at the first token that is not part of the expression.）
次は、関数定義等々を処理出来るようにする必要がある。

訳注:
“a+b+(c+d)*e*f+g”という式を例として、どう処理されていくかの説明がこの章の大部分を占めているが、その過程の説明で「どの演算子について話してるか？」が原文にほとんど書かれてないため勘で訳した部分が多い。
「bの後の+」とか「eの前の*」とか一言書いてあるだけでもかなり分かりやすくなるはずなのに、「RHSの後」とかいう書き方がされているため非常に分かりにくい。
RHSが何を表すかは処理が進むに連れてどんどん変わっていくところなので。