Packrat解析与LALR解析

Question

很多网站都说packrat解析器可以在线性时间内解析输入。

所以乍一看，它们可能比由工具yacc或bison构造的LALR解析器更快。

我想知道当使用公共输入(如编程语言源文件)而不使用任何理论输入进行测试时，packrat解析器的性能是否优于LALR解析器的性能。

有人能解释一下这两种方法的主要区别吗？

谢谢!

Answer 1

我不是packrat解析方面的专家，但您可以在Parsing expression grammar on Wikipedia上了解更多。

我还没有深入研究它，所以我假设packrat解析的线性时间特征是正确的。

L(AL)R解析器也是线性时间解析器。因此，在理论上，packrat和L(AL)R解析器都不是“更快”的。

当然，在实践中，重要的是实现。L(AL)R状态转换可以在很少的机器指令中执行(“在向量中查找令牌代码，获取下一个状态和操作”)，因此它们在实践中可以非常快。通过将L(AL)R解析“编译”成机器码，您可以得到闪电般的解析器，如this 1986 Tom Pennello paper on Very Fast LR parsing所示。(机器现在比他写这篇论文时快了20年！)

如果packrat解析器正在存储/缓存结果，那么它们可能是线性时间，但我猜测恒定的开销会相当高，然后L(AL)R解析器在实践中会快得多。据我所知，YACC和Bison的实现相当不错。

如果你关心答案，请仔细阅读基本的技术文件；如果你真的关心，那么实现每一个并检查开销常量。我的钱主要放在L(AL)R上。

注意:大多数语言前端并不将大部分时间花在“解析”上；相反，它们将大量时间花在词法分析上。优化这一点(你的简历说你是)，解析器的速度不会有太大影响。

(我曾经构建LALR解析器生成器和相应的解析器。我不再这样做了；相反，我使用GLR parsers，它实际上是线性时间，但可以处理任意上下文无关的语法。我放弃了一些性能，但我可以而且确实可以看到bio为许多语言构建了几十个解析器，而且没有太多麻烦。)

Answer 2

我是LRSTAR的作者，这是一个开源的LR(k)解析器生成器。因为人们对它表现出了兴趣，所以我把这个产品放回了。

多年来，我一直在研究LALR解析器和DFA词法分析器的速度。Tom Pennello的论文非常有趣，但对于编译器来说，更多的是一种学术练习，而不是现实世界的解决方案。但是，如果您只想要一个模式识别器，那么它可能是最适合您的解决方案。

问题在于，现实世界中的编译器通常需要做的不仅仅是模式识别，比如针对传入符号的符号表查找、错误恢复、提供期望的列表(语句完成信息)，以及在解析时构建抽象语法树。

1989年，我将LRSTAR解析器的解析速度与"yacc“解析器进行了比较，发现它们的解析速度是"yacc”解析器的2倍。LRSTAR解析器使用了论文中发表的思想：“针对可移植编译器的解析器表的优化”。

对于词法分析器(词法分析)速度，我在2009年发现"re2c“生成的词法分析器是最快的，大约是"flex”生成速度的两倍。当时我正在重写LRSTAR词法分析器生成器部分，并找到了一种方法来使词法分析器几乎和"re2c“一样快，而且更小。但是，我更喜欢LRSTAR生成的表驱动词法分析器，因为它们几乎和LRSTAR一样快，并且代码的编译速度要快得多。

顺便说一句，LRSTAR生成的编译器前端可以以每秒2,400,000行或更快的速度处理源代码。LRSTAR生成的词法分析器每秒可以处理30,000,000个令牌。测试计算机是一台3.5 GHz的机器(从2010年开始)。

Answer 3

2015/02/15以下是1986年Tom Pennello发表的关于超快LR解析的论文

http://www.genesishistory.org/content/ProfPapers/VF-LRParsing.pdf