パーサーコンビネータ

コンピュータプログラミングにおいて、パーサーコンビネータは、複数のパーサーを入力として受け取り、新しいパーサーを出力として返す高階関数です。ここで言うパーサーとは、文字列を入力として受け取り、何らかの構造（通常は構文解析木、または文字列内で解析が正常に終了した位置を表すインデックスの集合）を出力する関数です。パーサーコンビネータは、モジュール化された区分的な構築とテストを容易にする再帰下降構文解析戦略を可能にします。この構文解析手法は、組み合わせ構文解析と呼ばれます。

コンビネータを用いたパーサは、データベースへの自然言語ユーザインターフェースなどのドメイン固有言語用のコンパイラやプロセッサのプロトタイプ作成において広く利用されてきた。これらの言語では、複雑で多様な意味処理が構文処理と密接に統合されている。1989年、リチャード・フロストとジョン・ローンチベリーは、パーサコンビネータを用いて自然言語インタプリタを構築することを実証した^{[ 1 ]} 。グラハム・ハットンも1992年に基本的な構文解析に高階関数を使用しました^{[ 2 ] 。}また、1996年にはモナド構文解析を使用しました^{[ 3 ]}。SD・スウィエストラも2001年に構文解析器コンビネータの実用的な側面を示しました^{[ 4 ] 。} 2008年には、フロスト、ハフィズ、キャラハン^{[ 5 ]}が関数型プログラミング言語Haskellで、左再帰に対応するという長年の問題を解決し、多項式時間と空間で完全なトップダウン構文解析ツールとして機能する構文解析器コンビネータのセットを説明しました。

基本的な考え方

第一級関数を持つプログラミング言語では、パーサーコンビネータを用いて基本的なパーサーを組み合わせ、より複雑な規則に対応するパーサーを構築することができます。例えば、文脈自由文法（CFG）の生成規則には1つ以上の選択肢があり、各選択肢は非終端記号および／または終端記号の列で構成される場合もあれば、単一の非終端記号または終端記号、あるいは空文字列で構成される場合もあります。これらの選択肢それぞれに単純なパーサーが利用可能な場合、パーサーコンビネータを用いて各パーサーを組み合わせ、選択肢のいずれかまたはすべてを認識できる新しいパーサーを生成することができます。

演算子オーバーロードをサポートする言語では、パーサコンビネータは中置演算子の形をとることができ、異なるパーサを結合して完全な規則を形成するために使用されます。これにより、パーサコンビネータは、形式文法の規則に構造が類似したコードで、埋め込み形式でパーサを定義することを可能にします。したがって、実装は、可読性などの利点をすべて備えた実行可能な仕様と考えることができます。

コンビネータ

議論を比較的分かりやすくするために、パーサーコンビネータを認識器のみの観点から考察します。入力文字列の長さが で#input、そのメンバーにインデックス を介してアクセスする場合j、認識器とは、インデックス で始まるトークンのシーケンスの認識に成功したインデックスの集合を出力として返すパーサーですj。空の結果セットは、認識器がインデックス で始まるシーケンスを認識できなかったことを示しますj。

• 認識empty器は空文字列を認識します。このパーサーは常に成功し、入力インデックスを含むシングルトンセットを返します。

${\displaystyle empty(j)=\{j\}}$

• 認識器は終端記号 を認識します。入力文字列のインデックス のトークンが の場合、このパーサーは を含むシングルトン集合を返します。それ以外の場合は、空集合を返します。term xxjxj + 1

${\displaystyle term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}}$

2 つの認識子とが与えられればp、q代替ルールのマッチング用とルールの順序付け用の 2 つの主要なパーサー コンビネータを定義できます。

• 「代替」パーサーコンビネータ ⊕ は、各認識子を同じインデックスに適用しj、認識子の終了インデックスの結合を返します。

${\displaystyle (p\oplus q)(j)=p(j)\cup q(j)}$

