从 AST 生成代码
本课从 AST 生成栈字节码：后序遍历，先子节点，再运算符，每个节点写一条指令。因此 1 + 2 * 3 先生成 MUL 再生成 ADD，是因为乘法在树中更深，不是重新排列源码字符。生成时间与节点数线性相关。
栈机执行运算前要有两个操作数，因此生成器将运算指令放在它们后面。IR 面板展示正在生成的程序列表，不是运行时栈。本课只生成，下一课才执行。
AST 代码生成如何工作
语法分析已把源码转成 Lit、Name、BinOp 节点。生成器读取树，追加供 VM 执行的字节码：字面量生成 LOAD_CONST，名称生成 LOAD_NAME，加乘节点在两子树生成完后追加 ADD 或 MUL。
1 + 2 * 3 与 (1 + 2) * 3 的运算与操作数相同，树却不同，所以程序不同。优先级已在解析时处理，代码生成只读取形状。
编译转换、表达式优化或 VM 后端常采用“先改树，再生成”的分工，例如常量折叠、语法降级；Babel、TypeScript 也有树变换与输出的阶段。本课 Fold 就演示这个分工。
Fold 在 emit 之前运行：先折叠左右孩子，若结果都是字面量，就用 Lit(eval(op, left, right)) 替换二元节点，再对余树使用同一生成器。1 + 2 * 3 可变为 LOAD_CONST 7。x + 2 * 3 只折叠乘法，因为名称不是字面量，余下生成三条指令。
AST 代码生成逐步演示
默认 Naive 处理 +(1, *(2, 3))，IR 起初为空。
- 展示根 +、左叶 1、右子树 * 及其叶 2、3，尚未写指令。
- 下降到 1，父运算符等待。
- 写入
LOAD_CONST 1。 - 返回 +，左子树已生成。
- 下降到右子树 *。
- 下降到 2，* 等待。
- 写入
LOAD_CONST 2。 - 返回 *。
- 下降到 3。
- 写入
LOAD_CONST 3。 - 返回 *，两孩子都已生成。
- 写入 MUL。源码先写 +，但树更深的 * 先生成。
- 返回 +。
- 写入 ADD，根最后生成。
- 得到五条：
LOAD_CONST 1, LOAD_CONST 2, LOAD_CONST 3, MUL, ADD。
切换 Fold，叶子已经是字面量，无需重写；先把 2 * 3 改为 6，再把 1 + 6 改为 7，最后只写 LOAD_CONST 7。切到 x + 2 * 3，乘法仍折叠，但加法保留，生成 LOAD_NAME x / LOAD_CONST 6 / ADD。
代码面板下降时分别高亮 emit(node.left)、emit(node.right)，生成字面量只亮 LOAD_CONST，不同时亮 LOAD_NAME。Fold 的 return Lit(...) 和 return BinOp(...) 也分别对应实际分支。
为什么 MUL 在 ADD 前
(1 + 2) * 3 的 + 更深，Naive 就先写 ADD，再写 MUL。解析器构建不同树，生成器仍按相同规则遍历。
Fold 不是另一套生成器。两变体共享 emit，只改变输入树。若先改当前节点再折叠孩子，默认根 + 会看到右边仍是 *，无法折叠成一个字面量，最后可能留下三条而非一条指令。自底向上是这次重写成立的条件。
时间与空间复杂度
n 节点的 Naive 生成 O(n) 条指令，时间 O(n)。Fold 重写 O(n)，再用 O(k) 生成余树，其中 k ≤ n。x + y 无可折叠二元节点，k=n；名称会阻止所有依赖它的祖先，但不依赖它的字面量子树仍可折叠：x + 2 * 3 的乘法仍折叠，所以 k<n。代价是线性重写，收益是可能更短的程序。递归辅助栈随树高增长，IR 与树的保存另计。
边界情况
- 括号改变树，不改变遍历规则，
(1 + 2) * 3因而产生不同程序。 - 名称阻止其祖先折叠，不阻止其他子树：
(x + 1) * 2两个二元节点都不折叠，x + 2 * 3仍可折叠乘法。 2 * 3 + 4 * 5先变成6 + 20，再变成 26；Naive 则生成七条指令。- 单个字面量只生成一条 LOAD_CONST，不再有运算符等待孩子。
- 预设都有根，不处理空树；空程序的输入处理属于解析阶段。
常见错误
- 按源码先写 ADD，栈机执行时还没有两个操作数，会下溢。
- 把反解析排版与代码生成当成相同操作。源码把 + 写在中间，栈字节码将其放在操作数之后。
- 自顶向下折叠，父在孩子成为字面量之前就决定不能优化，错过多层常量表达式。
- 为 Fold 另写生成器。两者共用 emit；若 Fold 仍写五条，应检查是否先执行重写。
- 把 IR 列表当运行时栈。这里是生成的程序，执行栈属于下一课。
模型范围
IR 是 LOAD_CONST、LOAD_NAME、ADD、MUL 等教学栈字节码，没有 if、循环，也不显示运行栈。实际编译器可能降到三地址码或 SSA，进行常量传播、死代码删除、内联，再选择机器指令和分配寄存器。
本课强调表达式树的后序生成，以及改树后复用生成器的阶段分工；完整编译器还会根据目标与控制流使用其他调度和表示。