语法分析器：递归下降把 Token 变成 AST

目标

Token 流只是"词的列表"，还没有结构。本节课用递归下降（Recursive Descent）解析法，把它变成一棵抽象语法树（AST），并正确处理运算符优先级（乘除法高于加减法）。

运行环境：Node.js v18+。运行方式：保存为 parser.js，执行 node parser.js。

// parser.js —— 复用 l1 的 tokenize，再做递归下降解析
const KEYWORDS = new Set(['var', 'if', 'else', 'while', 'func', 'return', 'print'])

function tokenize(src) {
  const tokens = []; let i = 0
  const isDigit = (c) => c >= '0' && c <= '9'
  const isAlpha = (c) => (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c === '_'
  while (i < src.length) {
    const c = src[i]
    if (c === ' ' || c === '\n' || c === '\t' || c === '\r') { i++; continue }
    if (isDigit(c)) { const s = i; while (i < src.length && isDigit(src[i])) i++; tokens.push({ type: 'NUMBER', value: Number(src.slice(s, i)) }); continue }
    if (isAlpha(c)) { const s = i; while (i < src.length && (isAlpha(src[i]) || isDigit(src[i]))) i++; const w = src.slice(s, i); tokens.push(KEYWORDS.has(w) ? { type: 'KEYWORD', value: w } : { type: 'IDENT', value: w }); continue }
    const one = { '+': 'PLUS', '-': 'MINUS', '*': 'STAR', '/': 'SLASH', '(': 'LPAREN', ')': 'RPAREN' }[c]
    if (one) { tokens.push({ type: one, value: c }); i++; continue }
    throw new Error('无法识别的字符: ' + c)
  }
  tokens.push({ type: 'EOF', value: null }); return tokens
}

function parse(src) {
  const tokens = tokenize(src); let pos = 0
  const peek = () => tokens[pos]
  const next = () => tokens[pos++]
  // 表达式：+ - （最低优先级）
  function parseExpr() {
    let node = parseTerm()
    while (peek().type === 'PLUS' || peek().type === 'MINUS') {
      const op = next().value
      node = { type: 'Binary', op, left: node, right: parseTerm() }
    }
    return node
  }
  // 项：* / （高于 + -）
  function parseTerm() {
    let node = parseFactor()
    while (peek().type === 'STAR' || peek().type === 'SLASH') {
      const op = next().value
      node = { type: 'Binary', op, left: node, right: parseFactor() }
    }
    return node
  }
  // 因子：数字 / 变量 / 括号
  function parseFactor() {
    const t = peek()
    if (t.type === 'MINUS') { next(); return { type: 'Unary', op: '-', operand: parseFactor() } }
    if (t.type === 'NUMBER') { next(); return { type: 'Number', value: t.value } }
    if (t.type === 'IDENT') { next(); return { type: 'Ident', name: t.value } }
    if (t.type === 'LPAREN') { next(); const e = parseExpr(); next(); return e }
    throw new Error('无法解析: ' + t.type)
  }
  return parseExpr()
}

// ===== 调用示例 =====
console.log(JSON.stringify(parse('1 + 2 * 3')))

输出是一棵树：Binary(+ , 1, Binary(* , 2, 3))。它精确表达了"先乘后加"——优先级就藏在函数的调用层级里。

名词解释

AST（抽象语法树）：把源码结构化的树。叶子是数字、变量等"原子"，内部节点是运算符、语句等"组合"。"抽象"指它丢掉了括号、分号等纯书写细节，只保留语义结构。
递归下降解析：一类手写解析法。为每种语法结构写一个同名函数，函数内部通过"互相调用"表达"谁包含谁"。因为语法是递归定义的（表达式里可以套表达式），所以函数也递归。
运算符优先级：不同运算符求值的先后顺序。* / 高于 + -，实现手段是让 parseTerm（处理乘除）被 parseExpr（处理加减）调用，从而乘除先结合。

课后练习

练习：上面 parseFactor 里 LPAREN 分支写的是 next() 吃掉右括号，但没校验它真的是 )。改成校验，不匹配时报清晰错误。

答案：下面是可独立运行的小例子（用 parseExpr 占位演示校验点）：

function expectRparen(tokens) {
  let pos = 0
  const next = () => tokens[pos++]
  const t = next()
  if (t.type !== 'RPAREN') throw new Error('缺少右括号 )')
  return { type: 'group' }
}
try {
  expectRparen([{ type: 'NUMBER' }]) // 故意不给 RPAREN
} catch (e) {
  console.log('捕获到:', e.message)
}

总结

递归下降是最适合人类上手的一类解析法：它把"语法规则"直接翻译成"函数",读起来几乎就是文法本身。代价是你得手动安排优先级（靠函数层级），大型语言会有几十个这样的函数。但正因为它直观，很多生产级语言（如 Go、早期 TypeScript）的解析器就是手写递归下降。理解它，你就拿到了"为什么 1 + 2 * 3 不等于 (1 + 2) * 3"的底层答案——不是数学约定，而是解析函数调用的先后顺序决定的。