第十一卷：编译原理与形式语言

这一卷把源文本逐步变成 token、语法树、IR 和机器码，同时保住语义。每个 pass 都有前置条件和验证点，否则优化只会更快地产生错误答案。

先修知识

• 能写函数、递归，并使用栈、树和图；可参考第一卷与第二卷。
• 理解集合、关系和基本证明会有帮助，可按需查阅 Math A。目标代码与 ABI 部分还会用到第三卷的机器模型。

覆盖内容

第 1–4 章从文法、自动机走到可计算性与复杂度；第 5–8 章沿编译过程讨论扫描、解析、名称与类型、中间表示、优化和代码生成。

第 1 章

• 1.1 字母表、字符串与文法：先定义什么算合法
• 1.2 乔姆斯基谱系与识别边界：规则需要多少记忆

第 2 章

• 2.1 DFA 设计与执行：让每个状态都有明确含义
• 2.2 NFA、子集构造与最小化：从多条可能路径到唯一状态
• 2.3 正则表达式与匹配引擎：从 Thompson 构造到性能边界

第 3 章

• 3.1 CFG、推导树与二义性：让嵌套结构只有一种解释
• 3.2 下推自动机与 CFL 边界：一个栈能记住什么

第 4 章

• 4.1 图灵机、可识别与可判定：给算法能力画一条边界
• 4.2 停机问题、归约与 Rice 定理：证明不存在通用判定器
• 4.3 P、NP 与归约：可计算之后还要问算得动吗

第 5 章

• 5.1 Token 契约与源位置：字符流怎样交给解析器
• 5.2 手写扫描器：游标、前瞻与安全边界
• 5.3 最长匹配、Lexer Mode 与生成器：多条规则怎样协作

第 6 章

• 6.1 递归下降与 AST：把优先级写进调用结构
• 6.2 FIRST、FOLLOW 与错误恢复：预测解析为何能做决定
• 6.3 LR 移入归约与语法树：从栈中的前缀恢复结构

第 7 章

• 7.1 名称解析与作用域：同一个名字究竟指向谁
• 7.2 类型检查与转换：让每个操作满足语言规则
• 7.3 IR、控制流图与 SSA：为分析暴露数据依赖

第 8 章

• 8.1 数据流分析与优化合法性：删掉的代码为什么真的能删
• 8.2 指令选择、ABI 与寄存器分配：把 IR 放进真实机器
• 8.3 AOT、JIT 与反优化：用运行时信息下注，也要能撤回

学完能做什么

• 为简单语言定义文法与识别器，说明正则、上下文无关和可判定问题的区别。
• 跟踪源位置、作用域和类型信息从字符流进入 AST 与 IR 的过程。
• 解释一项优化为什么保持程序语义，以及目标平台的 ABI 和寄存器约束怎样影响生成代码。

怎样使用这份目录

希望补理论时，从第 1 章按顺序阅读。希望动手做小语言时，可以先从第 5–6 章写扫描器和表达式解析器，再回补相关理论。每加入一个阶段，都保留输入、输出和错误位置；先用正确而简单的实现作参照，再检查优化版本的结果。