parsing - イプシロン遷移を伴う左再帰LR（0）アイテムのクロージャとは何ですか？

Question

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

A: ε
 | B 'a'
B: ε
 | B 'b'

アイテムの閉鎖とは何と見なされますA: • B 'a'か？
言い換えれば、クロージャを理解するときにイプシロン遷移をどのように処理しますか？

Answer 1

これは非常に簡単です。の閉鎖に含まれる

    A = ... <dot> X ... ;

すべてのルールです

    X =   <dot> R1 R2 R3 ... ;

ここで、first（R1）は空ではありません。first（R1）の（空でない）トークンKごとに、（推移的に！）含める必要があります

    R1 = <dot> k ... ;

などですが、おそらくあなたはすでにこれを明確にしています。

あなたの具体的な質問は、R1が空になる可能性がある場合はどうなるかということです。次に、含める必要があります

    X =   R1 <dot> R2 ... ;

同様に、R2が空の場合、R1が空になる可能性があり、Riが空の場合、R1..Ri-1が空になる可能性があります。極端な状況では、すべてのRiが空になる可能性があり（文法にオプションの副次句がたくさんあります）、最終的には次のようになります。

    X =  R1 R2 ... Rn <dot> ;

first（R1）を「空にすることができる」と判断すること自体が推移閉包の質問であることに注意してください。

DMS用に構築したGLRパーサージェネレーターは、Warshallのアルゴリズムを使用してfirst_can_be_emptyを事前計算し、それをクロージャー構築で使用します。