7.4 符号表
.符号表的作用和地位
.符号的主要属性及作用
.符号表的组织符号表的作用和地位 -----语义检查的依据目标代码生成阶段地址分配的依据在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息,符号表中所登记的信息在编译的不同阶段都要用到。
在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。
在目标代码生成阶段，当对符号名进行地址分配时，
符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。
因为每遍所关心的信息各有差异。
符号 属性 (信息）
几种通常都是需要的 。
1 符号名
2 符号的类型
3 符号的存储类别
4 符号的作用域及可视性
5 符号变量的存储分配信息
6 符号的其它属性 （１） 数组内情向量
（２） 记录结构型的成员信息 （３） 函数及过程的形参对符号表的操作
创建符号表在编译开始时或进入一个分程序
插入表项在遇到新的标识符声明时进行
查询表项在引用声明过的标识符时进行
修改表项在获得新的语义值信息时进行
删除一个或一组无用的项
释放符号表的空间在编译结束前或退出一个分程序符号表的组织总体组织和表项属性信息组织第一种,把属性种类完全相同的那些符号组织在一起，构造出多个符号表,常数表、变量名表、过程名表,标号表第二种,把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表符号表项的排列符号表作为一个多元组,表中元组的排列组织是构造符号表的重要成分 。 在编译程序的整个工作过程中,符号表被频繁地用来建立表项,查找表项,填充和引用表项的属性 。 因此表项的排列组织对该系统运行的效率起着十分重要的作用 。 在编译程序中,符号表项的组织传统上采用三种构造方法 。 即线性法,二分法及散列法 。
关键字域的组织符号表的关键字域（段）就是符号名称等长关键字域（段）符号表不等长关键字段符号表 ---采用关键字池的索引结构 。
作用域检查 作用域和可见性基本作用域规则（ lexical rule)
int a;
void Binky(int a) {
int a;
a = 2;
...
}
作用域检查实现：
1每个作用域一个独立的符号表，这些符号表组织成作用域栈
2对所有作用域的全局符号表，每个作用域有一个作用域号
(1) program sort(input,output)
(2) var a,array[0..10] of integer;
(3) x,integer;
(4) procedure readarray;
(5) var i,integer;
(6) begin,.,a,.,end {readarray};
(7) procedure exchange (i,j,integer);
(8) begin
(9） x,= a[i]; a[i:=a[j]; a[j]:=x
(10) end {exchange};
(11) procedure quicksort (m,n:integer);
(12) var k,v,integer;
(13) function partition (y,z,integer),integer;
(14) var i,j:integer;
(15) begin,.,a,..
(16),.........
(17),.,exchange (i,j);,..
(18) end {partition};
(19) begin,.,end {quicksort};
(20) begin,.,end (sort}.
嵌套结构型程序设计语言 （ Pascal） 的特点,可采用的办法：
,将其符号表设计为栈符号表,当新的名字出现总是从栈顶填入 。 查找操作从符号表的栈顶往底部查 （ 保证先查最近出现的名字 ） 。 因为程序是分层的,并且一个过程结束时将释放相应的子符号表,因此查找范围与线性表比相对要小一些 。
,引入一个显示 （ DISPLAY） 层次关系表,称为过程的嵌套层次表 。 其作用是为了描述过程的嵌套层次,指出当前正在活动着的各嵌套的过程 （ 或函数 ） 相应的子符号表在栈符号表中的起始位置 （ 相对地址 ） 。 DISPLAY
表也是一个栈,栈顶指针为 level。 当进入一个新过程时,level增加 1；每当退出一个过程时,level减 1。 DISPLAY(level)总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置 。
,在符号表的信息栏中引入一个指针域 （ previous） 用以链接它在同一过程内的前一域名字在表中的下标 （ 相对位置 ） 。 每一层的最后一个域名字,
其 previous之值为 0。 这样,每当需要查找一个新名字时,就能通过
DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置 。 然后,通过 previous可以找到同一过程内的所有被说明的名字 。
符号表
(program p0 (I,o);
(2) Const a=0;
(3) Var b,c:integer;
(4) e:real;
(5) Procedure p1(x:real);
(6) Var f,g:real;
(7) Procedure p2( i:integer);
(8) Const b=5;
(9) Var h:boolean;
(10) …..
(11) ….
(12)….
(13)….
(14) …
(15)}
1
6
localmain
display
栈符号表
top
编译程序分析第 9行时符号表的内容
PL/0编译器的符号表实现
PL/0编译器符号表的数据结构
alfa = packed array[1..al] of char;
object = (constant,variable,procedur);
table,array[0..txmax] of record
name:alfa;
case kind,object of
constant,(val,integer);
variable,procedur,(level,adr,size,integer)
end;
PL/0编译器通过 block()函数的值参 tx传递各作用域符号表的起始位置,值参 level传递作用域的嵌套层次。
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,CONSTANT
KIND,CONSTANT
KIND,VARIABLE
KIND,VARIABLE
KIND,VARIABLE
KIND,PROCEDUR
VAL,35
VAL,49
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,
S I Z E,4
NAME,G
……
KIND,VARIABLE
……
LEV EL,L E V + 1
……
ADR,DX
……
例程序说明部分为：
CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G ； …
名字 类型 层次 /值 地址 存储空间
Const（ 常量） 无 层次对应名字表某 编译器的符号表实例
(1)class Computer {
(2) int cpu;
(3) void Crash(int nTimes) {
(4) int i;
(5) …
(6) }
(7)}
(8) class Mac extends Computer {
(9) int mouse;
(10)}
(11) void main() {
(12) class Mac powerbook;
(13) powerbook.Crash(2);
(14) …
(15)}
global
function
local
Computer
Mac
class
class
main
powerbook class Macvariable
nil
Computer类的描述
parent
field
nil cpu
crash function
function
variable int
Mac类的描述
parent
mouse variable intfield
略略作用域栈
local作用域的符号表
global作用域的符号表
Computer类成员符号表
Mac类成员符号表
top
编译程序分析第 13行时符号表的内容
.符号表的作用和地位
.符号的主要属性及作用
.符号表的组织符号表的作用和地位 -----语义检查的依据目标代码生成阶段地址分配的依据在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息,符号表中所登记的信息在编译的不同阶段都要用到。
在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。
在目标代码生成阶段，当对符号名进行地址分配时，
符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。
因为每遍所关心的信息各有差异。
符号 属性 (信息）
几种通常都是需要的 。
1 符号名
2 符号的类型
3 符号的存储类别
4 符号的作用域及可视性
5 符号变量的存储分配信息
6 符号的其它属性 （１） 数组内情向量
（２） 记录结构型的成员信息 （３） 函数及过程的形参对符号表的操作
创建符号表在编译开始时或进入一个分程序
插入表项在遇到新的标识符声明时进行
查询表项在引用声明过的标识符时进行
修改表项在获得新的语义值信息时进行
删除一个或一组无用的项
释放符号表的空间在编译结束前或退出一个分程序符号表的组织总体组织和表项属性信息组织第一种,把属性种类完全相同的那些符号组织在一起，构造出多个符号表,常数表、变量名表、过程名表,标号表第二种,把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表符号表项的排列符号表作为一个多元组,表中元组的排列组织是构造符号表的重要成分 。 在编译程序的整个工作过程中,符号表被频繁地用来建立表项,查找表项,填充和引用表项的属性 。 因此表项的排列组织对该系统运行的效率起着十分重要的作用 。 在编译程序中,符号表项的组织传统上采用三种构造方法 。 即线性法,二分法及散列法 。
关键字域的组织符号表的关键字域（段）就是符号名称等长关键字域（段）符号表不等长关键字段符号表 ---采用关键字池的索引结构 。
作用域检查 作用域和可见性基本作用域规则（ lexical rule)
int a;
void Binky(int a) {
int a;
a = 2;
...
}
作用域检查实现：
1每个作用域一个独立的符号表，这些符号表组织成作用域栈
2对所有作用域的全局符号表，每个作用域有一个作用域号
(1) program sort(input,output)
(2) var a,array[0..10] of integer;
(3) x,integer;
(4) procedure readarray;
(5) var i,integer;
(6) begin,.,a,.,end {readarray};
(7) procedure exchange (i,j,integer);
(8) begin
(9） x,= a[i]; a[i:=a[j]; a[j]:=x
(10) end {exchange};
(11) procedure quicksort (m,n:integer);
(12) var k,v,integer;
(13) function partition (y,z,integer),integer;
(14) var i,j:integer;
(15) begin,.,a,..
(16),.........
(17),.,exchange (i,j);,..
(18) end {partition};
(19) begin,.,end {quicksort};
(20) begin,.,end (sort}.
嵌套结构型程序设计语言 （ Pascal） 的特点,可采用的办法：
,将其符号表设计为栈符号表,当新的名字出现总是从栈顶填入 。 查找操作从符号表的栈顶往底部查 （ 保证先查最近出现的名字 ） 。 因为程序是分层的,并且一个过程结束时将释放相应的子符号表,因此查找范围与线性表比相对要小一些 。
,引入一个显示 （ DISPLAY） 层次关系表,称为过程的嵌套层次表 。 其作用是为了描述过程的嵌套层次,指出当前正在活动着的各嵌套的过程 （ 或函数 ） 相应的子符号表在栈符号表中的起始位置 （ 相对地址 ） 。 DISPLAY
表也是一个栈,栈顶指针为 level。 当进入一个新过程时,level增加 1；每当退出一个过程时,level减 1。 DISPLAY(level)总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置 。
,在符号表的信息栏中引入一个指针域 （ previous） 用以链接它在同一过程内的前一域名字在表中的下标 （ 相对位置 ） 。 每一层的最后一个域名字,
其 previous之值为 0。 这样,每当需要查找一个新名字时,就能通过
DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置 。 然后,通过 previous可以找到同一过程内的所有被说明的名字 。
符号表
(program p0 (I,o);
(2) Const a=0;
(3) Var b,c:integer;
(4) e:real;
(5) Procedure p1(x:real);
(6) Var f,g:real;
(7) Procedure p2( i:integer);
(8) Const b=5;
(9) Var h:boolean;
(10) …..
(11) ….
(12)….
(13)….
(14) …
(15)}
1
6
localmain
display
栈符号表
top
编译程序分析第 9行时符号表的内容
PL/0编译器的符号表实现
PL/0编译器符号表的数据结构
alfa = packed array[1..al] of char;
object = (constant,variable,procedur);
table,array[0..txmax] of record
name:alfa;
case kind,object of
constant,(val,integer);
variable,procedur,(level,adr,size,integer)
end;
PL/0编译器通过 block()函数的值参 tx传递各作用域符号表的起始位置,值参 level传递作用域的嵌套层次。
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,CONSTANT
KIND,CONSTANT
KIND,VARIABLE
KIND,VARIABLE
KIND,VARIABLE
KIND,PROCEDUR
VAL,35
VAL,49
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,
S I Z E,4
NAME,G
……
KIND,VARIABLE
……
LEV EL,L E V + 1
……
ADR,DX
……
例程序说明部分为：
CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G ； …
名字 类型 层次 /值 地址 存储空间
Const（ 常量） 无 层次对应名字表某 编译器的符号表实例
(1)class Computer {
(2) int cpu;
(3) void Crash(int nTimes) {
(4) int i;
(5) …
(6) }
(7)}
(8) class Mac extends Computer {
(9) int mouse;
(10)}
(11) void main() {
(12) class Mac powerbook;
(13) powerbook.Crash(2);
(14) …
(15)}
global
function
local
Computer
Mac
class
class
main
powerbook class Macvariable
nil
Computer类的描述
parent
field
nil cpu
crash function
function
variable int
Mac类的描述
parent
mouse variable intfield
略略作用域栈
local作用域的符号表
global作用域的符号表
Computer类成员符号表
Mac类成员符号表
top
编译程序分析第 13行时符号表的内容
