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

Question

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

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

Answer 1

简答

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

更长的答案

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

PEG formal grammar属性(property)

PEG metasyntax , 或符号

PEG 的解析算法(即 Packrat 解析；参见 this SO question)

Bryan Ford(PEG 的创造者)在他的 2004 article 中描述了前两点，但第一点并不是新的贡献。相反，PEG 等效于 top-down parsing language (TDPL) 在表现力方面源自 1970 年代，但福特借用了 EBNF 的便利方面和 regular expression使语法比极小的 TDPL 更易于阅读和编写的语法。基本上，PEG 的符号使 TDPL 更容易理解，就像用 C 或 Python 编写代码而不是用汇编语言编写代码一样。

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

与 CFG 相比，PEG 形式属性的一个有趣之处是优先选择运算符(PEG 符号使用 / 而不是 EBNF 的 | 用于模糊选择)。优先选择是按顺序尝试备选方案，一旦备选方案成功，其他备选方案将不会被尝试。因此，PEG 不同于 context-free grammar (CFG)，是明确的；输入有一个解析，或者没有解析。相关地，PEG 被认为是“分析”语法而不是“生成”语法(例如，CFG，其起源于语言学，用于描述自然语言表达)，因为它们的目的是解析而不是许可(或生成)有效字符串。

结论

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