语义分析与中间代码

概念

语义分析是在语法树已经合法的基础上，回答"这句话说得通吗"：类型对不对、变量声明没有、名字用错作用域没有。

中间代码生成紧接着做第二件事：把这棵面向语言的树翻译成面向机器的线性指令——但还不落到具体机器。

int x = 3 + 42;   --(词法)-->  记号流  --(语法)-->  语法树
                  --(语义)-->  带类型的语法树 + 符号表
                  --(中间代码)-->  t1 = 3 + 42 ; x = t1

两步合起来，正是 lang/20-steps.md 里编译器六小步的第 ③ ④ 步。

为什么要分出"中间代码"这一层：如果 10 种源语言 × 10 种目标机器都要各写一个翻译器，是 100 个；中间加一层 IR，就变成 10 + 10 = 20 个。IR 是编译器里的"通用插座"，也是所有优化的主战场。

原理

一、静态语义检查的五类内容

类别	检查什么	反例
类型检查	运算符两边的类型是否相容	int * char*
控制流检查	break 是否在循环/switch 里	循环外写 break
一致性检查	同一对象前后说法是否一致	声明 int f() 又定义 double f()
相关名字检查	成对出现的名字要配套	标签与 goto 不匹配
作用域检查	名字在当前位置可见吗	用了外层没声明过的名字

注意：这一层全是静态检查，在编译期完成；像数组下标越界、除零这种动态错误，静态检查只能尽力，最终要靠运行期检查或硬件异常。

二、符号表与作用域

符号表就是编译器自己的"通讯录"：每个名字对应它的类型、种类（变量/函数/类型名）、存储位置、作用域层级。

实现方式	查表代价	说明
线性表（数组/链表）	O(n)	最简单，适合小作用域
排序表 + 折半	O(log n)	插入贵
哈希表	期望 O(1)	主流

作用域用栈解决：进入一个块就压一层新表，离开就弹掉。查找时从栈顶往下找，先找到的胜出——这就是"内层同名变量遮蔽外层"的实现方式。

符号表栈
┌───────────────────────────┐
│ 作用域 1（内层块）  t:int   │  ← 查找从这里开始
├───────────────────────────┤
│ 作用域 0（函数体）          │
│  a:double b:int c:int      │
│  d:double e:int x:double   │
└───────────────────────────┘

名字表 + 符号表分离是个常见优化：把所有名字的长字符串集中放在一张"名字表"里，符号表只存下标，这样符号表里的每一项大小固定。

三、类型检查

类型系统的两条分界：

分界	左边	右边
检查时机	静态类型（编译期查，如 C/Java）	动态类型（运行期查，如 Python）
严格程度	强类型（不许隐式乱来）	弱类型（允许隐式转换，如 C）

C 是静态 + 弱类型：类型在编译期定，但 int + double 允许隐式提升为 double。这套规则就是类型检查器手里的那张表：

左类型	右类型	结果
int	int	int
int	double	double（int 提升）
double	int	double（int 提升）
double	double	double

每个运算符都查一次表，从叶子往根推，最后看根的类型与左值是否相容——这正是一次后序遍历。

四、中间代码的五种形式

形式	长什么样	特点
逆波兰式	a b c + *	最接近"栈式机"，但难做全局优化
三地址码	t1 = b + c	最常用，每个指令最多三个操作数
树形表示	就是语法树的简化版	与三地址码可互相转换
四元式	(op, arg1, arg2, result)	三地址码的"表格版"，一行四个字段
三元式	(op, arg1, arg2)	少一个字段，用序号引用中间结果
间接三元式	三元式 + 一张指示器表	想重排指令时只动指示器

三地址码的常见指令类型：

类型	例
赋值	x = y
二元运算	t1 = a + b
复制	t2 = t1（一元负号也属这类）
无条件跳转	goto L
条件跳转	if a < b goto L
数组/指针	t3 = a[i]、*p = t4
过程调用	call f, n

