1

对于家庭作业，我得到了以下语法：

S: D
D: AbBb | BaAb
A: ε 
B: ε

我用 LL(1) 计算得很好。第一组是：

S: a, b
D: a,b
A: ε 
B: ε

以下套装是：

S: $
D: $
A: b
B: a,b

当我制作解析表时，示例字符串“ab”解析得很好。但是，当我尝试使用 LR(1) 解析相同的语法时，我遇到了错误。

对于项目集 0，我得到以下信息：（ , 分隔前瞻终端）

Item set 0:

S: .D, $
D: .AbBb, $ 
D: .BaAb, $
A: ., b
B: ., a,b

如果你做表，你会清楚地看到项目集0中A和B之间存在reduce-reduce冲突。如果要求我解析字符串“ab”，解析器将不知道是否要减少我的空到A或减少到B。我做错了什么？我总是被告知 LR(1) 实际上可以解析比 LL(1) 更多的语法，那么这里有什么问题呢？如果有人可以帮助我，我将不胜感激，因为这让我发疯。谢谢

4

1 回答 1

2

他们说您生成的看起来像是从SLR(1)解析器生成的。

如果你使用LR(1)or even LALR(1)，你会发现没有冲突。例如，这里是LALR(1)机器的状态 0，由 Bison 生成：

状态 0

0 $accept: . S $end
1 S: . D
2 D: . A 'b' B 'b'
3  | . B 'a' A 'b'
4 A: . %empty  ['b']
5 B: . %empty  ['a']

'a'       reduce using rule 5 (B)
$default  reduce using rule 4 (A)

S  go to state 1
D  go to state 2
A  go to state 3
B  go to state 4

虽然确实如此，但and 或orLL(1) ⊂ LR(1)之间没有简单的关系。（我在这里谈论语法。对于语言集，关系更简单。）您的语法是一个相当简单的语法示例，它不是; 有关不是的语法示例，请参阅此答案。LL(1)SLR(1)LALR(1)LL(1)SLR(1)LL(1)LALR(1)

于 2019-11-04T21:10:36.493 回答