为什么这种语法在LR(0)中减少/减少冲突？

Question

我有以下语法：

S -> a b D E
S -> A B E F
D -> M x
E -> N y
F -> z
M -> epsilon
N -> epsilon

我的教科书上说在LR(0)中有一个减少/减少冲突。我构建了一个图表，发现有一个状态：

S -> a b . D E
S -> A B . E F
D -> . M x
E -> . N y
M -> .
N -> .

教科书上说这是一种减少[减少]冲突。我想找出原因。如果构建SLR表，将得到以下行(3是上面的状态)：

​

​

那是因为

3.

• Follow(N)={y}
• 遵循(M)={x}，这样我们就可以从状态
• 简化为规则6，所以我们可以从状态3降为规则7。

我被教导说，如果有一个有S/R的单元格，就有一个冲突的S/R，如果有一个R/R的单元格，则是冲突的R/R，但是我在表中没有看到在同一个单元格中有两个R。那么，为什么这是一个减少/减少冲突呢？

Answer 1

您将显示一个SLR( 1 )解析表，其中的列对应于长度为1的前瞻性。它是正确的，并且没有冲突。

但是这里我们讨论的是一台LR(0)机器，它没有前瞻性。(这是LR(0)中的0)。机器所能做的唯一决定就是移动或减少，因为它不能使用前瞻性，所以只能使用状态本身。给定的状态必须是移位状态或减少状态(如果是减少状态，则是生产正在减少的状态)。

(如果它是令人困惑的，而且经常是这样的话，前瞻性的概念并不是指使用移位的符号来决定要转换到哪个状态。转换是基于移位符号进行的，该符号此时不再是前瞻性的一部分。)

因此，在这种状态下，不存在可能的shift操作；在项目集中的所有项中，点在末尾，或者下一个符号是非终端(表示从reduce返回后的GOTO操作)。

但是，国家并没有一个独特的削减。取决于前瞻，解析器需要选择减少M或减少N。由于没有前瞻性，所以不能做出决定，因此这是一个冲突。