Shift-Reduce和Reduce-Reduce示例和一个已解决的示例？

Question

在对以下语法的简单优先解析(分解)中，我们有shift-reduce和reduce-reduce冲突。X是开始符号，X'-->$X$是添加的规则。此外，+和lower symbol是终端。

X'-->$X$
X-->Y | X + a
Y-->b | b + Y

问:我的助教是如何解决这个问题并解决shift-reduce和reduce-reduce冲突的？有什么解决这个问题的步骤吗？这对我来说太含糊了！也许有错误的答案。

Answer 1

我尝试使用SLR算法创建自动机。如下所示，状态1和前瞻符号+之间存在shift-reduce冲突。您可以看到状态1和4的项目集。

在状态1中，有项r3: Y -> b .，因此正确的操作应该是使用第三个规则来减少。

但是，状态1也包含项

• r4: Y -> b . + Y，，而状态4包含item
• r4: Y -> b + . Y，，因此另一个正确的操作是转换到状态4。

对于自动机中的同一个单元格，这会导致一个正确的shift和一个正确的reduce操作，从而产生shift-reduce冲突。

我看不到reduce-reduce冲突。

每个规则的所有项目

r0: root -> . X EOF
r0: root -> X . EOF
r0: root -> X EOF .

r1: X -> . Y
r1: X -> Y .

r2: X -> . X + a
r2: X -> X . + a
r2: X -> X + . a
r2: X -> X + a .

r3: Y -> . b
r3: Y -> b .

r4: Y -> . b + Y
r4: Y -> b . + Y
r4: Y -> b + . Y
r4: Y -> b + Y .

自动机

    +   a   b   EOF X   Y
0:          s1      2   3
1:  inv         r3      
2:  s5          acc     
3:  r1          r1      
4:          s1          6
5:      s7              
6:  r4          r4      
7:  r2          r2      

冲突

shift/reduce conflict for state 1 and symbol +: s4 r3
s1
r4: Y -> b . + Y
r3: Y -> b .

s4
r4: Y -> b + . Y
r3: Y -> . b
r4: Y -> . b + Y