LR(0)、LL(0)、LALR(1) 等之间的关系？

Question

我真的很难理解之间的关系：

• LR(0)
• LL(0)
• LALR(1)
• 单反(1)
• LR(1)
• LL(1)

我很确定 LALR(1) 和 SLR(1) 是 LR(1) 的子集，但我不知道其他的。都是独家的吗？ LL(0) 是 LL(1) 的子集吗？

谢谢

Answer 1

收容规则如下：

• 每个 LR(0) 文法也是 SLR(1)，但并非所有 SLR(1) 文法都是 LR(0)。
• 每个 SLR(1) 文法也是 LALR(1)，但并非所有 LALR(1) 文法都是 SLR(1)。
• 每个 LALR(1) 文法也是 LR(1)，但并非所有 LR(1) 文法都是 LALR(1)。
• 每个 LL(1) 文法也是 LR(1)，但并非所有 LR(1) 文法都是 LL(1)。
• 每个 LL(0) 语法也是 LR(0)、SLR(1)、LALR(1)、LR(1) 和 LL(1)。 （LL(0) 文法基本上没用；see this question for details why）。

还有一种情况是，如果您对语法进行了结束标记，则每种具有 LR(1) 语法的语言也具有 LR(0) 语法，尽管不能保证语法是漂亮的。