课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这部分回顾语义分析和类型检查。

语义分析导论

编译器的前端部分如下：

  • 词法分析
    • 检测输入中的非法token。
  • 解析
    • 检测输入中格式错误的解析树。
  • 语义分析
    • “前端”的最后阶段。
    • 作用捕获所有剩余的错误。

之所以需要语义分析，主要有以下两点原因：

  • 解析无法捕获某些错误。
  • 某些语言的构造不是上下文无关的。

语义分析的要求取决于语言，coolc的语义分析检查：

  1. 所有标识符都已声明。
  2. 类型。
  3. 继承关系。
  4. 类只定义一次。
  5. 类中的方法只定义一次。
  6. 保留的标识符没有被滥用。

作用域（scope）

作用域将标识符声明与用途匹配：

  • 这是大多数语言中重要的静态分析步骤，也包括COOL。

例子

  • 例1

    这里$\text{y}$被定义为String。

  • 例2

    这里$\text{x}$没有定义。

定义

  • 标识符的作用域是程序中可访问该标识符的部分。
  • 同一标识符在程序不同部分中可能表示不同内容。
    • 同一标识符的不同作用域不重叠。
  • 标识符可能具有受限作用域。

静态作用域和动态作用域

  • 大多数语言都有静态作用域。

    • 作用域仅取决于程序文本，而不取决于运行时行为。

    • Cool有静态作用域。

    • 例子：

      下图是静态作用域的例子，相同部分表示$\text{x}$对应的类型：

  • 某些语言有动态作用域。

    • Lisp，SNOBOL。

    • Lisp已修改为大多数静态作用域。

    • 作用域依赖于程序的执行。

    • 动态作用域变量指向程序执行中最接近的封闭绑定（enclosing binding）。

    • 例子

Cool标识符

Cool标识符绑定通过如下内容引入：

  • 类声明（引入类名称）
  • 方法定义（引入方法名称）
  • Let表达式（引入对象ID）
  • 形式参数（引入对象ID）
  • 属性定义（引入对象ID）
  • Case表达式（引入对象ID）

注意：

  • 并非所有标识符都遵循最近嵌套规则。
  • 例如，Cool的类定义
    • 无法嵌套。
    • 在整个程序中全局可见。
  • 类名可以在定义之前使用

例子：

Class Foo {
	...
	let y: Bar in ...
};

Class Bar { 
	...
};
属性

在Cool中，属性名称在定义它们的类中是全局的：

Class Foo {
	f(): Int { a }; 
	a: Int <- 0;
}
方法
  • 方法名称具有复杂的规则：
    • 方法不必在使用该类的类中定义，可以在父类中定义。
    • 方法也可以重新定义（重载）。

习题

判断标识符和定义绑定是否正确：

  • Line 6 binds to line 2（F）
  • Line 9 binds to line 7（F）
  • Line 11 binds to line 2 （T）
  • Line 11 binds to line 14（F）

符号表

  • 许多语义分析可以表示为AST的递归关系
    • Before：处理AST节点$n$。
    • Recurse：处理$n$的后代。
    • After：完成处理AST节点$n$。
  • 对AST的一部分执行语义分析时，我们需要知道定义了哪些标识符。
  • 符号表是一种数据结构，可跟踪标识符的当前绑定。

例子

  • 示例：

    • let绑定的作用域是AST的一棵子树：

    • $\text x$在子树$\mathrm e$中定义。

分析步骤：

  • 在处理$\text{e}$之前，将$\text x$的定义添加到当前定义中，覆盖$\text x$的任何其他定义。
  • 递归。
  • 处理$\text e$之后，删除$\text x$的定义并恢复$\text x$的旧定义。

简单符号表

  • 对于简单的符号表，我们可以使用堆栈。
  • 操作
    • $\text{add_symbol(x)}$：
      • 将$\text x$和相关信息（例如$\text x$的类型）push到堆栈中。
    • $\text{find_symbol(x)}$：
      • 从堆栈顶部开始搜索$\text x$，返回找到的第一个$\text x$，如果找不到则返回NULL。
    • $\text{remove_symbol()}$：
      • 从堆栈中弹出元素。

该符号表适用于$\text{let}$，因为

  • 符号一次添加一个。
  • 声明完全嵌套。
推广

注意到当前符号表无法处理作用域的问题，考虑如下非法代码：

f(x: Int, x: Int){

}

该代码重复定了$\text x$，注意堆栈无法处理这点，解决该问题的方法是增加如下方法：

  • $\text{enter_scope()}$:

    • 开始一个新的嵌套作用域。

  • $\text{find_symbol(x)}$:

    • 查找当前的$\text x$（或null）。

  • $\text{add_symbol(x)}$:

    • 在表中添加符号$\text x$。

  • $\text{check_scope(x)}$:

    • 如果在当前作用域中定义了$\text x$，则为true。

  • $\text{exit_scope()}$:

    • 退出当前作用域。

