PEG 和递归下降解析器之间的区别？
Difference between a PEG and recursive descent parser?
我最近遇到了 PEG 解析器和 Guido van Rossum 的 article on PEG parsers 以及如何构建它们。那篇文章讨论了“PEG”解析器，但在内部它看起来完全像一个递归下降解析器（生成器）。我感觉 PEG 解析器与生成递归下降解析器有关，但我不确定。
递归下降解析器和 PEG 解析器有什么区别？我应该什么时候使用其中之一？
简答
PEG 是描述递归下降解析器的语法。
更长的答案
当人们谈论解析表达式语法 (PEG) 时，他们经常将三件事混为一谈：
- PEG 的 formal grammar 属性
- PEG 的 metasyntax 或符号
- PEG 的解析算法（即 Packrat 解析；参见 this SO question）
Bryan Ford（PEG 的创建者）在他的 2004 article describes the first two, but the first point is not a novel contribution. Rather, PEG is equivalent to top-down parsing language (TDPL) from the 1970s in terms of expressive power, but Ford borrows convenient aspects of EBNF and regular expression 语法中使语法比极小的 TDPL 更易于阅读和编写。基本上，PEG 的表示法使 TDPL 更容易理解，就像用 C 或 Python 而不是 Assembly 编写代码一样。
在福特的 2002 article 中，基于他的硕士论文，他还介绍了 Packrat 解析算法，该算法允许递归下降解析器，即使是像 PEG 这样具有无限前瞻性的解析器，也可以通过记忆在线性时间内 运行 ，或缓存，中间结果。然而，这是一个理论上的结果，即使它有助于解决某些病态案例，但在许多情况下，Packrat 的记忆化开销还是很大的。没有Packrat解析的PEG解析就是简单的递归下降解析。
与 CFG 相比，关于 PEG 的正式属性的一个有趣的事情是优先选择运算符（PEG 符号使用 / 而不是 EBNF 的 | 来进行不明确的选择）。有了优先选择，就会按顺序尝试备选方案，一旦备选方案成功，就不会再尝试其他备选方案。因此，与 context-free grammar (CFG) 不同，PEG 是明确的；要么有一个输入解析，要么没有解析。相关地，PEG 被认为是 "analytical" 语法而不是 "generative" 语法（例如，CFG，其根源在于描述自然语言话语的语言学），因为它们的目的是解析而不是许可（或生成）有效字符串。
结论
您实际上并没有在 PEG 解析和递归下降解析之间做出选择，因为它们大致相同，但您可以选择使用 PEG 解析库通过语法实现您的解析器，而不是手写解析职能。然而，正如 Michael Dyck ，PEG 是递归下降解析器的一个子集，因为您可以编写超出 PEG 可表示范围的递归下降解析器。再说一次，许多 PEG 库扩展了原始形式主义，具有语义操作或附加句法结构等功能。
我最近遇到了 PEG 解析器和 Guido van Rossum 的 article on PEG parsers 以及如何构建它们。那篇文章讨论了“PEG”解析器，但在内部它看起来完全像一个递归下降解析器（生成器）。我感觉 PEG 解析器与生成递归下降解析器有关，但我不确定。
递归下降解析器和 PEG 解析器有什么区别？我应该什么时候使用其中之一？
简答
PEG 是描述递归下降解析器的语法。
更长的答案
当人们谈论解析表达式语法 (PEG) 时，他们经常将三件事混为一谈：
- PEG 的 formal grammar 属性
- PEG 的 metasyntax 或符号
- PEG 的解析算法（即 Packrat 解析；参见 this SO question）
Bryan Ford（PEG 的创建者）在他的 2004 article describes the first two, but the first point is not a novel contribution. Rather, PEG is equivalent to top-down parsing language (TDPL) from the 1970s in terms of expressive power, but Ford borrows convenient aspects of EBNF and regular expression 语法中使语法比极小的 TDPL 更易于阅读和编写。基本上，PEG 的表示法使 TDPL 更容易理解，就像用 C 或 Python 而不是 Assembly 编写代码一样。
在福特的 2002 article 中，基于他的硕士论文，他还介绍了 Packrat 解析算法，该算法允许递归下降解析器，即使是像 PEG 这样具有无限前瞻性的解析器，也可以通过记忆在线性时间内 运行 ，或缓存，中间结果。然而，这是一个理论上的结果，即使它有助于解决某些病态案例，但在许多情况下，Packrat 的记忆化开销还是很大的。没有Packrat解析的PEG解析就是简单的递归下降解析。
与 CFG 相比，关于 PEG 的正式属性的一个有趣的事情是优先选择运算符（PEG 符号使用 / 而不是 EBNF 的 | 来进行不明确的选择）。有了优先选择，就会按顺序尝试备选方案，一旦备选方案成功，就不会再尝试其他备选方案。因此，与 context-free grammar (CFG) 不同，PEG 是明确的；要么有一个输入解析，要么没有解析。相关地，PEG 被认为是 "analytical" 语法而不是 "generative" 语法（例如，CFG，其根源在于描述自然语言话语的语言学），因为它们的目的是解析而不是许可（或生成）有效字符串。
结论
您实际上并没有在 PEG 解析和递归下降解析之间做出选择，因为它们大致相同，但您可以选择使用 PEG 解析库通过语法实现您的解析器，而不是手写解析职能。然而，正如 Michael Dyck