parsing - LR(1) 解析器状态大小仍然是一个问题吗？

Question

从历史上看，LALR(1) 解析器比 LR(1) 解析器更受青睐，因为 LR(1) 解析器生成的大量状态需要资源。很难相信这仍然是当今计算环境中的一个问题。情况仍然如此，还是现代编译器现在使用规范的 LR 解析器构建，因为 LALR 语法是 LR 语法的真子集？

Answer 1

LR(1) 解析器的主要问题是表大小，而表大小会以某种方式造成损害。

如果您有一个具有 10,000,000 个状态(并非不常见)的 LR(1) 解析器，其中有 50 个非终结符和 50 个终结符(并非那么不合理)，那么您将拥有一个包含 10 亿个条目的表。如果每个条目使用一个字节，现在就需要 1GB 空间来保存该表。该空间要么位于应用程序二进制文件中，在这种情况下，您现在拥有 1GB 的可执行文件，要么它是动态生成的，在这种情况下，您现在需要 1GB RAM 加上填充它的时间。这些都不是很有吸引力。

如果你有这样的内存，你绝对可以使用 LR(1) 解析器，但这不是一个好主意。首先，应用程序二进制文件的大小将非常巨大。这将使应用程序的分发变得困难。其次，将表加载到内存中的操作需要将大约 1GB 的数据从磁盘传输到 RAM，这会非常慢。还有分页进出解析表的问题。如果操作系统不能很好地驱逐页面，您最终可能会陷入困惑，从而导致性能下降到令人无法接受的程度。

虽然您可以将解析器放在服务器上，但这通常不会立即完成，并且需要通过网络完成所有编译。

还有一个问题是它是否值得。解析器资源成本的巨大上升需要通过解析质量方面的一些比例优势来证明是合理的。实际上，LALR 解析器适用于许多语法。对于那些它不起作用的情况，IELR 或 GLR 等较新的解析算法将是比 LR(1) 更好的选择，因为它们提供相同的解析能力(或者在 GLR 的情况下更强)，同时显着减少空间。因此，您最好使用这些算法。

总之，是的，您今天可以使用 LR(1)，但它的资源效率非常低，因此您最好使用其他解析算法。

希望这有帮助!