Published on

从力扣基本计算器到编译原理

把 2 + 3 * 4 交给计算器,答案是 14。可如果扫描到 2 + 3 就把它算成 5,最后只能得到 20。再加一对括号,(2 + 3) * 4 又确实应该得到 20。同一组数字与符号,怎么组合,决定了怎么算。

力扣的基本计算器要求我们自己解释这串字符,不能交给 eval()。先看 2 + 3 * 4 怎么一步步变成 14。

  1. 词法分析读出 [2, '+', 3, '*', 4]。每个数字或符号都是一个 token。
  2. 语法分析按优先级把 token 组装成抽象语法树(AST)。加法是根节点,乘法是它的右子树。
  3. 求值从叶子开始,先算出 3 * 4,再把结果加到 2 上。
    +
   / \
  2   *
     / \
    3   4

这棵树把「先算谁」写进了结构里。接下来给计算器加上括号和一元负号,看看它们分别在哪一步处理。

三道题,共用一个表达式解析器

题目输入范围
224. 基本计算器整数、加减、空格和括号,允许 -1、-(2 + 3) 这样的一元负号
227. 基本计算器 II非负整数字面量、空格和四则运算,整数除法向零截断
面试题 16.26. 计算器非负整数字面量、空格和四则运算,同样使用整数除法

三道题的语法可以合进同一个 calculate。实现还允许乘除与括号混用,以及在二元运算符后使用一个一元负号,例如 7 / -3。题目保证输入有效,这里也会检查括号、操作数和运算符的位置,把拼错的表达式拦下来。一元正号、连续的一元负号、小数和隐式乘法都超出这套语法的范围。

下面三个 TypeScript 代码块按顺序放在同一个文件里,就是完整的计算器。先从读取输入开始。

词法分析:用栈把括号配成组

123 应该是一个数字 token,-123 则拆成 - 和 123。同一个减号也会出现在 5-123 里,词法分析先保留符号,等语法分析根据前后关系判断它的角色。

这里的 tokenize 还顺手给括号分组。一般的扫描器可以发出平铺的左右括号 token,由解析器负责配对。这份实现把分组并入扫描,每遇到一个左括号就压入新的 token 数组,匹配到右括号时再把它放回外层。于是 12 + (3 * 4) 会变成 [12, '+', [3, '*', 4]],内层数组在外层看来就是一个操作数。

扫描连续数字只需要有限状态,匹配任意深度的括号还需要栈来记住当前在哪一层。栈底是整条表达式的数组,因此读到右括号时,栈里只有一层就说明它没有匹配的左括号。

type BinaryOperator = '+' | '-' | '*' | '/'
type Token = number | BinaryOperator | Tokens
type Tokens = Token[]

function isDigit(char: string | undefined): boolean {
  return char !== undefined && char >= '0' && char <= '9'
}

function tokenize(s: string): Tokens {
  const tokens: Tokens = []
  const stack: Tokens[] = [tokens]
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    const current = stack[stack.length - 1]
    if (/\s/.test(char)) continue

    if (isDigit(char)) {
      const start = i
      while (isDigit(s[i + 1])) i++
      const value = Number(s.slice(start, i + 1))
      if (!Number.isSafeInteger(value)) throw new RangeError('整数超出安全范围')
      current.push(value)
    } else if (char === '+' || char === '-' || char === '*' || char === '/') {
      current.push(char)
    } else if (char === '(') {
      stack.push([])
    } else if (char === ')') {
      if (stack.length === 1) throw new SyntaxError(`多余的右括号,位置 ${i}`)
      stack.pop()
      stack[stack.length - 1].push(current)
    } else {
      throw new SyntaxError(`无法识别字符 ${char},位置 ${i}`)
    }
  }

  if (stack.length !== 1) throw new SyntaxError('缺少右括号')
  return tokens
}

语法分析:用状态机读 token,按优先级构树

有了 token 还不能开始算。比如 1 2 能扫出两个合法的整数,但第一个数后面应该接运算符。再看 -,它在 -3 里表示取负,在 5-3 里表示减法。解析器在每层括号里维护三个状态,用当前期待和下一枚 token 来判断该怎么读。

