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

Question

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

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

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

Answer 1

我尝试使用 SLR 算法创建自动机。如下所示，状态 1 和先行符号 + 存在移位归约冲突。您可以看到状态 1 和 4 的项目集。

在状态 1 中，存在项 r3: Y -> b .，因此正确的操作是使用第三条规则进行归约。

但是，状态 1 也包含该项目

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

这会导致自动机中同一单元格发生一次正确的移位和一次正确的归约操作，从而产生移位归约冲突。

我看不到归约-归约冲突。

每个规则的所有项目

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