演算子優先順位文法によるパース
二項演算子の 優先順位 と 結合性 を、文法規則を段階的にネストすることで表現する手法。再帰下降パーサやパーサコンビネータ (parser-combinator) のように「マッチしたら即消費」する貪欲なパーサで正しい構文木を作るための定石。
問題
1 + 2 * 3 を (1 + (2 * 3)) と解釈させたい。単一の expr := expr op expr という文法では曖昧 (どの結合が先か決まらない) になる。yacc では %left/%prec の優先順位宣言で解決できるが、パーサコンビネータには曖昧性解消機構が無いので、文法そのものに優先順位を埋め込む。
優先順位の階層化
優先度の 低い 演算子を外側、高い 演算子を内側にして文法を多段に分割する。トイ言語 ipulang の例:
<or-expr> := <and-expr> | <or-expr> '||' <and-expr>
<and-expr> := <equality-expr> | <and-expr> '&&' <equality-expr>
<equality-expr> := <relational-expr> | <equality-expr> ('=='|'!=') <relational-expr>
<relational-expr> := <additive-expr> | <relational-expr> ('>'|'<'|'<='|'>=') <additive-expr>
<additive-expr> := <multiplicative-expr> | <additive-expr> ('+'|'-') <multiplicative-expr>
<multiplicative-expr> := <factor> | <multiplicative-expr> ('*'|'/'|'%') <factor>
<factor> := <const> | <paren_expr> | <call> | <variable>
各段は「下位の式を1つ読み、続けて同段の演算子と下位式の並びを読む」形になっている。低優先度の段から呼び出すと、最終的に factor (リテラル・括弧・呼び出し・変数) まで降りる。括弧式 ( <or-expr> ) は最上位へ戻る再帰なので、優先順位を明示的に上書きできる。
左再帰とパーサコンビネータ
上の BNF は左再帰 (<or-expr> := <or-expr> '||' ...) を含む。再帰下降/パーサコンビネータは左再帰で無限ループするため、実装では <下位> ( op <下位> )* のような 反復 に書き換え、畳み込みで左結合の木を組む。nom では下位パーサ + many0/fold_many0 で表現する。yacc は LALR なので左再帰をそのまま扱え、むしろ左再帰が推奨される (スタック消費が一定)。
ポイント
- 優先順位 = 文法のネスト深さ。結合性 = 左再帰か右再帰か (反復畳み込みの向き)。
- 「即消費」型パーサでは曖昧性を文法構造で吸収する。
- yacc 系は宣言で済むが、生成された構文木をスタックマシンコードに落とす流れは stack-machine-codegen を参照。