Sherfiter's wiki for fun

第 6 章 · 语义分析与符号表

第 3 章说过文法是「上下文无关」的,但语言显然有上下文:用没声明的变量、类型不匹配、重复定义,这些错误语法层完全合法。本章的语义分析就是补上这块:「带上下文的检查」。主角是符号表(symbol table)和类型系统,它们也是这门课和「程序语言设计」交汇最深的地方。C 指针课第 2 章(作用域与栈帧)、Java 课第 8 章(类型与访问控制)的知识在此全部兑现为「编译器视角」。

6.1 语义检查查什么

一份典型清单(以类 C 语言为例):

  • 声明先于使用:x = 1 之前,x 声明过吗?
  • 类型检查:int + char*?if (数组名)?类型系统逐节点裁决;
  • 作用域规则:内层同名变量遮蔽(shadow)外层,离开作用域失效;
  • 其他静态约束:break 必须在循环里、case 不重复、抽象类的抽象方法必须被实现(Java 课第 8 章)。

这些检查的共同形状:遍历 AST,每个节点带着「当前上下文」去查。上下文就是符号表。

6.2 符号表:作用域的栈式实现

符号表 = 「名字 → 声明信息(类型、位置等)」的映射,作用域规则用栈式哈希表实现:进入作用域压一层,离开弹一层,查找从栈顶往下:

#define SCOPE_MAX 32
typedef struct Sym { char name[64]; Type *type; struct Sym *next; } Sym;
Sym *scopes[SCOPE_MAX];      // 每层一个链表(或哈希表)
int  depth = -1;

void enter(void) { scopes[++depth] = NULL; }
void leave(void) { depth--; }

Sym *declare(const char *name, Type *t) {   // 当前层登记(重名报错)
    Sym *s = malloc(sizeof(Sym));
    strcpy(s->name, name); s->type = t; s->next = scopes[depth];
    scopes[depth] = s;
    return s;
}

Sym *lookup(const char *name) {             // 从内向外找(遮蔽语义)
    for (int d = depth; d >= 0; d--)
        for (Sym *s = scopes[d]; s; s = s->next)
            if (!strcmp(s->name, name)) return s;
    return NULL;
}

遍历 AST 时的动作模式:{ 进 enter,} 走 leave;声明节点 declare;引用节点 lookup,查不到报 undefined variable。验证一下:

{ int x = 1; { int x = 2; use(x); } use(x); }   // 内层 x 遮蔽外层,各用各的

数据结构课第 7 章(哈希表)的直接应用:符号表查找是编译器最热的小操作之一,真实编译器用精心设计的哈希(string interning,字符串驻留)。

6.3 类型系统:检查与推导

类型检查的基本形状是递归的谓词:每个 AST 节点带类型属性,自底向上合成:

Type *check(Node *n) {
    switch (n->kind) {
        case ND_NUM:  return ty_int;
        case ND_VAR:  return lookup(n->name)->type;      // 查不到已在别处报
        case ND_ADD:
            Type *l = check(n->lhs), *r = check(n->rhs);
            if (l == ty_int && r == ty_int) return ty_int;
            if (l == ty_ptr && r == ty_int) return ty_ptr;  // 指针+整数(C 课第 3 章)
            type_error(n, "type mismatch");
    }
}

两条路线:类型检查(声明里写了类型,查一致性,如 C/Java)与类型推导(不写类型,编译器推断,如 Rust 的 let x = 5、Hindley-Milner)。推导是检查的超集(它先「算出」类型再查),实现上就是双向传播:表达式向上合成类型、约束向下传递。子类型(Student 是 Person 的子类,Java 课第 8 章)引入「可赋值性」和「协变逆变」的深水区,本课止步于知道门槛在哪。

6.4 类型转换与检查的层次

合法但不完全匹配的类型对,语言规定隐式转换(int → double 提升,C 课第 2 章「窄转必须显式」的反面),编译器在 AST 上插入转换节点(implicit cast),让后续阶段看到的是「类型完全一致」的树。这个「检查时顺手改树」的手法到处都是:插转换、插默认初始化、把语法糖展开(syntactic sugar desugaring,Python 的推导式、Java 的增强 for 都在语义分析或更早阶段被翻译成朴素结构)。编译器前端的后半程,大量工作是「把糖剥掉」。

6.5 错误信息:编译器的用户界面

语义检查的错误处理,是编译器工程质量的试金石。好报错的三要素:位置(行:列,第 5 章建树时记的)、因果(「expected int, got char*」而不只是「error」)、修复建议(「did you mean ...?」「add a semicolon here」)。rustc 把这条做到了艺术品级。错误恢复延续第 3 章 panic mode 的思路:语义错误也不中断,记下来继续检查(常见技巧:出错的地方给一个「万能错误类型」ty_error,它能和任何类型兼容,避免一错引发连环误报)。

常见错误

  • 符号表只查不记作用域栈。全局一张哈希表,同名遮蔽全乱;进 scope 就 push 是铁律。
  • 重复声明只查当前层还是查全部层搞混。遮蔽合法,同层重定义非法;两个判断是不同的查询。
  • 类型错误连环误报。第一个错之后全树的类型都「脏」了;用 ty_error 吸收。
  • 忘了隐式转换节点。直接放行类型不匹配,代码生成阶段炸出莫名的寄存器错误,排查成本远高于语义层报错。

练习

  1. 动手:给第 5 章的迷你语言加变量:文法加 stmt → ident = expr | decl ident = expr,实现栈式符号表 + 「先声明后使用」检查,报错带行号。
  2. 手算:对嵌套作用域 {int x; {char x; {double x;}}} 画出三个作用域的符号表栈的push/pop 过程,标每个 x 的类型。
  3. 动手:实现「隐式转换节点插入」:int 和 double 混合运算时自动插 cast 节点,打印转换后的树。
  4. 思考:C 语言为什么「声明先于使用」?(历史:单遍编译器必须一遍看完就能查。)对比 Java 允许先使用后声明(两遍编译)。从「编译器实现约束塑造语言设计」的角度,再找一个例子(提示:C 旧版的变量声明必须在块首,也是单遍解析的遗产)。
豫ICP备2026027944号