AST：从字符串到可变换程序

1. AST 是什么

源代码本质上是字符串，但直接用正则替换字符串无法可靠理解嵌套、作用域、注释、字符串字面量和语法上下文。抽象语法树（Abstract Syntax Tree，AST）把代码表示成带类型的树节点，保留程序结构而忽略不影响语义的空白。

例如：

const answer = add(2, 2)

可以抽象为：

Program
└── VariableDeclaration (const)
    └── VariableDeclarator
        ├── Identifier (answer)
        └── CallExpression
            ├── Identifier (add)
            └── NumericLiteral (2), NumericLiteral (2)

AST 不是固定的一种 JSON 格式。ESTree、Babel AST、TypeScript AST 的节点命名和字段可能不同；编写工具前要确认 parser、traverse 和 generator 属于同一生态，并用 fixture 锁定节点形状。

2. 编译器四个核心阶段

2.1 词法分析（Lexing）

词法分析器从字符流生成 token，例如关键字、标识符、数字、字符串、操作符和括号：

const x = 2 + 3
  -> [const] [identifier:x] [=] [number:2] [+] [number:3]

token 通常附带起止位置、行列号和原始文本。空白和注释一般不参与语法结构，但格式化器、代码迁移和 source map 可能需要保留它们。

2.2 语法分析（Parsing）

Parser 根据 token 的语法规则构造 AST。递归下降、Pratt parser 等实现能够处理嵌套表达式、优先级和语句边界。遇到缺少括号、未闭合字符串或非法 token 时应报告位置明确的错误，不要默默生成半棵树。

import { parse } from '@babel/parser'

const ast = parse('const answer = add(2, 2)', {
  sourceType: 'unambiguous',
  plugins: ['jsx', 'typescript'],
  sourceFilename: 'input.tsx',
})

sourceType、JSX/TypeScript 插件、装饰器和 proposal 配置必须与项目语法匹配。解析器接受的语法越宽，不代表目标运行时就支持这些语义。

2.3 语义分析

语义分析关注 AST 结构以外的关系：

标识符是否在作用域中定义；
变量/函数引用指向哪个绑定；
类型是否兼容；
模块导入是否存在、是否有副作用；
变换是否改变 this、求值顺序、异常和短路语义。

Babel 可以提供 scope/binding 信息，但不替代 TypeScript 的完整类型检查。低代码或公式 DSL 更应建立白名单语法和显式类型系统，不能把用户输入直接当 JavaScript 执行。

2.4 代码生成

Generator 遍历新 AST 生成目标代码，可同时生成 source map。生成器应负责正确的括号、分号、转义和注释；不要把节点字段直接拼成字符串。

3. 节点、父子关系和路径

以 Babel AST 为例：

{
  type: 'CallExpression',
  callee: { type: 'Identifier', name: 'add' },
  arguments: [
    { type: 'NumericLiteral', value: 2 },
    { type: 'NumericLiteral', value: 2 },
  ],
}

遍历库通常把节点包装成 NodePath，除了 node 还提供：

parent/parentPath：向上查找上下文；
scope：查询 binding、生成唯一标识符；
replaceWith、insertBefore、insertAfter、remove：结构化修改；
isIdentifier 等类型判断：避免手写字符串比较；
skip/stop：控制遍历范围。

4. Visitor：进入和退出

AST 是树，访问器模式把“遇到某类节点时做什么”与遍历算法分离：

import traverse from '@babel/traverse'
const calls = []

traverse(ast, {
  CallExpression(path) {
    const callee = path.get('callee')
    if (!callee.isIdentifier()) return
    calls.push({ name: callee.node.name, loc: path.node.loc })
  },
})

这个 visitor 只收集直接调用的名称和位置。不能看到 add(a, b) 就将它替换为 a + b：同名函数可能存在局部绑定、运行时替换或额外副作用，参数是数值字面量也不能证明函数等价于加法。优化必须先确认绑定及其语义契约。

对于嵌套节点，enter 在子节点之前执行，exit 在子节点之后执行：

traverse(ast, {
  FunctionDeclaration: {
    enter(path) { /* 建立函数作用域 */ },
    exit(path) { /* 完成统计或校验 */ },
  },
})

修改正在遍历的树时要注意新节点是否会再次被访问、是否需要 skip()，以及替换后父子引用是否仍然完整。复杂转换应拆成“收集 -> 校验 -> 修改”几个阶段，避免边遍历边依赖尚未更新的状态。

5. 一个最小转换流程

import { parse } from '@babel/parser'
import traverse from '@babel/traverse'
import generate from '@babel/generator'
import * as t from '@babel/types'

