实验2 语义分析¶

语义分析是在语法分析的结果, 即语法树的基础上, 增添语义信息, 建立符号表和进行类型检查的过程. 我们将语义分析分为两个部分: 符号表与类型检查.

符号表¶

我们举一个例子来说明符号表的作用:

int x = 1; // x1
int y = 0; // y1
{
    int x = 3; // x2
    y += x; // x2
}
y += x; // x1

对于上述代码, 容易发现 y += x 加的两个 x 来自于两个不同的定义, 那么编译器在生成代码的时候, 仅仅看 y += x 是判断不出来该选择哪个变量的. 这就是语义分析所需要解决的问题之一, 为这些使用的变量提供额外的语义信息. 而这一过程实际上就对应了符号表的建立.

在变量的指向确定后, 你同时也可能发现一些语义错误, 例如使用的变量是未定义的或者在同一个作用域内变量有重复定义, 这时你应该向使用者报错. 同时, 为了后面的类型检查, 你还需要在符号表里记录每个符号的类型.

除了变量之外, 你还需要考虑函数的符号. 你完全可以把函数当作一个变量来处理, 只不过它的类型有些特殊. 比如一个 int gcd(int a, int b) 函数可以当作一个类型为 (int, int) -> int 的变量.

为了简单起见, 我们只通过名字去进行判断符号是否重定义, 不考虑函数重载等特性. 也就是说, 不可以定义两个同名的函数, 即使他们的参数不同. 同时, 我们将函数和变量放在两个不同的符号表进行处理, 这样允许你在同一个作用域内 (全局作用域) 去定义一对同名的函数和变量. 这里我们只允许在全局作用域内定义函数 (和 C 一致, 和 Tiger 不一致), 并且所有符号在使用前必须被定义 (我们不区分定义和声明).

符号表实现¶

假如我们不存在作用域 (scope) 这个概念, 我们仅仅需要一个哈希表或者二叉搜索树 (std::map<std::string, Type>) 就可以实现符号表. 但是如果要考虑作用域, 我们需要支持在每个作用域内建立一个新符号表, 它需要满足:

支持对上级作用域的符号表的访问, 即新作用域可以访问上级作用域的符号
支持在新作用域内定义新的符号, 允许覆盖上级作用域的符号, 并且在同一个作用域内不可以重复定义同一个符号
离开作用域时, 可以销毁当前的符号表, 并上级作用域的符号表恢复

虎书上将符号表的实现分为两种风格:

函数式风格. 在进入一个新的作用域时, 创建一个新的符号表, 并保持上级符号表内容不变. 离开作用域时仅需要销毁新符号表, 而不会影响上级符号表.
命令式风格. 只维护一个符号表, 并记录操作历史记录. 进入一个新的作用域时, 新的符号可能会覆盖上级作用域的符号 (比如上面例子中的变量 x). 离开作用域时, 根据操作记录将其还原即可.

当然你可以考虑一些更直白的实现方式, 比如 std::vector<std::map<std::string, Type>> 或者 std::map<std::string, std::vector<Type>>.

第一种方法是维护一个符号表的栈, 每个符号表对应一个作用域, 查找变量时从栈顶开始查找. 例如刚才的例子, 在运行到第 2 行时符号表是这样的：

#Table 1
x -> [x1]
y -> [y1]

在运行到第 3 行时, 我们新建一个符号表, 并压入栈中, 然后根据第 4 行的定义更新当前的符号表:

#Table 1         #Table 2
x -> [x1]        x -> [x2]
y -> [y1]

在寻找某个符号时, 我们首先在栈顶的符号表中查找, 如果找不到, 我们就去上一个符号表中查找. 例如在第 5 行时, 我们会在表 2 中查找 x, 而对于 y, 表 2 中我们并没有重复定义, 所以我们会在表 1 中找到.

而在第 6 行也就是离开该作用域时, 我们只需要销毁栈顶的符号表即可.

第二种方法是在每个符号下维护一个栈, 每次进入新的作用域时, 将一个新的符号表压入栈中, 离开作用域时弹出. 还是刚才的例子, 在运行到第 2 行时符号表是这样的：

x -> [x1]
y -> [y1]

而运行到第 4 行时, 符号表变成了：