• 「シーケンス」コンビネータ ⊛ は、最初の認識器をp入力インデックス に適用しj、各終了インデックスに対して、qそれを開始インデックスとして2番目の認識器を適用します。これは、 のすべての呼び出しから返される終了インデックスの和集合を返しますq。

${\displaystyle (p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}}$

文字列を解析する際に、同じインデックスで終了するにもかかわらず、複数の異なる方法が存在する場合があり、これは文法が曖昧であることを示します。単純な認識器はこのような曖昧さを認識しません。つまり、終了インデックスの候補はそれぞれ結果セットに一度だけリストされます。より完全な結果セットを得るには、解析木などのより複雑なオブジェクトを返す必要があります。

例

非常に曖昧な文脈自由文法を考えてみましょう。s ::= ‘x’ s s | ε先に定義したコンビネータを用いることで、この文法の実行可能な表記を、現代の関数型プログラミング言語（例えば、Haskell）において のようにモジュール的に定義することができます。入力シーケンスのインデックス にs = term ‘x’ <*> s <*> s <+> empty認識器を適用すると、結果セット が返されます。これは、インデックス 2 から始まり、2 から 5 までの任意のインデックスで終わる一致があったことを示します。 s2x x x x x{2,3,4,5}

欠点と解決策

パーサーコンビネータは、すべての再帰下降パーサーと同様に、文脈自由文法に制限されず、したがってLL( k ) 解析のFirst _kおよび Follow _kセットの曖昧さをグローバルに検索しません。したがって、曖昧さは、入力によってトリガーされるまで実行時までわかりません。このような場合、再帰下降パーサーは、（おそらく文法設計者に知られずに）可能性のある曖昧なパスの 1 つをデフォルトとすることがあり、その結果、言語の使用時に意味の混乱（エイリアシング）が発生します。これにより、曖昧なプログラミング言語のユーザーにバグが発生しますが、これはコンパイル時には報告されず、人的エラーではなく曖昧な文法によって導入されます。これらのバグを排除する唯一の解決策は、曖昧さを排除して文脈自由文法を使用することです。

パーサコンビネータの単純な実装には、トップダウン構文解析に共通するいくつかの欠点があります。ナイーブな組み合わせ構文解析では、曖昧な文脈自由文法を解析する際に指数関数的な時間と空間を必要とします。1996年、フロストとシドロウスキーは、メモ化をパーサコンビネータと組み合わせて用いることで、時間計算量を多項式にまで削減できることを示しました。^{[ 6 ]}その後、フロストはモナドを用いてコンビネータを構築し、計算全体を通してメモテーブルを体系的かつ正確にスレッド化できるようにしました。^{[ 7 ]}

あらゆるトップダウン再帰下降構文解析と同様に、従来の構文解析器コンビネータ（上記コンビネータなど）は、左再帰文法（例s ::= s <*> term ‘x’|empty：）の処理中に終了しません。直接左再帰規則を持つ曖昧な文法に対応する認識アルゴリズムは、2006 年に Frost と Hafiz によって説明されました。 ^{[ 8 ]}このアルゴリズムは、深さ制限を課すことで、そうでなければ増え続ける左再帰解析を削減します。そのアルゴリズムは、2007 年に Frost、Hafiz、Callaghan によって完全な構文解析アルゴリズムに拡張され、直接左再帰だけでなく間接左再帰にも多項式時間で対応し、高度に曖昧な文法の潜在的に指数関数的な数の構文解析ツリーのコンパクトな多項式サイズの表現を生成しました。^{[ 9 ]}この拡張アルゴリズムは、「計算されたコンテキスト」を「現在のコンテキスト」と比較することで間接左再帰に対応します。同じ著者らは、同じアルゴリズムに基づいてHaskell言語で書かれたパーサーコンビネータのセットの実装についても説明した。^{[ 5 ] [ 10 ]}

注記

