compiler-construction - 递归下降与生成的解析器 - 效率

Question

就性能而言，手写递归下降解析器（不可避免地是 LL(k)）与生成的 LALR 解析器相比如何？

我知道 LALR 解析器能够处理比 LL(k) 多得多的语法；然而，我打算手动编写我的解析器，递归下降似乎是最合适的选择。出于兴趣，是否可以手动（合理地可读）编写任何其他类型？

注意我使用的是带有尾调用优化 (F#) 的函数式语言，因此 [精心定制的] 递归不会像其他语言那样成为问题。

Answer 1

我认为很大程度上取决于您要解析的语言。另一个有时会被遗忘的性能部分是词法分析（扫描）部分——它对性能很重要，因为它处理的是字符而不是符号。递归下降是编写解析器的一个很好的第一次迭代，它使得遵循被解析语言的逻辑非常自然。我认为如果解析的语言适合（没有左递归），你应该从递归下降开始。在这个阶段为性能选择 LALR 似乎是过早的优化。您可以手动编写图表解析器，但我怀疑这就是您的意思。手动编写 LALR 解析器是可能的，但很乏味。

Answer 2

此时出于性能原因在LALR 和 LL 之间做出决定听起来像是过早的优化。解析时间很少是编译器的瓶颈。如果我是您，我会根据您是否更愿意自下而上或自上而下定义语法来进行选择。

就我个人而言，我发现 LALR 语法易于使用，并且 F# 的 fsyacc 集成（这是我学习解析的方法）使得将 yacc 集成到您的项目中变得非常容易。