1 词法分析

识别 token，例如关键字、标识符、数字、操作符等。

正则文法
有限自动机
- 确定性有限自动机 DFA，每个输入只对应一个状态，转换过程中没有 epsilon。解析速度快，占用空间大。
- 不确定性有限自动机 NFA。解析速度慢，占用空间小。
- NFA 可以转为 DFA，需要找到每个状态的 epsilon 闭包。
- 实现：一个表格，行是状态，列是输入。可以进行状态压缩。

2 语法分析

生成程序的解析树。

歧义：会生成两种解析树
- 不常用：改写语法，但是没有自动的方式去改写，只能手工转换，而且会使语法更加复杂和难以阅读。
- 常用：通过一些方式消除歧义，比如定义优先级和结和性声明。
上下文无关文法 CFG：可以表达嵌套，例如 ((()))
AST：简化的解析树，只保留所需。
多种解析方式
- 递归下降：容易实现，但是一旦成功匹配非终结符 X 的某条生成式，便无法再回溯去尝试 X 的其它生成式。可以改写语法，将左公因式提取出来。
- 最左推导：存在无限递归问题，可以改写语法，改为右递归语法。
- LL(k)：从左到右查看 token，最左推导。先求出 first set 和 follow set，然后构建解析表格。大多数 CFG 都不是 LL(k) 文法，因为可能存在一个表格中有多个选择的情况。
- LR(k)：从左到右查看 token，最右推导。自底向上，移动规约，过程中需要识别 handle（有效 item），可以通过 NFA 和栈识别 handle 可行前缀，将 NFA 转为 DFA。
  - 问题：存在 reduce/reduce 冲突，shift/reduce 冲突
  - SLR（simple LR），对 LR(0) 的改进，在 shift 或 reduce 时加入一些引导提示，以减少冲突状态。
    - 对于 X -> b.，下一个输入符号为 t，当 t 属于 follow(X)，则 reduce。
    - 如果还冲突，如 S -> SaS，则不是 SLR 语法。可以通过声明优先级等解决。
    - 只使用 DFA 和 input，没有用到 stack symbol。
  - SLR(1) 不常用，LR(1) 会更强大一些，将向前看的能力内置到 item 中。
  - LALR(1) 是对 LR(1) 的优化。

3 语义分析

编译器前端的最后一关，可捕获前面两关无法捕获到的错误，因为有些语言不是上下文无关的，例如，(e1: int ^ e2: int) => e1 + e2: int

可以进行一些检查，例如：所有标识符都已经被声明了；类型；继承关系；类和类中的方法都只被定义了一次；保留关键字没有被无用；等。
作用域：静态、动态；类、方法等
大多数的语义分析都是在一个 AST 上进行递归下降分析。
符号表：在分析 AST 时追踪标识符。可通过栈实现一个简单的符号表。
类型：定义了哪些操作在哪些类型上是有效的。
- 在 AST 上进行自底向上计算而得。
- 分类：
  - 静态：编译时检查，检测多数错误
  - 动态：运行时检查，dynamic_type(E) <= static_type(E)，比如多态
  - 无类型（比如机器码）
- 类型检查：检查类型是否正确。
- 类型推断：补充缺失的类型。
类型环境：是标识 -> 类型的函数，可以给表达式中的变量一个类型。
子类型：是另一个类型的子类型，比如多态
self type：在多态的情况下，返回自身
no type：对于所有类型，No_type <= C。用于当一个类型没被定义时，其类型为 No_type，避免发生更多级联错误。但是在实现时，会导致类型体系不再是树，所以还是用 Object，而不是 No_type。

4 运行时系统 & 代码生成

