Week 7 - Semantic Part 1 - Symbol Table

我们需要在哪些层面验证程序的正确性？

我们在前面两章详细讲解了词法分析和语法分析，本章将在此基础上，从语义的角度来检查程序是否正确。请注意，从本周开始，实验内容可能会稍快于理论课内容，原因是语法与语义分析背后的理论较多，但实际基于 ANTLR 动手开展语法与语义分析并不太复杂。这种进度上的不一致不会影响课程学习。相反，先动手体验再琢磨背后的理论可以加深你对编译技术的理解。

回顾一下，在词法分析阶段，我们只关心输入的程序能否被 正确 地拆分成一个又一个词法符号；如果出现了未定义的符号，我们需要将其识别出来。进入语法分析阶段，我们则关注程序在语法结构上是否正确，例如：每个语句末尾是否添加了分号？函数调用时是否使用了括号？

然而，仅仅通过这两步验证还远远不够。简单来说，词法和语法分析保证了程序在结构上 看上去 没有问题，而语义分析则要在此基础上，确保程序在逻辑上能够 说得通。这是什么意思呢？让我们通过下面这个程序来理解。

int main() {
    int x = 0;
    String y = "xyz";
    c = x + y;
    return y;
}

从语法角度看，这个程序是完全正确的：无论是函数定义还是赋值语句，其结构都符合语法规则。然而，你可能已经敏锐地发现了，这个程序在逻辑上充满了错误：

1. 程序使用了变量 c，但在使用前并未定义。
2. 赋值语句的右侧表达式 x + y 也是错误的，因为变量 x 和 y 的类型不同，一般情况下不能直接进行加法运算。
3. main 函数声明的返回值是 int，但最后一句却返回了一个 String 类型的值。

上述这些都属于语义问题。语义分析的任务，就是要把这些问题全部检查出来，它是我们将程序翻译成 中间表示 之前的最后一道防线。

在语义分析中，作用域（Scope） 是一个至关重要的概念。简单来说，作用域定义了一个变量的“可见范围”——即它在程序的哪些部分是可访问的，在哪些部分是不可访问的。我们来看下面这个例子：

int main() {
    int x = 10;  // x 定义在这里

    {
        int y = 5;    // y 只在内层的这对花括号范围内可见
        int x = 11;   // x 在子作用域（内层花括号内）内被重新声明和定义
        x = x + y;    // 这里的x指的是子作用域内定义的x，而不是外部的x
    }

    y = y + 1; // ❌ 错误：y 已经不在作用域内
}

在上面例子中：

• 我们在 main 函数的子作用域中定义了一个新的 int x = 11;。它与外部的 x 同名，但它是一个 新的、独立的变量 ，其作用范围仅限于这个子作用域。因此，x = x + y 中的 x 指的是新定义的 x。这种现象被称为 变量遮蔽（Variable Shadowing） 。当程序尝试访问一个变量时，会优先从当前作用域开始查找；如果找不到，再逐层向父作用域追溯，直到找到为止。通常情况下，父作用域的变量在子作用域中是可见的，除非被同名变量遮蔽。
• 变量 y 的作用域仅限于内部的花括号 {...}。当程序试图在花括号外部访问 y 时，就会因为 y 超出作用域而报错。

下面，我们来系统地梳理一下在语义分析阶段需要找出的几类典型问题。

---

1. 变量使用前是否已定义？

在使用一个变量之前，必须确保它已经被声明过。

示例（错误）：

int main() {
    x = 5; // ❌ 错误：x 未定义
    return 0;
}

2. 变量是否被重复定义？

在同一个作用域内，重复声明同名变量通常是语义错误。

示例（错误）：

int main() {
    int x = 1;
    int x = 2; // ❌ 错误：x 在同一作用域内重复定义
    return 0;
}

3. 类型是否匹配？（类型检查）

赋值或运算时，值的类型必须符合变量或表达式的要求。例如，不能将字符串赋值给整型变量。

示例（错误）：

int main() {
    int x = "hello"; // ❌ 错误：类型不匹配
    return 0;
}

4. 表达式中参与运算的操作数是否兼容？

参与运算的各方必须是类型兼容的。例如，在大多数静态类型语言中，整数和字符串不能直接相加。

示例（错误）：

int x = 5;
String y = "abc";
int z = x + y; // ❌ 错误：不兼容的类型无法进行加法运算

