1. Motivation (动机：为什么需要语义分析？)
语法分析（Syntax
Analysis）只能处理上下文无关（Context-Free）的结构，无法发现与上下文有关（Context-Dependent）的错误。单纯的语法正确并不代表程序有意义。
我们需要语义分析来解决以下具体问题：
- 标识符作用域
(Scope)：变量是否在引用的位置可见？（例如：在块外引用块内定义的变量）。
- 重复声明：同一作用域内是否存在同名变量？
- 类型一致性 (Type Consistency)：
- 操作数类型是否匹配？（例如：boolean 类型参与算术加法）。
- 赋值号两边类型是否兼容？
- 数组下标是否为整数？
- 函数调用的实参和形参是否匹配？
- 操作数类型是否匹配？（例如：boolean 类型参与算术加法）。
- 控制流合法性：break 是否出现在循环语句中？
解决方案：利用语法制导翻译技术，在语法分析的过程中嵌入语义动作，收集信息（符号表）并进行检查。
2. Concept (核心概念)
2.1 语义分析的任务
- 收集信息：将标识符的属性（类型、存储位置、作用域等）存入符号表。
- 类型检查：验证语法成分是否满足语义规则。
2.2 符号表 (Symbol Table)
- 定义：一种记录标识符属性（名字、类型、地址、维数、声明行、引用行、指针等）的数据结构。
- 动态性：在编译过程中，符号表的入口不断增加（进入新作用域），有时也不断删除（退出作用域）。
2.3 类型表达式 (Type Expressions)
类型本身也有结构，递归定义如下：
* 基本类型：boolean, char, integer, real, type_error,
void。
* 类型名：即类型别名。
* 构造类型（由类型构造器生成）：
* 数组 (Array)：
* 笛卡儿积/记录 (Record)：
* 指针 (Pointer)：
* 函数 (Function)：
2.4 类型等价 (Type Equivalence)
判断两个类型
1. 结构等价 (Structural Equivalence)：
*
* 或者是将同一类型构造器应用于结构等价的内部类型上。
*
注意：C语言数组作为参数传递时，通常不检查第一维界限，这属于结构等价的特例调整。
2. 名字等价 (Name Equivalence)：
* 两个类型表达式等价，当且仅当它们是同一个类型名。
* Pascal 和 C (对于 struct/union/enum) 通常采用名字等价。
3. Method (实现方法与算法)
3.1 符号表的组织与操作
针对块结构语言（如 Pascal, C），支持嵌套作用域。
A. 组织形式
1. 栈式符号表：
* 新作用域的变量压入栈顶。
* 退出作用域时，栈顶相关的变量出栈。
* 优点：自然实现“最近嵌套作用域原则”。
2. 栈式哈希表：
* 结合哈希表提高查找效率。
*
哈希表存头指针，具体记录通过链表连接（链表方向指向同一哈希桶的旧记录）。
* 同时维护一个 scope 栈来管理作用域的进入和退出。
B. 核心操作
* Insert
(插入)：在当前作用域（栈顶子表）添加新名字。需检查重复声明。
* Lookup
(检索)：从当前作用域（栈顶）向外层（栈底）线性查找。
* Locate
(定位)：进入新块时，建立新子表（或标记栈位置）。
* Relocate
(重定位)：退出块时，删除该块的子表，恢复外层环境。
3.2 结构等价判定算法 seqtest(s, t)
递归判断两个类型表达式是否结构等价：
* 若
* 若
* 若
* 若
* 否则
3.3 简单类型检查程序 (语法制导翻译 SDT)
通过在产生式中嵌入语义动作实现。
A. 变量声明的处理
* 利用全局变量 offset 记录相对地址。
* 基本类型：设置 T.type 和 T.width（如 integer
宽4，real 宽8）。
* 数组：
* 声明动作：调用 enter(id.name, T.type, offset)
填表，并更新 offset = offset + T.width。
B. 过程与作用域的处理
* 使用 符号表栈 (tableptr) 和 偏移量栈
(offset)。
* 进入过程 (P -> M D; S)：
* M -> ε: 创建新表 maketable(top(tableptr))，将其压入 tableptr
栈；压入新 offset=0。
* 退出过程：
* 计算总宽度，弹出 tableptr 和 offset，恢复外层环境。
* 将该过程及其符号表挂载到外层符号表中 (enterproc)。
C. 表达式类型检查
综合属性 E.type 用于向上传递类型。
* 算术运算 (
* 若
* 若其中一个是 real
* 否则
* 函数调用 (
* 查找 id，检查 p 是否非空。
* 检查类型是否为函数 (fun)。
* 检查参数个数 (rparam.num) 和参数类型 (checkptype) 是否匹配。
* 结果类型设为返回值类型。
D. 语句类型检查
* 赋值 (
* 查找 id。
* 检查 id.type 是否等于 E.type。
* 控制流 (
* 必须检查 E.type == boolean。
4. Example (经典例题与场景)
例 1：结构等价 vs 名字等价 (C语言结构体)
struct { int i; char c; } x, y;
struct { int i; char c; } b; 结构等价：x, y, b 的内部结构完全一样（int + char），三者等价。
名字等价（C语言采用）：
x 和 y 在同一条语句声明，视为使用同一个内部生成的类型名，相互等价。
b 是另一次结构体定义，编译器生成了新的内部名字，因此 x 与 b 不等价。
例 2：SDT 应用（声明语句翻译）
输入：i: integer; x: real; A: array[10] of char;
过程推导：
初始 offset = 0。
i: integerenter(i, integer, 0) offset 变为 4。 x: realenter(x, real, 4) offset 变为 4+8=12。 A: array[10] of char宽度 enter(A, array(10, char), 12) offset 变为 22。
例 3：符号表逻辑结构 (Pascal Sort 程序)
场景：主程序 sort 包含子过程 quicksort，quicksort 包含子过程 partition。
查找链条：
Head Area (橙色箭头)：建立作用域链。
partition 表头指向 quicksort 表头。
quicksort 表头指向 sort 表头。
sort 表头指向 nil。
查找 x 的过程：如果在 partition 中引用 x（假设它是 sort 中定义的全局变量），编译器会沿着橙色箭头：partition (无)
quicksort (无) sort (找到 x)。
如果您喜欢我的文章，可以考虑打赏以支持我继续创作.
