这个语法LR(1)怎么样而不是SLR(1)？

Question

我有以下语法,我被告知是LR(1)而不是SLR(1):

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

A :: = d

我不明白为什么会这样.你会怎么证明这一点？

Answer 1

我没有足够的业力来评论上面的答案,我对这个问题有点迟,但......

我在其他地方看过这个语法就是一个例子,OP实际上是一个错字.它应该是:

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

A :: = d

即,S的第一个条款是' A a',而不是'a A '.

在这种情况下,为A设置的FOLLOWS是{$,a,c},并且状态8中存在SLR冲突.

Answer 2

解决这个问题的一种方法是尝试为语法构造LR(1)和SLR(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).

希望这可以帮助!