1. フロスト＆ローンチベリー 1989 .
2. ハットン 1992 .
3. Hutton, Graham; Meijer, Erik. Monadic Parser Combinators (PDF) (レポート). ノッティンガム大学. 2023年2月13日閲覧。
4. スウィエルストラ 2001 .
5. フロスト、ハフィズ、キャラハン 2008 .
6. フロスト＆シドロウスキー 1996 .
7. フロスト 2003 .
8. フロスト＆ハフィズ 2006 .
9. フロスト、ハフィズ、キャラハン 2007 .
10. 参照。X - SAIGA —実行可能な文法仕様​​​​​

参考文献

• バージ、ウィリアム・H. (1975). 『再帰プログラミング技法』 . システムプログラミングシリーズ. アディソン・ウェスレー. ISBN 978-0201144505。
• リチャード・フロスト、ジョン・ローンチベリー (1989). 「遅延関数型言語による自然言語インタープリタの構築」(PDF) .コンピュータジャーナル. 遅延関数型プログラミング特集号. 32 (2): 108– 121. doi : 10.1093/comjnl/32.2.108 . 2013年6月6日時点のオリジナルよりアーカイブ。{{cite journal}}: CS1 maint: bot: 元のURLステータス不明（リンク）
• リチャード・A・フロスト；バーバラ・シドロウスキー（1996）「純粋関数型トップダウンバックトラッキング言語プロセッサのメモ化」（PDF）科学計算プログラム27 （ 3）263-288 . doi：10.1016/0167-6423(96)00014-7 .
• リチャード・A・フロスト (2003). 「モナドメモ化による正確性維持型探索縮約」.第16回カナダ計算知能学会人工知能の進歩に関する会議 (AI'03) 議事録(PDF) . シュプリンガー. pp.  66– 80. ISBN 978-3-540-40300-5。
• リチャード・A・フロスト、ラフマトゥラー・ハフィズ (2006). 「多項式時間で曖昧性と左再帰に対応する新しいトップダウン構文解析アルゴリズム」(PDF) . ACM SIGPLAN Notices . 41 (5): 46– 54. doi : 10.1145/1149982.1149988 . S2CID  8006549 .
• リチャード・A・フロスト、ラフマトゥラー・ハフィズ、ポール・キャラハン (2007). 「曖昧な左再帰文法のためのモジュール型で効率的なトップダウン構文解析」第10回国際構文解析技術ワークショップ (IWPT) 論文集、ACL-SIGPARSE : 109–120 . CiteSeerX  10.1.1.97.8915 .
• リチャード・A・フロスト、ラフマトゥラー・ハフィズ、ポール・キャラハン (2008). 「曖昧な左再帰文法のためのパーサコンビネータ」.宣言型言語の実践的側面. ACM-SIGPLAN. 第4902巻. pp.  167– 181. CiteSeerX  10.1.1.89.2132 . doi : 10.1007/978-3-540-77442-6_12 . ISBN 978-3-540-77441-9。
• ハットン、グラハム (1992). 「構文解析のための高階関数」.関数型プログラミングジャーナル. 2 (3): 323– 343. CiteSeerX  10.1.1.34.1287 . doi : 10.1017/s0956796800000411 . S2CID  31067887 .
• 岡崎, クリス (1998). 「構文解析や解析のための高階関数、あるいはなぜ6階関数を使いたがる人がいるのか？」 . Journal of Functional Programming . 8 (2): 195– 199. doi : 10.1017/S0956796898003001 . S2CID  59694674 .
• Swierstra, S. Doaitse (2001). 「コンビネータパーサ：おもちゃからツールへ」 .電子計算機科学理論ノート. 41 : 38–59 . doi : 10.1016/S1571-0661(05)80545-6 .
• Wadler, Philip (1985). 「失敗を成功のリストに置き換える方法：遅延関数型言語における例外処理、バックトラッキング、パターンマッチングのための手法」.関数型プログラミング言語とコンピュータアーキテクチャ. コンピュータサイエンス講義ノート. 第201巻. pp.  113– 128. doi : 10.1007/3-540-15975-4_33 . ISBN 978-0-387-15975-1– 関数型プログラミング言語とコンピューターアーキテクチャに関する会議の議事録より。

「 https://en.wikipedia.org/w/index.php?title=Parser_combinator&oldid=1334837580」から取得