运行时组织
- 运行时资源管理
- 编译时和运行时之间的关联
- 存储组织：低地址 -> 高地址，code，data。data：static data（存放全局变量、静态变量），stack（存放 AR），heap（存放生命周期长于作用域的变量等）
程序的运行是在 OS 的控制之下的。当一个代码运行时：OS 分配空间，加载代码到空间，OS 跳转到程序入口，如 main。
两个假设：运行是顺序的；当一个程序被调用后，控制总是会回到调用之前的地方。
活动：P 的调用过程被称为 P 的活动。活动树依赖于运行时行为。因为活动树可以嵌套，所以用栈跟踪比较好。
活动记录 AR：如果 F 调用 G，那么 G 的活动记录包含 F 和 G 的信息，因为需要回到 F。AR 包括 result，arg，return address。将 result 放在第一个位置，调用者就可以通过自身栈的固定位移找到它。
AR 布局和代码生成必须一起设计。因为在编译时，生成的代码需要正确地访问 AR。
对齐：大多数机器是 32 或 64 bit，一个 word 中有 4 或 8 字节。word 对齐可以提高访问速度。
栈机：唯一的存储是栈。相对于寄存器机，程序更紧凑，因为所有的操作都在栈顶，所以指令中不需要出现操作数。
- n-register 栈机：将栈顶的 n 项存到寄存器。
- 1-register 栈机中的 register 称为 accumulator，还可存储返回结果。
代码生成：使用栈机、accumulator、MIPS 指令集。
MIPS：accumulator 保存在 $a0。栈存储在内存中，向低地址增长。栈的下一个位置保存在 $sp 中，栈顶是 $sp + 4。$fp，frame pointer，指向当前活动，栈底，这样参数等就可以有一个固定位移。
MIPS 指令：
- lw reg1 offset(reg2)：load 32-bit word reg1 <- reg2 + offset
- add reg1 reg2 reg3：reg1 <- reg2 + reg3
- sw reg1 offset(reg2)：store 32-bit word reg1 -> reg2 + offset
- adddiu reg1 reg2 imm：reg1 <- reg2 + imm
- li reg imm：reg <- imm
- sub reg1 reg2 reg3：reg1 <- reg2 - reg3
- beq reg1 reg2 label：如果 reg1 = reg2，则跳转到 label
- b label：无条件跳转到 label
- jal label：跳转到 label，将下一条指令的保存保存到 $ra
- jr reg：跳转到寄存器 reg 中包含的位置

代码生成模板

cgen(i)
```
li $a0 i
```

cgen(e1 + e2)

cgen(e1)
sw $a0 0($sp)  // 将 e1 的结果保存到栈中
addiu $sp $sp -4  // push
cgen(e2)
lw $t1 4($sp)  // 将 e1 的结果从栈中取出
add $a0 $t1 $a0
addiu $sp $sp 4  // pop，恢复栈

cgen(if e1 = e2 then e3 else e4)

sw $a0 0($sp)  // 将 e1 的结果保存到栈中
    addiu $sp $sp -4
    cgen(e2)
    lw $t1 4($sp)  // 将 e1 的结果从栈中取出
    addiu $sp $sp 4  // pop
    beq $a0 $t1 true_branch  // 比较 e1 和 e2
false_branch:
    cgen(e4)
    b end_if
true_branch:
    cgen(e3)
end_if:

cgen(f(e1, ..., en))

sw $fp 0($sp)  // 保存 old fp
addiu $sp $sp -4
cgen(en)
sw $a0 0($sp)  // 保存 en 结果
addiu $sp $sp -4
...
cgen(e1)
sw $a0 0($sp)  // 保存 e1 结果
addiu $sp $sp -4
jal f_entry  // 调用者将返回地址保存到 $ra，跳转到 f_entry

cgen(def f(x1, ..., xn) = e)

f_entry:
    move $fp $sp  // 保存 old fp
    sw $ra 0($sp)  // 保存返回地址
    addiu $sp $sp -4
    cgen(e)  // 函数体
    lw $ra 4($sp)  // 加载返回地址
    addiu $sp $sp z  // 恢复栈，z = 4 * n + 8，包含返回地址和 old fp
    lw $fp 0($sp)  // 恢复 fp
    jr $ra  // 跳转到返回地址

cgen(xi)，xi 是第 i 个参数
```
lw $a0 z($fp)  // z = 4 * i
```

可以通过递归遍历 AST 生成代码。

例子：def sumto(x) = if x = 0 then 0 else x + sumto(x-1)，以下代码没有经过优化

sumto_entry:
    move $fp $sp  // 保存 old fp
    sw $ra 0($sp)  // 保存返回地址
    addiu $sp $sp -4

    // 保存 x
    lw $a0 4($fp)  // 加载 x 到 a0
    sw $a0 0($sp)  // 保存 x 到栈
    addiu $sp $sp -4

    // 加载 0
    li $a0 0

    // 加载 x
    lw $t1 4($sp)  // 加载 x 到 t1
    addiu $sp $sp 4

    // if x = 0
    beq $a0 $ t1 true1

false1:
    // 保存 x
    lw $a0 4($fp)
    sw $a0 0($sp)
    addiu $sp $sp -4

    // sumto(x-1)

    sw $ fp 0($sp)  // 保存 old fp
    addiu $sp $sp -4

    // 保存 x
    lw $a0 4($fp)
    sw $a0 0($sp)
    addiu $sp $sp -4

    li $a0 1
    lw $t1 4($sp)  // 加载 x
    sub $a0 $t1 $a0  // x - 1
    addiu $sp $sp 4

    sw $a0 0($sp)  // 保存参数 x - 1
    addiu $sp $sp -4
    jal sumto_entry

    lw $t1 4($sp)  // 加载 x
    add $a0 $t1 $a0  // x + sumto(x-1)
    addiu $sp $sp 4  // pop
    b endif1

true1:
    li $a0 0

