パーサコンビネータ（）は、コンピュータプログラミングにおいて、いくつかのパーサーを入力として受け取り、出力として新しいパーサーを返す高階関数である。この文脈において、パーサーとは、文字列を入力として受け取り、出力として何らかの構造（通常は構文木や、構文解析が正常に終了した文字列内の位置を表すインデックスの集合など）を返す関数である。パーサコンビネータは、モジュール式で断片的な構築やテストを容易にする、再帰下降構文解析戦略を可能にする。この構文解析手法はコンビネータ構文解析（combinatory parsing）と呼ばれる。
コンビネータを使用したパーサーは、複雑で多様な意味的アクションと構文処理が密接に統合されている、データベースへのなどのドメイン固有言語用コンパイラやプロセッサのプロトタイピングに広く使用されてきた。1989年、Richard FrostとJohn Launchburyは、パーサコンビネータを使用して自然言語インタープリタを構築する方法を示した。また、Graham Huttonも1992年に基本的な構文解析に高階関数を使用し、1996年にモナド構文解析（monadic parsing）に使用した。S. D. Swierstraも2001年にパーサコンビネータの実用的な側面を提示している。2008年には、Frost、Hafiz、Callaghanが、左再帰への対応という長年の問題を解決し、完全なトップダウン構文解析ツールとして多項式時間と空間で動作する、関数型プログラミング言語Haskellでのパーサコンビネータのセットについて記述した。
基本概念 第一級関数を持つ任意のプログラミング言語において、パーサコンビネータを使用すると、基本的なパーサーを組み合わせてより複雑な規則用のパーサーを構築することができる。たとえば、文脈自由文法（CFG）の生成規則（production rule）は1つ以上の選択肢 (alternative) を持つ場合があり、各選択肢は非終端記号と終端記号の並びで構成されるか、あるいは単一の非終端記号、終端記号、または空文字列で構成される場合がある。これらの選択肢のそれぞれに対して単純なパーサーが利用できる場合、パーサコンビネータを使用してこれらの各パーサーを組み合わせ、選択肢のいずれかまたはすべてを認識できる新しいパーサーを返すことができる。
演算子のオーバーロードをサポートする言語では、パーサコンビネータは中置演算子の形式をとることができ、異なるパーサーを接着して完全な規則を形成するために使用される。これにより、パーサコンビネータは、形式文法の規則と構造的に類似したコードにおいて、埋め込みスタイルでパーサーを定義することを可能にする。そのため、その実装は読みやすさなどの関連するすべての利点を備えた「実行可能な仕様 (executable specifications)」と見なすことができる。
コンビネータ 議論を比較的単純にするため、ここでは「認識器 (recognizer)」のみの観点からパーサコンビネータについて議論する。入力文字列の長さが #input であり、その要素がインデックス j を通じてアクセスされるとする。このとき認識器とは、出力として、インデックス j から始まるトークンの並びをパーサーが正常に認識し終えた位置を表すインデックスの集合を返すパーサーである。空の戻り値（空集合）は、認識器がインデックス j から始まるいかなるシーケンスも認識できなかったことを示す。
empty 認識器は空文字列を認識する。このパーサーは常に成功し、入力インデックスのみを含む単一要素の集合 (シングルトン) を返す。
認識器 term x は終端記号 x を認識する。入力文字列のインデックス j にあるトークンが x である場合、このパーサーは j + 1 を含む単一要素の集合を返す。それ以外の場合は、空集合を返す。
2つの認識器 p と q が与えられたとき、2つの主要なパーサコンビネータを定義できる。1つは選択規則にマッチするためのものであり、もう1つは規則を連続させるためのものである。
「選択 (alternative)」パーサコンビネータ ⊕ は、同じインデックス j に対して各認識器を適用し、認識器の終了インデックスの和集合を返す。
「連続 (sequence)」コンビネータ ⊛ は、入力インデックス j に最初の認識器 p を適用し、その終了インデックスのそれぞれについて、それらを開始インデックスとして2番目の認識器 q を適用する。そして、q のすべての呼び出しから返された終了インデックスの和集合を返す。
同じインデックスで終了するように文字列を構文解析する際に、複数の異なる方法が存在する場合がある。これは曖昧な文法であることを示している。単純な認識器はこれらの曖昧さを認識せず、考えられる各終了インデックスは結果セットに一度だけリストされる。より完全な結果セットを得るためには、構文木などのより複雑なオブジェクトを返す必要がある。
例 高度に曖昧な文脈自由文法 s ::= ‘x’ s s | ε を考えてみよう。先に定義したコンビネータを使用すると、現代の関数型プログラミング言語（例：Haskell）において、この文法の実行可能な表記法を s = term ‘x’ <*> s <*> s <+> empty のようにモジュール式に定義できる。認識器 s を入力シーケンス x x x x x のインデックス 2 に適用すると、結果セット {2,3,4,5} が返される。これは、インデックス 2 から始まり、2 から 5 までの任意のインデックスで終了する一致があったことを示している。
欠点と解決策 パーサコンビネータは、すべての再帰下降パーサと同様に文脈自由文法に限定されないため、LL(k) 構文解析の Firstk 集合および Followk 集合における曖昧さのグローバルな探索を行わない。したがって、入力によって引き起こされるまで、実行時まで曖昧さは判明しない。そのような場合、再帰下降パーサは（おそらく文法設計者の知らないうちに）考えられる曖昧なパスの1つをデフォルトとして選択してしまい、言語の使用において意味的な混乱（エイリアシング）をもたらす可能性がある。これは、コンパイル時には報告されず、人間のミスではなく曖昧な文法によって持ち込まれるため、曖昧なプログラミング言語のユーザーによるバグを引き起こす。これらのバグを排除する唯一の解決策は、曖昧さを取り除き、文脈自由文法を使用することである。
パーサコンビネータの単純な実装には、トップダウン構文解析に共通するいくつかの欠点がある。単純な (Naïve) コンビネータ構文解析は、曖昧な文脈自由文法を構文解析する際に指数関数的な時間と空間を必要とする。1996年、FrostとSzydlowskiは、パーサコンビネータでメモ化を使用することで時間計算量を多項式時間へと削減できる方法を示した。その後、Frostは計算全体を通してメモテーブルを体系的かつ正確にスレッド化するコンビネータを構築するためにモナドを使用した。
トップダウンの再帰下降構文解析と同様に、従来のパーサコンビネータ（上記で説明したコンビネータなど）は、左再帰文法（例：s ::= s <*> term ‘x’|empty）を処理する際に終了しなくなる。直接左再帰規則を持つ曖昧な文法に対応する認識アルゴリズムが、2006年にFrostとHafizによって説明されている。このアルゴリズムは、深さ制限を課すことによって、放っておくと増大し続ける左再帰構文解析を打ち切る。このアルゴリズムは、2007年にFrost、Hafiz、Callaghanによって完全な構文解析アルゴリズムへと拡張され、間接的および直接的な左再帰の両方に多項式時間で対応し、高度に曖昧な文法における指数関数的な数になりうる構文木のコンパクトな多項式サイズ表現を生成するようになった。この拡張されたアルゴリズムは、「計算されたコンテキスト」と「現在のコンテキスト」を比較することで、間接的な左再帰に対応する。同じ著者らはまた、同じアルゴリズムに基づいてHaskell言語で書かれたパーサコンビネータのセットの実装についても記述しているcf. X-SAIGA — executable specifications of grammars。
脚注
参考文献