手写递归下降 Parser：把 token 拼成 AST
本节目标
- 理解“语法分析”如何把 token 流拼成树
- 用手写**递归下降（Recursive Descent）**解析器，处理运算符优先级
- 得到一个能跑、能打印 AST 的迷你语言
上一节我们得到了 token 流。这一步叫语法分析（Syntactic Analysis）：按照“语法规则”把 token 组装成一棵 AST。
我们用的写法叫递归下降：为每一种语法结构写一个函数，函数里再调用更细的函数。例如“表达式”分三层：
表达式 expression = 赋值 assignment
赋值 assignment = Identifier '=' 表达式 | 加减 additive
加减 additive = 乘除 multiplicative (('+'|'-') 乘除)*
乘除 multiplicative = 一元 unary (('*'|'/') 一元)*
一元 unary = ('-')? 基础 primary
基础 primary = 数字 | 字符串 | 标识符 | 调用 call | '(' 表达式 ')'
调用 call = Identifier '(' (表达式 (',' 表达式)*)? ')'优先级怎么体现？ 看调用顺序：additive 调用 multiplicative，所以 * 比 + 先结合——1 + 2 * 3 自然解析成 1 + (2 * 3)。这就是“递归下降天然表达优先级”。
动手：一个能解析算术/变量/调用的 Parser
// 运行环境：Node.js 18+（无需任何依赖，依赖上一节的 tokenize）
// 运行方式：把整段保存为 app-l4.cjs，终端执行 node app-l4.cjs
// （这里把 tokenize 一起带上，保证单文件可运行）
function tokenize(src) {
const tokens = []
let i = 0, buf = '', state = 'idle'
const isDigit = (c) => c >= '0' && c <= '9'
const isIdentStart = (c) => /[A-Za-z_$]/.test(c)
const isIdentPart = (c) => /[A-Za-z0-9_$]/.test(c)
const isSpace = (c) => c === ' ' || c === '\n' || c === '\t' || c === '\r'
const flush = (type) => { if (buf) { tokens.push({ type, value: buf }); buf = '' } }
while (i < src.length) {
const c = src[i]
if (c === '/' && src[i + 1] === '/') { flush(state === 'idle' ? null : state); while (i < src.length && src[i] !== '\n') i++; state = 'idle'; continue }
if (isSpace(c)) { flush(state === 'idle' ? null : state); state = 'idle'; i++; continue }
if (isDigit(c)) { state = 'num'; buf += c; i++; continue }
if (isIdentStart(c)) { state = 'ident'; buf += c; i++; continue }
if (isIdentPart(c) && state !== 'idle') { buf += c; i++; continue }
const two = src.slice(i, i + 2)
const multiOps = ['==', '===', '&&', '||', '<=', '>=', '!=', '!==']
if (multiOps.includes(two)) { flush(state === 'idle' ? null : state); tokens.push({ type: 'op', value: two }); state = 'idle'; i += 2; continue }
if ('+-*/%=<>!'.includes(c)) { flush(state === 'idle' ? null : state); tokens.push({ type: 'op', value: c }); state = 'idle'; i++; continue }
if (c === '(' || c === ')') { flush(state === 'idle' ? null : state); tokens.push({ type: 'paren', value: c }); state = 'idle'; i++; continue }
flush(state === 'idle' ? null : state); tokens.push({ type: 'op', value: c }); state = 'idle'; i++; continue
}
flush(state === 'idle' ? null : state)
const KEYWORDS = ['let', 'const', 'var', 'function', 'return', 'if', 'else']
return tokens.map((t) => t.type === 'ident' && KEYWORDS.includes(t.value) ? { type: 'keyword', value: t.value } : t)
}
// ---- 递归下降解析器 ----
class Parser {
constructor(tokens) { this.tokens = tokens; this.pos = 0 }
peek() { return this.tokens[this.pos] }
next() { return this.tokens[this.pos++] }
expect(type, value) {
const t = this.next()
if (!t || t.type !== type || (value !== undefined && t.value !== value))
throw new Error('语法错误：期望 ' + (value || type) + '，但得到 ' + JSON.stringify(t))
return t
}
// 程序 = 多条语句
parseProgram() {
const body = []
while (this.pos < this.tokens.length) body.push(this.parseStatement())
return { type: 'Program', body }
}
parseStatement() {
const t = this.peek()
let stmt
if (t && t.type === 'keyword' && ['let', 'const', 'var'].includes(t.value))
stmt = this.parseVarDecl()
else
stmt = { type: 'ExpressionStatement', expression: this.parseExpression() }
// 消费可选的语句结束符 ;（不强制，兼容无分号写法）
if (this.peek() && this.peek().type === 'op' && this.peek().value === ';') this.next()
return stmt
}
parseVarDecl() {
const kind = this.next().value
const name = this.expect('ident').value
this.expect('op', '=')
const init = this.parseExpression()
return { type: 'VariableDeclaration', kind, id: { type: 'Identifier', name }, init }
}
// 表达式入口：先试赋值，否则按加减处理
parseExpression() { return this.parseAssignment() }
parseAssignment() {
const left = this.parseAdditive()
const t = this.peek()
if (t && t.type === 'op' && t.value === '=' && left.type === 'Identifier') {
this.next()
return { type: 'AssignmentExpression', operator: '=', left, right: this.parseExpression() }
}
return left
}
// 加减（+ -），左结合
parseAdditive() {
let node = this.parseMultiplicative()
while (this.peek() && this.peek().type === 'op' && ['+', '-'].includes(this.peek().value)) {
const op = this.next().value
node = { type: 'BinaryExpression', operator: op, left: node, right: this.parseMultiplicative() }
}
return node
}
// 乘除（* /），左结合，优先级高于加减
parseMultiplicative() {
let node = this.parseUnary()
while (this.peek() && this.peek().type === 'op' && ['*', '/'].includes(this.peek().value)) {
const op = this.next().value
node = { type: 'BinaryExpression', operator: op, left: node, right: this.parseUnary() }
}
return node
}
parseUnary() {
if (this.peek() && this.peek().type === 'op' && this.peek().value === '-') {
this.next()
return { type: 'UnaryExpression', operator: '-', argument: this.parseUnary() }
}
return this.parsePrimary()
}
parsePrimary() {
const t = this.next()
if (!t) throw new Error('语法错误：表达式不完整')
if (t.type === 'num') return { type: 'Literal', value: Number(t.value) }
if (t.type === 'string') return { type: 'Literal', value: t.value }
if (t.type === 'ident') {
if (this.peek() && this.peek().type === 'paren' && this.peek().value === '(') {
this.next() // 吃掉 (
const args = []
if (!(this.peek() && this.peek().type === 'paren' && this.peek().value === ')')) {
args.push(this.parseExpression())
while (this.peek() && this.peek().type === 'op' && this.peek().value === ',') { this.next(); args.push(this.parseExpression()) }
}
this.expect('paren', ')')
return { type: 'CallExpression', callee: { type: 'Identifier', name: t.value }, arguments: args }
}
return { type: 'Identifier', name: t.value }
}
if (t.type === 'paren' && t.value === '(') {
const e = this.parseExpression()
this.expect('paren', ')')
return e
}
throw new Error('语法错误：无法解析 ' + JSON.stringify(t))
}
}
// === 调用示例 ===
function parse(src) { return new Parser(tokenize(src)).parseProgram() }
const code = 'let x = 1 + 2 * 3; foo(10)'
const ast = parse(code)
console.log(JSON.stringify(ast, null, 2))
// 关键结构（节选）：
// BinaryExpression(+) 的 right 是 BinaryExpression(*)，说明 * 先于 + 结合：
// left: Literal(1)
// right: BinaryExpression(*) -> left: Literal(2), right: Literal(3)
// 以及 CallExpression(foo, args:[Literal(10)])名词解释
递归下降（Recursive Descent）：一种手写语法分析的方法——为每一种语法结构写一个解析函数，函数内部再调用更细的函数去解析它的子结构。“递归”指的是这些函数常常互相调用（多为间接递归）。它是最容易让人“看懂”的解析写法。
运算符优先级（Precedence）：不同运算符结合的先后顺序（例如 * 先于 +）。在递归下降里，优先级不是靠查表，而是靠“谁调用谁”自然表达：让 additive 去调用 multiplicative，就意味着 * 会在更内层先结合。
课后练习
练习 1：1 + 2 * 3 经过本节的 Parser 后，最外层的 BinaryExpression 节点的 operator 是什么？它的 right 子树根节点又是什么类型？
答案：最外层
operator是+；它的right是一棵BinaryExpression，其operator为*。这正说明*（在内层）先于+（在外层）结合，符合数学优先级。
练习 2：如果把 parseAdditive 与 parseMultiplicative 的调用关系反过来（让 additive 不再调用 multiplicative，而是反过来），会发生什么？
答案：优先级会颠倒——
*会比+后结合。原本1 + 2 * 3会被错误解析成(1 + 2) * 3，计算结果从 7 变成 9。这恰好证明：递归下降里“调用方向”直接决定了运算符优先级。
本节小结（观点与完整描述）
本节你写出的是编译原理里最经典、也最“肉眼可读”的语法分析器：递归下降 = 为每种语法写个函数，函数间互相调用。你不必死记那套文法，只要理解一件事——优先级是“喊谁来帮忙”喊出来的：additive 调用 multiplicative，所以 * 自然先于 + 结合。再配上 peek / next / expect 这三个小工具（看一眼、吃掉、断言并吃掉），你就能从 token 流里拼出任意复杂的树。loc 字段还能在出错时带上“第几行第几列”。但也要清醒：手写解析器只适合玩具语言；真实 JS 的边界情况多到吓人，所以下一节起我们把“解析”这步交给 acorn / @babel/parser，把精力留在真正有价值的第 ② 步——转换。