PEG 和递归下降解析器之间的区别？

Question

我最近遇到了 PEG 解析器，以及 Guido van Rossum关于 PEG 解析器的文章以及如何构建它们。那篇文章讨论了“PEG”解析器，但在内部它看起来就像一个递归下降解析器（生成器）。我推断 PEG 解析器与生成递归下降解析器有关，但我不确定。

递归下降解析器和 PEG 解析器有什么区别？我什么时候应该使用其中一个？

Answer 1

简答

PEG 是描述递归下降解析器的语法。

更长的答案

当人们谈论解析表达式语法 (PEG) 时，他们通常会将三件事混为一谈：

• PEG 的形式语法属性
• PEG 的元语法或符号
• PEG 的解析算法（即 Packrat 解析；请参阅此 SO 问题）

Bryan Ford（PEG 的创造者）在他2004 年的文章中描述了前两点，但第一点并不是新奇的贡献。相反，就表达能力而言，PEG 相当于1970 年代的自顶向下解析语言(TDPL)，但福特借用了EBNF和正则表达式语法的便利方面，使语法比极简的 TDPL 更易于阅读和编写。基本上，PEG 的符号使 TDPL 更容易理解，就像用 C 或 Python 编写代码而不是用汇编语言编写代码一样。

在 Ford 2002 年基于他的硕士论文的文章中，他还介绍了 Packrat 解析算法，该算法允许递归下降解析器，甚至像 PEG 这样具有无限前瞻的解析器，通过记忆或缓存中间结果在线性时间内运行。然而，这是一个理论结果，即使它对某些病理情况有所帮助，但在许多情况下，Packrat 的记忆开销很大。在没有 Packrat 解析的情况下使用 PEG 进行解析只是递归下降解析。

与 CFG 相比，关于 PEG 形式属性的一件有趣的事情是优先选择运算符（PEG 符号使用/EBNF 代替 EBNF|进行模糊选择）。优先选择是按顺序尝试备选方案，一旦备选方案成功，其他备选方案将不会被尝试。因此，与上下文无关文法(CFG)不同，PEG是明确的；输入有一个解析，或者没有解析。相关地，PEG 被认为是“分析”语法而不是“生成”语法（例如，CFG，其根源在于描述自然语言话语的语言学），因为它们的目的是解析而不是许可（或生成）有效字符串。

结论

您并没有真正在 PEG 解析和递归下降解析之间进行选择，因为它们大致相同，但是您可以选择使用 PEG 解析库通过语法来实现您的解析器，而不是手写解析函数。然而，正如 Michael Dyck评论的那样，PEG 是递归下降解析器的一个子集，因为您可以编写超越 PEG 可表示的递归下降解析器。再说一次，许多 PEG 库通过语义动作或附加句法结构等特征扩展了原始形式。