7

我有以下语法，我被告知是 LR(1) 但不是 SLR(1)：

S ::= 一个A | b A c | 直流| bda

一个::= d

我不明白为什么会这样。你将如何证明这一点？

4

4 回答 4

12

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

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

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

一个::= d

即，S的第一个子句是' A a'，而不是'a A '。

在这种情况下，A 的 FOLLOWS 集是 { $, a, c} 并且在状态 8 中存在 SLR 冲突。

于 2013-04-23T06:13:24.023 回答
10

One way to figure this out would be to try to construct LR(1) and SLR(1) parsers for the grammar. If we find any shift/reduce or reduce/reduce conflicts in the course of doing so, we can show that the grammar must not belong to one of those classes of languages.

Let's start off with the SLR(1) parser. First, we need to compute the LR(0) configurating sets for the grammar. These are seen here:

(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.

Next, we need to get the FOLLOW sets for all the nonterminals. This is shown here:

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

Given this, we can go back and upgrade the LR(0) configurating sets into SLR(1) configurating sets:

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

Interestingly enough, there are no conflicts here! The only possible shift/reduce conflict is in state (8), but there is no conflict here because the shift action is on a and the reduce is on $. Consequently, this grammar actually is SLR(1). Since any SLR(1) grammar is also LR(1), this means that the grammar is both SLR(1) and LR(1).

Hope this helps!

于 2012-07-02T21:32:53.963 回答
1

我考虑编写一个网络应用程序来确定 CFG 以及 LR(0)、SLR(1) 和 LR(1) 表的第一组和后一组。这将使您可以轻松地尝试一下。

但幸运的是我先google了一下，发现已经有这样的工具了（我没想到会是这样）。您可以在此处找到该工具：

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)。

于 2018-04-22T08:47:07.043 回答
0

1）给定的语法在自顶向下解析中为LL(1)，在自底向上解析中为LALR(1)。

2）当您创建解析表时，并且解析表没有多个条目，那么语法往往会参加 LALR(1)。

3）如果您的解析表有多个条目（我的意思是发生冲突），则该语法被称为 SLR(1)。

4）一个语法被称为LR（1），因为它的解析表或ACTION / GOTO表没有冲突，我们都知道在LR（1）发生冲突期间我们合并数据并得到LALR。

LR(0) OR SLR OR SLR(1) 相同

LR(1) OR CLR 相同

LALR 或 LALR(1) 相同

(1) 参数定义语法分析器的内部构建效率类型。

谢谢你。

于 2019-04-14T14:01:35.197 回答