パーサコンビネータ
小さなパーサを高階関数で合成して大きなパーサを組み立てる手法。パーサジェネレータ (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 がプログラム文字列を全消費できれば妥当なプログラムとみなす。式の優先順位は文法のネストで表現する (operator-precedence-parsing)。注意点として、パーサは「マッチしたら即消費」する貪欲動作なので、左再帰を直接書くと無限ループする。<下位> (op <下位>)* の反復に書き換えて畳み込むのが定石。
パーサジェネレータとの比較
- パーサジェネレータ (yacc/racc/bison): 別ファイルの文法 + LALR テーブル生成。曖昧性解消・優先順位宣言が組み込み。
- パーサコンビネータ (nom 等): ホスト言語の値/関数。型検査・デバッグ・テストが普通のコードとして書け、エラー位置情報 (
nom_locate) や LSP 連携 (Semantic Tokens) に発展させやすい。曖昧性は自前で吸収する必要がある。