编译原理目录
1、词法分析
2、语法分析（重点）
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
四、语义分析
语义分析任务： 抽象语法树 => 语义分析器 => 中间代码
语义分析也称为类型检查、 上下文相关分析。负责检查程序（抽象语法树）的上下文相关的属性，这是具体语言相关的，典型的情况包括：变量在使用前先进行声明、每个表达式都有合适的类型、函数调用和函数的定义一致 等等…
程序语言的语义
- 传统上，大部分的程序设计语言都采用自然语言来表达程序语言的语义。例如，对于
+运算：要求左右操作数都必须是整型数。 - 编译器的实现者必须对语言中的语义规定有全面的理解。主要的挑战是如何能够正确高效的实现
接下来的内容，将讨论涉及的主要问题和解决方案
4.1 语义检查
以 C-- 为例
4.1.1 类型检查算法:
文法:
E -> n
| true
| false
| E + E
| E && E举例:
// 类型合法的程序：
3+4
false && true
// 类型不合法的程序：
3 + true
true + false
// 对这个语言，语义分析的任务是：对给定的一个表达式e，写一个函数
type check(e);
// 返回表达式e的类型；若类型不合法，则报错。算法:
enum type {INT, BOOL};
enum type check_exp (Exp_t e)
switch(e->kind)
case EXP_INT: return INT;
case EXP_TRUE: return BOOL;
case EXP_FALSE: return BOOL;
case EXP_ADD:
t1 = check_exp (e->left);
t2 = check_exp (e->right);
if (t1!=INT || t2!=INT)
error (“type mismatch”);
else return INT;
case EXP_AND:
t1 = check_exp (e->left);
t2 = check_exp (e->right);
if ( (t1!=EXP_TRUE && t1!=EXP_FALSE) || (t2!=EXP_TRUE && t2!=EXP_FALSE) )
error (“type mismatch”);
else return BOOL;示例1: $3+4$
算法执行流程: +作为参数传进去，匹配case EXP_ADD，t1 = check_exp(3) = 3，同理t2 = 4，return INT，+的位置上接收到一个INT。
示例2: $3+(4+true)$
算法执行流程:+作为参数传进去，匹配case EXP_ADD，t1 = 3，t2 = check_exp(+),t2调用的函数中，匹配case EXP_ADD，t1 = 4, t2 = true，t2 != INT报错。
4.1.2 变量声明的处理
文法:
P -> D E
D -> T id ; D
|
T -> int
| bool
E -> n
| id
| true
| false
| E + E
| E && E举例:
// 类型合法的程序：
int x;
x+4
// 类型合法的程序：
bool y;
false && y
// 类型不合法的程序：
x + 3
// 类型不合法的程序：
int x;
x + false算法:
enum type {INT, BOOL};
Table_t table; // 符号表 <key, value>, 在这里<id, type>
enum type check_prog (Dec_t d, Exp_t e)
table = check_dec (d)
return check_exp (e)
Table_t check_dec (Dec_t d)
foreach (T id ∈ d)
table_enter (table, id, T)
enum type check_exp (Exp_t e)
switch (e->kind)
case EXP_ID:
t = Table_lookup (table, id)
if (id not exist)
error (“id not found”)
else return t示例:
4.2 符号表
- 用来存储程序中的变量相关信息：类型、作用域、访问控制信息等等。
- 必须非常高效，程序中的变量规模会很大。
4.2.1 符号表的接口
#ifndef TABLE_H
#define TABLE_H
typedef … Table_t; // 符号表的数据结构
// 新建一个符号表
Table_t Table_new ();
// 符号表的插入
void Table_enter (Table_t, Key_t, Value_t);
// 符号表的查找
Value_t Table_lookup (Table_t, Key_t);
#endif4.2.2 符号表的典型数据结构
// 符号表是典型的字典结构：
symbolTable: key -> value
// 一种简单的数据结构的定义（概念上的）：
typedef char *key;
typedef struct value{
Type_t type;
Scope_t scope;
… // 必要的其他字段
} value;| 变量映射 | type | scope | ... |
|---|---|---|---|
| x | INT | 0 | ... |
| y | BOOL | 1 | ... |
| ... | ... | ... | ... |
4.2.3 符号表的高效实现
- 为了高效，可以使用哈希表等数据结构来实现符号表，查找是O(1)时间。
- 为了节约空间，也可以使用红黑树等平衡树，查找是O(logN)时间。
4.2.4 作用域 —— 符号表处理作用域的方法
方法1：一张表的方法
- 进入作用域时， 插入元素
- 退出作用域时， 删除元素
方法2：采用符号表构成的栈
- 进入作用域时， 插入新的符号表
- 退出作用域时， 删除栈顶符号表
4.2.5 名字空间 —— 用符号表处理名字空间
变量名、结构体名、标号名存在名称相同时，需要对这些名字进行处理。
- 每个名字空间用一个表来处理。
- 以C语言为例，有不同的名字空间：变量、结构体、标签、标号等等，可以每类定义一张符号表。
4.3 其它问题
- 类型相容性?
- 错误诊断?
- 代码翻译?
4.3.1 类型相等
- 类型检查问题往往归结为判断两个类型是否相等t1==t2？在实际的语言中，这往往是个需要谨慎处理的复杂问题
示例1： 名字相等vs结构相等
- 对采用名字相等的语言，可直接比较
- 对采用结构相等的语言，需要递归比较各个域
示例2： 面向对象的继承，子类赋值给父类
- 需要维护类型间的继承关系
4.3.2 错误诊断
- 要给出尽可能准确的错误信息
要给出尽可能多的错误信息
- 从错误中进行恢复
要给出尽可能准确的出错位置
- 程序代码的位置信息要从前端保留并传递过来
4.3.3 代码翻译
- 现代的编译器中的语义分析模块，除了做语义分析外，还要负责生成中间代码或目标代码。
- 代码生成的过程也同样是对树的某种遍历
- 因此语义分析模块往往是编译器中最庞大也最复杂的模块
- - - 结束 - - -