parsing - Pratt 解析器与其他解析器类型相比如何，为什么它们使用得这么少？

Question

我最近从这篇优秀的文章中了解了 Pratt 解析器，发现 Pratt 解析器比递归下降解析器更简单、更优雅。我试图找到更多关于它们如何与其他解析器类型进行比较的信息，但发现维基百科的文章几乎不是一个存根，而且我能找到的使用它的更大项目的数量等于两个。

为什么 Pratt 解析器很少使用？它们是否有我不知道的严重限制或缺点？它们与其他解析器类型相比究竟如何？什么时候应该和什么时候不应该使用它们？

Answer 1

Pratt 解析器和所谓的“调车场”解析器（附有更长的 Wikipedia 文章）之间几乎没有区别；主要区别在于 Pratt 使用递归，因此使用堆栈，而 Djikstra（“分流场”）保留显式堆栈。除此之外，它们执行完全相同的操作序列。我想 Djikstra 对算法的表达由于递归恐惧症而更常见。

使用程序栈有一些好处；其中之一是更容易维护类型安全，因为整个堆栈不必是一种类型。另一方面，许多表达式解析器只有一种类型。

Dragon Book 包含一个算法，该算法将从语法中生成运算符优先级表。正如它所指出的，算法成功的事实并不一定意味着运算符优先级解析器将解析完全相同的语言。那里有更多有趣的信息，我当然已经忘记了；如果您对算法感兴趣，那是您可以查看的地方之一。它包括一个有趣的见解，即 < 和 > 优先关系运算符可以通过查看派生来生成，如果您以明显的方式用 < 和 > 包围产生式的结果。

总的来说，我的经验是，大多数时候当你发现一篇博文说“我的上帝，我刚刚偶然发现了 X，它很棒，为什么没有更多的人知道它？？？？”，答案是“请不要假设你的无知是普遍的。” 但也许我今天只是玩世不恭。

顺便说一句，Lua解析器是一个手工构建的递归下降解析器，它使用 Pratt 风格的解析来解析表达式；我认为这是一种非常常见的技术，您可能会在其他地方找到它，尽管您可能必须通过代码筛选才能看到模式。