四元式与三元式的取舍：四元式多存一个 result，但引用的是名字而不是位置，所以优化时想搬动指令、删掉指令，都不会破坏引用；三元式省一个字段，代价是任何一条指令的位置一变，所有引用它的序号都要跟着改。这是本章最容易考的一个对比。

示例

例 1：类型检查（C）

#include <stdio.h>

/* 0 = int, 1 = double */
static const char *TN[2] = {"int", "double"};

/* int + double -> double：取更"宽"的那个 */
static int wider(int a, int b) { return (a > b) ? a : b; }

int main(void) {
    /* x = a + b * c - d / e */
    struct { const char *name; int ty; } T[6] = {
        {"a", 1}, {"b", 0}, {"c", 0}, {"d", 1}, {"e", 0}, {"x", 1}
    };
    int r1 = wider(T[1].ty, T[2].ty);      /* b * c       : int * int    */
    int r2 = wider(T[0].ty, r1);           /* a + (b*c)   : double + int */
    int r3 = T[3].ty;                      /* d / e       : 左操作数说事 */
    int r4 = wider(r2, r3);                /* (...) - (..): 两个结果相减 */
    printf("b * c      -> %s\n", TN[r1]);
    printf("a + (b*c)  -> %s\n", TN[r2]);
    printf("d / e      -> %s\n", TN[r3]);
    printf("整式        -> %s\n", TN[r4]);
    printf("x 是 %s，%s\n", TN[T[5].ty],
           (r4 == T[5].ty) ? "类型一致，通过" : "类型不符，报错");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

b * c      -> int
a + (b*c)  -> double
d / e      -> double
整式        -> double
x 是 double，类型一致，通过

例 2：符号表、类型检查与三种中间代码（Python 对照）

def pad(s, w):
    """按显示宽度补空格：中文算 2 列"""
    return s + " " * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))


# ---- ① 符号表：栈式作用域 ----
class SymTab:
    def __init__(self):
        self.scopes = [{}]          # 第 0 层 = 全局作用域
        self.errors = []

    def enter(self):
        self.scopes.append({})

    def leave(self):
        self.scopes.pop()

    def declare(self, name, typ):
        if name in self.scopes[-1]:
            self.errors.append("重复声明: %s" % name)
            return False
        self.scopes[-1][name] = typ
        return True

    def lookup(self, name):
        for s in reversed(self.scopes):
            if name in s:
                return s[name]
        return None


st = SymTab()
print("=== 符号表：进入函数 f 的作用域 ===")
for n, t in [("a", "double"), ("b", "int"), ("c", "int"),
             ("d", "double"), ("e", "int"), ("x", "double")]:
    st.declare(n, t)
for i, s in enumerate(st.scopes):
    print("  " + pad("作用域 %d" % i, 14) + ", ".join("%s:%s" % (k, v) for k, v in s.items()))

print()
print("=== 进入内层块后 x 被遮蔽 ===")
st.enter()
st.declare("t", "int")
st.declare("x", "int")          # 内层同名，合法（遮蔽）
print("  " + pad("查 x ->", 14) + str(st.lookup("x")) + "（内层）")
st.leave()
print("  " + pad("离开后查 x ->", 22) + str(st.lookup("x")) + "（外层）")

print()
print("=== 两类语义错误 ===")
st.errors.clear()
st.declare("a", "double")       # 同一层重复声明
print("  " + pad("重复声明 a ->", 20) + (st.errors[0] if st.errors else "无"))
print("  " + pad("使用未声明的 y ->", 24)
      + ("未声明" if st.lookup("y") is None else "已声明"))

# ---- ② 类型检查 ----
RULES = {
    ("int", "int"): "int",
    ("int", "double"): "double",
    ("double", "int"): "double",
    ("double", "double"): "double",
}