当前期待数字或括号组-+、*、/输入结束
操作数接收,接下来等二元运算符记为一元负号,继续等操作数报错报错
一元负号后的操作数构建一元表达式,接下来等二元运算符报错报错报错
二元运算符报错记为二元减法,接下来等操作数记为二元运算符,接下来等操作数完成

收到操作数时,如果有待处理的一元负号,解析器先为它构建 UnaryExpression,再决定怎么与已有的左表达式合并。这个节点记录了负号作用在哪个表达式上,真正取负要等到求值阶段。AST 节点借用了 Babel 常见的命名,包括 NumericLiteral、UnaryExpression、BinaryExpression 和 ParenthesizedExpression。这里显式保留括号节点,让外层解析器在处理优先级时把整个括号组视为一个操作数。也可以在 AST Explorer 里输入相同表达式,切换解析器观察括号的表示方式。 Babel Parser 文档 · AST Explorer

以 2 + 3 * 4 为例,读完 2 + 3 时,当前树的根是加法。后续的乘法优先级更高,所以把 3 和 4 组合成新的右子树,而根仍然是加法。继续读 / 2 时,已有的整个乘法子树成为除法的左侧,得到 2 + ((3 * 4) / 2)。同级运算总是用已有子树作为左操作数,因此 8 / 4 / 2 得到 (8 / 4) / 2。如果根是括号节点,例如 (2 + 3) * 4,乘法就直接把整个括号组接到左侧。

这个接到右子树的规则依赖当前只有两档二元优先级,且同档都是左结合。若要加入右结合的幂运算,或继续增加优先级层次,优先级爬升或 Pratt 解析器能直接表达这些规则,扩展起来更清楚。

type Expression =
  | { type: 'NumericLiteral'; value: number }
  | { type: 'UnaryExpression'; operator: '-'; argument: Expression }
  | { type: 'BinaryExpression'; operator: BinaryOperator; left: Expression; right: Expression }
  | { type: 'ParenthesizedExpression'; expression: Expression }

type State = 'operand' | 'unary' | 'binary'
type TokenType = 'number' | 'group' | 'minus' | 'operator'

const transform: Record<State, Partial<Record<TokenType, State>>> = {
  operand: { number: 'binary', group: 'binary', minus: 'unary' },
  unary: { number: 'binary', group: 'binary' },
  binary: { minus: 'operand', operator: 'operand' },
}

function getTokenType(token: Token): TokenType {
  if (typeof token === 'number') return 'number'
  if (Array.isArray(token)) return 'group'
  return token === '-' ? 'minus' : 'operator'
}

interface ParseFrame {
  tokens: Tokens
  index: number
  state: State
  negate: boolean
  left?: Expression
  operator?: BinaryOperator
}

function createFrame(tokens: Tokens): ParseFrame {
  return { tokens, index: 0, state: 'operand', negate: false }
}

function appendOperand(frame: ParseFrame, operand: Expression): void {
  const right: Expression = frame.negate
    ? { type: 'UnaryExpression', operator: '-', argument: operand }
    : operand
  frame.negate = false

  const { left, operator } = frame
  if (left === undefined || operator === undefined) {
    frame.left = right
  } else if (
    left.type === 'BinaryExpression' &&
    (left.operator === '+' || left.operator === '-') &&
    (operator === '*' || operator === '/')
  ) {
    left.right = { type: 'BinaryExpression', operator, left: left.right, right }
  } else {
    frame.left = { type: 'BinaryExpression', operator, left, right }
  }
  frame.operator = undefined
}

