CS143 编译器笔记

视频链接：CS143 编译器

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 中包含的位置
• 可以通过递归遍历 AST 生成代码。
• 临时变量：保存在 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))
• 对象布局：
  • 每个属性都在 object 内有着固定位移。
  • Cool object：Class Tag，Object Size，Dispatch Ptr（指向方法表），Attribute 1，Attribute 2
  • 子类可以继承父类的布局，并添加额外的属性。也可以重写父类中的方法，但是该方法仍然有着与父类相同的位移。
• 中间代码，较高级别的汇编语言
  • 使用寄存器，但是寄存器的数量是无限的
  • 使用类似汇编语言的控制结构
  • 使用较高级别的操作码，比如 push 会对应多条汇编指令

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 结构；每次赋值时操作引用计数比较慢。