Vue.js

Appearance

On this page

Pratt 解析法：算法核心 ​

在上一章，我们看到了传统递归下降解析器在处理表达式时遇到的困境——“函数瀑布”不仅冗长，而且难以维护。现在，是时候揭晓那个更优雅的解决方案了：Pratt 解析法（Pratt Parser）。

这个算法由 Vaughan Pratt 在 1973 年提出，它的核心思想颠覆了我们之前的认知：与其编写大量的函数来区分运算符优先级，不如让每个运算符 Token 自己来驱动解析过程。

一、两大核心概念：nud 与 led ​

Pratt 将解析逻辑与 Token 类型本身关联起来，并定义了两种解析函数：

  1. nud (Null Denotation)

    • 当一个 Token 出现在**前缀（Prefix）**位置时，调用 nud。
    • nud 的 n 代表 null，因为它的左侧（null）没有表达式可供它操作。
    • 它适用于什么场景？
      • 字面量和标识符：如 123、x。它们的 nud 逻辑最简单，就是返回代表自身的 AST 节点。
      • 前缀运算符：如 -a、!b。- 和 ! 的 nud 逻辑是先解析它右侧的表达式（a 或 b），然后创建一个一元运算（UnaryExpression）节点。

  2. led (Left Denotation)

    • 当一个 Token 出现在**中缀（Infix）或后缀（Postfix）**位置时，调用 led。
    • led 的 l 代表 left，因为它需要一个已经解析好的、位于其左侧的表达式作为输入。
    • 它适用于什么场景？
      • 中缀运算符：如 a + b。+ 的 led 会接收 a 的 AST 节点作为左侧，然后继续向右解析 b，最后将它们组合成一个二元运算（BinaryExpression）节点。
      • 后缀运算符：如 i++。++ 的 led 接收 i 的 AST 节点，并将其包装成一个更新表达式（UpdateExpression）节点。
      • 调用和成员访问：如 fn()、obj[key]。( 和 [ 的 led 都会接收左侧的表达式（fn 或 obj）并构建相应的 AST 节点。

简单来说：

  • nud：处理“开头”的 Token，创建表达式的“起点”。
  • led：处理“中间”的 Token，将新的部分“附加”到已有的表达式上。

二、用"绑定力"取代"优先级" ​

Pratt 解析法用一个更通用的概念——绑定力（Binding Power）——来取代"优先级"。绑定力是一个简单的数值，它决定了一个运算符"粘合"其周围表达式的能力有多强。

  • 绑定力越高的运算符，越优先计算。
  • 例如，* 的绑定力（如 20）会高于 + 的绑定力（如 10）。

每个中缀和后缀运算符（即拥有 led 的 Token）都会被赋予一个绑定力值。前缀运算符（nud）和原子表达式（如数字、标识符）则不需要，它们的绑定力可以视为 0。

运算符绑定力示例：

  • a（原子表达式）：类型 nud，绑定力 0
  • + / -（加减）：类型 led，绑定力 10，左结合
  • * / /（乘除）：类型 led，绑定力 20，左结合
  • =（赋值）：类型 led，绑定力 2，右结合

注意赋值运算符的绑定力最低（2），这确保了赋值在整个表达式求值完成后才执行。

三、算法主循环：parseExpression ​

Pratt 解析器的核心是一个非常简洁的函数，我们称之为 parseExpression。它只接收一个参数：rightBindingPower（右侧绑定力），代表了当前解析上下文的“最低粘合力要求”。

让我们看看它的伪代码实现：

javascript
function parseExpression(rightBindingPower = 0) {
  // 1. 获取当前 Token，并执行它的 nud 函数。
  // 这会处理字面量、标识符或前缀运算符，为我们生成表达式的“左手侧” (left)。
  let t = advance(); // 获取当前 Token 并前进一步
  let left = t.nud();

  // 2. 循环：只要下一个 Token 的绑定力比我们当前的 rightBindingPower 大，就继续处理。
  while (peek().bindingPower > rightBindingPower) {
    // 消费这个中缀或后缀运算符
    t = advance();

    // 3. 执行它的 led 函数，并将当前的 left 传入。
    // led 会完成剩余的解析，并返回一个新的、更完整的 left。
    left = t.led(left);
  }

  return left;
}

这个循环就是 Pratt 解析法的魔法所在！让我们一步步拆解它：

  1. 起点：parseExpression 首先通过调用当前 Token 的 nud 获得一个初始的 left 表达式。这总能成功，因为任何表达式都必须由一个字面量、标识符或前缀运算符开头。

  2. 循环条件：while (peek().bindingPower > rightBindingPower) 是算法的决策核心。它在问：“下一个运算符的绑定力是否足够强，值得我把它‘抢’过来，成为当前 left 表达式的一部分？”

  3. “抢夺”与组合：如果答案是肯定的，循环体就会执行。它会消费掉那个更强的运算符，并调用其 led 方法。led 方法会接收已经解析好的 left，继续向右解析，然后将所有部分组合成一个新的、更大的 left 表达式。这个新 left 会在下一次循环中继续接受考验。

  4. 终点：当循环条件不满足时（即下一个 Token 的绑定力不够强，或者没有更多 Token 了），意味着当前的表达式已经完整，可以返回了。

四、图解 2 + 3 * 4 解析过程 ​

让我们用这个算法来手动推演 2 + 3 * 4 的解析过程。假设绑定力：+ 为 10，* 为 20。

  1. parseExpression(0) 被调用（初始调用，最低绑定力为 0）。

  2. nud: 读取 2。2 的 nud 返回 NumericLiteral(2)。left 现在是 NumericLiteral(2)。

  3. 循环检查: 查看下一个 Token +。它的绑定力是 10，10 > 0，循环开始。

  4. led: 消费 +，调用 + 的 led(NumericLiteral(2))。

    • 在 + 的 led 内部，它需要解析右侧的表达式。关键来了：它会递归调用 parseExpression(10)，传入 + 自身的绑定力作为新的 rightBindingPower！
    • 进入内层 parseExpression(10)
      1. nud: 读取 3。3 的 nud 返回 NumericLiteral(3)。内层的 left 是 NumericLiteral(3)。
      2. 循环检查: 查看下一个 Token *。它的绑定力是 20，20 > 10，内层循环开始。
      3. led: 消费 *，调用 * 的 led(NumericLiteral(3))。
        • 在 * 的 led 内部，它同样需要解析右侧，于是递归调用 parseExpression(20) (传入 * 的绑定力)。
        • 进入最内层 parseExpression(20)
          1. nud: 读取 4。4 的 nud 返回 NumericLiteral(4)。最内层的 left 是 NumericLiteral(4)。
          2. 循环检查: 文件结束，没有更多 Token。最内层循环结束。
          3. 返回: 最内层 parseExpression(20) 返回 NumericLiteral(4)。
        • * 的 led 接收到 NumericLiteral(4) 作为右侧，组合成 BinaryExpression(3 * 4)，并返回这个新节点。
      4. 循环检查: 文件结束。内层循环结束。
      5. 返回: 内层 parseExpression(10) 返回 BinaryExpression(3 * 4)。
    • + 的 led 接收到 BinaryExpression(3 * 4) 作为右侧，组合成 BinaryExpression(2 + (3 * 4))，并返回这个最终的 AST 节点。

  5. 循环检查: 文件结束。外层循环结束。

  6. 最终返回: parseExpression(0) 返回 BinaryExpression(2 + (3 * 4))。

通过这个过程，你可以看到，* 因为比 + 有更高的绑定力，所以在 + 的 led 函数内部被"抢先"执行了。整个过程就像一场"拔河比赛"，绑定力强的运算符总能把操作数从绑定力弱的运算符那里"拉"过来。

五、总结 ​

Pratt 解析法是一个极其优雅且强大的算法。它通过以下几个核心思想，彻底解决了表达式解析的难题：

  • 职责下放：将解析逻辑（nud 和 led）和优先级信息（绑定力）附加到 Token 本身。
  • 统一循环：使用一个 parseExpression(rightBindingPower) 函数和主循环来处理所有类型的表达式。
  • 递归组合：通过在 led 函数中递归调用 parseExpression，并传递新的绑定力上下文，巧妙地处理了复杂的优先级和结合性问题。

在接下来的章节中，我们将亲手实现这个算法，你会更深刻地体会到它的简洁与强大。准备好告别“函数瀑布”，迎接解析表达式的全新方式吧！

在 GitHub 上编辑此页