5. 函数调用方式是否正确？

函数调用时必须满足其定义的要求：

• 函数名是否存在？
• 传递的参数个数是否匹配？
• 传递的参数类型是否匹配？

示例（错误）：

int add(int a, int b) {
    return a + b;
}

int main() {
    int x = add(1); // ❌ 错误：参数数量不匹配
    return 0;
}

6. return 语句的返回值是否与函数声明的返回值类型一致？

函数的实际返回值类型必须与声明的返回值类型相符。void 函数不能有返回值，而非 void 函数必须返回一个类型匹配的值。

示例（错误）：

int main() {
    return "abc"; // ❌ 错误：返回类型不匹配，应为 int
}

7. 作用域规则是否被正确遵守？

变量只能在其定义的作用域内被访问。一旦离开该作用域，变量就变得不可访问。

示例（错误）：

int main() {
    {
        int x = 5;
    }
    int y = x + 1; // ❌ 错误：x 已超出其作用域
}

---

符号表

了解了语义分析需要做什么之后，接下来的问题是：我们应该如何实现这些检查？我们以最简单的一条规则为例来探讨：

变量使用前是否已定义？

为了实现这一点，当解析器遇到变量定义时，就必须将该变量的信息记录在一张表中。后续遇到使用该变量的语句时，我们就可以通过查询这张表，来判断变量是否已被定义：如果在表中能查到，说明定义过，可以使用；反之，则说明未定义，应当报错。

那么，这张表中需要记录哪些信息呢？只记录变量名够吗？如果仅仅为了检查变量是否已定义，记录名称似乎是足够的。但考虑一下另一条规则：类型是否匹配？ 这时，只记录变量名就不够了，我们还必须记录变量的类型，以便在类型检查时进行比对。

同理，函数定义也需要被记录。只有将函数信息预先存入表中，我们才能在遇到函数调用时，通过查表来判断函数是否存在。同时，为了核实函数调用是否正确，我们还需要记录函数的参数列表（类型和数量）以及返回值的类型。

接下来，我们必须考虑作用域。一个程序包含多个作用域，它们之间存在嵌套（父子）或并列（兄弟）关系。我们可以很自然地将作用域的层级关系抽象成一棵树，每个作用域节点都包含该作用域内定义的变量和函数。这里有个小细节： 函数本身也构成一个作用域 。

在这样的模型中，每个作用域都可以看作一张独立的表，其中记录的变量和函数统称为 符号（Symbol） 。而这些作用域表构成的层级结构，整体就称为 符号表（Symbol Table） 。

有了上述构想，你可能已经对符号表有了初步的认识。下面，我们来探讨如何用 Java 一步步实现这个符号表。

---

我们从最基本的构成单元 符号（Symbol） 开始定义。假设我们的语法中主要有两种符号： FunctionSymbol 和 VariableSymbol。为此，我们可以创建这两个 Java 类。

它们需要包含哪些成员变量呢？ 首先，名称（name） 是必不可少的，因为它是查找符号的主要标识。 其次，需要一个 类型（type） 信息，用于类型检查。对于 VariableSymbol，这个类型就是它自身的类型；对于 FunctionSymbol，这个类型是它的返回值类型。

为了灵活地表示类型（如基本类型、数组类型等），我们可以定义一个 Type 接口，并让 PrimitiveType 和 ArrayType 等具体的类型类去实现它。这样，Symbol 类中就可以包含一个 Type 类型的成员变量，其具体实现在运行时确定。

FunctionSymbol 还有一个特殊需求：它需要存储参数列表，而这些参数本身也都是 VariableSymbol。

接着，我们来定义 作用域（Scope） 类。这个类的核心功能是存储 Symbol。很自然地，它需要包含用于存储 VariableSymbol 和 FunctionSymbol 的数据结构。使用 HashMap 是一个高效的选择，以符号名称为键（Key），因为后续的查找操作主要依赖名称。

此外，Scope 类还需要一个至关重要的成员变量：指向其 父作用域（Parent Scope） 的引用。这样，当在当前作用域查找符号失败时，程序可以沿着这个引用链向上层作用域继续查找。

Scope 类还需要提供两个核心方法：

1. 定义符号 ：在记录新符号时，需要检查当前作用域内是否已存在同名符号，因为我们不允许在同一作用域内对一个符号进行重复定义。
2. 查找符号 ：查找时，先在当前作用域中寻找；如果找不到，则沿着父作用域引用链向上查找，直到找到或抵达最顶层的 根作用域（Root Scope） 。

