因此,一个消息来源说是,另一个消息来源说不是
有消息来源这样说:
另一个人这样说:
我找到的最接近的答案是:
Relationship between LR(0), LL(0), LALR(1), etc?
但这并不能回答 LL(1) 和 LALR(1) 之间的关系
另外如果你能回答更一般的问题,即 LL(k) 和 LALR(k) 之间的关系是什么,那会更有帮助
谢谢。
最佳答案
明确的答案(至少在 SE 网络上)可以在 answer 中找到。在 computing science网站,解析理论问题可能会吸引更好的回答。
在阅读该答案中的图表时,请注意语法的包含关系和语言的包含关系之间存在差异。最明显的例子之一是所有 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's Modern Compiler Implementation textbook中有一个练习它提供了一个 LL(1) 语法的示例,该语法不是 LALR(1);你可以在this answer中找到转录的语法。 。这应该提供如何构造 k > 1 的示例的想法。(查找不是 LL(k) 的 LALR(k) 语法很简单:您需要的只是左递归。)
关于parsing - 每个 LL(1) 文法也是 LALR(1) 文法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49493005/