课程项目包含一个符号表管理器。

类（class）

  • 因为类名可以在定义之前使用，所以我们无法用如下方式检查类名：
    • 使用符号表。
    • 一次pass。
  • 解决方案，进行两次pass
    • Pass1：收集所有类名。
    • Pass2：进行检查。
  • 语义分析需要多次pass
    • 可能需要两次以上。

类型（type）

  • 什么是类型？
    • 概念因语言而异。
  • 共同点
    • 值的集合。
    • 对值这些值的操作。
  • 类（class）是现代类型（type）概念的一种实例

例子

考虑汇编语言片段

那么$\mathrm{$ r 1, $ r 2, $ r 3}$的类型是什么？答案是无法回答，因为汇编代码中看不出类型信息。

类型的作用

  • 某些操作对于每种类型的值都是合法的。
    • 在C语言中相加函数指针和整数是没有意义的；
    • 将两个整数相加有意义；
    • 但是两者具有相同的汇编语言实现。
  • 语言的类型系统指定哪些操作对哪些类型有效。
  • 类型检查的目的是确保对正确的类型使用操作。

类型分类

  • 三种语言类型：
    • 静态类型：所有或几乎所有类型检查都是在编译过程中完成（C，Java，Cool）
    • 动态类型化：几乎所有类型检查都是程序执行的过程中完成（Lisp，Scheme，Python，Perl）
    • 无类型：无类型检查（机器代码）

对比

  • 静态类型 vs 动态类型
    • 静态类型支持者说：
      • 静态检查在编译时捕获许多编程错误。
      • 避免了运行时类型检查的开销。
    • 动态类型支持者说：
      • 静态类型系统是受限制的。
      • 在静态类型系统中难以快速进行原型制作。
  • 许多代码除了一小部分以外都是用静态类型的语言编写的：
    • C，Java中的不安全类型转换，这部分在运行时才能检测出。
  • 人们将静态类型语言转换为动态类型的语言
    • 目的是用于优化，调试。

Cool中的type

  • Cool中的类型为：
    • 类名
    • SELF_TYPE
  • type是用户声明标识符的类型。
  • 编译器为每个表达式推断类型。

类型检查与类型推断

  • 类型检查是验证全类型程序的过程。
  • 类型推断是补充缺失的类型信息的过程。
  • 两者是不同的，但是术语经常互换使用。

类型检查

  • 我们已经看到了两个用于指定编译器的各个部分的形式化符号的例子：
    • 正规表达式。
    • 上下文无关法。
  • 类型检查基于推理的逻辑规则。
  • 推理规则有如下形式：
    • 如果假设为true，那么结论为true。
  • 类型检查通过推理计算
    • 如果$E_1$和$E_2$具有特定类型，则$E_3$具有特定类型。

推理规则

  • 推理规则是“If-Then”语句的紧凑表示法。
  • 从简化的系统开始，逐步添加功能。
  • 基本模块
    • 符号$\wedge $表示”与”
    • 符号$\Rightarrow$表示“如果，那么”
    • $\mathrm{x:T}$表示“$\mathrm x$具有类型$\mathrm T$”

例子

注意到上述例子是如下推理规则的特例：

该规则通常写为

Cool类型规则具有假设和结论

其中$\vdash$表示“可以证明……”。

那么在上述记号下的例子等价于：

这两个规则提供了如何描述输入整数以及加法表达式的模板，通过填写模板，我们可以为表达式生成完整的类型：

  • 一个类型系统是合理的，如果

    • 每当$\vdash \mathrm{ e:T}$。
    • 那么$\mathrm e$被评估为$\mathrm{T}$类型的值。

  • 我们需要合理的规则

    • 但是某些合理规则比其他规则更好！

    • 例如

      比

      更好。

习题

选择第一项和第四项。

小结

  • 类型检查证明$\mathrm{e:T}$
    • 证明是在AST的结构上；
    • 证明具有AST的形状；
    • 每个AST节点都使用一种类型规则。
  • 在用于节点$\mathrm{e}$的类型规则中：
    • 假设是$\mathrm{e}$的子表达式类型；
    • 结论是$\mathrm{e}$的类型、
  • 类型是通过自下而上的$\mathrm{AST}$来计算的。

类型环境

例子

False和String：

$\text{new T}$产生一个$\text{T}$类型的对象（现在暂时忽略$\text{SELF_TYPE}$）：

$\text{Not}$和$\text{Loop}$：

变量引用的类型是什么？

局部结构规则没有足够的信息来给$\mathrm{x}$提供类型，所以我们应该在规则中增加信息，这就引出了类型环境。