export function transform(source, filename = 'input.js') {
  const ast = parse(source, { sourceType: 'module', sourceFilename: filename })

  traverse(ast, {
    Identifier(path) {
      if (path.node.name !== '__DEV__') return
      // 仅替换引用，不误改对象属性键或声明名。
      // 本地绑定的同名变量属于业务语义，不能当成全局编译常量处理。
      if (path.isReferencedIdentifier() && !path.scope.getBinding('__DEV__')) {
        path.replaceWith(t.booleanLiteral(false))
      }
    },
  })

  return generate(ast, { sourceMaps: true, sourceFileName: filename }, source)
}

生产转换还应：

保留 sourceFilename、输入 source map 和注释策略；
对每种语法写正例、反例和边界 fixture；
检查变换前后的运行时语义，而不只是字符串快照；
在类型检查、Lint 和构建失败时停止发布；
对未知语法采用安全失败或跳过，不能静默破坏文件。

6. 编译器示例的正确抽象

教学型 Lisp 编译器常把 (add 2 (subtract 4 2)) 依次转换为：

字符 -> paren/name/number token
  -> CallExpression(name, params)
  -> JavaScript CallExpression(callee, arguments)
  -> add(2, subtract(4, 2));

表示	调用节点的关键结构	父子关系
输入 AST	`CallExpression { name, params }`	嵌套表达式放在 `params` 中
目标 AST	`CallExpression { callee: Identifier, arguments }`	嵌套调用仍然是参数表达式
顶层语句	`ExpressionStatement { expression }`	放入 `Program.body`，生成时补语句分隔

转换器需要知道新节点应加入哪个父节点的参数或语句列表；可递归返回新节点，再由父节点接收，避免把输出上下文挂到输入 AST 上。这里的结构转换并未做类型检查或名称解析，不能把 transformer 直接等同于完整的语义分析器。

实现时要为游标越界、未闭合字符串、缺少右括号和未知 token 报告明确错误。扫描字符时先检查 current < input.length，尤其不能直接对可能为 undefined 的字符做 /[a-z]/i.test(char)：正则会把它转成字符串 "undefined"，导致字母扫描不终止。字符串扫描也必须在到达输入末尾时抛错，生成字符串字面量则需要处理引号、反斜杠和换行转义。

这个例子用于理解流水线，不应直接用于解析 JavaScript：真实 JavaScript 还包含作用域、运算符优先级、异步语义、类、模块、注释、JSX 和错误恢复。工程实现优先使用成熟 parser/traverse/generator，而不是用正则或不完整的自制解析器处理生产代码。

7. AST 的工程应用

7.1 Codemod 和版本迁移

通过节点类型和 binding 做结构化迁移，例如把旧 API 调用改为新 API，同时保留别名和导入。迁移脚本应可重复运行（幂等），输出变更 diff，并在 CI 中用 fixture 防止误改。

7.2 Lint 和安全扫描

Lint 可检查 eval、危险 DOM API、未处理 Promise 或团队约定；安全规则应考虑别名、可选链、动态属性和跨文件关系，不能只搜索字符串。规则命中需带位置、修复建议和误报抑制机制。

7.3 按需引入和代码优化

根据 ImportDeclaration、JSX 使用和 binding 判断真正引用的组件，再生成具体模块和样式导入。此类转换必须处理默认/命名/命名空间导入、别名、动态用法和副作用；详见 Babel 插件开发与调试。

7.4 低代码和公式 DSL

推荐使用独立 DSL AST：

用户表达式 -> 受限 tokenizer/parser -> DSL AST
  -> 类型/权限/复杂度校验 -> 解释执行或生成安全查询

不要把任意用户字符串交给 eval/new Function。限制函数白名单、最大深度、执行时间和数据访问范围，并对错误和超时做可观测处理。

8. 性能与安全边界

大文件 AST 可能占用大量内存，支持流式/分文件处理或设置大小上限；
多次全树遍历会放大构建耗时，合并可兼容的 visitor 或缓存中间结果；
生成代码后要验证 source map，错误堆栈必须能定位到源文件；
插件处理第三方代码时要隔离路径和依赖，避免执行任意源码；
变换应记录输入版本、插件版本、配置哈希，便于重现和回滚。

9. 面试追问速答

Q: AST 和正则替换有什么区别？

A: AST 有语法结构、父子关系和作用域信息，能区分代码、字符串和注释中的同名文本，适合嵌套和语义变换；正则适合简单文本格式，不应承担生产级 JavaScript 解析。

Q: AST 转换为什么需要 `enter` 和 `exit`？

A: enter 在进入节点时处理上下文，exit 在子节点处理完后聚合结果或做后置校验；例如作用域建立、表达式折叠和统计都可能需要不同阶段。

Q: parser 能解析就说明代码正确吗？

A: 只能说明语法在 parser 配置下可接受。类型、作用域、导入存在性、运行时兼容和副作用仍需语义检查、类型检查及测试。