28

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

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

4

6 回答 6

20

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

自下而上的解析器往往非常有效。因此，一旦您为一些复杂的机器付出了代价，编写语法就会更容易，并且解析器的性能也会很好。

你应该期望在任何经常出现某种编程结构的地方看到这种选择：如果它更容易指定，并且性能相当好，即使机器很复杂，复杂的机器也会获胜。作为另一个例子，数据库世界已经转向关系工具，尽管您可以自己手动构建索引文件。编写数据模式更容易，指定索引更容易，并且背后有足够复杂的机器（您不必查看齿轮，只需使用它们），它们几乎可以毫不费力地快速运行。同样的原因。

于 2010-11-30T18:36:11.527 回答
8

它源于几个不同的事情。

BNF（以及语法理论等）来自计算语言学：研究自然语言解析的人们。BNF 是一种非常有吸引力的语法描述方式，因此很自然地希望使用这些符号来生成解析器。

不幸的是，自顶向下解析技术在应用于此类符号时往往会失败，因为它们无法处理许多常见情况（例如，左递归）。这样就剩下 LR 系列了，它性能很好并且可以处理语法，而且由于它们是由机器生成的，谁在乎代码是什么样子的呢？

不过，您是对的：自上而下的解析器更“直观”地工作，因此它们更易于调试和维护，并且一旦您稍加练习，它们就与工具生成的解析器一样容易编写。（尤其是当您陷入转移/减少冲突的地狱时。）许多答案都在谈论解析性能，但实际上自上而下的解析器通常可以优化为与机器生成的解析器一样快。

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

于 2010-11-30T22:08:51.910 回答
6

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

随着语法复杂性的增加，性能差异变得更大。

于 2010-11-30T17:25:50.177 回答
3

为了补充其他答案，重要的是要认识到除了效率之外，自下而上的解析器可以接受比递归下降解析器更多的语法。自上而下的解析器——无论是否预测——只能有 1 个前瞻令牌，如果当前令牌和紧跟在令牌后面的任何东西可以使用两种不同的规则派生，则失败。当然，您可以实现解析器以获得更多的前瞻（例如 LL(3)），但是在它变得像自下而上的解析器一样复杂之前，您愿意将它推进多远？另一方面，自下而上的解析器（特别是 LALR）维护一个列表，firsts并且follows可以处理自上而下的解析器不能处理的情况。

当然，计算机科学是关于权衡的。如果您的语法足够简单，那么编写自上而下的解析器是有意义的。如果它很复杂（例如大多数编程语言的语法），那么您可能必须使用自下而上的解析器才能成功接受输入。

于 2014-08-08T18:48:53.473 回答
1

我有两个猜测，但我怀疑其中任何一个都不能完全解释：

  1. 自上而下的解析可能很慢。递归下降解析器可能需要指数时间来完成他们的工作。这将对使用自顶向下解析器的编译器的可扩展性造成严重限制。

  2. 更好的工具。如果您可以用 EBNF 的某些变体来表达该语言，那么您很有可能可以通过 Lex/Yacc 摆脱大量繁琐的代码。似乎没有那么多工具可以帮助自动完成将自上而下的解析器组合在一起的任务。让我们面对现实吧，编写解析器代码并不是玩弄语言的乐趣所在。

于 2010-11-30T17:22:09.217 回答
1

我从未见过自上而下和 shift-reduce 解析器之间的真正比较：

只有 2 个小程序同时运行，一个使用自上而下的方法，一个使用自下而上的方法，每个大约 200 行代码，

能够解析任何类型的自定义二元运算符和数学表达式，两者共享相同的语法声明格式，然后可能添加变量声明和影响来展示如何实现“hacks”（非上下文无关）。

那么，如何诚实地谈论我们从未做过的事情：严格比较这两种方法？

于 2015-11-12T05:40:33.183 回答