编译原理目录
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);
#endif
4.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 代码翻译
- 现代的编译器中的语义分析模块,除了做语义分析外,还要负责生成中间代码或目标代码。
- 代码生成的过程也同样是对树的某种遍历
- 因此语义分析模块往往是编译器中最庞大也最复杂的模块
- - - 结束 - - -