parsing - 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 状态转换可以在很少的机器指令中执行(“在向量中查找标记代码，获取下一个状态和 Action ”)，因此它们在实践中可以非常快。通过将 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] 为多种语言构建数十个解析器，而不会遇到很多麻烦。)。