function buildExpression(tokens: Tokens): Expression {
  const stack = [createFrame(tokens)]
  while (true) {
    const frame = stack[stack.length - 1]
    if (frame.index === frame.tokens.length) {
      if (frame.state !== 'binary' || frame.left === undefined) {
        throw new SyntaxError('表达式为空或缺少操作数')
      }

      stack.pop()
      if (!stack.length) return frame.left
      appendOperand(stack[stack.length - 1], {
        type: 'ParenthesizedExpression',
        expression: frame.left,
      })
      continue
    }

    const token = frame.tokens[frame.index++]
    const next = transform[frame.state][getTokenType(token)]
    if (next === undefined) throw new SyntaxError('此处不应出现该 token')

    frame.state = next
    if (typeof token === 'number') {
      appendOperand(frame, { type: 'NumericLiteral', value: token })
    } else if (Array.isArray(token)) {
      stack.push(createFrame(token))
    } else if (next === 'unary') {
      frame.negate = true
    } else {
      frame.operator = token
    }
  }
}

状态表只管当前层,括号栈负责跨层。比如 -(2 + 3),外层记住待处理的负号,内层先建好加法树。出栈时,外层再把整个括号表达式放进一元负号节点。这样既能区分一元和二元减号,也能拒绝 1 2、()、1 + 和 +1。

求值:从叶子往上算

树建好以后,求值阶段就不用再判断优先级了。数字节点直接产生值,括号节点把求值交给内部表达式,一元负号等一个值,二元运算等两个值。这样开头那棵树会先得到 3 * 4 的 12,再算 2 + 12。数值栈中后弹出的是左值,顺序颠倒会把减法和除法算错。

实现使用显式栈做后序遍历。很深的括号和很长的左结合表达式都可能产生很深的树,直接递归求值容易先碰到 JavaScript 的调用栈上限。解析也使用显式栈,避免把括号深度转成函数调用深度。

function applyBinary(operator: BinaryOperator, left: number, right: number): number {
  switch (operator) {
    case '+':
      return left + right
    case '-':
      return left - right
    case '*':
      return left * right
    case '/':
      if (right === 0) throw new RangeError('除数不能为 0')
      return Math.trunc(left / right)
  }
}

function evaluate(ast: Expression): number {
  const work: { node: Expression; expanded: boolean }[] = [{ node: ast, expanded: false }]
  const values: number[] = []

  while (work.length) {
    const { node, expanded } = work.pop()!
    switch (node.type) {
      case 'NumericLiteral':
        values.push(node.value)
        break
      case 'ParenthesizedExpression':
        work.push({ node: node.expression, expanded: false })
        break
      case 'UnaryExpression':
        if (expanded) {
          values.push(-values.pop()!)
        } else {
          work.push({ node, expanded: true }, { node: node.argument, expanded: false })
        }
        break
      case 'BinaryExpression':
        if (expanded) {
          const right = values.pop()!
          const left = values.pop()!
          const result = applyBinary(node.operator, left, right)
          if (!Number.isSafeInteger(result)) throw new RangeError('结果超出安全整数范围')
          values.push(result)
        } else {
          work.push(
            { node, expanded: true },
            { node: node.right, expanded: false },
            { node: node.left, expanded: false }
          )
        }
        break
    }
  }

  const result = values[0]
  return result === 0 ? 0 : result
}

function calculate(s: string): number {
  return evaluate(buildExpression(tokenize(s)))
}

整数除法只保留商的整数部分,(-7) / 3 得到 -2,用 Math.floor 会算成 -3。这也是计算器与 JavaScript 本身的区别之一:对两个 Number 使用 / 时,JavaScript 保留小数部分,非零值除以零还可能得到无穷大。这里把除零和超出安全整数范围当作求值错误。 ECMAScript 2024 的 Number 除法

验证与开销

下面几组输入分别覆盖了括号、一元负号、结合性和截断方向。遇到括号不配对、未知字符或操作数缺失时抛出 SyntaxError,除零和安全整数越界抛出 RangeError。

输入结果检查点
(1+(4+5+2)-3)+(6+8)23多层括号和返回外层后的运算
-(2 + 3) * 4-20一元负号应用于整个括号组
2 + 3 * 5 / 29加法右侧先乘后除
2 + 3 * (5 / 2)8括号内先做整数除法,结果比上一行少 1
8 / 4 / 21连续除法按左结合求值
7 / -3-2负商向零截断
1a2、1 +、2)SyntaxError分别拒绝未知字符、缺失操作数和多余的右括号
1 / (2 - 2)RangeError除数求值后为零

