?符号表
? 标识符的作用：
声明部分：定义了各种对象及对应的属性和
使用规则。
程序体：对所定义的对象进行各种操作。
$id idname
Idname AttributeIR
? 必要性
Token：
新表－符号表（种类、类型等信息）：
? 有关符号表的操作：
添加、作用域删除、查询
?处理符号表的模块：
定义符号表数据结构
定义符号表上的操作
符号表
?符号表的作用,为语义检查和代码生成提供
标识符的语义信息。
?标识符的处理思想：
?遇到定义性标识符时，在符号表中填写
被定义标识符的符号项；
?当遇到使用性标识符时，用该标识符查
符号表求得其属性。
标识符的特点
?标识符的作用域,标识符有效的最大程序段
?嵌套作用域规则,当存在标识符的嵌套声明
时，最近定义的属性为标识符的当前属性
?局部化单位,允许有声明的程序段
P,Var x,y,z
Var x,m,n
x:=1;
m:=x+1;
y:=x+1;
x:=0;
Q:
?符号表的种类,全局符号表、局部符号表
?符号表的操作特点：
? 在 声明部分，定义标识符，要加入符号表
? 在表达式或语句中，使用标识符，应查表
查其属性。
? 每个标识符在其作用域结束后，要删掉该
属性表项
? 体现嵌套作用规则和局部化
符号表处理技术
基本表组织结构：
? 线性表结构：顺序查表法
? 二叉树结构：平分查表法
? Hash表结构：散列查表法
符号表的局部化处理
? 思想,确定在某个程序点处有效的所有标
识符属性表项。即每个局部化单位能确定
其符号表。
? 方法：
二叉式局部符号表
散列式全局符号表
嵌套式局部符号表
二叉式局部符号表
?组织结构：
每个局部化单位构造一个符号表, 每个符号表采用二
叉树结构 。
?具体实现：
用栈 (Scope)来保存活跃的局部化单位的符号表地址
? 进入局部化区,创建一个新的空符号表, 其
地址压入 scope栈
? 遇定义性标识符,其属性加入当前栈顶符号表
? 遇使用性标识符,从栈顶符号表依次往下查找
? 退出局部化区,删掉栈顶符号表
二叉式局部符号表例子
[1]BEGIN A,int；
[2]BEGIN A,real;
[3]BEGIN A,bool;
A,= false
END ;
A,= 0.55 ;
END ;
A,= 100
END
散列式全局符号表
? 组织结构：
整个程序用一个符号表，采用外拉链散列表
? 具体实现：
符号表的局部化：
嵌套作用域规则：
设置计数器标记局部化单位,n:=0
? 进入局部化单位,n:=n+1;
? 定义性标识符,hash(Key)= pos;放入最前面位置
? 使用性标识符,hash(Key)=pos;第一个遇到的
? 退出局部化单位：删除局部化单位编号为 n的标识
符 ;n:= n-1;
散列式全局符号表例
[1]BEGIN A,int；
[2]BEGIN A,real;
[3]BEGIN A,bool;
A,= false
END ;
A,= 0.55 ;
END ;
A,= 100
END
嵌套式局部符号表
? 组织结构：
整个程序一个表，采用线性组织方式，用栈记录
每个局部化单位符号表的头地址。
? 具体实现：
? 进入局部化单位,登记符号表头地址；
level:=level+1;Scope[level]:=top;
? 定义性标识符,登记标识符属性到符号表中；
? 使用性标识符,从本层依次往下查；
? 退出局部化单位,关闭本层符号表；
top:=top+1;
SymbTable[top]:=(0,Scope[level]-1);
level:= level-1;
嵌套式局部符号表例
Proc P( )
VAR i,j,k,int；
Proc Q( )
VAR x,y, real;
BEGIN …………… END
Proc S( )
VAR c,e, char;
BEGIN …………… END
BEGIN ………………… END
? 标识符的作用：
声明部分：定义了各种对象及对应的属性和
使用规则。
程序体：对所定义的对象进行各种操作。
$id idname
Idname AttributeIR
? 必要性
Token：
新表－符号表（种类、类型等信息）：
? 有关符号表的操作：
添加、作用域删除、查询
?处理符号表的模块：
定义符号表数据结构
定义符号表上的操作
符号表
?符号表的作用,为语义检查和代码生成提供
标识符的语义信息。
?标识符的处理思想：
?遇到定义性标识符时，在符号表中填写
被定义标识符的符号项；
?当遇到使用性标识符时，用该标识符查
符号表求得其属性。
标识符的特点
?标识符的作用域,标识符有效的最大程序段
?嵌套作用域规则,当存在标识符的嵌套声明
时，最近定义的属性为标识符的当前属性
?局部化单位,允许有声明的程序段
P,Var x,y,z
Var x,m,n
x:=1;
m:=x+1;
y:=x+1;
x:=0;
Q:
?符号表的种类,全局符号表、局部符号表
?符号表的操作特点：
? 在 声明部分，定义标识符，要加入符号表
? 在表达式或语句中，使用标识符，应查表
查其属性。
? 每个标识符在其作用域结束后，要删掉该
属性表项
? 体现嵌套作用规则和局部化
符号表处理技术
基本表组织结构：
? 线性表结构：顺序查表法
? 二叉树结构：平分查表法
? Hash表结构：散列查表法
符号表的局部化处理
? 思想,确定在某个程序点处有效的所有标
识符属性表项。即每个局部化单位能确定
其符号表。
? 方法：
二叉式局部符号表
散列式全局符号表
嵌套式局部符号表
二叉式局部符号表
?组织结构：
每个局部化单位构造一个符号表, 每个符号表采用二
叉树结构 。
?具体实现：
用栈 (Scope)来保存活跃的局部化单位的符号表地址
? 进入局部化区,创建一个新的空符号表, 其
地址压入 scope栈
? 遇定义性标识符,其属性加入当前栈顶符号表
? 遇使用性标识符,从栈顶符号表依次往下查找
? 退出局部化区,删掉栈顶符号表
二叉式局部符号表例子
[1]BEGIN A,int；
[2]BEGIN A,real;
[3]BEGIN A,bool;
A,= false
END ;
A,= 0.55 ;
END ;
A,= 100
END
散列式全局符号表
? 组织结构：
整个程序用一个符号表，采用外拉链散列表
? 具体实现：
符号表的局部化：
嵌套作用域规则：
设置计数器标记局部化单位,n:=0
? 进入局部化单位,n:=n+1;
? 定义性标识符,hash(Key)= pos;放入最前面位置
? 使用性标识符,hash(Key)=pos;第一个遇到的
? 退出局部化单位：删除局部化单位编号为 n的标识
符 ;n:= n-1;
散列式全局符号表例
[1]BEGIN A,int；
[2]BEGIN A,real;
[3]BEGIN A,bool;
A,= false
END ;
A,= 0.55 ;
END ;
A,= 100
END
嵌套式局部符号表
? 组织结构：
整个程序一个表，采用线性组织方式，用栈记录
每个局部化单位符号表的头地址。
? 具体实现：
? 进入局部化单位,登记符号表头地址；
level:=level+1;Scope[level]:=top;
? 定义性标识符,登记标识符属性到符号表中；
? 使用性标识符,从本层依次往下查；
? 退出局部化单位,关闭本层符号表；
top:=top+1;
SymbTable[top]:=(0,Scope[level]-1);
level:= level-1;
嵌套式局部符号表例
Proc P( )
VAR i,j,k,int；
Proc Q( )
VAR x,y, real;
BEGIN …………… END
Proc S( )
VAR c,e, char;
BEGIN …………… END
BEGIN ………………… END
