LL（1）不能解析语法，而LR（1）不能解析语法吗？

Question

关于作业，我得到了以下语法：

S: B
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: ., a,b
B: ., a,b

如果创建表格，您将清楚地看到项目集中的A和B之间存在减少-减少冲突。如果要求我解析字符串“ ab”，则解析器将不知道是否要将我的空值减少为A或将其减少为B。我在做什么错？经常有人告诉我LR（1）实际上可以解析比LL（1）更多的语法，那么这有什么用呢？如果有人可以帮助我，我将不胜感激，因为这使我发疯。谢谢

Answer 1

您生成的状态来自SLR(1)解析器。如果使用LR(1)甚至LALR(1)，您将发现没有冲突。

例如，这是LALR(1)机器的状态0，由Bison生成（将第一个产生的值校正为S: D之后：]]]

状态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

---

[通常，LL(1) ⊂ LR(1)当然是正确的，但是LL(1)与SLR(1)或LALR(1)之间没有简单的关系。 （我在这里谈论语法。对于语言集，关系更简单。）您的语法是LL(1)语法的相当简单的示例，而不是SLR(1)；有关不是LL(1)的LALR(1)语法的示例，请参见[此答案]（不是LL(1)的SLR(1)语法）。