这是如何语法LR(1)而不是SLR(1)？

Question

我有以下语法，据说是LR(1)，但没有SLR(1)：

S ::= a A x b A c_b_b d_a

A ::= d

我不明白这是为什么。你怎么证明这个？

Answer 1

我没有足够的声誉来评论上面的答案，而且我对这个问题有点晚了，但是.

我在其他地方看到过这个语法的例子，而OP实际上做了一个错误。它应该是：

S ::= A a\b A c_b_b d_a

A ::= d

也就是说，S的第一句是“Aa”，而不是“aA”。

在这种情况下，A的下列集合是{ $，a，c}，并且在状态8中存在单反冲突。

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(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.    [ $ ]

有趣的是，这里没有冲突！唯一可能的shift/reduce冲突处于状态(8)，但是这里没有冲突，因为shift操作是在a上，而减少是在$上。因此，这个语法实际上是SLR(1)。由于任何SLR(1)文法也是LR(1)，这意味着该语法既是SLR(1)又是LR(1)。

希望这能有所帮助！

Answer 3

我想写一个web应用程序来确定CFG的第一组和后续集，还有LR(0)、SLR(1)和LR(1)表。这样你就可以轻松地尝试了。

但幸运的是，我先搜索了一下，发现这样的工具已经存在了(我不一定认为是这样的)。您可以在这里找到该工具：

http://smlweb.cpsc.ucalgary.ca/

它期望输入的格式如下：

S -> a A | b A c | d c | b d a.
A -> d.

使用这个工具，我已经验证了其他人已经说过的话:所讨论的语法是SLR(1)。(我就这个问题给出-1 )。

经过Toby Hutton的修改，它不再是SLR(1)，而是LR(1)。