编译原理入门

已收录：本页面向「会用语言但好奇它怎么跑起来」的工程师，用最小可运行示例走通 词法 → 语法 → AST → 求值/字节码 全流程，再对照五门语言真实运行时的取舍。JS/TS/Python/Go/Rust 语言细节见对应页。

全景：语言实现的四种形态

「编译器」不只指生成机器码的工具，它泛指「把一种表示翻译成另一种表示」。语言实现按执行方式分四档：

形态	典型代表	流程	特点
纯解释	早期 JS、bash	边解析边执行（或解析完直接遍历 AST 求值）	启动快、无独立编译产物，性能差
字节码 VM	CPython、Java、.NET	源码 → 字节码 → 虚拟机解释执行	跨平台、与源码解耦，性能中
JIT 编译	V8、Java HotSpot	先解释/轻量编译，热点函数运行时编译为机器码	兼顾启动与峰值性能，复杂度高
AOT 编译	Go、Rust、C	源码 → 目标机器码（静态链接）	启动最快、无运行时解释开销

分档不是边界清晰：CPython 也会把字节码缓存为 .pyc；V8 先跑字节码解释器再逐层升级优化；Go/Rust 内部同样有「前端（解析+检查）→ 中端（IR/优化）→ 后端（机器码）」流水线。

编译器流水线（以 AOT 为例）

源码 ──词法分析──► Token 流 ──语法分析──► AST ──语义分析/类型检查──► 带类型 AST
                                                                    │
   目标机器码 ◄──后端(指令选择/寄存器分配)◄── 优化 ──中间表示(IR)◄──┘

• 前端：与语言相关。词法/语法/语义分析、类型检查（Rust 的所有权检查也在这里）；
• 中端：与语言和机器都无关。把 AST 翻译成 IR（如 SSA），做平台无关优化；
• 后端：与机器相关。指令选择、寄存器分配，产出目标平台机器码。

TS 是特例：它的「编译」就是前端的一部分——类型擦除 + 降级语法，输出 JS，没有中端/后端。

词法分析：把字符串切成 Token

