問題タブ [glr]

私はGLRパーサジェネレーターを書いていますが、インターネットと枯れ木の種類（オタクの話に慣れていない人のための本）の両方で、このアルゴリズムに関連するリソースについてアドバイスを求めています。

BisonがGLRパーサーを生成できることは知っています。また、GPLの下にある場合は、そのコードを調べることができますが、アルゴリズムの完全な説明があると便利です。

それで、誰かが私が利用できる良いリソースを知っていますか？ありがとう。

では、GLRパーサジェネレータを作成したいと思います。私はおそらく私が作るものよりも優れたそのようなプログラムが存在することを知っていますが、私は楽しみ/学習のためにこれを行っているので、それは重要ではありません。

私はGLR解析について読んでいますが、今ではそれについてかなり高いレベルで理解していると思います。しかし今、ビジネスに取り掛かる時が来ました。

グラフ構造化スタック（GSS）は、GLRパーサーで使用するための主要なデータ構造です。概念的にはGSSがどのように機能するかは知っていますが、これまでに調べたソースのいずれも、GSSの実装方法を説明していません。サポートする操作の信頼できるリストすらありません。誰かがGSSの良いサンプルコード/チュートリアルを教えてもらえますか？グーグルは今のところ助けにはならなかった。この質問が曖昧すぎないことを願っています。

組み合わせ GLR パーサーを実装しました。その中には次のものがあります。

• char(·)指定された文字または文字範囲を消費するパーサー。
• many(·)指定されたパーサーをゼロから無限に繰り返すコンビネーター。

例:は、任意の数の-s"char('a').many()"を含む文字列に一致します。"a"

しかし、many(·)コンビネーターは貪欲であるため、たとえば、char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}')(">>"パーサーのシーケンシャル チェーンはどこにありますか) は文字列全体を正常に消費し"{{foo}}some{{bar}}"ます。

many(·)前の例で使用されている、消費"{{foo}}"のみの遅延バージョンを実装したいと思います。どうやってやるの？

編集：

私はあなたを混乱させたかもしれません。私のプログラムでは、パーサーは「ステップ」を受け入れて「ステップ」の森を返す関数 (または C++ の用語では「ファンクター」) です。「ステップ」には、OK タイプ (パーサーが入力の一部を正常に消費したことを意味する) と FAIL タイプ (パーサーがエラーに遭遇したことを意味する) があります。より多くの種類のステップがありますが、それらは補助的なものです。

したがって、入力を解析すると、次のようになります。

• 単純な事前定義されたパーサー関数を構成して、必要な文法を表す複雑なパーサー関数を取得します。

• 入力から最初のステップを形成します。

• 複雑なパーサー関数に初期ステップを与えます。

• Steps で TreeNodes をフィルタリングし、OK のものだけを残します (または、入力にエラーがあった場合は最小限の FAIL-s で)。

• 残されたステップから情報を集める。

前文

エラー回復機能を備えた GLR パーサーを作成しました。エラーが発生すると、次の代替手段に分割されます。

1. 期待される要素を入力に挿入し (ユーザーが見逃した可能性があります)、通常どおりに処理を進めます。
2. エラーのある要素を予想される要素 (ユーザーがタイプミスした可能性があります) に置き換えて、通常どおり続行します。
3. エラーのある要素をスキップし、次の要素もエラーの場合は #2 に進みます。

しかし、入力に多くのエラーがある場合 (たとえば、ユーザーが誤って JPEG ファイルをパーサーに渡してしまった場合)、代替手段の数が指数関数的に増加します。

例

次の文法に対応するこのようなパーサー:

次のテキストに適用されます。

中程度の最新のデスクトップ コンピューターでは、「メモリ不足」で失敗します。

質問

入力エラーが発生した場合に選択肢の数を減らす方法は?

bison / yacc GLRパーサーで「期待されるトークン」を取得するにはどうすればよいですか？

やあ、

私が行っているプロジェクトには、あいまいな文法がいくつかあります。だから私は％glr-parserを使ってshift/reduceの競合を解決しようとしています。

