パーサコンビネータ
小さなパーサを高階関数で合成して大きなパーサを組み立てる手法。パーサジェネレータ (lex-yacc) が独立した文法定義ファイルからコードを生成するのに対し、パーサコンビネータはホスト言語の関数として文法をそのまま記述する。Rust の nom を使ったトイ言語コンパイラ (toy-llvm-compiler) を題材に整理する。
パーサの型
nom ではパーサは関数 fn(I) -> IResult<I, O> で表される。成功時は Ok((残りの入力, パース結果)) を返し、入力の消費分と生成した値を同時に持ち回る。今回の例では I = &str、O = AST ノード。失敗時はエラー (回復可能/不能の区別あり) を返す。この「入力→(残り, 値)」という形が合成可能性の核心で、あるパーサの残り入力を次のパーサへ渡せる。
主なコンビネータ
tag: 固定文字列 (予約語・記号) にマッチ。delimited(open, body, close): 括弧で囲まれた中身を取り出す。tuple((p1, p2, ...)): 連接 (順に適用しタプルで返す)。alt((p1, p2, ...)): 選択 (最初に成功したもの)。many0/many1: 0回以上 / 1回以上の反復。opt: 省略可能 (0回または1回)。map/map_res: パース結果を変換して AST ノードを構築。
これらは「連接・選択・反復・省略」という BNF の演算子に1対1で対応するため、文法を素直にコードへ写せる。
文法をコードへ写す
program_parser がプログラム文字列を全消費できれば妥当なプログラムとみなす。式の優先順位は文法のネストで表現する (parser-combinator)。注意点として、パーサは「マッチしたら即消費」する貪欲動作なので、左再帰を直接書くと無限ループする。<下位> (op <下位>)* の反復に書き換えて畳み込むのが定石。
パーサジェネレータとの比較
- パーサジェネレータ (yacc/racc/bison): 別ファイルの文法 + LALR テーブル生成。曖昧性解消・優先順位宣言が組み込み。
- パーサコンビネータ (nom 等): ホスト言語の値/関数。型検査・デバッグ・テストが普通のコードとして書け、エラー位置情報 (
nom_locate) や LSP 連携 (Semantic Tokens) に発展させやすい。曖昧性は自前で吸収する必要がある。
関連
- parser-combinator、compiler-optimization。
- ツール/プロジェクト: lex-yacc、toy-llvm-compiler、rust-lang。
演算子優先順位文法によるパース
二項演算子の 優先順位 と 結合性 を、文法規則を段階的にネストすることで表現する手法。再帰下降パーサやパーサコンビネータ (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 系は宣言で済むが、生成された構文木をスタックマシンコードに落とす流れは compiler-optimization を参照。