直觉理解 Pratt 解析
文章摘要
这篇文章旨在帮助读者建立对 Pratt 解析（Pratt Parsing，也称为”自顶向下运算符优先解析”）的直觉理解。Pratt 解析是一种优雅而高效的表达式解析技术，由 Vaughan Pratt 在 1973 年提出，至今仍被广泛应用于编程语言的编译器和解释器中。
传统的表达式解析方法通常依赖 BNF（巴科斯-诺尔范式）语法规则，为每个运算符优先级定义不同的语法规则层级。例如，要正确解析 1 + 2 * 3，需要定义加法表达式和乘法表达式的层级关系。这种方法虽然直观，但当运算符优先级增多时（如 SystemVerilog 有 16 个优先级），代码会变得冗长且难以维护。
Pratt 解析的核心思想是”绑定力”（binding power）。每个运算符被赋予一个数值表示其绑定力（即优先级），解析器通过比较当前运算符与上下文中的绑定力来决定如何组合表达式。绑定力越高的运算符越”紧密”地绑定其操作数。
解析过程的直觉理解可以这样建立：想象解析中缀表达式时，算法在遇到每个运算符时都会问一个简单的问题——”这个运算符的绑定力是否足够强，能够’抢走’左边已经解析的表达式？”如果是，它就继续向右解析；如果不是，它就返回当前的结果，让调用者（绑定力更低的运算符）来处理。
这种方法的美妙之处在于：它只需要一个简单的循环和递归调用，加上一个绑定力查找表，就能正确处理任意数量的运算符优先级和结合性。前缀运算符（如负号 -x）通过 “nud”（null denotation，空符号）函数处理，中缀运算符（如加法 x + y）通过 “led”（left denotation，左符号）函数处理。
文章还介绍了几个相关的解析算法：优先级攀升（precedence climbing）本质上与 Pratt 解析等价，只是组织方式略有不同；调度场算法（shunting yard）是 Pratt 解析的迭代变体，使用显式栈而非递归。作者引导读者从简单的全括号表达式开始，逐步移除括号并引入优先级概念，最终自然地推导出 Pratt 解析的逻辑。
对于编译器和语言设计爱好者来说，Pratt 解析是一个”知道就无法忘记”的技术——它将复杂的语法解析问题简化为一个直观的数值比较问题。
HN 评论精华
对 Pratt 解析的赞誉
- logdahl 赞扬递归下降解析结合 Pratt 处理表达式是一种实用的方法，称其为”超级简单的技术”，能以最小的前瞻量处理大多数玩具语言的需求。
- randomNumber7 推荐阅读 Pratt 的原始论文，形容其”非常酷，很有范儿”，指出作者在论文中批评了传统 BNF 方法的局限性。
学术方法 vs 实践方法的辩论
- eru 批评《龙书》（经典编译器教材）已经过时，主张函数式语言方法和解析器组合子是更直觉的学习工具。
- pklausler（拥有 40 多年经验的编译器工程师）反驳说，生产级编译器需要强大的错误恢复和信息丰富的错误消息，递归下降在这方面表现最好。
- joe_the_user 认为形式语言理论的理解仍然是必要的，即使在使用实用解析方法时也不应忽视。
实现方式的讨论
- antirez 分享了一个 40 行的 Pratt 风格解析器实现，用于 Picol 中的 Tcl 表达式解析，展示了这种技术的简洁性。
- priceishere 提议为每个优先级显式定义函数，镜像 EBNF 结构而无需查找表。
- tasty_freeze 反驳说 SystemVerilog 有 16 个运算符优先级，在这种情况下表驱动方法比深度嵌套的递归函数更加实用。
核心直觉的解释
- ogogmad 用简洁的方式解释了中缀表达式解析的核心：找到绑定力最低的运算符，然后递归解析子表达式。这种”最弱绑定力优先”的视角有助于理解 Pratt 解析为什么能正确处理运算符优先级。
- IshKebab 指出了几个相关算法的关系：优先级攀升（本质上等价于 Pratt 解析）和调度场算法（迭代变体）。
- duped 提出了一种最简方案：强制所有子表达式使用括号，从根本上消除优先级的复杂性——虽然不实用，但有助于理解优先级解析在解决什么问题。