非GLRパーサーを使用していた場合、構文エラーを検出したときにyystate（グローバル変数）を使用して「予期されるトークン」を取得できます。しかし、GLRパーサーに切り替えた後、グローバル変数ではなくなったことがわかりました。

だから私の質問は、構文エラーがあるときにGLRパーサーで「期待されるトークン」を取得する方法はありますか？

Bison を使用してパーサーを生成しています。Bison が LALR ではなく GLR を使用して対処する必要がある場合に、shift/reduce の競合が 1 つあります。しかし、%glr-parserディレクティブを渡しましたが、ソース ファイルにはまだ LALR パーサーであると記載されています。%skeleton "glr.cc"GLR C++ パーサーであり、それを使用しても出力が変わらないことを示唆する "glr.cc" スケルトンも見つけました。Bison はすべてのターゲット言語のすべてのアルゴリズムを出荷していませんか?

shift\reduce 競合を GLR メソッドで強制的に解決するにはどうすればよいですか?
右シフト演算子とそれ自体のテンプレート引数の 2 つの閉じ山かっこの間の競合をパーサーに解決させたいとします。1 つの ">>" トークンにマージせずに、レクサーに 2 つの連続する ">" 記号を個別のトークンとして渡すようにします。次に、これらのルールを文法に入れます。

これを shift\reduce 競合にしたい。左結合で ">" のトークン宣言がある場合、これは競合しません。そのため、token precedence\associativity 宣言を削除する必要がありますが、競合するルールごとにコンテキストの優先順位を指定して手動で解決したくない他の多くの競合が発生します。それで、トークンを宣言している間に shift\reduce 競合を強制する方法はありますか?

私はC/ALプログラミング言語用のある種のlintツールを作成しようとしています。したがって、基本的には、ソースコードに対して構文と字句解析を実行する必要があります。パーサーを最初から作成することを計画しましたが、これらのパーサーを自動的に生成するのに役立つツールがたくさんあることに気付きました。

20メガバイトのコードを1つのピースでチェックするのが通常のシナリオであり、そのツールをカスタムルールで拡張できるようにする必要があるため、パフォーマンスが必要です。そこで、JavaScriptを使用することにしました。

これまでのところ、 JisonとPEG.jsを使用できる2つのジェネレーターを見つけました。

それらのどれが私にもっと解析パフォーマンスを与えますか？たぶんライブラリを比較するのではなく、アルゴリズムを比較するのでしょうか？

どちらが私のニーズに適していますか（汎用プログラミング言語の解析）？

更新： 私は同様のQ＆Aを見つけました：

• Packrat解析とLALR解析
• パーサーのパフォーマンス：PEGとLALR（1）またはLL（k）

私は楽しみのためにGLRを書いています（前回の試行以来、いくつかのことを理解したためです）。パーサーは現在機能しており、曖昧性解消ルールを実装しています。私はうまくいくように見える方法で優先順位を処理しています。今、私は結合性に関して少し途方に暮れています。

私はこのような文法を持っているとしましょう：

ルール1）と2）の優先順位が同じで、結合性が残っている場合。

結合性の処理がない場合、文字列「1-1+0」は2つの解析ツリーを生成します。

ここで、数字は削減に使用されるルールを示します。正しい解析ツリーは最初のものであるため、これだけを保持したいと思います。

結合法則の侵害をアルゴリズムで効率的に検出する方法を考えています。

私が試したアプローチの1つは、最初のツリーの最上位ノードで、ルール2がルール1の子のリストのルール3の左側にあるのに対し、2番目のツリーではルール1がルール4の右側にあることを確認することでした。 2と1は左結合です。最初のツリーのみを保持します。

しかし、これは、より複雑な例ではそれほど遠くはありませんでした。このソリューションの制限は、別のツリーとの比較に基づいてのみツリーを破棄できることです。

このアプローチの洗練されたバージョンを使用して解決策を見つけることができると思いますか？標準的な方法は何ですか？

ウィキペディアのGLRの説明によると、「非決定論的で曖昧な文法を処理します」。ぶら下がっているelse問題 のように、あいまいな文法を視覚化することはできますが、あいまいではない非決定論的なCF文法とは何ですか？