Scope 还应具备创建 子作用域（Child Scope） 的功能。值得注意的是，FunctionSymbol 本身也代表一个作用域，因此它可以直接继承 Scope 类，同时拥有符号和作用域的双重特性。

最后，我们来考虑一个具体场景：如何检查函数内的 return 语句是否与函数返回类型匹配？看下面这个例子：

int add(int a, int b) {
  int x = 10;
  {
    int y = 11;
    {
      int z = 13;
      return z; // 如何知道这里的返回值z应该匹配add函数的int类型？
    }
  }
}

return 语句中的变量 z 位于一个深层嵌套的块作用域中，我们如何将它与外层的 add 函数关联起来？ 在我们目前的设计中，VariableSymbol 似乎没有直接指向它所属的函数。一个有效的解决方案是：为每个 Symbol 增加一个 scope 成员变量，用于记录该符号被定义在哪个作用域中。

你可能会问：变量 z 的 scope 只是一个匿名的块作用域，并不是 FunctionSymbol 啊？没错，但我们可以通过 scope 引用链一直向上查找，直到找到一个其真实类型为 FunctionSymbol 的作用域（因为 FunctionSymbol 继承了 Scope 类），这时就可以用 Java 的 instanceof 操作符来判断。这样，我们就找到了变量所在的最内层函数（在上述例子中为 add），从而可以进行返回类型匹配的检查。

以上就是实现一个简单符号表的大致思路。你可以基于这些想法，很快地构建出属于自己的符号表。至于如何将符号表与语法分析树结合使用，我们将在下一节进行介绍。

练习题

我们正在为一个简单的脚本语言实现解释器。该语言支持变量定义和嵌套作用域（用 {...} 表示）。变量查找遵循“从当前作用域开始，逐层向上查找”的规则。

语言定义

语言只支持一种类型：int。 作用域是嵌套的，每个作用域可以访问其父作用域中的变量（除非被遮蔽）。 我们已经实现了 Scope 类来表示一个作用域，并包含一个指向父作用域的引用。

给定代码

import java.util.HashMap;
import java.util.Map;

// 表示一个整型变量
class IntVariable {
    String name;
    int value;

    public IntVariable(String name, int value) {
        this.name = name;
        this.value = value;
    }

    @Override
    public String toString() {
        return name + "=" + value;
    }
}

// 表示一个作用域
class Scope {
    Map<String, IntVariable> variables = new HashMap<>();
    Scope parent; // 指向父作用域，根作用域的 parent 为 null

    public Scope(Scope parent) {
        this.parent = parent;
    }

    // 在当前作用域中定义一个变量
    // 如果已存在同名变量，会覆盖（即在一个定义域内可以重复定义变量）
    public void define(String name, int value) {
        // TODO:定义变量
    }

    // TODO: 在当前作用域或其父作用域中查找变量
    // 请补全此方法
    // 如果找到，返回对应的 IntVariable
    // 如果未找到，返回 null
    public IntVariable lookup(String name) {
        // 请在此处补全代码
        // 提示：先查当前作用域，查不到则递归查父作用域
    }
}

测试代码

public class TestLookup {
    public static void main(String[] args) {
        // 创建全局作用域
        Scope global = new Scope(null);
        global.define("x", 100);
        global.define("y", 200);

        // 创建函数作用域（子作用域）
        Scope func = new Scope(global);
        func.define("x", 10); // 遮蔽全局的 x
        func.define("z", 30);

        // 创建块作用域（孙作用域）
        Scope block = new Scope(func);
        block.define("w", 40);

        // 测试查找
        System.out.println("block.lookup('w'): " + block.lookup("w")); // w=40
        System.out.println("block.lookup('z'): " + block.lookup("z")); // z=30
        System.out.println("block.lookup('x'): " + block.lookup("x")); // x=10 (被遮蔽)
        System.out.println("block.lookup('y'): " + block.lookup("y")); // y=200 (从全局继承)
        System.out.println("block.lookup('notExist'): " + block.lookup("notExist")); // null
    }
}

预期输出

block.lookup('w'): w=40
block.lookup('z'): z=30
block.lookup('x'): x=10
block.lookup('y'): y=200
block.lookup('notExist'): null