本地还跑了长度为 300,000 的深层括号输入、长度为 299,999 的连续加法,以及 1,000 个用 BigInt 核对结果的生成表达式。这些用例分别检查了深层解析、左深树求值和整数运算的结果。

设输入长度为 n,扫描、构树、求值的总时间是 O(n),额外空间是 O(n)。我当时的力扣提交记录是通过测试,运行用时只超过约 16% 的提交。记录只留下了平台相对排名,具体题号、毫秒数、运行环境和计时边界都没有留下来。这个数字无法区分扫描、构树和求值各自的耗时,也无法与这里的实现直接比较。

如果题目只要一个数,边扫描边归约就能省去 token 数组和 AST 节点。只有加减和括号时,还可以用栈保存外层的累计结果和符号。保留 AST 的好处是,结合顺序可以单独检查,同一棵树也可以交给不同的程序去打印、求值或生成指令。

V8 怎样把源码变成可执行程序

V8 选择先把语法树编译成字节码。字节码可以直接交给 Ignition 解释执行,也能作为其他编译层的输入。理解这条执行路径,可以先看它和计算器共有的前端步骤。

编译前端示意图,源码经过词法、语法和语义分析后进入代码生成或解释执行
JavaScript 源码
  ↓ Scanner 做词法分析
Token 流
  ↓ Parser 做语法分析
AST(解析过程中检查早期错误,记录和分析作用域)
  ↓ 字节码生成器遍历 AST
Ignition 字节码
  ├─→ Ignition 解释执行,积累运行反馈
  └─→ Sparkplug 可直接从字节码生成基线机器码

字节码 + 运行反馈
  ↓ Maglev 或 TurboFan 可据此做推测性优化
优化机器码(由 CPU 执行)
  ↓ 假设失效并触发反优化
恢复执行状态,从对应的字节码位置继续

解析:从字符到 AST

在计算器里,tokenize 先切出数字和符号,buildExpression 再判断它们怎么组合。V8 的 Scanner 和 Parser 也有类似的分工:Scanner 从字符流识别标识符、字面量和运算符等 token,Parser 按 JavaScript 的语法识别表达式、函数声明和其他结构,并构建 AST。比如 (2 + 3) * 4 的括号已经改变了树的结合方式,AST 可以直接用子树表达这个关系。空格和注释通常也无需保留成节点,有语法意义的换行则需要在解析时处理。 V8 Scanner · ECMAScript 2024 的词法文法

JavaScript 还需要回答计算器里没有的问题。例如两个同名的 let 声明出现在同一个块里,会触发早期错误。遇到一次变量访问,引擎还要确定它对应哪个作用域里的绑定。这些工作和解析、编译前端密切相关。V8 也可以先预解析暂时用不到的函数体,到需要时再生成其完整的 AST 和字节码,以减少启动阶段的工作。 V8 惰性解析与变量分配 · ECMAScript 2024 的块级早期错误

生成字节码:同一棵树,换一种访问方式

前面的 evaluate 遇到数字就取值,遇到二元表达式就处理左右两棵子树。要增加打印或代码生成,可以复用这些节点,再给每种节点定义另一套处理逻辑。这就是访问者模式在 AST 上的用途:把对节点做什么和节点本身的数据结构分开。计算器用 switch 体现了按节点类型分派的思路。V8 的字节码生成器则有不同的节点访问方法,例如 VisitBinaryOperation 会按运算符继续分派,把算术和短路逻辑交给不同路径。 V8 12.4.254 的字节码生成器源码

Ignition 的字节码生成器把 AST 转成较紧凑的指令序列,Ignition 解释器再逐条分派。这样,同一份字节码可以交给解释器,也能作为后续编译层的输入。常量折叠和死代码消除是编译中常见的优化,能在哪一步做,要看当时掌握了哪些信息以及是否能保住 JavaScript 的语义。生成本地机器码时,还要针对目标 CPU 做指令选择和寄存器分配。 V8 的 Ignition 设计 · Sparkplug 如何从字节码生成机器码

