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

Question

手写递归下降解析器(不可避免地是LL(k))在性能方面与生成的LALR解析器相比如何？

我知道LALR解析器能够处理比LL(k)更多的语法; 但是我打算手工编写我的解析器,递归下降似乎是最合适的选择.是否有可能手工编写任何其他类型(合理可读)？

NB我正在使用带尾调用优化(F#)的函数式语言,因此[精心定制的]递归不会像其他语言一样出现问题.

Answer 1

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