编译原理与语言实现学习笔记#

从词法分析到代码生成，系统理解编译器如何把源代码变成可执行程序。

1 · 编译器概述#

1.1 编译器的阶段#

一个典型编译器的工作流程：

1.2 编译器 vs 解释器#

编译器：

• 一次性把源码翻译成目标代码
• 执行时不依赖源码
• 典型：C、C++、Rust、Go

解释器：

• 边解释边执行
• 不生成独立的目标文件
• 典型：Python、Ruby、早期的 JavaScript

混合模式：

• 先编译成字节码，再由虚拟机执行或 JIT 编译
• 典型：Java（JVM）、V8 引擎

1.3 常见编译器架构#

GCC

• 多语言前端 → GIMPLE（IR）→ 后端生成目标代码
• 历史悠久，优化能力强

LLVM

• 前端（如 Clang）生成 LLVM IR
• 中端进行优化
• 后端生成多种目标代码
• 模块化设计，被广泛采用

V8

• JS 源码 → AST → 字节码（Ignition）
• 热点代码 JIT 编译为机器码（TurboFan）

2 · 词法分析#

2.1 Token#

词法分析把源代码字符流切分成 Token。

例如代码 int x = 10 + 20; 会被切成：

常见 Token 类型：

• 关键字：if、while、return
• 标识符：变量名、函数名
• 字面量：数字、字符串、布尔值
• 运算符：+、-、*、/、==
• 分隔符：(、)、{、}、;

2.2 有限自动机#

词法分析用有限自动机识别 Token。

正则表达式 → NFA（非确定有限自动机）→ DFA（确定有限自动机）

DFA 执行更快，因为每个状态对每个输入字符只有一条转移路径。

2.3 手写 Lexer 示例#

func lex(src string) []Token {
    var tokens []Token
    i := 0
    for i < len(src) {
        c := src[i]
        switch {
        case isWhitespace(c):
            i++
        case isDigit(c):
            j := i
            for j < len(src) && isDigit(src[j]) { j++ }
            tokens = append(tokens, Token{NUMBER, src[i:j]})
            i = j
        case isAlpha(c):
            j := i
            for j < len(src) && isAlphaNum(src[j]) { j++ }
            word := src[i:j]
            if isKeyword(word) {
                tokens = append(tokens, Token{KEYWORD, word})
            } else {
                tokens = append(tokens, Token{IDENTIFIER, word})
            }
            i = j
        case c == '+':
            tokens = append(tokens, Token{PLUS, "+"})
            i++
        case c == '=':
            if i+1 < len(src) && src[i+1] == '=' {
                tokens = append(tokens, Token{EQ, "=="})
                i += 2
            } else {
                tokens = append(tokens, Token{ASSIGN, "="})
                i++
            }
        // ... 更多符号
        default:
            panic("unexpected char: " + string(c))
        }
    }
    return tokens
}

2.4 词法分析难点#

• 字符串转义："Hello\nWorld" 中的 \n 应解析为换行符
• 注释处理：单行 //、多行 /* */、文档注释 /** */
• 数字格式：整数、浮点数、十六进制、科学计数法
• 最大 munch 原则：>>= 应作为一个 Token，而不是 >> + =

3 · 语法分析#

3.1 上下文无关文法#

编程语言通常用上下文无关文法（CFG）描述。

BNF 示例：

3.2 解析方法#

3.3 递归下降解析器#

func parseExpr() Expr {
    left := parseTerm()
    for match(PLUS) || match(MINUS) {
        op := consume()
        right := parseTerm()
        left = BinaryOp{Op: op, Left: left, Right: right}
    }
    return left
}

func parseTerm() Expr {
    left := parseFactor()
    for match(MUL) || match(DIV) {
        op := consume()
        right := parseFactor()
        left = BinaryOp{Op: op, Left: left, Right: right}
    }
    return left
}

func parseFactor() Expr {
    if match(NUMBER) {
        return Literal{Value: consume().value}
    }
    if match(LPAREN) {
        consume()
        expr := parseExpr()
        expect(RPAREN)
        return expr
    }
    panic("unexpected token")
}

3.4 抽象语法树（AST）#

AST 是源代码的结构化表示，去掉了括号等语法细节。

表达式 1 + 2 * 3 的 AST：

AST 节点类型：

• BinaryOp：二元运算
• UnaryOp：一元运算
• Literal：字面量
• Identifier：标识符
• VarDecl：变量声明
• IfStmt：if 语句
• WhileStmt：while 语句
• FuncDecl：函数声明

3.5 Pratt Parser#

Pratt Parser 用绑定权（Binding Power）处理运算符优先级。

func parseExpression(minBP int) Expr {
    lhs := parseNud()  // null denotation，处理前缀
    for {
        op := peek()
        leftBP, rightBP := getBindingPower(op)
        if leftBP < minBP {
            break
        }
        consume()
        rhs := parseExpression(rightBP)
        lhs = BinaryOp{Op: op, Left: lhs, Right: rhs}
    }
    return lhs
}

4 · 语义分析#

4.1 符号表#

符号表记录变量、函数、类型的定义信息。