x -> [x1, x2]
y -> [y1]

在每次我们想要查看某个变量的定义时, 我们只需要查看栈顶的元素即可. 而当我们离开某个作用域时, 我们只需要将在该语句块定义的元素弹出即可. 所以在第 6 行时, 符号表又变回了:

x -> [x1]
y -> [y1]

那么我们怎么知道哪些元素是在该作用域下定义的呢? 你可以在每次进入一个块时, 将一个特殊的标记符压入栈中, 而当你离开该块时, 你只需要将栈顶的元素弹出直到遇到这个特殊的元素即可. 或者你也可以记录当前作用域内新定义的所有符号, 依次将这些符号的栈顶弹出即可 (比较类似于上面提到的命令式风格).

可持久化数据结构

书上提到了一种更高效的函数式符号表, 是用可持久化数据结构 (persistent data structure) 来实现的. 这种 "可持久化" 又被称为 "不可变", 也就是每一次更改都会创建一个新的 "版本" 而保持 "历史版本" 不变.

我们提供的样例编译器 accsys-rs 中使用了 rpds 库提供的可持久哈希表来实现这种符号表. 而对于 C++ 来说, 你可以考虑 immer. 如果你精力充沛, 你也可以尝试自己实现一个, 还是比较简单的. 可以参考 OI Wiki 上的内容.

当然你不必太过关心符号表的效率, 上面提到的 std::vector<std::map<std::string, Type>> 和 std::map<std::string, std::vector<Type>> 已经够用了.

类型检查¶

所谓类型, 就是一组值构成的集合, 对于这组集合我们可以进行其专属的操作, 例如整型的加减乘除, 数组的访问等. 当我们在某组值上尝试去执行其不支持的操作时, 类型错误就产生了. 而类型检查, 就是检查我们对这些类型的操作有没有错误.

void f() {
    return;
}
int a;
int c = a / f();

例如上述代码, 你需要发现得到 f() 返回值是 void, 是无法进行除法的, 也就产生了类型错误. 这时你会发现变量绑定是十分重要的, 如果碰到了使用某一变量如 a = b + c 时我们怎么知道 b 的类型呢? 答案是我们上面介绍的符号表, 通过查找b是被哪个符号定义的, 我们就可以知道b的类型了. 除此之外, 函数调用的参数类型, 个数和返回类型等也都是你应该检查的.

类型检查实现¶

和打印语法树和符号表的建立一样, 类型检查也是遍历语法树的过程. 不同于打印语法树的遍历操作不需要返回值, 类型检查中一个自然的返回值就是该表达式的类型. 例如, 对于赋值语句你可以这么写：

Type type_check(Assign assign, Table table) {
    Type left = type_check(assign->left, table);
    Type right = type_check(assign->right, table);
    if (equal(left, right)) 
        ...
}

Type type_check(Ident ident, Table table) {
    return table.lookup(ident);
}

其中的 type_check 函数负责的就是检查某个表达式的类型是否正确, 并返回其类型.

不过我们会涉及到的类型只有 int, void 和 int 数组, 并且所有单元/二元运算符的操作数和输出均为 int.

你的任务¶

你的任务就是在实验 1 所构建的语法树基础上完成上述语义分析, 对语法树进行遍历以进行符号表的构建以及类型的检查. 对于违反语义的程序进行报错. 你应该支持检测出以下错误：

符号表相关：
- 调用未定义的函数, 使用未定义的变量
- 重复定义函数, 同一个作用域内重复定义变量
类型检查相关：
- 变量定义或赋值中左右表达式类型不匹配
- 操作数类型不匹配或操作数类型与操作符不匹配, 如整型变量与数组变量相加减
- return 语句的返回类型与函数定义的返回类型不匹配
- 函数调用时实参与形参的数目或类型不匹配; 特别的, 函数调用时数组对应维数不匹配
- 对非数组型变量使用 "[...]" (数组访问) 操作符
- 对普通变量使用 "(...)" (函数调用) 操作符, 也可以认为是调用未定义的函数

实际上你应该把构建符号表和进行类型检查放在同一个函数内执行. 在 Lab 2 里你构建的符号表只需要知道变量/函数的类型, 这个符号表在进行完类型检查后就没有用了.

