历史上，由于LR(1)分析器生成大量状态所需的资源要求，LALR(1)分析器比LR(1)分析器更受欢迎。很难相信这在今天的计算环境中仍然存在问题。现代编译器是否使用规范LR分析器构建，因为LALR语法是LR语法的一个子集？
LR(1)解析器状态大小仍然是一个问题吗？
7
- tgoneil
9
2据我所知，仍然是LALR(1)。考虑到语法类别的微小差异，实际上没有理由支付额外的空间成本，这个成本大约是数量级的。 - user207421
相对空间成本是一个问题。许多年前，我和弗兰克·德雷默（啊咳）在课堂上，有人问他这个未来学问题——当内存变得如此之大时会发生什么——他说这仍然不值得。他还说，使用巨大的LR表对缓存一致性来说也是一个性能问题。 - user207421
好的，在支持多个客户端的服务器环境中，这尤其有意义。谢谢。 - tgoneil
除非你在谈论基于NFA正则表达式的解析器，否则你绝对不必担心状态。任何其他使用过多资源的解析器要么不是手写的，要么格式本来就很复杂。 - Leopold Asperger
@ESP 我没有混淆任何事情。你可能会说扫描器和解析器总是分开的程序，但在我的经验中，大多数真实的实现同时具有这两个特征，这样才能达到最佳性能。但我不打算进入解析器/词法分析器/扫描器的讨论。 - Leopold Asperger
显示剩余4条评论
2个回答
6
LR(1)解析器的主要问题是表格大小，而且表格大小会以某种方式对其造成伤害。
假设您拥有一个具有1000万个状态（并不罕见）的LR(1)解析器，在其中有50个非终端符和50个终端符（也不算不合理），那么您将拥有一个包含10亿个条目的表格。如果每个条目使用了一个字节，现在你需要1GB的空间来保存这个表格。这个空间或者在应用程序二进制文件中，这样你就有了一个1GB的可执行文件，或者是动态生成的，这样你现在需要1GB的RAM加上填充时间。这两种情况都不是很吸引人。
当然，如果你有那么多的内存，你绝对可以使用LR(1)解析器，但这不是一个好主意。首先，应用程序二进制文件的大小将是巨大的。这将使分发应用程序变得困难。其次，将表格加载到内存中的行为将需要将大约1GB的数据从磁盘转移到RAM中，这将是极其缓慢的。还存在分页解析表格的问题。如果操作系统不能很好地逐出页面，你可能会遇到交换现象，导致性能不可接受的下降。
虽然您可以将解析器放在服务器上，但目前通常不这样做，并且需要在网络上完成所有编译。
还有一个问题是是否值得。解析器所需的资源成本的急剧增加必须通过某种比例上的解析质量获得证明。实际上，LALR解析器可以适用于许多语法。对于它无法处理的语法，像IELR或GLR这样的新解析算法将是LR(1)的优良选择，因为它们提供相同的解析能力（在GLR的情况下更多）并显著减少了空间占用。因此，你最好使用那些算法。
总之，是的，您今天可以使用LR(1)，但它的资源效率如此低下，以至于您最好使用另一种解析算法。希望这可以帮助到您！
假设您拥有一个具有1000万个状态（并不罕见）的LR(1)解析器，在其中有50个非终端符和50个终端符（也不算不合理），那么您将拥有一个包含10亿个条目的表格。如果每个条目使用了一个字节，现在你需要1GB的空间来保存这个表格。这个空间或者在应用程序二进制文件中，这样你就有了一个1GB的可执行文件，或者是动态生成的，这样你现在需要1GB的RAM加上填充时间。这两种情况都不是很吸引人。
当然，如果你有那么多的内存，你绝对可以使用LR(1)解析器，但这不是一个好主意。首先，应用程序二进制文件的大小将是巨大的。这将使分发应用程序变得困难。其次，将表格加载到内存中的行为将需要将大约1GB的数据从磁盘转移到RAM中，这将是极其缓慢的。还存在分页解析表格的问题。如果操作系统不能很好地逐出页面，你可能会遇到交换现象，导致性能不可接受的下降。
虽然您可以将解析器放在服务器上，但目前通常不这样做，并且需要在网络上完成所有编译。
还有一个问题是是否值得。解析器所需的资源成本的急剧增加必须通过某种比例上的解析质量获得证明。实际上，LALR解析器可以适用于许多语法。对于它无法处理的语法，像IELR或GLR这样的新解析算法将是LR(1)的优良选择，因为它们提供相同的解析能力（在GLR的情况下更多）并显著减少了空间占用。因此，你最好使用那些算法。
总之，是的，您今天可以使用LR(1)，但它的资源效率如此低下，以至于您最好使用另一种解析算法。希望这可以帮助到您！
- templatetypedef
4
是的，我们已经知道LR（1）解析器生成了大量状态。问题的关键是这是否是今天的实际问题。现代笔记本电脑和计算机具有超过8GB的内存，并且速度非常快。因此，在单个用户环境中，时间和空间不应该是问题。这就是我首先提出问题的原因。另一方面，服务器环境必须与许多用户共享资源，这使得更加迫切地需要高效利用资源，因此需要实现LALR。 - tgoneil
@tgonelli 为什么我们要在服务器环境中运行编译器？ - user207421
@tgoneil 我已经更新了我的答案以回答你的问题。你可以看一下并决定这是否有所帮助？ - templatetypedef
@templatetypedef，谢谢您提供的关于我可以研究的替代解析算法，例如IELR和GLR的提示。 - tgoneil
4
最小LR(1)解析器可以解决这个问题。1977年，Pager博士是第一个撰写有关如何做到这一点的论文的人。最小LR(1)解析器具有规范LR(1)解析器的所有功能，可以识别由LR(1)语法定义的相同语言。然而，最小LR(1)解析器的解析表几乎与LALR(1)解析表一样小。
所需技巧是在构建规范LR(1)状态机时合并兼容状态。这很复杂，向前看集合计算与LALR(1)一样复杂。但最终结果是美丽的。
顺便说一下，LRSTAR Parser Generator创建最小LR(1)和最小LR(k)解析器，非常强大。
所需技巧是在构建规范LR(1)状态机时合并兼容状态。这很复杂，向前看集合计算与LALR(1)一样复杂。但最终结果是美丽的。
顺便说一下，LRSTAR Parser Generator创建最小LR(1)和最小LR(k)解析器，非常强大。
- user1524750
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接