为什么自下而上的解析比自上而下的解析更常见？

Question

似乎递归下降解析器不仅是最容易解释的，而且也是最容易设计和维护的。它们并不局限于LALR(1)语法，代码本身也可以被普通人理解。相比之下，自下而上解析器对它们能够识别的语法有限制，需要使用特殊工具生成(因为驱动它们的表几乎不可能手动生成)。

那么，为什么自下而上(即shift-reduce)解析比自上而下(即递归下降)解析更常见？

Answer 1

如果您选择了功能强大的解析器生成器，则可以编写语法代码，而无需担心特殊的属性。(LA)LR意味着你不必担心左递归，少了一个头痛。GLR意味着您不必担心局部歧义或先行。

而自下而上的解析器往往非常高效。因此，一旦你为一些复杂的机器付出了代价，编写语法就会变得更容易，解析器也会表现良好。

只要有一些常见的编程构造，你就会看到这种选择:如果它更容易指定，而且性能很好，即使机器很复杂，复杂的机器也会胜出。作为另一个例子，数据库世界已经转向关系工具，尽管您可以自己手动构建索引文件。它更容易编写数据模式，更容易指定索引，并且背后有足够复杂的机制(您不必查看齿轮，只需使用它们)，它们几乎可以毫不费力地非常快。同样的原因。

Answer 2

它源于几个不同的东西。

BNF (以及语法等理论)来自计算语言学:研究自然语言解析的人们。BNF是描述语法的一种非常吸引人的方式，因此使用这些表示法来生成解析器是很自然的。

不幸的是，自上而下的解析技术在应用于这样的符号时往往会失败，因为它们不能处理许多常见的情况(例如，左递归)。这给您留下了LR系列，它执行得很好，可以处理语法，既然它们是由机器产生的，谁会关心代码是什么样子的呢？

不过，您说得对:自顶向下解析器的工作更“直观”，因此它们更容易调试和维护，并且一旦您进行了一些实践，它们就像工具生成的解析器一样容易编写。(尤其是当你进入shift/reduce冲突地狱的时候。)许多答案都谈到了解析性能，但在实践中，自顶向下的解析器通常可以优化为与机器生成的解析器一样快。

这就是为什么许多产品编译器使用手工编写的词法分析器和解析器。

Answer 3

递归下降解析器尝试假设输入字符串的一般结构，这意味着在到达字符串末尾之前会发生大量的反复尝试。这使得它们的效率低于自下而上的解析器，后者不需要这样的推理引擎。

随着语法复杂度的增加，性能差异会被放大。