endif1:
    lw $ra 4($sp)  // 加载返回地址
    addiu $sp $ sp 12  // 恢复栈
    lw $fp 0($sp)  // 恢复 fp
    jr $ra  // 跳转到韩辉地址

临时变量：保存在 AR 中，拥有固定地址，可以预先分配，避免不断的 push 和 pop 栈。
临时变量数量
- NT：next unused temporary
- NT(e1 + e2) = max(NT(e1), NT(e2)) + 1)，e1 的临时变量空间可以被 e2 复用。
- NT(if e1 = e2 then e3 else e4) = max(NT(e1), 1 + NT(e2), NT(e3), NT(e4))

可以重写 cgen(e1 + e2, nt)

cgen(e1, nt)
sw $a0 nt($fp) // 直接将结果保存到目标位置
cgen(e2, nt + 4)
lw $t1 nt($fp)
add $a0 $t1 $a0

对象布局：
- 每个属性都在 object 内有着固定位移。
- Cool object：Class Tag，Object Size，Dispatch Ptr（指向方法表），Attribute 1，Attribute 2
- 子类可以继承父类的布局，并添加额外的属性。也可以重写父类中的方法，但是该方法仍然有着与父类相同的位移。
中间代码，较高级别的汇编语言
- 使用寄存器，但是寄存器的数量是无限的
- 使用类似汇编语言的控制结构
- 使用较高级别的操作码，比如 push 会对应多条汇编指令
- 例子：igen(e1 + e2, t)
```
igen(e1, t1)
igen(e2, t2)
t = t1 + t2
```

5 优化

时机：AST、中间语言、汇编语言
basic block：最大数量的连续指令，块内无 label，无 jump
control flow graph：basic block 作为 node；当 block A 的最后一条指令执行后继续执行 block B 的第一条指令时，block A 到 block B 有一条边。
优化目的：提升程序的资源利用，包括执行时间、代码大小、网络消息发送等。
优化粒度：局部优化 --作用于 basic block；全局优化 -- 作用于 control flow graph（函数内）；程序间优化 -- 作用于函数间
局部优化：
- 数学简化：一些指令可被删除、简化
- 拷贝传播
- 常量折叠：一些计算可在编译时完成
- 删除公共子表达式
- 删除无用代码
- 常量传播：x = 3; q = x + y => x = 3; q = 3 + y
- 一个优化可能会开启另一个优化；可以重复优化直到没有提升。
窥孔优化可以有效提升汇编。”窥孔“是一个较短序列的指令。优化器会讲该序列替换为另一个等价序列。例如：addiu $a $ b 0 -> move $a $ b
数据流分析：基于 control flow graph
常量传播：从前往后分析
liveness 分析：从后往前分析，分析结束后，可删除无用代码。

6 高级话题

寄存器分配：在同一时间 live 的变量不可分配同一个寄存器。
- 可构建一个无向图，节点是临时变量，如果两个节点在同一时间 live，则连一条边，然后采用图着色算法分析。
- 如果颜色不够分，则选出一个候选节点放在内存中，比如放在栈中。
- 选择候选节点策略：最多冲突；最少定义和使用；避免位于循环内。
管理缓存：光靠编译器比较难做到，还需要靠程序员，比如写循环时，将内循环的变量赋值给外循环，可以提高缓存利用率。
自动内存管理 / 垃圾回收
- 如何知道一个对象不会再被用到？程序只能使用它可以找到的对象。一个对象 x 是可达的，仅当寄存器包含指向 x 的指针，或者另一个可被找到的对象 y 包含了指向 x 的指针。可以从寄存器开始并跟随这些指针来找到所有可达对象。不可达对象即为垃圾。
- 可以使用计数器来跟踪对象的被引用次数。栈中保存了 AR，也可以知道哪些对象被引用。
- 垃圾回收步骤：为新对象分配所需空间；当空间将被用完时，计算哪些对象也许还会被用到，释放那些不会被用到对象的空间。
- 方式一：标记 & 清除
  - 标记阶段：跟踪可达对象。每个对象都有 mark bit。问题：需要空间来构建 todo 列表，todo 列表的大小又不可预知。解决：使用反向指针，将指针反向指向其父，从而将 free 列表保存在 free 对象中。
  - 清除阶段：回收垃圾对象。
- 方式二：停止 & 拷贝
  - 内存被分为两部分，old space 用来分配，new space为 GC 保留。当 old space 满了后，将所有可达对象拷贝到 new space，然后 old space 和 new space 互换。
  - 最快的 GC，但是一些语言不允许拷贝，如 C/C++
- 方式三：引用计数
  - 优点：实现容易；垃圾回收时无需太多停顿。缺点：无法回收 circular 结构；每次赋值时操作引用计数比较慢。

阿萍的博客

CS143 编译器笔记