词法分析器（lexer）只关心「字符怎么拼成词」，不关心语法。产物是一串带类型的 token：NUM(123)、+、(……空白与注释在此阶段被丢弃，拼不出 token 的字符报「无法识别」。

最小的正则驱动 lexer：

# 编译运行：python3（含 1/2/4 段为同一个文件，见第五节完整版）
import re

_TOKEN_RE = re.compile(r"\s*(?:(\d+)|(\+)|(-)|(\*)|(/)|(\()|(\)))")

def lex(src):
    toks, i = [], 0
    while i < len(src):
        m = _TOKEN_RE.match(src, i)
        if not m:
            raise SyntaxError(f"第 {i} 个字符无法识别: {src[i:]!r}")
        i = m.end()
        if m.group(1) is not None:
            toks.append(("NUM", int(m.group(1))))   # 数字带上值
        else:
            toks.append((m.group(0).strip(), None)) # 运算符/括号只留标签
    return toks

print(lex("1+ (2*3)"))
# [('NUM', 1), ('+', None), ('(', None), ('NUM', 2), ('*', None), ('NUM', 3), (')', None)]

工程级 lexer 常用状态机按字符逐个推进（处理字符串、注释、关键字 vs 标识符），正则适合符号简单的语言。分词正则顺序讲究：长的、具体的模式放前面（如 \d+ 先于 .），否则被短模式抢先吞掉。

语法分析：Token 流 → AST

语法分析器按文法组织 token。算术表达式用三层文法表达优先级：

expr   := term (('+'|'-') term)*      # 最低优先级，最外层递归
term   := factor (('*'|'/') factor)*
factor := NUM | '(' expr ')'          # 括号兜底，可递归回 expr

• 层与层之间天然实现了优先级：+ 的子树只能收到 term（整块乘除），所以 1+2*3 的 AST 是 1+(2*3)；
• while 循环朝左构建树 → 左结合：10-2-3 = (10-2)-3 = 5；
• 左递归（expr := expr '+' term 直接以自己开头）会让递归下降无限递归——上面写法用迭代循环避开；
• 产物 AST 把「源码的结构」物化：1+2*3 → BinOp('+', Num(1), BinOp('*', Num(2), Num(3)))。后续求值、编译都只认 AST，不再碰源码文本。

完整示例：带括号四则计算器（词法 + 语法 + 求值）

# 编译运行：python3 四则计算器（词法 1 → 语法 2 → 求值 3，三段组装）
import re

# ---------- 1. 词法分析：字符串 -> Token 流 ----------
_TOKEN_RE = re.compile(r"\s*(?:(\d+)|(\+)|(-)|(\*)|(/)|(\()|(\)))")

def lex(src):
    toks, i = [], 0
    while i < len(src):
        m = _TOKEN_RE.match(src, i)
        if not m:
            raise SyntaxError(f"第 {i} 个字符无法识别: {src[i:]!r}")
        i = m.end()
        if m.group(1) is not None:
            toks.append(("NUM", int(m.group(1))))
        else:
            toks.append((m.group(0).strip(), None))
    return toks

# ---------- 2. 语法分析：Token 流 -> AST ----------
class Num:
    def __init__(self, v):
        self.v = v
    def __repr__(self):
        return f"Num({self.v})"

class BinOp:
    def __init__(self, op, l, r):
        self.op, self.l, self.r = op, l, r
    def __repr__(self):
        return f"({self.op} {self.l} {self.r})"

def parse(toks):
    pos = 0

    def peek():
        return toks[pos] if pos < len(toks) else (None, None)

    def eat(tag):
        nonlocal pos
        t = peek()
        if t[0] != tag:
            raise SyntaxError(f"期望 {tag!r}, 实际 {t[0]!r}")
        pos += 1
        return t

    # 文法（优先级从低到高，每层一个函数）：
    #   expr   := term (('+'|'-') term)*     左结合
    #   term   := factor (('*'|'/') factor)*
    #   factor := NUM | '(' expr ')'
    def expr():
        node = term()
        while peek()[0] in ("+", "-"):
            node = BinOp(eat(peek()[0])[0], node, term())
        return node

    def term():
        node = factor()
        while peek()[0] in ("*", "/"):
            node = BinOp(eat(peek()[0])[0], node, factor())
        return node

    def factor():
        if peek()[0] == "NUM":
            return Num(eat("NUM")[1])
        if peek()[0] == "(":
            eat("(")
            node = expr()
            eat(")")
            return node
        raise SyntaxError(f"意外的 token: {peek()}")

    ast = expr()
    if pos != len(toks):
        raise SyntaxError(f"输入末尾有多余 token: {toks[pos:]}")
    return ast

# ---------- 3. 求值：遍历 AST -> 数字 ----------
def eval_ast(n):
    if isinstance(n, Num):
        return n.v
    l, r = eval_ast(n.l), eval_ast(n.r)
    return {"+": l + r, "-": l - r, "*": l * r, "/": l / r}[n.op]

for src in ["1+2*3", "(1+2)*3", "2*3-8/4", "10-2-3"]:
    ast = parse(lex(src))
    print(f"{src} = {eval_ast(ast)}   ast={ast}")

运行输出（python3 实测；/ 是浮点除所以 8/4 得 4.0，整数除法应改用 // 运算）：

1+2*3 = 7   ast=(+ Num(1) (* Num(2) Num(3)))       # 优先级：+ 的右子是整块乘
(1+2)*3 = 9   ast=(* (+ Num(1) Num(2)) Num(3))     # 括号改变了树形
2*3-8/4 = 4.0   ast=(- (* Num(2) Num(3)) (/ Num(8) Num(4)))
10-2-3 = 5   ast=(- (- Num(10) Num(2)) Num(3))     # 左结合：(10-2)-3

错误路径同样显式：lex("1+@2") 报「第 2 个字符无法识别」，parse(lex("1++2")) 报「意外的 token: ('+', None)」，parse(lex("(1+2")) 报「期望 ')'」。词法错误报位置、语法错误报期望与实际——这是真实编译器报错信息的设计原型。

从解释到编译：AST → 字节码，栈机运行

把「求值」换成「生成指令」，解释器就变成编译器。下面把 AST 编译成最小栈机指令，再在虚拟机上执行：

# 编译运行：python3（接上文，同一文件追加；中缀树翻译为后缀指令序列）
def compile_code(node, code):
    """后序遍历 AST -> 指令序列（每个算子都用栈）"""
    if isinstance(node, Num):
        code.append(("PUSH", node.v))   # 数字直接入栈
    else:
        compile_code(node.l, code)      # 先编译左子树
        compile_code(node.r, code)      # 再编译右子树
        code.append(("BINOP", node.op)) # 弹出两个操作数，运算后压回
    return code

def run_code(code):
    stack = []
    for ins, arg in code:
        if ins == "PUSH":
            stack.append(arg)
        else:
            b, a = stack.pop(), stack.pop()
            stack.append({"+": a + b, "-": a - b, "*": a * b, "/": a / b}[arg])
    return stack[-1]

code = compile_code(parse(lex("(1+2)*3")), [])
print("code:", code)   # [('PUSH', 1), ('PUSH', 2), ('BINOP', '+'), ('PUSH', 3), ('BINOP', '*')]
print("run :", run_code(code))  # 9

这段「编译」揭示了字节码 VM 的核心直觉：中缀树的后序遍历 = 后缀指令序列，栈天然保存中间结果。CPython 的 1+2*3 与上面的 (1+2)*3 都是这类指令（LOAD_CONST/BINARY_OP）的规模化版本；区别只是多了名字、作用域、控制流（跳转指令）、异常表等。

解释器与编译器不是对立面，而是同一流水线的不同切分点：遍历 AST 直接算 = 解释器；AST 先生成指令再跑 = 字节码 VM；指令再翻译成机器码 = JIT/AOT。V8 就是 解释字节码（Ignition）→ 热点函数 JIT（TurboFan）逐级升级。

Rust 版 AST：枚举 + match 的穷尽性

同一棵 AST，Rust 用枚举表达「节点种类」——编译期就能检查所有分支都被处理：

// 编译运行：rustc
enum Expr {
    Num(i64),
    Bin(char, Box<Expr>, Box<Expr>), // Box：递归结构必须指针化
}

fn eval(e: &Expr) -> i64 {
    match e {
        Expr::Num(n) => *n,
        Expr::Bin('+', l, r) => eval(l) + eval(r),
        Expr::Bin('-', l, r) => eval(l) - eval(r),
        Expr::Bin('*', l, r) => eval(l) * eval(r),
        Expr::Bin('/', l, r) => eval(l) / eval(r),
        _ => unreachable!("表达式仅含 + - * / 四种运算符"),
    }
}

fn main() {
    // 手构 1+2*3 的 AST（parser 与 Python 版同构：lexer 按字符 + 同款递归下降）
    let ast = Expr::Bin('+', Box::new(Expr::Num(1)),
                        Box::new(Expr::Bin('*', Box::new(Expr::Num(2)), Box::new(Expr::Num(3)))));
    println!("{}", eval(&ast)); // 7
}

实测输出：7。完整版（含 lexer/parser，与 Python 版同构）用 rustc 1.98 跑出 7 / 9 / 4 / 5 与 Python 完全一致。

同一棵树，五种语言表示

语言	AST 表示	节点分派写法	结构保证
JavaScript	普通对象 {type, ...}	switch (n.type)	无——忘写分支只是 undefined
TypeScript	可辨识联合（tagged union）	switch + 穷尽检查	strict 下新增 type 提醒未处理
Python	类层级 + isinstance	if isinstance(...) / 多态方法	无——新子类忘了可能 AttributeError
Go	接口 + 结构体	switch v := n.(type)（类型断言）	编译期检查方法集，动态断言
Rust	枚举（标签联合）	match	穷尽性由编译器强制

这也是「语言对比」页同一条光谱的延续：JS/Python 把「节点分派」留到运行期，Rust 用类型把「忘处理分支」变成编译错误——AST 越复杂（真实编译器的 visitor 上百种节点），这个保证越值钱。

五门语言运行时对照

语言	实现方式	前端之后的形态	亮点 / 代价
JavaScript	V8：字节码 + JIT	JS → Ignition 字节码 → TurboFan 机器码	热点函数自适应优化 + 去优化；单线程事件循环
TypeScript	类型擦除 → JS	只做类型检查与语法降级，输出 JS	「编译」没有后端；类型信息不参与运行
Python	CPython：AST → 字节码 → CEval 解释	.pyc 缓存字节码	字节码可 dis 查看；GIL 限制解释器内并行
Go	AOT → 原生机器码	逃逸分析决定堆/栈分配，静态链接	编译快、部署单二进制；GC 与 goroutine 在运行时内嵌
Rust	LLVM 后端 AOT	borrow checker 在前端完成，零成本抽象	无 GC runtime；优化交给 LLVM 成熟管线

阅读联动：JS 的 Event Loop 与异步在 JS 页；TS 类型擦除在 TS 页；Python 字节码与 dis 在 Python 页；Go 的 goroutine 调度器与逃逸分析在 Go 页；Rust 的所有权检查（编译期前端）与 cargo/LLVM 在 Rust 页。

术语速查

术语	一句话
Token	词法产物：(类型, 值)，如 NUM(123)
词法分析 / lexer	字符 → token 流，处理空白注释，报「无法识别」
语法分析 / parser	token 流 → AST，按文法组织，报「期望 X 实际 Y」
AST	抽象语法树：丢弃空白/括号等只对「人」有意义的结构
文法 / EBNF	语言的递归规则描述，如 `expr := term (('+'
递归下降	每个文法非终结符写一个函数的手写 parser 方式
左递归	expr := expr '+' term——递归下降必须消除（否则无限递归）
结合性	同级运算的捆绑方向：10-2-3 左结合 = (10-2)-3
优先级爬升 / Pratt	把优先级表变成数据的替代技术（处理一元/右结合更强）
语义分析	类型检查、作用域解析、所有权检查等「词法语法之外」的检查
IR	中间表示（如 SSA），跨语言复用的优化载体（LLVM IR）
字节码	面向 VM 的指令集（栈机/寄存器机），比机器码可移植
VM	解释执行字节码的运行时（CPython CEval、V8 Ignition）
JIT	运行时把热点代码编译为机器码（V8 TurboFan、HotSpot C2）
AOT	编译期一次性生成目标机器码（Go、Rust）
符号表	名字 → 类型/地址/作用域的映射，作用域解析的载体
逃逸分析	Go 编译器决定变量放栈还是堆（不逃逸则栈分配，零 GC 压力）

踩坑记录

• Lexer 正则顺序：长/特殊模式不前置会被短模式抢匹配（if 被 i 吞掉），报错还难查；
• 左递归即死循环：写出 expr := expr '+' term 的递归下降会栈溢出——要么改写为 term (op term)*，要么换 Pratt；
• 优先级与结合性搞反：验证用 10-2-3（左结合）与 2^3^2 这类右结合用例一测便知；
• eat 后忘了推进位置 / 忘了检查 token 流耗尽：parser 会静默接受残缺输入——完整示例里 parse 末尾的 pos != len(toks) 检查就是为此；
• AST 节点不可变假设：若求值/优化阶段复用并就地改 AST，多遍 pass 之间会互相污染——优先「遍历生成新结构」；
• 报错信息是编译器质量的一部分：真实编译器会做错误恢复（跳过若干 token 继续找更多错误）并给「建议」，最小实现至少做到「报位置 + 报期望/实际」；
• 把「解释器」当性能方案：AST 遍历每次重建 Python 对象成本高；先翻译成字节码再跑通常快一个量级——这也是 CPython 先 compile 再运行的原因；
• JIT 复杂度陷阱：手写 JIT（V8 级别）远超个人项目范围——需要热点的产品级路径是 Go/Rust AOT，或复用 LLVM/Graal 等成熟编译器栈。

状态与参考

• 状态：已收录（2026-09-02，完成编程语言模块规划清单最后一项）。
• 运行环境：Python 完整示例（词法/语法/求值/字节码栈机）python3 实测，输出与文中注释一致；Rust 示例 rustc 1.98 实测（完整 parser 版输出 7/9/4/5 与 Python 一致）。
• 参考：Crafting Interpreters（Robert Nystrom，配套 jlox/clox 手写实现）、The Dragon Book（工程性理论体系）、CPython 源码与 dis 文档、V8 Blog（Ignition/TurboFan 深入）。

下一步

• [ ] 扩展迷你语言：加入变量与作用域（符号表）、if/while 控制流（跳转指令）、函数调用（调用栈/帧）
• [ ] 用本页套路对照 TS「类型擦除编译」：写一个把类型注解剥掉的小 transpiler
• [ ] 进阶：把迷你计算器接入真实工具链（用 parser 生成器对比手写递归下降；或输出到 LLVM IR 跑通后端）

写作规范与页面规划请参阅领域概览。