class Typer:
    def __init__(self, env):
        self.env = env
        self.notes = []

    def check(self, node):
        """node: ('bin', op, l, r) / ('id', name) / ('num', value)"""
        if node[0] == "num":
            return "int" if isinstance(node[1], int) else "double"
        if node[0] == "id":
            t = self.env.lookup(node[1])
            if t is None:
                raise NameError("未声明: %s" % node[1])
            return t
        _, op, l, r = node
        tl, tr = self.check(l), self.check(r)
        res = RULES[(tl, tr)]
        self.notes.append("%s %s %s  ->  %s" % (tl, op, tr, res))
        return res


env = SymTab()
for n, t in [("a", "double"), ("b", "int"), ("c", "int"),
             ("d", "double"), ("e", "int"), ("x", "double")]:
    env.declare(n, t)

# x = a + b * c - d / e
ast = ("bin", "-",
       ("bin", "+", ("id", "a"), ("bin", "*", ("id", "b"), ("id", "c"))),
       ("bin", "/", ("id", "d"), ("id", "e")))
tp = Typer(env)
res = tp.check(ast)

print()
print("=== 类型检查：x = a + b * c - d / e ===")
for n in tp.notes:
    print("  " + n)
print("  " + pad("整式类型 ->", 16) + res)
print("  " + pad("x 的类型 ->", 16) + env.lookup("x")
      + ("  （一致，通过）" if res == env.lookup("x") else "  （不一致，报错）"))

print()
print("=== 反例：把 double 直接赋给 int ===")
print("  左值 int，右值 double -> 需要显式转换，否则编译期警告")
print("  warning: conversion from 'double' to 'int' may change value")

# ---- ③ 中间代码：四元式 / 三元式 ----
print()
print("=== 四元式（op, arg1, arg2, result） ===")
QUAD = [
    ("*", "b", "c", "t1"),
    ("+", "a", "t1", "t2"),
    ("/", "d", "e", "t3"),
    ("-", "t2", "t3", "t4"),
    ("=", "t4", "_", "x"),
]
print("  " + pad("序号", 6) + pad("op", 6) + pad("arg1", 8) + pad("arg2", 8) + "result")
for i, q in enumerate(QUAD, 1):
    print("  " + pad(str(i), 6) + pad(q[0], 6) + pad(q[1], 8) + pad(q[2], 8) + q[3])
print("  -> 共 %d 个四元式；临时变量用了 t1..t4，共 4 个" % len(QUAD))

print()
print("=== 三元式（op, arg1, arg2，用序号引用中间结果） ===")
TRI = [
    ("*", "b", "c"),
    ("+", "a", "(1)"),
    ("/", "d", "e"),
    ("-", "(2)", "(3)"),
    ("=", "x", "(4)"),
]
print("  " + pad("序号", 6) + pad("op", 6) + pad("arg1", 8) + "arg2")
for i, t in enumerate(TRI, 1):
    print("  " + pad(str(i), 6) + pad(t[0], 6) + pad(t[1], 8) + t[2])
print("  -> 同为 %d 条；三元式少一个 result 字段，" % len(TRI))
print("     代价是一旦要搬动某条指令，所有引用它的序号都得改")

print()
print("=== 三种中间代码形式的等价性 ===")
print("  " + pad("形式", 16) + pad("每条存什么", 24) + "能不能被搬动/重排")
print("  " + pad("四元式", 16) + pad("op + 两个操作数 + 结果", 24) + "能（引用的是显式名字）")
print("  " + pad("三元式", 16) + pad("op + 两个操作数", 24) + "不能（引用的是位置序号）")
print("  " + pad("间接三元式", 16) + pad("三元式 + 一张指示器表", 24) + "能（搬指示器即可）")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== 符号表：进入函数 f 的作用域 ===
  作用域 0      a:double, b:int, c:int, d:double, e:int, x:double

=== 进入内层块后 x 被遮蔽 ===
  查 x ->       int（内层）
  离开后查 x ->         double（外层）

=== 两类语义错误 ===
  重复声明 a ->       重复声明: a
  使用未声明的 y ->       未声明

=== 类型检查：x = a + b * c - d / e ===
  int * int  ->  int
  double + int  ->  double
  double / int  ->  double
  double - double  ->  double
  整式类型 ->     double
  x 的类型 ->     double  （一致，通过）

