这本古怪的龙书很好地解释了LR解析器的工作原理.还有解析技术.实用指南.如果我记得很清楚,你可以在哪里阅读它们.维基百科上的文章(至少是介绍)是不对的.他们是由唐纳德克努特创作的,他在他的"计算机编程艺术"第5卷中解释了这些.如果你理解西班牙语,我会在这里发布完整的书籍清单.并非所有的书籍都是西班牙语.
在了解它们如何工作之前,您必须先了解一些概念,如第一,后续和前瞻.另外,我真的建议你在尝试理解LR(上升)解析器之前理解LL(后代)解析器背后的概念.
有一系列解析器LR,特别是LR(K),SLR(K)和LALR(K),其中K是他们需要工作多少的前瞻.Yacc支持LALR(1)解析器,但你可以进行调整,而不是基于理论,以使它适用于更强大的语法.
关于性能,它取决于所分析的语法.它们以线性时间执行,但是它们需要多少空间取决于您为最终解析器构建的状态数.
我个人很难理解函数调用如何更快 - 比表查找更"明显更快".而且我怀疑,与词法分析器/解析器必须做的其他事情(主要是读取和标记文件)相比,即使"明显更快"也是微不足道的.我看了维基百科页面,但没有按照参考文献; 作者是否真的描述了一个完整的词法分析器/解析器？
对我来说更有趣的是表驱动解析器在递归下降方面的下降.我来自C背景,其中yacc(或等效的)是首选的解析器生成器.当我转移到Java时,我发现了一个表驱动实现(JavaCup)和几个递归下降实现(JavaCC,ANTLR).
我怀疑答案类似于"为什么选择Java而不是C"的答案:执行速度并不像开发速度那么重要.正如维基百科文章所述,表格驱动的解析器几乎不可能从代码中理解(当我使用它们时,我可以遵循他们的行为,但永远无法从解析器重构语法).相比之下,递归下降非常直观(毫无疑问,为什么它早于桌面驱动约20年).