递归下降vs.生成的解析器 - 效率

Question

手写递归下降解析器（不可避免地LL（k））与生成的LALR解析器在性能方面的差异如何？我知道LALR解析器能够处理比LL（k）更多的语法;不过，我打算手工编写解析器，而递归下降似乎是最合适的选择。是否有可能用手（合理可读地）写出任何其他类型的兴趣？

N.B.我正在使用函数式语言进行尾部调用优化（F＃），所以[精心设计的]递归不会像其他语言那样严重。

Answer 1

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

Answer 2

决定LALR和LL之间的表现在这一点上的原因听起来像是一个不成熟的优化。解析时间很少是编译器的瓶颈。如果我是你，我会根据你是否更自如地定义自下而上或自上而下的语法来选择。个人而言，我发现LALR语法易于使用，而F＃的fsyacc集成（这是我学习解析的过程）使得将yacc集成到您的项目中非常容易。