問題タブ [parse-forest]

パーサーがあいまいな文法から可能なすべての解析結果 (解析フォレスト) を返し、それらをユーザー コンテキスト/履歴およびナレッジ ベースに対して評価して解析フォレストから選択するようにしようとしています。パフォーマンス上の理由から、無限ループを回避するためにプロダクション ルールを適用する際の再帰呼び出しの数を制限するために、packrat パーサーと検索制限/上限パラメーターを使用してこれを行う必要があります。

Scala とそのパーサー コンビネーターの両方に慣れていないので、これを行う方法や、できるかどうかがまったくわかりません。誰か助けてくれませんか？とても有難い。

よろしく、 トーマス・フアン

パーサー コンビネーター (推奨) の形で、または C または C++ のパーサー ジェネレーターとして、GLLアルゴリズムの既存の実装はありますか?

私の要件は、出力が共有パックパース フォレスト (SPPF) であることです。これは、後でセマンティック ルールやコンテキスト ルールを使用して明確にすることができます。一般的な文脈自由文法に対処できる GLR などの他の解析アルゴリズムがありますが、私が見つけたすべての GLR パーサー ジェネレーターは、最初に成功した解析ツリーを返すか、最後にあいまいさが残っている場合は失敗します。

あいまいな Marpa 文法とあいまいな入力文字列があるとします。

Marpa を使用して文字列を解析し、解析フォレストを作成できます。フォレスト内の各解析ツリーを反復処理することもできます。

しかし、パース フォレストに沿って反復処理するにはどうすればよいでしょうか。

私が何を意味するかを説明するには：

解析フォレストは一種のグラフであり、代替が分割されるノードと、代替が結合して「メイン ストリーム」になるノードを持つことができます。

これらが 1 つのパース フォレストの代替パース ツリーであるとします。

• A B1 C
• A B2 C
• A B3 B4 C

本流はあるがA……CあいまいなB部分がある。

もちろん、実際の解析では、分岐時に多くのレベルの分岐が存在する可能性があり、単一のメイン ストリームに再結合しないストリームが存在する場合があります。しかし、一般的には、2 つまたは多くの解釈に共通する多くの部分があります。

明確で曖昧なノードのチェーンに沿って反復するには、どのようなアプローチを使用できますか?

実際、グラフ全体を出力できますか?

同じ番号を持つ 2 つのノードがないように、フォレストの各ノードに番号を割り当てようとします。相互に再帰的に呼び出す 2 つの関数を使用しようとしましたが、コンパイル エラーが発生します。コードは次のとおりです。

私が得るエラーは次のとおりです。

.hs:27:34: 予想される型b0 -> c0' with actual typeTree Int と一致しませんでした 考えられる原因: Node' is applied to too many arguments In the first argument of(.)​​'、つまり `Node n fst' 式: Node n fst 。数の森 (n + 1) xs

何が問題で、どうすれば解決できますか?