パーサーがあいまいな文法から可能なすべての解析結果 (解析フォレスト) を返し、それらをユーザー コンテキスト/履歴およびナレッジ ベースに対して評価して解析フォレストから選択するようにしようとしています。パフォーマンス上の理由から、無限ループを回避するためにプロダクション ルールを適用する際の再帰呼び出しの数を制限するために、packrat パーサーと検索制限/上限パラメーターを使用してこれを行う必要があります。
Scala とそのパーサー コンビネーターの両方に慣れていないので、これを行う方法や、できるかどうかがまったくわかりません。誰か助けてくれませんか？とても有難い。
よろしく、 トーマス・フアン
Scalaの組み込みパーサーコンビネーターではこれを行うことはできません。Packratコンビネータは、明確な文法のみに制限されています。あいまいさを処理しようとすると、メモ化する機能が失われ、あいまいでないトレイルであっても、解析の複雑さはO（k ^ n）になります。だから、そうしないでください。
必要なのは、あいまいさを正しく処理するパーサーコンビネーターフレームワークです。私の知る限り、Scalaのそのようなフレームワークは私のGLLコンビネータだけです。構文はScalaのパーサーコンビネーターとほぼ同じですが（主な違いは、より高いアリティ関数が正しく機能することです）、出力はです。Stream[A]ここAで、は結果タイプです。したがって、解析フォレストを取得します。結果は実際にはSPPF（共有パック解析フォレスト）ではないため、指数関数的な数の結果を生成すると、ストリームのサイズは比例することに注意してください。これは、結果タイプの究極の柔軟性を維持するために行われました。
GLLコンビネータは、最悪の場合、病理学的にあいまいな文法であってもO（n ^ 3）です。解析トレイルが明確である平均的なケースでは、GLLコンビネータはO（n）です。一定時間のオーバーヘッドは現在少し過剰ですが、最適化は進行中のプロジェクトです。Precogでの本番環境ではGLLコンビネータを使用しているため、ライブラリは今後も適切に維持されることが期待できます。