每个 LL(1) 文法也是 LALR(1) 文法吗？

Question

所以一位消息人士说是，另一位消息人士说不是

一位消息人士说：

另一个说：

我找到的最接近的答案是：

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

但这并不能回答 LL(1) 和 LALR(1) 之间的关系

此外，如果您能回答更一般的问题，即 LL(k) 和 LALR(k) 之间的关系，那将更有帮助

谢谢。

Answer 1

明确的答案（至少在 SE 网络上）可以在 计算科学网站的这个答案中找到，其中解析理论问题可能会吸引更好的回应。

在阅读该答案中的图表时，请注意语法的包含关系和语言的包含关系之间存在差异。最明显的例子之一是所有 LR(k) 语法都可以机械地转换为 LR(1) 语法，因此 LR 语言只有两类： LR(0) 和 LR(1) 。（事实上​​，您可以将 LR(k) 语言简化为 SLR(1)，因此各种算法差异也在语言级别消失。）另一方面，LL(k) 语言是严格的包含层次结构。LL(k) 语言（对于有限 k）的并集是 LR(1) 的严格子集。

但对于语法来说，这些关系就没那么简单了。显然，LL(k)、LR(k)、LALR(k)、SLR(k) 等直观地形成层次结构，因为不需要使用所有先行信息，并且因为对于任何语法都可以添加需要 k+1 次前瞻的产生式（对于 LL 和 LR 算法）。

LL(k) 文法必然是 LR(k) 但不一定是 LALR(k)。Appel 的《现代编译器实现》教科书中有一个练习，提供了一个 LL(1) 语法的示例，该语法不是 LALR(1)；您可以在这个答案中找到转录的语法。这应该提供如何构造 k > 1 的示例的想法。（查找不是 LL(k) 的 LALR(k) 语法很简单：您需要的只是左递归。）