=== 反例：把 double 直接赋给 int ===
  左值 int，右值 double -> 需要显式转换，否则编译期警告
  warning: conversion from 'double' to 'int' may change value

=== 四元式（op, arg1, arg2, result） ===
  序号  op    arg1    arg2    result
  1     *     b       c       t1
  2     +     a       t1      t2
  3     /     d       e       t3
  4     -     t2      t3      t4
  5     =     t4      _       x
  -> 共 5 个四元式；临时变量用了 t1..t4，共 4 个

=== 三元式（op, arg1, arg2，用序号引用中间结果） ===
  序号  op    arg1    arg2
  1     *     b       c
  2     +     a       (1)
  3     /     d       e
  4     -     (2)     (3)
  5     =     x       (4)
  -> 同为 5 条；三元式少一个 result 字段，
     代价是一旦要搬动某条指令，所有引用它的序号都得改

=== 三种中间代码形式的等价性 ===
  形式            每条存什么              能不能被搬动/重排
  四元式          op + 两个操作数 + 结果  能（引用的是显式名字）
  三元式          op + 两个操作数         不能（引用的是位置序号）
  间接三元式      三元式 + 一张指示器表   能（搬指示器即可）

三条结论：

1. 求值顺序由优先级决定：b*c 与 d/e 先算，a + (b*c) 再算，最后才相减——四元式的行序就是这三个层次的先后。
2. 四元式与三元式条数完全相同，区别只在"引用中间结果的方式"：四元式写名字 t1，三元式写位置 (1)。
3. 类型检查的顺序是"从叶子往根"：每算出一个子表达式的类型就记一条，最后才与左值比对。表驱动的类型检查 = 一次后序遍历。

考点

考点

1. 五类静态语义检查（能默写）

类型检查 / 控制流检查 / 一致性检查 / 相关名字检查 / 作用域检查。

2. 符号表

• 组织：线性表、排序表、哈希表；哈希表是工程主流。
• 作用域：栈式分配，进入块压栈、离开块弹栈，查找从栈顶往下、先命中者胜。
• 名字表与符号表分开存的目的：让符号表的每一项定长，便于索引。

3. 三种中间代码的对比（高频）

项	四元式	三元式	间接三元式
字段数	4（含 result）	3	3 + 指示器
中间结果引用	显式变量名	位置序号	位置序号
优化时能否搬动	能	不能	能
空间开销	最大	最小	居中

4. 高频陷阱

• "语法错"与"语义错"不能混：int a = ; 是语法错（结构不成句）；a = b + 1;（b 未声明）是语义错（结构成句但意思不通）。
• 中间代码与机器无关，与语言也无关——正因为如此，同一套优化才能服务所有源语言与所有目标机器。
• = 号在四元式里也是一条指令：( =, t4, _, x ) 表示"把 t4 存进 x"，它不是"等于"的比较。
• 作用域检查发生在语义分析，但符号表的建表可能早于它——"建表"与"查表"是两件事。
• 三元式写成 ( =, x, (4) ) 与四元式 ( =, t4, _, x ) 的参数位置不一样：三元式把左值放在 arg1、右值放进 arg2，这是 408 常考的细节题。

小结

• 语义分析回答"意思对不对"：查类型、查声明、查作用域，靠一张符号表加一张类型规则表。
• 符号表的作用域用栈实现，查找从栈顶往下、先命中者胜。
• 中间代码的五种形式里，三地址码是主流，落到表格上就是四元式；四元式好优化、三元式省空间。
• IR 的价值在于"10 + 10 而不是 100"：它是源语言与目标机器之间的唯一接口，也是所有优化的舞台。

回到主线：lang/20-steps.md 里，编译阶段的第 ③ ④ 步就是本章这件事。上一章把记号流变成树（结构），本章在树上查类型并生成三地址码（意义与中间形态）；而下一章要做的，是在这批三地址码上动手改——这就是优化。

下一篇：代码优化