type Symbol struct {
    Name    string
    Type    Type
    Scope   *Scope
    Kind    string // var / func / param
    Offset  int
}

type Scope struct {
    Parent *Scope
    Symbols map[string]*Symbol
}

作用域链：内层作用域可以访问外层变量，但外层不能访问内层。

4.2 类型检查#

静态类型语言在编译期检查类型。

常见错误：

• int 和 string 相加
• 函数参数数量/类型不匹配
• 返回类型不匹配

类型推断：

let x = 5;      // 编译器推断为 i32
let y = "hello"; // 推断为 &str

4.3 语义检查#

• 变量未定义 / 重复定义
• break / continue 在循环外使用
• return 在非函数内使用
• 不可达代码
• 变量未使用 / 未初始化

5 · 中间代码生成#

5.1 为什么需要 IR#

如果没有 IR：

• N 种前端 × M 种后端 = N×M 个翻译器

有了 IR：

• N 个前端生成 IR
• M 个后端把 IR 翻译到目标平台
• 只需 N + M 个翻译器

5.2 常见 IR#

三地址码（TAC）：

SSA（静态单赋值）： 每个变量只赋值一次。

如果变量在不同分支中有不同值，用 φ 函数合并：

LLVM IR： 基于 SSA 的强类型 IR，指令接近汇编但更抽象。

5.3 IR 的优势#

• 与源语言和目标机器无关
• 优化在 IR 层进行，所有语言共享
• 便于移植到新平台

6 · 代码优化#

6.1 常见优化#

6.2 优化级别#

• -O0：不优化，调试信息完整
• -O1：基本优化
• -O2：常规优化（推荐）
• -O3：激进优化
• -Os：优化代码大小
• -Ofast：激进，可能违反标准

6.3 优化的限制#

编译器只能做安全的优化，不能改变程序语义。例如：

• 不能随意重排带副作用的函数调用
• 浮点数优化要谨慎（结合律在浮点数中不严格成立）

7 · 目标代码生成#

7.1 寄存器分配#

把 IR 中的虚拟寄存器映射到物理寄存器。

图着色算法：

• 构造寄存器干涉图
• 相邻节点不能分配同一个寄存器
• 如果颜色不够，选择某些值溢出到栈（Spill）

线性扫描：

• 按变量生命周期扫描
• 速度快，适合 JIT

7.2 指令选择#

把 IR 指令映射到目标机器指令。

例如 IR：

x86-64 汇编：

mov eax, a
add eax, b
imul eax, c
mov t2, eax

7.3 指令调度#

重排指令顺序以利用 CPU 流水线，减少停顿。

8 · 链接与加载#

8.1 链接器#

链接器把多个目标文件和库组合成可执行文件。

主要工作：

• 符号解析：把符号引用绑定到定义
• 重定位：调整地址引用

静态链接：

• 把库代码直接复制到可执行文件
• 优点：不依赖外部环境
• 缺点：体积大、多个程序重复加载同一库

动态链接：

• 运行时才加载共享库
• 优点：节省内存、更新库不需要重新编译程序
• 缺点：依赖环境

8.2 ELF 文件#

Linux 可执行文件用 ELF 格式。

主要部分：

• ELF Header：文件类型、入口地址
• Program Header Table：段信息，加载器用
• Section Header Table：节信息，链接器用
• .text：代码段
• .data：已初始化数据
• .rodata：只读数据
• .bss：未初始化数据
• .symtab：符号表

8.3 加载器#

程序执行时，加载器：

1. 读取 ELF Header
2. 创建虚拟内存空间
3. 映射代码段、数据段
4. 设置栈和堆
5. 跳转到入口点 _start
6. _start 调用 __libc_start_main，再调用 main

9 · 垃圾回收#

9.1 为什么需要 GC#

带 GC 的语言（Java、Go、Python）需要运行时自动回收不再使用的内存。

9.2 经典 GC 算法#

标记-清除（Mark-Sweep）

• 从 GC Root 出发标记可达对象
• 清除未标记对象
• 缺点：内存碎片

复制算法（Copying）

• 把存活对象从 From 区复制到 To 区
• 优点：无碎片
• 缺点：需要两倍空间

标记-压缩（Mark-Compact）

• 标记存活对象
• 把它们移动到内存一端
• 消除碎片

分代回收

• 新生代：大部分对象很快死亡，用复制算法
• 老年代：存活时间长，用标记-清除/压缩

三色标记法

• 白色：未访问
• 灰色：已访问，子节点未处理
• 黑色：已处理完成

9.3 Go 的 GC#

• 并发标记-清除
• 低 STW（Stop The World）停顿
• 写屏障（Write Barrier）：保证并发标记时引用关系正确
• 目标：毫秒级停顿

10 · 自己实现一个小语言#

如果你想动手，可以从一个极简语言开始：

实现步骤：

1. 手写 Lexer，识别关键字、数字、标识符、符号
2. 递归下降 Parser 生成 AST
3. 遍历 AST 解释执行，或者生成字节码
4. 用栈式虚拟机执行字节码
5. 逐步添加变量作用域、函数调用、类型检查

推荐项目：

• Crafting Interpreters（经典教程）
• 用 Python/Go/Rust 写一门解释型语言