我最近遇到了PEG解析器，以及Guido van Rossum关于PEG解析器以及如何构造它们的文章。那篇文章讨论了"PEG"解析器，但在内部它看起来完全像一个递归下降解析器(生成器(。我有一种感觉，PEG解析器与生成递归下降解析器有关，但不确定。
递归下降解析器和PEG解析器有什么区别？ 我什么时候应该使用其中一个？
简答
PEG 是描述递归下降解析器的语法。
更长的答案
当人们谈论解析表达式语法(PEG(时，他们经常将三件事混为一谈：
- PEG的形式语法属性
- PEG的元语法或符号
- PEG的解析算法(即Packrat解析;见这个SO问题(
布莱恩·福特(PEG的创造者(在他2004年的文章中描述了前两点，但第一点并不是新颖的贡献。相反，PEG 在表达能力方面相当于 1970 年代的自上而下解析语言 (TDPL(，但福特借用了 EBNF 和正则表达式语法的便利方面，使语法比极小的 TDPL 更容易阅读和编写。基本上，PEG的符号使TDPL更平易近人，就像用C或Python而不是汇编编写代码一样。
在福特2002年基于他的硕士论文的文章中，他还介绍了Packrat解析算法，该算法允许递归下降解析器，即使是那些像PEG这样具有无限前瞻性的解析器，通过记忆或缓存中间结果来线性时间运行。然而，这是一个理论上的结果，即使它有助于某些病理病例，在许多情况下，Packrat记忆的开销也是巨大的。使用PEG进行解析而不进行Packrat解析只是递归下降解析。
与CFG相比，PEG的形式属性的一个有趣的事情是优先级选择运算符(PEG符号使用/而不是EBNF的|来表示模糊的选择(。通过优先选择，将按顺序尝试替代方案，一旦替代方案成功，将不会尝试其他替代方案。因此，与上下文无关语法 (CFG( 不同，PEG 是明确的;输入要么有一个解析，要么没有解析。相关地，PEG被认为是"分析"语法而不是"生成"语法(例如，CFG，它起源于描述自然语言话语的语言学(，因为它们的目的是解析而不是许可(或生成(有效字符串。
结论
您实际上不会在PEG解析和递归下降解析之间进行选择，因为它们大致相同，但是您可以选择使用PEG解析库通过语法实现解析器，而不是手动编写解析函数。然而，正如Michael Dyck所评论的那样，PEG是递归下降解析器的一个子集，因为您可以编写超越PEG中可表示内容的递归下降解析器。再说一次，许多PEG库通过语义动作或其他语法结构等功能扩展了原始形式。