parsing - この文法LR（1）はどうですか？SLR（1）ではありませんか？

Question

私は次の文法を持っていますが、それはLR（1）ですが、SLR（1）ではないと言われています。

S :: = a A | b A c | dc | bda

A :: = d

なぜなのかわかりません。これをどのように証明しますか？

Answer 1

上記の回答についてコメントするほどの評判はありません。この質問には少し遅れていますが...

私はこの文法を他の場所の例として見てきました.OPは実際にタイプミスをしました. そのはず：

S ::= A a | b A c | 直流 | bda

あ::= 日

つまり、 Sの最初の節は、'a A ' ではなく、' A a ' です。

この場合、 A に設定された FOLLOWS は { $, a, c} であり、状態 8 で SLR 競合が発生します。

Answer 2

これを理解する1つの方法は、文法のLR（1）およびSLR（1）パーサーを構築することです。その過程でシフト/削減または削減/削減の競合が見つかった場合、文法がこれらのクラスの言語の1つに属してはならないことを示すことができます。

SLR（1）パーサーから始めましょう。まず、文法のLR（0）構成セットを計算する必要があります。これらはここに見られます：

(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda

(2)
S -> a.A
A -> .d

(3)
S -> aA.

(4)
A -> d.

(5)
S -> b.Ac
S -> b.da
A -> .d

(6)
S -> bA.c

(7)
S -> bAc.

(8)
S -> bd.a
A -> d.

(9)
S -> bda.

(10)
S -> d.c

(11)
S -> dc.

次に、すべての非終端記号のFOLLOWセットを取得する必要があります。これはここに示されています：

FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }

これを前提として、戻ってLR（0）構成セットをSLR（1）構成セットにアップグレードできます。

(1)
S -> .aA    [ $ ]
S -> .bAc   [ $ ]
S -> .dc    [ $ ]
S -> .bda   [ $ ]

(2)
S -> a.A    [ $ ]
A -> .d     [ $, c ]

(3)
S -> aA.    [ $ ]

(4)
A -> d.     [ $, c ]

(5)
S -> b.Ac   [ $ ]
S -> b.da   [ $ ]
A -> .d     [ $, c ]

(6)
S -> bA.c   [ $ ]

(7)
S -> bAc.   [ $ ]

(8)
S -> bd.a   [ $ ]
A -> d.     [ $, c ]

(9)
S -> bda.   [ $ ]

(10)
S -> d.c    [ $ ]

(11)
S -> dc.    [ $ ]

興味深いことに、ここでは競合はありません。考えられる唯一のシフト/リデュースの競合は状態（8）にありますが、シフトアクションがオンaで、リデュースがオンになっているため、ここでは競合はありません$。したがって、この文法は実際にはSLR（1）です。すべてのSLR（1）文法もLR（1）であるため、これは、文法がSLR（1）とLR（1）の両方であることを意味します。

お役に立てれば！