编译技术教程：符号表与类型系统

系列导航：
《编译技术教程：前言》
《编译技术教程：词法分析》
《编译技术教程：抽象语法树》
《编译技术教程：语法分析》
《编译技术教程：符号表与类型系统》
《编译技术教程：语义分析》
《编译技术教程：附录 - 项目测试》

在语法分析部分，我们将单词序列转化为结构化的抽象语法树。然而抽象语法树依旧无法表达完整的程序语义。因为抽象语法树的定义基于上下文无关文法，而无法反映程序执行时的上下文环境。因此为了记录程序中的上下文相关信息，为后续语义分析阶段提供建议，我们需要定义新的数据结构以维护上下文信息。在程序设计语言中，最为关键的上下文信息即符号信息，因此本章节我们着重讨论符号表。

一、符号表

符号表是编译过程中的一个重要结构，主要用于记录各个符号的标识以及相应的信息，例如名称、作用域、类型、大小、维度、存储地址、行数等各项信息。其目的是在编译过程中遇到对应符号时即可快速查询到相关信息。接下来我们也将提供符号表的实现思路以供参考。要注意，符号表的设计与使用将贯穿后续的全部实验流程，请同学们三思而后行！

二、符号表的创建

在不区分作用域的情况下，符号表仅由需记录符号与符号信息的简单映射。但如果语言支持嵌套作用域，那么我们就需要表示各作用域符号表间的嵌套关系。在这种情况下，对于一张符号表来说，通常具有如图的结构：一个指向外层作用域符号表的指针 pre，表主体（符号名与对应信息），若干指向内层作用域符号表的指针 next。此外，在编译的过程中，有一个指向当前作用域符号表的指针 cur。

符号表

符号表的生成主要有以下几个操作：

初始时，创建一个全局变量符号表，也是最外层作用域符号表，cur 指向该符号表。
编译时，遇到变量声明语句，解析出需要的信息（一般包括类型、维度、大小等），填入 cur 指向的符号表。
编译时，进入新的作用域（block），生成新的符号表，设置 cur 指向的符号表的 next 指针指向新符号表，新符号表的 pre 设置为 cur，然后将 cur 指向新符号表，后续会在新符号表上填入信息。
编译时，离开作用域（block），通过 cur 指向的符号表的 pre 指针回溯至外层符号表，并对应修改 cur 指针。

不难发现，这样生成的符号表具有树状结构。当然，由于两个无嵌套关系的作用域中的符号并无任何联系，所以我们也可以按栈式结构来组织符号表，即进入新的作用域，就压入新的符号表，离开作用域时，弹出当前符号表。

在 tolangc 中，我们定义了一个栈式符号表。符号表类 SymbolTable 对应某一作用域的符号表。每一个符号表拥有一个 _father 字段，指向更外层作用域的符号表。另有 _symbols 字段存储当前作用域的符号。以符号名称为键，以符号信息（这里为 Symbol 类对象）作为值。

class SymbolTable : public std::enable_shared_from_this<SymbolTable> {
    // ...
private:
    std::unordered_map<std::string, std::shared_ptr<Symbol>> _symbols;

    std::shared_ptr<SymbolTable> _father;
};

当进入新的作用域时，我们调用 push_scope 函数，创建新的符号表，并将该符号表的 _father 字段设置为当前符号表。

std::shared_ptr<SymbolTable> push_scope() {
    auto new_table = std::make_shared<SymbolTable>();
    new_table->_father = shared_from_this();
    return new_table;
}

当离开作用域时，我们调用 pop_scope 函数，返回上一层作用域的符号表，即 _father 字段取值。由于我们使用了 std::shared_ptr，所以并不需要手动析构被弹出的符号表。

std::shared_ptr<SymbolTable> pop_scope() { return _father; }

此时，假设我们使用变量 cur_scope 保存当前符号表，那么在进入和离开作用域的时候，我们可以采用如下代码操作符号表。

// enter scope
cur_scope = cur_scope->push_scope();

// do something in scope

// exit scope
cur_scope = cur_scope->pop_scope();

三、符号的插入

符号的上下文相关性来自于其在不同位置的定义和使用。在同一作用域中，符号的定义意味着符号信息的创建，符号的使用则将符号信息由程序的一处传递到当前位置。这一过程反映到符号表上，就是符号的插入和查找。

符号的插入也就是将我们声明的标识符转化为符号单元，添加到当前的符号表中。当我们在语义分析阶段解析到某一符号的定义之时，就需要将该符号插入到符号表中。该符号在定义处所能得知的相关信息，如符号类型、数据类型等等，也应当一同插入到符号表中。另外，同一个作用域下是不允许出现两个同名标识符的，出现这种情况时，应进行错误处理。

综上，符号的插入操作具体流程如下：

在标识符声明时，判断该标识符名称在当前作用域下是否重复。若重复则报错，否则执行 2。
将标识符名称作为键，将该定义处的相关信息作为符号信息，插入到当前符号表中。

在 tolangc 中，我们使用 exist_in_scope 和 add_symbol 函数实现上述流程。

bool exist_in_scope(const std::string &name) {
    return _symbols.find(name) != _symbols.end();
}

bool add_symbol(std::shared_ptr<Symbol> symbol) {
    if (exist_in_scope(symbol->name)) {
        return false;
    }

    _symbols[symbol->name] = symbol;
    return true;
}

