直觉理解 Pratt 解析器：优雅算法的新视角

Louis Stowasser 的一篇新博文对 Pratt 解析器——计算机科学中最优雅却被低估的算法之一——提供了直观的解释。该文章通过可视化生成的解析树，重新构建了我们对运算符优先级和结合性的思维方式。

问题

如何编码 a + b * c + d 应该被计算为 a + (b * c) + d？这是解析中运算符优先级的经典问题。最常见的解决方案是构建抽象语法树（AST），其中每个运算符位于其操作数之上。

  +
 / \
 +   d
/ \
a   *
    / \
   b   c

视觉直觉

Stowasser 的关键洞察是：不要从文法和解析器生成器的角度思考解析，而是从树形结构的角度思考：

• 递减优先级产生左倾树——如 a * b + c * d，乘法绑定更紧
• 递增优先级产生右倾树——如 a + b * c + d，加法在左侧绑定更松
• 等优先级左结合的行为类似于递减优先级

为什么选择 Pratt 解析器？

传统方法使用带有复杂文法规则的解析器生成器（ANTLR、yacc）。Pratt 解析器仅用两个简单的概念处理运算符优先级：

1. 绑定能力： 每个运算符有一个数字绑定能力
2. 空表示和左表示： 处理前缀和中缀位置的函数

该算法实现起来极其简单——通常不到 50 行代码——却能处理所有标准的运算符优先级模式。

当代相关性

Pratt 解析器在编程语言社区正获得重新关注：

• 用于 Go 标准库的模板解析
• 因其简洁性在脚本语言实现中很受欢迎
• 越来越多被作为递归下降的替代方案来教授表达式解析
• 与构建 DSL（领域特定语言）的任何人相关

更广泛的意义

Stowasser 的贡献不仅仅关于 Pratt 解析器本身——它关于为复杂算法寻找直观、可视化的解释的价值。太多时候，计算机科学教育在建立使形式化变得有意义的心理模型之前，就跳到了形式化符号。

来源：Louis Stowasser 博客、Hacker News