递归下降与生成解析器 - 效率
就性能而言，手写的递归下降解析器（不可避免地是 LL(k)）与生成的 LALR 解析器相比如何？
我知道 LALR 解析器能够处理比 LL(k) 更多的语法； 然而，我的目的是手动编写解析器，而递归下降似乎是最合适的选择。 出于兴趣，是否可以手写任何其他类型（合理可读）？
NB 我使用的是带有尾部调用优化 (F#) 的函数式语言，因此[精心定制的] 递归不会像其他语言那样成为问题。
How do hand-written recursive descent parsers (which are inevitably LL(k)) compare to generated LALR parsers in terms of performance?
I know that LALR parsers are able to handle far more grammars than LL(k); however it's my intention to write my parser by hand, and recursive descent seems the most appropriate choice. Is it possible to write any other kind by hand (reasonably readably) out of interest?
N.B. I am using a functional language with tail-call optimisation (F#), so [well-tailored] recursion won't be as much of an issue as in other languages.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为很大程度上取决于您要解析的语言。 有时被遗忘的性能的另一个部分是词法分析（扫描）部分 - 它对性能很重要，因为它处理字符而不是符号。 递归下降是编写解析器的一个很好的第一次迭代，它使得遵循解析语言的逻辑变得非常自然。 我认为如果解析的语言适合（没有左递归），你应该从递归下降开始。 现阶段选择LALR来进行性能优化似乎还为时过早。
您可以手动编写 图表解析器，但我怀疑这就是您的意思。 手动编写 LALR 解析器是可能的，但很乏味。
I think a lot depends on the language you are trying to parse. Another part of performance which sometimes gets forgotten is the lexical analysis (scanning) part - it is significant for performance as it deals with characters rather than symbols. Recursive descent is a good first iteration at writing a parser, and it makes following the parsed language's logic quite natural. I think that if the parsed language fits (no left recursion) you should start with recursive descent. Choosing LALR for performance at this stage seems to be premature optimization.
You can write a chart parser by hand, but I doubt this is what you mean. Writing an LALR parser by hand is possible but tedious.
此时出于性能原因在 LALR 和 LL 之间做出决定听起来像是一个不成熟的优化。 解析时间很少是编译器的瓶颈。 如果我是你，我会根据你是否更愿意自下而上或自上而下地定义语法来进行选择。
就我个人而言，我发现 LALR 语法很容易使用，并且 F# 的 fsyacc 集成（这就是我学习解析的方式）使得将 yacc 集成到您的项目中变得非常容易。
Deciding between LALR and LL for performance reasons at this point sounds like a premature optimization. Parsing time is rarely the bottleneck in a compiler. If I were you, I'd choose based on whether you are more comfortable defining your grammar bottom-up or top-down.
Personally, I find LALR grammars easy to work with, and F#'s fsyacc integration (which is how I learned parsing) makes it very easy to integrate yacc into your project.