四、符号的查找

在编译的过程中，如果遇到一个标识符的引用，就需要确定该标识符是否定义过，以及其相关信息，此时我们需要在符号表内查找该符号。

关于符号表的查找，各位同学回忆自己平时使用过的常见编程语言，应当能够显然的认识到某一名称所对应的符号是在当前作用域和其上嵌套的所有作用域中，与该名称同名，且定义处于最内层的符号。因此，若当前作用域无待查询符号，我们应当沿符号表树向上递归查找最近的符号，直至最外层的符号表。如果最外层的符号表汇总依旧无法查找到名称所对应的符号，才能判定符号未定义。

因此，符号的查找操作具体流程如下：

在使用标识符时，在当前作用域符号表内查询是否有符号记录，有则返回其信息，无则执行 2。
利用当前作用域符号表的 pre 指针，访问外层作用域符号表。如果更外层符号表不存在（pre 指针为空），说明该标识符未定义，报错误；否则在外层作用域符号表中重新执行 1。

在 tolangc 中，我们使用 get_symbol 函数实现上述流程。

std::shared_ptr<Symbol> get_symbol(const std::string &name) {
    auto it = _symbols.find(name);
    if (it != _symbols.end()) {
        return it->second;
    } else if (_father != nullptr) {
        return _father->get_symbol(name);
    } else {
        return nullptr;
    }
}

五、符号与类型的设计

符号表本身的设计并不复杂，我们在之前的小节中已经进行了详尽的说明。但是在符号表当中究竟应当存储哪些信息，却是一个难以回答的问题。将符号表视为一个映射，那么我们已知其键为符号的字面名称，而其值却需要根据后续语义分析阶段的需要来确定。而目前各位同学还未正式接触中间代码生成，对符号表应该存什么内容想必会一头雾水（不用怀疑自己，作者当初也是）。

因此我们这里给出一些值得参考的思路。符号表中存储的信息应当包括符号定义处的信息，需要尽可能详细但不冗余，以方便后续的查找使用。具体来说，符号信息应当至少包括：符号类型（如变量、函数）、符号的数据类型（int、char、数组、指针等）以及中间代码中和符号相关的信息（例如 LLVM 中符号所对应的数据结构）。

由于 Java 和 C++ 都支持 OOP，所以很容易通过继承区分不同的符号类型。在 tolangc 中，我们也使用继承区分了不同的符号。

struct Symbol {
    // ...
};

struct VariableSymbol : public Symbol {
    // ...
};

struct FunctionSymbol : public Symbol {
    // ...
};

接下来我们希望重点讨论一下类型系统。这主要是由于今年的实验课程文法中除了 int 类型，又额外加入了 char 类型，当面临更加复杂的类型时，有必要设计更加结构化、可扩展的类型系统。

类型，一方面决定了数据在内存中的组织方式，另一方面又定义了不同数据的行为和约束。而类型系统就是在编译器中实现程序中类型的定义、转换、验证等等功能的系统。在一些语言中，类型系统可以极其复杂，不过我们实验所采用的类型系统十分简单。只设计两种基本类型：int 和 char，以及两种复合类型：数组和不完整的指针。

基本类型是类型系统中的基本元素，所有类型要么是基本类型，要么便是类型的组合。对于类型的组合，数组就是一个很好的例子，例如 int[3]，意味着三个 int 类型的顺序组合。这也暗示了其在内存中的存储方式，那就是三个 int 类型按顺序排列而成。

不同类型的变量或值之间能够进行一系列的运算，并产生新的值，该值同样具有一定的类型。这反映到类型本身，可以认为类型之间同样具有一系列的运算关系。

例如，int 和 char 类型之间能够进行加法运算，得到的结果为 int 类型（int + char = int）。又例如一个二维数组 int[2][3]，我们能够进行索引运算，第一次索引得到 int[3]，第二次索引得到 int（int[2][3] [] int = int[3]，int[3] [] int = int）。同样的，对于实验文法中的不完整的指针类型，我们也可以进行索引操作（int* [] int = int）。

这里容易产生的误区是将 int[2][3] 视为一个 2x3 大小的二维数组。但实际上应当视作一个长度为 2 的数组，其元素类型为 int[3]。

类型系统能够暗示类型间的隐式转换。例如由于 int 与 char 的算术运算结果为 int，因此进行运算时，char 类型需要自动转换为 int 类型（由 8 位符号扩展为 32 位），之后再进行运算；将 int 值赋给 char 类型变量时，需要强制类型转换为 char 类型（将待赋值的 32 位截断至后 8 位）。

最后，我们给出在代码中表示类型的一些建议。由于类型的嵌套关系，可以考虑定义所有类型的公共父类 Type。所有其他类型类集成自该类。对于不同基本类型，可以考虑将其设计为单例。对于数组和指针，则需在其字段中包含元素类型和引用类型。（另外数组还需额外设定数组长度。）

class Type {
    // ...
};

class ArrayType : public Type {
    // ...
private:
    Type *_elm_type;
    unsigned int _size;
};

class PointerType : public Type {
    // ...
private:
    Type *_ref_type;
}

一、符号表#

二、符号表的创建#

三、符号的插入#

四、符号的查找#

五、符号与类型的设计#

一、符号表

二、符号表的创建

三、符号的插入

四、符号的查找

五、符号与类型的设计