LR解析器相对于LL解析器“在今天”的“实际”优势是什么？

Question

我的英语能力很差，因为我不是说英语的人。请理解。

我写这篇文章是因为我想讨论这个话题。

我认为LR解析器与LL解析器相比没有“实际”优势。许多工具使用LR解析器这一事实并不是一个有效的优势。

我认为实际优势的标准如下。

1. 速度(快速->实用，慢->不切实际)
2. 错误恢复(容易的->实用，困难的->不切实际)
3. 编译器错误显示的方便性(容易->实用，困难->不实用)
4. 解析器开发的成本(简单的->实用，困难的->不切实际)

我认为LL解析器和LR解析器的速度没有太大的不同。LR解析器比LL解析器速度快得多，因为过去的硬件性能很低。但在今天，LR解析器的速度还不够快，无法比LL解析器更快。另外，在今天，其他因素对速度的影响也更大。我强调的是“在今天”，是的，我认为过去的优势是毫无意义的。

所以我认为在速度上没有明显的差别。

在2,3,4特性上，LL解析器优于LR解析器。LR解析器的典型缺点是错误处理困难。这导致外部程序(例如: IDE)难以显示有用的错误。此外，编写LL解析器比LR解析器简单。这意味着开发成本低于LR解析器。

“我猜”clang编译器考虑了这一点(错误处理方便，开发成本)，并使用了LL(k)算法。许多现代的解析器生成器，包括clang编译器，都使用LL(k)；另一方面，基于LR的编译器和解析器生成器很久以前就已经创建了，并且一直更新到现在。

我认为这一现象使趋势开始从LR向LL转变。

以往的人工智能算法由于硬件性能低下而失效，但随着硬件性能的提高，AI算法显示出真正的价值。

同样的，在过去，硬件的性能很低，所以算法的速度是最重要的，所以必须加快速度。结果表明，LR解析器非常有用。但是“在今天”，我认为速度并不是唯一重要的东西，因为硬件的性能是如此之高。

我认为LR解析器相对于LL解析器的优势仅仅是速度，速度优势也不是很大。我认为，由于硬件性能的提高，LR解析器的唯一优点会随着时间的推移而降低。

我想知道LR比LL解析器“在今天”有什么“实际”的优势？

感谢您的阅读。

Answer 1

真正的LL解析器是快速和简单的-但也完全不能解析许多有趣的语言。许多真实世界的编程语言都在LALR类中，它与LR密切相关，但可以更有效地进行解析。这些不同的方法，如LL、LALR、LR，不仅是不同的算法，而且还对应着一组可以被解析的不同语言。

例如，让我们考虑使用以下简单语法的算术表达式：

Expr ::= Expr "+" Term;
Expr ::= Term;
Term ::= Term "*" Factor;
Term ::= Factor;
Factor ::= Var;
Factor ::= Num;

此语法将将输入x * 3 + 2转换为解析树Expr(Term(Term(Factor(Var(x)), "*", Factor(Num(3))), "+", Term(Factor(Num(2))))。

虽然LL(k)能够识别这种语言，但它不能生成正确的解析树，因为它不能直接处理左递归生成。在使用LL解析器的情况下，这通常需要对解析树进行大量的后处理，以获得输入的有用表示。此外，修改语法以适应LL的限制是非常繁琐的，尽管一些解析器生成器可以自动完成这一任务。而且要明确一点: LR也有一些限制，语法需要写在周围。

所以没有人真正使用LL解析器。它们看起来很简单，但通常会带来比它们解决的更多的问题。对大多数语言来说，它们是不实用的。

经常使用的是递归下降或聚乙二醇(=形式化RecDesc)。它们与LL密切相关，因为它们的解析树是最左边的派生，但具有重要的扩展。

第一，选择的概念。LL(k)需要选择具有常量前瞻性的下一个产品，LL(*)具有无限的前瞻性，但只能使用常规语言(它甚至不能检测到平衡括号…)。相反，RecDesc和PEG使用了一个有序的选择:首先尝试这个产品，如果它不成功就回溯到另一个选择。这在实践中效果很好，但会导致指数最坏的时间复杂度。PEG可以限制这一点，并且有一个Packrat优化，允许进行时空权衡。

其次，这些解析器通常不是纯自上而下的解析器.通常使用自下而上的解析器扩展RecDesc解析器以进行表达式解析(例如使用分流场)，或者将聚乙二醇与Pratt分析器结合用于表达式。毕竟，语法中的任何终端都可以是自上而下解析器中自己嵌套的子语言。

第三，RecDesc和PEG的“计算”方法允许直接与副作用交互。在某些语言(如Perl或C++ )中，正确的解析取决于符号表的当前状态。虽然Perl扩展了Yacc生成的LR解析器，但大多数C++解析器现在都是RecDesc解析器。

Answer 2

现在，不管你是喜欢LL还是LR，还是其他解析器，都不重要了。设计程序设计语言的人不太关心将他们的语言强制到语法中(不再)。解析器不仅解析语言，还能合理地成功地解析语言和许多不正确的版本。

他们不介意使用模棱两可的语法，并在其中添加额外的规则。最简单的例子是许多语言中含糊不清的if-if-else。查看支持嵌套/*注释的语言*/。突然使语言的空白敏感的多行字符串。

但重要的是，解析是新编程语言中微不足道的一部分。还有其他真正的问题。

Answer 3

• LL是一种自顶向下，深度优先的算法。
• LR是一种自下而上、宽度优先的算法。

他们都有他们的用途，他们都有自己的问题。

声称一个人比另一个人高人一等，既傲慢又愚蠢。

LL解析器把他们想要的目标分解成子目标，然后冲洗和重复。

• 它很好地映射到函数/调用堆栈，所有主流语言都支持它，这样手工实现就更容易了。
• 这是伟大的，当类似的文本字符串有不同的含义基础上，在展开发生的地方。
• 但是，在构造不当的文法中，它确实会导致无限的展开循环。
• 最不期望的输入是要生成的最后一个扩展。

LR解析器从输入生成到输出。冲洗并重复，直到输入无法还原为止。

• 这确实确保了算法最大运行时的上限。
• 但是，它可能导致必须考虑的状态，特别是当类似的文本字符串有不同的含义时，根据它们发生在什么地方(也是一个糟糕语法的症状)。
• 在许多主流语言中，动态编程也没有得到很好的满足，这使得它们的实现更加困难。

就我个人而言，LL可以是快速的，但它也可能是残酷的慢到一定程度的回忆录(打包优化)，以允许任何一种温和复杂的语言的速度。然而，这是非常容易的教学，同样容易实现。

相反，LR需要的时间和空间与输入大小和语言复杂性成正比。即使在今天，这也是一个很好的特性。缺点是广度优先搜索(就像动态编程一样)是一个很难教授的想法，而且缺乏主流语言的支持(至少相对于LL所依赖的深度优先搜索而言)。