类型环境

  • 类型环境为自由变量提供类型

    • 类型环境是从对象标识符（Object Identifiers）到类型（Types）的函数。
    • 变量是自由的，如果表达式中未定义该变量。

  • 令$\mathrm{O}$为从Object Identifiers到Types的函数

    • 句子$\mathrm{O}\vdash \mathrm{e:T}$
    • 读作：假设自由变量具有$\mathrm{O}$给定的类型，则可以证明表达式$\mathrm{e}$具有类型$\mathrm{T}$

  • 类型环境可以添加到先前的规则中：

  • 添加新规则：

  • 其中

习题

选择第三项，因为$\text{x}$在$\text{O}_2$中类型为$\text{T}_1$。

小结

  • 类型环境将类型赋予当前作用域中的自由标识符；
  • 类型环境从根到叶向下传递AST；
  • 类型是从叶到根的AST向上计算的。

子类型

  • 在类上定义关系$\le $：
    • $\mathrm{X\le X}$；
    • $\mathrm{X\le Y}$，如果$\mathrm X$从$\mathrm Y$继承；
    • 如果$\mathrm{X\le Y},\mathrm{Y\le Z}$，那么$\mathrm{X\le Z}$。

那么带有初始化的let：

可以推广为

赋值部分：

令$\mathrm{O_C(x)= T}$为类$\mathrm{C}$中的所有属性$\mathrm {x:T}$，

$\text{lub}$

  • 考虑：

    • 结果可以是$\mathrm{e_1}$或$\mathrm{e_2}$
    • 类型可以是$\mathrm{e_1}$的类型或$\mathrm{e_2}$的类型。
    • 所以该表达式的类型应该是大于$\text{e}_1$或$\text{e}_2$的最小超类型。

  • 定义$\mathrm{lub(X, Y)}$为$\mathrm{X,Y}$的最小上界$\mathrm{Z}$，如果

    • $\mathrm{X\le Y \wedge Y\le Z}$（$\mathrm{Z}$是上界）
    • $\mathrm{X \leq Z^{\prime} \wedge Y \leq Z^{\prime} \Rightarrow Z \leq Z^{\prime}}$（$\mathrm{Z}$是最小上界）

  • 在COOL中，两种类型的最小上界是它们在继承树中的最小共同祖先。

利用记号可以得到如下内容：

对于case表达式：

习题

第一项和第三项正确。

类型方法

考虑分派的例子：

注意我们无法通过环境推出方法的类型，所以要补充信息。

方法环境

  • 在Cool中，方法和标识符对象位于不同的名称空间中

    • 所以方法foo和对象foo可以在同一范围内共存。

  • 在类型规则中，这由用于方法签名的单独映射$\text{M}$反映

    • 例如意味着类$\mathrm C$中存在方法$\text{f}$

利用该记号对分派进行补充得到：

静态分派：

其中如下符号

<expr>@<type>.id(<expr>,...,<expr>)

表示$\mathrm{e@B.f()}$对$\text{e}$值的对象上调用类$\mathrm{B}$中的方法$\mathrm{f}$。

  • 方法环境必须添加到所有规则；

  • 在大多数情况下，$\mathrm{M}$被向下传递但并未实际使用

    • 只有分派规则使用$\mathrm{M}$

  • 例子

  • 对于某些涉及$\text{SELF_TYPE}$的情况，我们需要知道表达式出现的类

完整类型环境

  • COOL的完整类型环境：

    • 给类型赋予对象$\text{ID}$的映射$\text{O}$
    • 将类型赋予方法的映射$\text{M}$
    • 当前的类$\text{C}$

  • 完整的形式

  • 例子

小结

  • 本讲座中的规则是特定于COOL的
    • 其他一些语言有非常不同的规则。
  • 共同主题
    • 在表达式的结构上定义类型规则；
    • 变量类型由环境建模。
  • 警告：类型规则非常紧凑！

习题

选择第二项和第四项，因为$\text{x}$应该为$\text{shape}$子类，$\text{y}$应该为$\text{point}$的子类。

实现类型检查

  • 可以在AST上的一次遍历中实现COOL类型检查。
  • 类型环境沿树传递
    • 从父级到子级
  • 类型沿树传递
    • 从子级到父级

例子

例1

检查方式如下：

TypeCheck(Environment, e1 + e2) = {
    T1 = TypeCheck(Environment, e1); 
    T2 = TypeCheck(Environment, e2); 
    Check T1 == T2 == Int;
    return Int; 
}
例2

检查方式如下：

TypeCheck(Environment, let x:T <- e0 in e1) = { 
    T0 = TypeCheck(Environment, e0);
    T1 = TypeCheck(Environment.add(x:T), e1); 
    Check subtype(T0,T1);
  	return T1
 }