13

许多网站声明 Packrat 解析器可以在线性时间内解析输入。
所以乍一看，它们比 yacc 或 bison 工具构建的 LALR 解析器更快。

我想知道当使用普通输入（如编程语言源文件）而不是任何理论输入进行测试时，packrat 解析器的性能是否比 LALR 解析器的性能更好/更差。

有谁可以解释这两种方法之间的主要区别。
谢谢！

4

5 回答 5

11

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

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

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

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

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

如果您关心答案，请仔细阅读基础技术论文；如果您真的很在意，请实现其中一个并检查开销常量。我的钱在 L(AL)R 上。

一个观察：大多数语言前端不会花费大部分时间“解析”；相反，他们花费大量时间进行词法分析。优化它（你的简历说你是），解析器的速度并不重要。

（我曾经构建 LALR 解析器生成器和相应的解析器。我不再这样做了；相反，我使用GLR 解析器，它们在实践中是线性时间，但可以处理任意上下文无关语法。我放弃了一些性能，但我可以 [和做，请参阅 bio] 为多种语言构建数十个解析器而不会遇到很多麻烦。）。

于 2010-09-27T02:06:19.590 回答
8

我是 LRSTAR 的作者，这是一个开源的 LR(k) 解析器生成器。由于人们对此表现出兴趣，我已将产品重新上线 LRSTAR。

我研究 LALR 解析器和 DFA 词法分析器的速度已经很多年了。Tom Pennello 的论文非常有趣，但更多的是学术练习，而不是编译器的实际解决方案。但是，如果您只想要一个模式识别器，那么它可能是您的完美解决方案。

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

1989 年，我将 LRSTAR 解析器的解析速度与“yacc”进行比较，发现它们的解析速度是“yacc”解析器的 2 倍。LRSTAR 解析器使用论文中发表的思想：“Optimization of Parser Tables for Portable Compilers”。

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

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

于 2012-07-13T22:19:45.590 回答
2

[2015/02/15] 这是 1986 年 Tom Pennello 发表的关于超快速 LR 解析的论文

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

于 2015-02-12T09:45:12.967 回答
1

我知道这是一篇旧帖子，但大约一个月前，我偶然发现了这篇论文：https ://www.mercurylang.org/documentation/papers/packrat.pdf ，今天无意中看到了这篇文章。

该论文的淡化版本说：packrat memoisation 是喜忧参半。如果您对这条或另一条规则的匹配频率有一些启发式方法，则可以获得最佳结果。本质上，记住具有以下两个属性的规则才有意义：（1）元素很少，（2）非常常见。

于 2018-08-14T10:34:37.897 回答
0

性能主要是语言设计的问题。对于每种语言，都会有一种最适合的方法、技术或解析器生成器。

我无法不加思索地证明这一点，但我认为没有什么能比自上而下的下降解析器更好，其中语义驱动解析器，解析器驱动词法分析器，性能方面。它也将是实现中最通用且更易于维护的。

于 2012-11-17T15:39:33.083 回答