符号表不是一个固定含义的东西, 你在不同阶段可能会用到不同的符号表. 对于 Lab 2, 你构建的符号表中只需要维护 name -> type 的关系, 并且这个符号表是随着你的语义检查动态构建的, 里面的内容会随着你进入/离开作用域而加入/删除. 这个符号表仅在进行语义检查的过程中使用, 也就是说, 语义检查的目的不是为了得到符号表, 而是你在语义检查的过程中需要符号表.

你在后续的 Lab 会重新构建更复杂的符号表, 比如包含每个符号的地址等信息. 同样的, 这些符号表也仅在你进行中间代码生成/汇编生成的过程当中构建并被使用.

由于我们的语言比较简单, Lab 2 的内容仅起到一个检查的作用, 不会生成其他的东西用于后续工作.

除此之外你还需要考虑 putint 和 getint 等运行时函数, 用户不需要定义也可以直接使用.

对于我们测试集没有覆盖到的情况, 你可以自行决定是否报错. 你可以在报告中注明这些没有覆盖到的情况.

同实验 1, 你的编译器必须支持一个命令行参数的情形, 即：

./compiler <input_file>

该程序必须接受一个输入的源代码文件名作为参数, 我们只会使用这种方式来测试你的编译器.

测试¶

运行以下命令来测试你的编译器：

python3 test.py ./compiler lab2

在实验2中, 我们提供了以下两类测试样例：

如 tests/lab2/main.sy 所示, 源文件中的语义没有错误, 你的编译器应该能够正常退出.

int main(){
    return 0;
}

如 tests/lab2/unmatch_call_num.sy 所示, 源文件中的函数形参与实参不匹配, 你的编译器应该能够检测出错误并报错后以非 0 返回值退出.

// Semantic Error at Line 8: Function arguments not matched

int f (int i) {
    return i;
}

int main () {
    int a = f(1, 2);
    return 0;
}

我们的测试完全采用输入输出形式, 即对于符合语义的源代码, 你的程序正常运行后正常退出, 对于不符合语义的源代码, 你的程序应该能够检测出错误报错后返回非0值, 我们对报错的格式没有要求. 测试文件中的报错注释供你参考.

实验提交¶

实验一和实验二统一提交一次. 你需要提供:

源程序，包括必要的构建系统文件（Makefile/CMakeLists.txt/Cargo.toml/dune-project 等）.
一份 PDF 格式的实验报告, 内容包括:
- 你的程序实现了哪些功能? 简要说明如何实现这些功能.
- 你的程序应该如何被编译? 请详细说明应该如何编译你的程序，包括构建系统需要传入的额外命令行参数、可能需要助教安装的某些第三方库等重要信息，请不要使用诸如“在 Dev-C++ 中打开并按 F9 编译"“在 Vscode 中打开”的模糊描述. 无法顺利编译将导致助教无法对你的程序所实现的功能进行任何测试, 从而丢失相应的分数.
- 实验报告的长度不得超过 6 页. 所以实验报告中需要重点描述的是你的程序中的亮点, 是你认为最个性化/最具独创性的内容, 尤其要避免大段地向报告里贴代码.
- 测试集中并没有覆盖所有的语法/语义规则, 你可以将你遇到的未覆盖的情况写到报告中, 或者你也可以设计一些新的测试一并提交上来.

源代码：你应当提供一个 .zip 文件, 文件名为 compiler-lab1-lab2-g<小组序号>.zip（例如第 0 组为 compiler-lab1-lab2-g0.zip）, 包含以上两项内容. 如果你使用我们提供的 C++ 模板代码，在压缩包解压后，在根目录下的结构应当如下:

compiler-lab1-lab2-g0.zip
├── src/
├── include/
├── third_party/
├── ... # other files
└── CMakeLists.txt

如果你使用其他语言或者不使用我们提供的模板自己造轮子，提交时可以参考上述文件结构. 简言之，尽量不要出现多余的文件夹嵌套.
如果你使用 macOS，请删除 zip 文件里的 __MACOSX 等文件夹.

报告：你应当提供一个 .pdf 文件，文件名为 compiler-lab1-lab2-g<小组序号>.pdf（例如第 0 组为 compiler-lab1-lab2-g0.pdf），内容要求如上.

建议使用 Git 管理你的代码