从历史上看，LALR(1) 解析器优于 LR(1) 解析器，因为 LR(1) 解析器生成的大量状态需要资源。很难相信这仍然是当今计算环境中的一个问题。由于 LALR 语法是 LR 语法的适当子集，现在仍然是这种情况还是现代编译器是使用规范的 LR 解析器构建的？
2 回答
5
LR(1) 解析器的主要关注点是表的大小，而表的大小会以一种或另一种方式受到伤害。
如果你有一个 LR(1) 解析器，它有 10,000,000 个状态（不是很常见），其中有 50 个非终结符和 50 个终结符（不是那么不合理），你将有一个包含十亿个条目的表。如果每个条目甚至使用一个字节，现在就需要 1GB 的空间来保存表。该空间要么在应用程序二进制文件中，在这种情况下您现在有一个 1GB 的可执行文件，或者它是动态生成的，在这种情况下您现在需要 1GB 的 RAM 加上填充它的时间。这些都不是很有吸引力。
如果你有那种内存，你绝对可以使用 LR(1) 解析器，但这不是一个好主意。首先，应用程序二进制文件的大小将是巨大的。这将使分发应用程序变得困难。其次，将表加载到内存中需要将大约 1GB 的数据从磁盘传输到 RAM，这会非常慢。还有解析表的分页进出问题。如果操作系统不能很好地驱逐页面，您最终可能会颠簸，性能下降到无法接受的程度。
虽然您可以将解析器放在服务器上，但这通常不会现在完成，并且需要通过网络完成所有编译。
还有是否值得的问题。解析器资源成本的巨大飙升需要通过解析质量的一些成比例的好处来证明。在实践中，LALR 解析器适用于许多语法。对于那些它不适用的人来说，像 IELR 或 GLR 这样的新解析算法将是 LR(1) 的更好选择，因为它们提供了相同的解析能力（或者在 GLR 的情况下更多），并且显着减少了空间。因此，您最好使用这些算法。
总之，是的，你现在可以使用 LR(1)，但是它的资源效率太低了，你最好使用另一种解析算法。
希望这可以帮助！
于 2014-06-12T05:43:44.177 回答
4
Minimal LR(1) 解析器解决了这个问题。Pager 博士是第一个在 1977 年写一篇关于如何做到这一点的论文的人。最小 LR(1) 解析器具有规范 LR(1) 解析器的所有功能，可以识别由 LR(1) 语法定义的相同语言。但是，最小 LR(1) 解析器的解析器表几乎与 LALR(1) 解析器表一样小。
所需的技巧是在构建规范的 LR(1) 状态机时合并兼容状态。这很复杂，并且前瞻集计算与 LALR(1) 一样复杂。但最终的结果是美丽的。
顺便说一句，LRSTAR 解析器生成器创建了最小的 LR(1) 和最小的 LR(k) 解析器，非常强大。
于 2017-03-20T23:24:09.720 回答