第6章 语义分析

语义分析处理上下文无关文法无法描述的信息，包括类型检查、作用域解析和属性计算。

6.1 属性和属性文法

属性（Attribute）

  • 综合属性（Synthesized）：子节点 → 父节点传递
  • 继承属性（Inherited）：父节点/兄弟节点 → 子节点传递

属性文法

  • 在 CFG 每个产生式上附加语义规则
  • 形式：产生式 { 语义规则 }

示例：表达式求值

产生式                  语义规则
exp → exp1 + term        exp.val = exp1.val + term.val
exp → term               exp.val = term.val
term → number            term.val = number.lexval
  • 所有 .val 属性为综合属性
  • 整个文法为 S-属性文法（只含综合属性）

继承属性示例：声明类型传递

decl → var-list : type    var-list.dtype = type.dtype
var-list1 → var-list2 , id  var-list2.dtype = var-list1.dtype
                           id.dtype = var-list1.dtype
type → int                type.dtype = integer
type → float              type.dtype = real

6.2 属性计算算法

S-属性文法的计算（后序遍历）

postorder(node):
    for each child c of node:
        postorder(c)
    compute synthesized attributes of node

L-属性文法的计算（深度优先）

  • 属性依赖从左到右
  • 可在 LL(1) 分析过程中一遍计算

依赖图与拓扑排序（通用方法）

  1. 为每个属性值建立依赖边
  2. 构造整个语法树的依赖有向图
  3. 拓扑排序确定计算顺序
  4. 若存在环 → 不是良定义的属性文法

树遍历算法

  • 预计算所有继承属性（深度优先）
  • 然后后序计算综合属性

6.3 符号表

作用

  • 记录标识符信息：名字、类型、作用域、存储位置等
  • 几乎与编译器的所有阶段交互

实现方式

方法 插入 查找 适用场景
线性列表 O(1) O(n) 小规模
有序列表 O(n) O(log n) 中规模
二叉搜索树 O(log n) O(log n) 通用
杂凑表 O(1) O(1) 最常用

作用域管理

嵌套作用域（嵌套块/嵌套过程）

方法：栈式符号表
- 进入新作用域 → push 新表
- 插入: 在当前作用域的表
- 查找: 从顶层到底层依次查找
- 退出作用域 → pop

常见语言的作用域规则

  • C：块作用域（{ }）、文件作用域
  • Pascal：嵌套过程作用域、最近的声明优先
  • Ada：嵌套作用域、使用 use 子句

6.4 数据类型和类型检查

类型系统

基本类型：int、float、char、bool 等

复合类型：数组、记录/结构体、指针、枚举、联合体

类型等价

等价策略 含义 示例语言
名字等价 类型名相同才等价 Ada、Pascal（默认）
结构等价 类型结构相同即等价 C（大部分情况）、Modula-2 
// 结构等价视角下以下类型等价
type A = array[1..10] of integer;
type B = array[1..10] of integer;
var x: A; y: B;  // 名字等价中 x, y 类型不同

类型检查规则

表达式 e1 + e2:
  若 e1.type = int 且 e2.type = int → int
  若 e1.type = float 且 e2.type = float → float
  若 e1.type = int 且 e2.type = float → float（强制类型转换）

赋值语句 id = e:
  要求 id.type 与 e.type 兼容

类型转换

  • 隐式转换（强制）：编译器自动完成（如 int → float）
  • 显式转换（强转）：程序员写出的转换（如 C 的 (float) x）

多态性和重载

  • 重载：同一名字用于多种不同类型的操作（如 + 既用于 int 也用于 float）
  • 参数多态：泛型/模板（如 C++ template）
  • 子类型多态：面向对象继承

6.5 TINY 语言的语义分析

两遍遍历

  1. 第一遍：构建符号表（遍历语法树，记录所有声明/变量）
  2. 第二遍：类型检查（再次遍历，检查每个表达式的类型一致性）

实现文件

  • symtab.h / symtab.c：杂凑表实现
  • analyze.h / analyze.c：符号表构建 + 类型检查

TINY 语义分析的特点

  • 所有变量是整型（类型检查相对简单）
  • 变量无需预先声明（首次赋值时隐式声明）
  • 检查：变量是否声明、布尔表达式是否用于控制语句、赋值类型是否匹配

考试重点

★★★ 第一梯队（必考）

考点 典型题型
属性文法的属性计算 给定属性文法和语法树，标注属性值
依赖图的构造 识别综合属性和继承属性

★★☆ 第二梯队

考点 典型题型
符号表的插入/查找过程 嵌套作用域下的符号查找
类型检查 判断表达式是否类型正确

★☆☆ 第三梯队

考点 典型题型
综合属性 vs 继承属性 方向和计算时机
S-属性文法 vs L-属性文法 对比
类型等价：结构等价 vs 名字等价 概念
符号表的杂凑表实现 简答