7

LR(1) クロージャーをすばやく計算するために、Warshall のアルゴリズムを実装しようとしています。

LR（0）でどのように機能するかを理解していると思います：

  • グラフのノードは、次のようなLR アイテムです。A → B • C
  • エッジは、から始まる「トランジション」ですA → B • C。C → • D

問題は、LR(1) には先読みの計算が必要であり、それらをアルゴリズムに組み込む方法がわかりません。与えられた LR アイテムの推移閉包を知っ
ていたとしても、各アイテムの先読みセットが何であるかを理解するためだけに、同じ計算をすべて行う必要があるように思えます。

ウォーシャルのアルゴリズムを使用して正規の LR(1) クロージャーを計算することは可能ですか?それとも、より制限されたケース (LR(0)、SLR(1) など) でのみ可能ですか?

4

1 に答える 1

2

新しいアイテムを追加するたびに、他のアイテムを追加する必要がある可能性があるため、これにウォーシャルのアルゴリズムを使用できるとは思いません。これは反復プロセスです。有向グラフまたは接続マトリックスは変化し続けます。私はこれについて間違っている可能性があります。クロージャー セットに既に含まれているアイテムの配列を保持しながら、反復プロセスで LR(1) アイテム セットのクロージャーを計算しました。私のLRSTAR パーサー ジェネレーターをダウンロードして、独自のパーサー ジェネレーターを作成する必要がないと判断することもできます。注: 先読みセットの計算には、Warshall のアルゴリズムではなく、DeRemer の論文の Digraph アルゴリズムを使用しました。LRSTAR に実装されている論文のリストを参照してください。

于 2014-05-13T05:17:27.313 に答える