解释执行:看一条加法怎样跑起来

用一个累加函数就能看到字节码在做什么。

function sum(arr) {
  let total = 0
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

把函数保存到 sum.js,加上一行 sum([1, 2, 3]),再运行下面的命令。

node --print-bytecode --print-bytecode-filter=sum sum.js

在 Node.js 22.23.2(V8 12.4.254.21-node.56)中,total += arr[i] 对应的指令里可以看到 Ldar r1、GetKeyedProperty 和 Add r0, [3]。它们先把下标加载到累加器,再读取数组元素,最后用累加器里的元素值和 r0 里的 total 做加法。计算器用数值栈暂存左右操作数,Ignition 用的是虚拟寄存器和累加器。 V8 的 Ignition 寄存器模型

Add r0, [3] 里的 [3] 还是一个反馈槽索引。随着函数执行,引擎会积累加法所见的值、数组访问所见的对象形状等运行反馈。同一段代码跑得越多,引擎就越有机会判断是否值得花时间生成更专门的机器码。 Maglev 的运行反馈与表示选择

即时编译:热点代码为什么值得多编译一次

ECMAScript 定义了 JavaScript 的语义,具体怎样执行由引擎决定。V8 用 Ignition 让代码较快开始执行,再用即时编译(JIT)减少热点代码反复执行的成本。这里的「热点」既可能是反复调用的函数,也可能是函数中持续运行的循环。

V8 的 Ignition 和 TurboFan 执行路径,含字节码、类型反馈和反优化

图中画的是 Chrome 59 搭载的 V8 5.9 所启用的两层管线,Ignition 负责解释,TurboFan 负责优化编译。后来 Chrome 91 引入 Sparkplug,快速把字节码翻译成本地机器码,省去解释器逐条分派的开销。Chrome 117 又引入 Maglev,放在 Sparkplug 和 TurboFan 之间,以较低的编译成本做推测性优化。TurboFan 可以花更多编译时间追求峰值性能。函数能走到哪一层,取决于热度、运行反馈和引擎配置。 V8 5.9 的两层管线 · Sparkplug · Maglev

回到 sum。如果调用时一直传入紧凑的小整数数组,优化编译器就可能为数组元素加载和加法生成更专门的机器码,并在运行时检查相关假设。这里的收益来自省去一些通用路径上的工作。编译耗时、启动延迟和稳态吞吐仍要分别衡量,单凭生成了机器码也无法推断它和某段 C++ 代码谁快。 V8 的数组元素种类 · Maglev 的推测性优化

反优化:假设失效后从哪里继续

假设 sum 已经按小整数数组优化,下一次却收到 [1, '2', 3]。这次的结果应该是字符串 '123':加到 '2' 时,+ 开始执行字符串拼接。传入对象数组也可能打破数组元素种类的假设。具体会不会触发反优化,取决于引擎先前生成的代码和正在检查的条件。 ECMAScript 2024 的加法语义

如果优化代码上的检查失败并触发反优化,V8 会利用编译时留下的元数据,把机器寄存器或栈里的值还原成未优化执行所需的帧和寄存器值,再从对应的字节码位置继续。这样已经完成的操作无需从函数开头再做一遍。把参数写成 TypeScript 的 number[] 可以在开发阶段检查调用方,但类型标注在生成 JavaScript 时会擦除。V8 做推测时仍然依据实际运行中看到的值。 Maglev 的反优化 · TypeScript 的类型擦除

总结

做这道题时,如果只关心结果,边扫描边归约更省空间。把 AST 留下来,则能看清为什么 2 + 3 * 4 先算乘法,也能把同一棵树交给求值器或代码生成器。V8 把解析后的结构进一步变成字节码,让程序能较早开始执行。至于一段代码值不值得继续编译、能对实际输入做多强的假设,要等它跑起来以后才能判断。