PEG与递归下降解析器的区别是什么？

Question

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

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

- Monolith

---

PEG解析器是递归下降解析器的子集。 - Michael Dyck

Answer 1

简短回答

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

较长回答

当人们谈论Parsing Expression Grammars（PEG）时，他们通常会混淆三件事：

• PEG的形式语法属性
• PEG的元语法，或者表示法
• PEG的解析算法（即Packrat解析；请参见此SO问题）

Bryan Ford（PEG的创建者）在其2004年文章中描述了前两者，但第一点并不是一项新颖的贡献。相反，PEG在表达能力上等同于20世纪70年代的自顶向下解析语言（TDPL），但Ford借鉴了EBNF和正则表达式语法的方便之处，使语法比极其简单的TDPL更易于阅读和编写。基本上，PEG的表示法使TDPL更加易于接近，就像用C或Python编写代码而不是汇编语言一样。

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

PEG的形式属性与CFG相比有趣的一点是优先选择运算符（PEG符号使用/而不是EBNF的|表示模棱两可的选择）。使用优先选择，备选项按顺序尝试，一旦备选项成功，其他备选项将不再尝试。因此，PEG与context-free grammar（CFG）不同，是无歧义的；对于一个输入，要么有一个解析结果，要么没有解析结果。相关地，PEG被认为是“分析”语法而不是“生成”语法（例如，CFG，它源于用于描述自然语言话语的语言学），因为它们的目的是用于解析而不是许可（或生成）有效字符串。

结论

你实际上不需要在PEG解析和递归下降解析之间做出选择，因为它们关注的是同样的事情，但是你可以选择使用PEG解析库通过语法来实现你的解析器，而不是手写解析函数。然而，正如Michael Dyck所commented的那样，PEG是递归下降解析器的子集，因为你可以编写超出PEG可表示范围的递归下降解析器。另一方面，许多PEG库通过添加语义动作或其他句法结构来扩展原始形式化。

- goodmami