# 阶段任务

这一阶段的任务是，对 Decaf 程序开展语义分析。 语义分析一般沿着语法树结构进行，并借助属性文法来开展，这种做法一般称为“语法驱动”或“语法制导” (syntax-guided)。 按照遍历 AST 的趟数，语义分析可以分为两种：

第一种，语义分析只遍历一趟 AST。这种方式的优点是编写的总代码量比较少，分析速度快，而且语法分析、语义分析、甚至中间代码翻译都可以同时进行。 但是它的缺点在于语义分析能够利用的信息严重受限于语法分析的顺序，通常要求所引用的所有符号都必须在前面已经声明。 例如 C 语言就需要通过前向声明才能使用后面定义的类型（如结构体等）或函数。这些属于历史糟粕，现代编译器很少有采用这种形式来实现的。

第二种，语义分析阶段多趟遍历 AST。这种方式的优点是功能强大，能够不受限于符号定义的语法顺序，且尽最大可能提取源程序的语义信息，实现逻辑简单。 缺点在于由于需要多次遍历，运行时开销可能较大。然而借助于现代强大的硬件设计和代码优化，这个缺点几乎可以被忽略。我们采用这一种。

语义分析的目的是理解输入程序的“含义”，具体来说，需要明确：

* 声明了哪些标识符
* 每一处使用的标识符对应于哪一处的声明
* 各语句和表达式是否类型正确

如果在语义分析阶段发现问题，那么整个编译过程在这一阶段结束后就终止，并报告编译错误。 否则，格式化输出符号表。

## 符号表构建

针对 Decaf 程序中所有定义的标识符，包括类名、方法名、变量名等，我们统一用一种具有层次结构的符号表来维护。 使用符号表的好处主要有两个： 第一，在分析各语句和表达式时，若它们引用了某些标识符，我们可以在符号表中查询这些符号是否有定义以及相关信息（如类型）； 第二，符号表的层次结构与作用域是一一对应的，因此容易检查出符号定义是否有冲突。

## 类型检查

完成符号表构建后，我们就可以自顶向下地遍历 AST，逐一对每个语句和表达式进行类型检查。 对于静态类型 (statically-typed) 语言，在语言设计之初，设计者都会考虑该语言支持表达哪些类型，并给出定型规则 (typing rules)。 在已知定型规则的情况下编码实现类型检查算法并不困难——往往只要逐条将其翻译为代码即可。

在 Scala 版的编译器中，上述两个步骤分别对应到了 `Namer` 和 `Typer` 类。 但是，这仅是一种粗略的划分，细心的同学会发现，我们在 `Namer` 类中有时候也会做一点类型检查（`Typer` 该做的事情）。 在更加复杂的工业界语言（如 Scala）中，这两个步骤往往有更强的耦合性。

## 相关文件

与本阶段相关的文件有：

```
src
└── main
    └── scala
        └── decaf
            └── frontend
            │   ├── annot
            │   │   ├── Annot.scala         标注的基类
            │   │   ├── Scope.scala         作用域与符号表
            │   │   ├── Symbol.scala        符号
            │   │   ├── Type.scala          类型
            │   └── typecheck
            │       ├── Namer.scala         符号表构建
            │       ├── Util.scala          公共代码
            │       └── Typer.scala         类型检查
            └── printing
                ├── PrettyPrinter.java      格式化缩进打印器
                └── PrettyScope.java        作用域符号表缩进打印
```