では、GLRパーサジェネレータを作成したいと思います。私はおそらく私が作るものよりも優れたそのようなプログラムが存在することを知っていますが、私は楽しみ/学習のためにこれを行っているので、それは重要ではありません。
私はGLR解析について読んでいますが、今ではそれについてかなり高いレベルで理解していると思います。しかし今、ビジネスに取り掛かる時が来ました。
グラフ構造化スタック（GSS）は、GLRパーサーで使用するための主要なデータ構造です。概念的にはGSSがどのように機能するかは知っていますが、これまでに調べたソースのいずれも、GSSの実装方法を説明していません。サポートする操作の信頼できるリストすらありません。誰かがGSSの良いサンプルコード/チュートリアルを教えてもらえますか？グーグルは今のところ助けにはならなかった。この質問が曖昧すぎないことを願っています。
まず、GLR に関する McPeak の論文http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.psをお読みください。これは学術論文ですが、GSS、GLR、およびそれらの実装に使用される手法について詳しく説明しています。また、GLR パーサーの実装に関する厄介な問題についても説明しています。
グラフ構造のスタックを実装するには、3 つの部分があります。
I. グラフのデータ構造自体
Ⅱ．スタック
III. GLR による GSS の使用
そうです、グーグルはあまり役に立ちません。また、アルゴリズムの本を読むのが好きでない限り、それらもあまり役に立ちません。
I. グラフのデータ構造
「直接表現」に関するロブの答えは、実装が最も簡単です。各ノードが 1 つだけではなく次のノードのリストを持っている点を除いて、これはリンク リストによく似ています。
このデータ構造は有向グラフですが、McPeak が述べているように、GSS にはイプシロン文法の循環がある可能性があります。
Ⅱ．スタック
グラフ構造のスタックは、概念的には通常のスタックの単なるリストです。明確な文法の場合、必要なスタックは 1 つだけです。解析の競合がある場合は、両方の解析アクションを同時に実行し、両方のアクションが作成する異なる状態を維持できるように、より多くのスタックが必要です。グラフを使用すると、これらのスタックが要素を共有するという事実を利用できます。
最初に、リンクされたリストを使用して単一のスタックを実装する方法を理解しておくと役立つ場合があります。リンクされたリストの先頭は、スタックの一番上です。要素をスタックにプッシュすることは、新しいヘッドを作成し、それを古いヘッドに向けるだけです。要素をスタックからポップすることは、ポインターを head->next に移動するだけです。
GSS の場合も、原則は同じです。要素のプッシュは、新しいヘッド ノードを作成し、それを古いヘッドに向けるだけです。2 つのシフト操作がある場合は、2 つの要素を古いヘッドにプッシュし、2 つのヘッド ノードを作成します。概念的には、これはトップのものを除くすべての要素を共有する 2 つの異なるスタックです。要素のポップとは、次の各ノードをたどることによって、ヘッド ポインターをスタックの下に移動することです。
III. GLR による GSS の使用
これは、McPeak の論文が役立つところです。
GLR アルゴリズムは、同じ状態要素を持つスタック ヘッドをマージすることで、GSS を利用します。これは、1 つの状態要素が複数の子を持つ可能性があることを意味します。削減する場合、GLR アルゴリズムはスタック ヘッドからすべての可能なパスを探索する必要があります。
各ノードの決定論的な深さを維持することで、GLR を最適化できます。これは、スタック内のスプリットからの距離です。このようにして、スタック分割を常に検索する必要はありません。
これは大変な作業です！とても幸運！
あなたが尋ねている質問は些細なことではありません。これを行う主な方法は 2 つあります。
直接表現。データ構造はメモリ内でノード オブジェクト/構造として表されます。各ノードには、スタック上のその下の構造体への参照/ポインターがあります (代わりに、参照を双方向にすることもできます)。これは、リストとツリーがメモリ内で通常表現される方法です。この場合はもう少し複雑です。なぜなら、ツリーを追跡するためにルート ノードまたはヘッド ノードへの参照を維持するだけでよいツリーやリストとは異なり、ここではすべての参照のリストを維持する必要があるからです。 「最上位」ノード。
隣接リストの表現。これは、数学者がグラフについて考える方法に似ています: G = (V, E)。各エッジの始点と終点である頂点によってインデックス付けされたエッジのリストを維持します。
最初のオプションには、GSS がフラットになりすぎない限り、トラバーサルを高速化できるという利点があります。しかし、構造は操作が少し難しくなります。多くの独自のアルゴリズムをロールバックする必要があります。
2 番目のオプションには、より簡単に操作できるという利点があります。教科書のほとんどのアルゴリズムは、ある種の隣接リスト表現を想定しているようです。これにより、豊富なグラフアルゴリズムを簡単に適用できます。
いくつかのリソース:
ハッシュ テーブル ベース、配列ベースなど、さまざまなタイプの隣接リストがあります。ウィキペディアの隣接リストページは、開始するのに適した場所です。
これは、同じ問題に取り組んでいる誰かからのブログ投稿です。コードは clojure であり、なじみがあるかもしれないし、なじみがないかもしれませんが、たとえそうでなくても、議論は一見の価値があります。
この種のモデルが広く適用されていることを考えると、有向非巡回グラフ (または、必要に応じてグラフ構造化スタック) を表すことについて、より多くの情報があればいいのにと思います。より良い解決策が見つかる余地があると思います。