パーサコンビネータ
小さなパーサを高階関数（combinator）で合成して、大きな文法のパーサを組み立てる技法。Parser a ＝「入力を消費して a を生む（失敗・残り入力を扱う）」関数の抽象。文法をホスト言語の値として書く点が、外部のパーサジェネレータと対照的。
構成
satisfy :: (Char -> Bool) -> Parser Char -- 原子
(<|>) :: Parser a -> Parser a -> Parser a -- 順序付き選択
many :: Parser a -> Parser [a] -- 繰り返しmap/<*>… アプリカティブ合成、>>=… モナド合成（文脈依存の文法）- 実体は再帰下降パーサ。PDA／文脈自由文法に対応
- 左再帰は直接扱えない（変換が要る）。パックラットで線形時間化する実装も
位置づけ
3つの近縁アプローチを並べると位置づけが鮮明になる：
| 観点 | パーサコンビネータ | パーサジェネレータ（生成系） | デコーダ |
|---|---|---|---|
| 入力 | テキスト（文字列） | テキスト（文字列） | 構造化データ（JSON/値） |
| 文法の表現 | ホスト言語の値（関数合成） | 外部 DSL（.y/.peg 文法ファイル） | ホスト言語の値（関数合成） |
| 生成タイミング | 実行時に合成（ライブラリ） | ビルド時にコード生成 | 実行時に合成（ライブラリ） |
| 扱える文法 | 再帰下降＝文脈自由、左再帰は不可（要変換） | LALR/LR/GLR/PEG など方式依存で広い | スキーマ（再帰可） |
| 性能 | バックトラックで悪化しうる（packrat で線形化） | テーブル駆動で高速・予測可能 | 入力が小さく軽い |
| エラー回復 | 弱い（工夫が要る） | 強い（同期トークン等の機構） | 失敗を型で返す |
| 手軽さ | 高（言語内で完結、ビルド工程不要） | 低（別ツール・別文法言語） | 高 |
| 代表 | parsec/megaparsec (Haskell), FastParse (Scala), nom (Rust) | yacc/bison, ANTLR, tree-sitter | aeson, elm/Json.Decode, zod |
- デコーダパターンと同型 —
Parser ≈ Decoder（未知入力→型付き値＋失敗）。違いはテキスト相手か構造化データ相手かだけで、合成の仕方（map/<*>/>>=）は同じ。 - コンビネータは「ライブラリとして言語内で完結」する手軽さが利点。性能・エラー回復は生成系が有利なことが多い。
なぜ重要か
文法を第一級の値として部品から組み立てられる。型で結果が保証され、パースの段階で型付き値に落とす「parse, don’t validate」の実装手段になる。
押さえどころ（カード化候補）
- パーサコンビネータとは → 小さなパーサを高階関数 (combinator) で合成して大きな文法を組む技法。
Parser a＝「入力を消費してaを生む（失敗・残り入力を扱う）」関数。 - 構成要素 → 原子
satisfy、順序付き選択<|>、繰り返しmany。map/<*>がアプリカティブ合成、>>=が文脈依存文法用のモナド合成。 - 実体と限界 → 中身は再帰下降＝文脈自由の認識。左再帰は直接扱えず変換が要る。packrat で線形時間化できる。
- 生成系との対比 → コンビネータはホスト言語の値・ビルド工程不要で手軽。生成系 (yacc/ANTLR/tree-sitter) はテーブル駆動で高速・エラー回復が強い。
- デコーダと同型 →
Parser ≈ Decoder（未知入力→型付き値＋失敗）。テキストか構造化データかの違いだけ。「parse, don’t validate」の実装手段。