Vue.js

Appearance

On this page

表达式解析的挑战：运算符优先级与结合性 ​

欢迎来到解析器中最激动人心，也最具挑战性的部分——表达式解析。在此之前，我们已经成功地解析了变量声明、if 语句、for 循环等语句（Statement）。语句的结构通常比较固定，解析过程相对直接。但表达式（Expression）则完全不同，它充满了“自由”与“变化”。

一、问题的提出：计算机如何理解 2 + 3 * 4？ ​

让我们从一个你在小学就烂熟于心的数学问题开始：

2 + 3 * 4

你一眼就能看出答案是 14，因为“先乘除，后加减”。你的大脑自动识别了运算符的 优先级（Precedence），将 3 * 4 视为一个整体，然后再与 2 相加。

但对于一个简单的、从左到右逐个读取 Token 的解析器来说，它看到的是这样一个序列：

  1. Number (2)
  2. + (Plus)
  3. Number (3)
  4. * (Star)
  5. Number (4)

如果解析器没有任何“智能”，它可能会简单地按照出现顺序进行组合，得到 (2 + 3) * 4，结果是 20——这显然是错误的。

这就是我们遇到的第一个核心挑战：解析器必须理解并遵守运算符的优先级规则。它需要一种机制，能够“预见”到后面有更高优先级的运算符，并优先处理它们。

二、第二个挑战：运算符的“站队”问题——结合性 ​

优先级解决了不同运算符同时出现时的顺序问题。但如果出现一连串相同的运算符呢？比如：

a - b - c

这里只有减法运算符，优先级相同。那么，应该先算 a - b 还是 b - c？

  • 如果先算 a - b，表达式等价于 (a - b) - c。
  • 如果先算 b - c，表达式等价于 a - (b - c)。

对于减法而言，这两种计算顺序会得到截然不同的结果。在 JavaScript（以及大多数编程语言）中，减法、加法、乘法和除法都是 左结合（Left-Associative） 的。这意味着当优先级相同时，运算从左到右进行。因此，a - b - c 的正确解析结果是 (a - b) - c。

然而，并非所有运算符都是左结合的。最典型的例子就是赋值运算符：

a = b = c

这个表达式的执行顺序是从右到左的：首先执行 b = c，然后将 b = c 的结果（即 c 的值）赋给 a。这被称为 右结合（Right-Associative）。它的正确解析结果是 a = (b = c)。

所以，这是我们遇到的第二个核心挑战：解析器必须理解并遵守运算符的结合性规则，以决定在优先级相同时，应该如何组织 AST 的结构。

三、传统递归下降解析的困境 ​

面对优先级和结合性这两座大山，传统的递归下降解析方法会变得异常笨拙。

想象一下，如果我们为每个优先级都编写一个独立的解析函数，会发生什么？

javascript
// 伪代码
function parseExpression() {
  return parseAssignmentExpression(); // 最低优先级
}

function parseAssignmentExpression() {
  let left = parseConditionalExpression();
  // 如果后面是 '='，处理赋值...
  return left;
}

function parseConditionalExpression() {
  let left = parseLogicalORExpression();
  // 如果后面是 '?'，处理三元表达式...
  return left;
}

function parseLogicalORExpression() {
  let left = parseLogicalANDExpression();
  // 如果后面是 '||'，处理逻辑或...
  return left;
}

// ... 一层又一层，直到最高优先级的乘法表达式 ...

function parseMultiplicativeExpression() {
  let left = parseUnaryExpression();
  while (this.type === tt.star || this.type === tt.slash) {
    // 处理 '*' 和 '/'
  }
  return left;
}

// ...

这种方式被称为“表达式瀑布”（Expression Cascade）。它确实能工作，但存在几个严重的问题：

  1. 函数爆炸：JavaScript 有十几个不同的运算符优先级，我们将为此编写十几个几乎雷同的函数。这使得代码冗长、难以维护。
  2. 性能问题：每一层函数调用都是一次开销，深度的递归调用链会影响解析器的性能。
  3. 僵硬与脆弱：每当语言新增一个运算符或修改了优先级，我们都需要痛苦地修改这个“瀑布”的结构，非常麻烦。

我们需要一种更优雅、更灵活、更高效的方法来处理表达式。这个方法应该能够用一个统一的逻辑，简洁地处理所有运算符的优先级和结合性。

幸运的是，这样的方法早已存在。它就是我们下一章的主角——Pratt 解析法。它将彻底改变我们对表达式解析的认知，让我们用一种极其巧妙的方式征服这座看似难以逾越的大山。

在 GitHub 上编辑此页