我已经看到一些声称优化的 PEG 解析器通常不能比优化的 LALR(1) 或 LL(k) 解析器快。（当然，解析的性能取决于特定的语法。）
我想知道 PEG 解析器是否有任何特定限制，无论是一般有效还是对于 PEG 语法的某些子集，这会使它们在性能方面不如 LALR(1) 或 LL(k)。
特别是，我对解析器生成器感兴趣，但假设在任何特定情况下都可以调整它们的输出以提高性能。我还假设解析器已经过优化，如果需要提高性能，可以稍微调整特定语法。
问问题
6166 次
2 回答
15
找到了一个关于 Packrat vs LALR parsing的好答案。其中的一些引述：
L(AL)R 解析器也是线性时间解析器。所以理论上，packrat 和 L(AL)R 解析器都不是“更快”的。
当然，在实践中重要的是实施。L(AL)R 状态转换可以在很少的机器指令中执行（“在向量中查找令牌代码，获取下一个状态和动作”），因此它们在实践中可以非常快。
一个观察：大多数语言前端不会花费大部分时间“解析”；相反，他们花费大量时间进行词法分析。优化那个......，解析器的速度并不重要。
于 2012-07-07T09:52:57.667 回答
7
PEG与（默认）不同，解析器可以使用无限前瞻（同时通过 Packrat 保持平均线性解析时间）LL(k)，或者LR(k)使用有限前瞻的解析器，同时保持线性解析时间。
最近（2014-2015）ANTLR4进行了扩展以处理任意前瞻（如PEG），同时保持平均线性解析时间（据说比packrat算法更有效），但是这包含了LR解析算法的新扩展和变体（而不是默认LR算法）。
packrat解析器（以及 ,的相关解析器LL）LR不一定实用，但提供了解析的理论界限，因此可以进行比较。
但请注意，无限前瞻可用于在线性时间（例如 viapackrat或antlr）解析语法/语言，而这些语法/语言无法通过甚至在非线性时间解析LL(k)，LR(k)因此了解什么与什么比较很重要。
于 2015-10-21T14:17:10.497 回答