第六章 符号表
编译程序工作的过程中,需要 不断收集、
记录和使用源程序中一些语法符号的类
型和特征等相关信息,
这些信息一般以表格形式存储于系统中,
如 常数表、变量名表、数组名表、过程
名表、标号表 等等，统称为 符号表 。
符号表 组织、构造和管理 方法的好坏会
直接影响 编译系统 的运行效率。
6.1 符号表的组织
对符号表的访问常见操作有,
(1)判定一给定的名字是否在表中 ;
(2)在表中填入一个新名字 ;
(3)访问与给定名字相关的信息 ;
(4)为给定的名字填入或更新其某些信息 ;
(5)从表中删除一个或一组名字
在很多程序设计语言中,对名字的作用域有相应的规定,
即同一名字的标识符,在不同的作用域里标识了不同的
对象,且占用了不同的存储空间,
因此,在组织符号表时,应能反映各个标识符的作用域,
6.2 分程序结构语言 符号表的建立
分程序结构语言 用其所写的 程序单元 (program unit)
中,可以再包含嵌套的 程序单元,且其中每个 程序单元 均
可定义属于自己的一组 局部变量,如 PASCAL中的过程
说明,C中花用括 {}号括起来的分程序或复合语句等,
程序单元 的嵌套导致了变量 作用域 的嵌套,故把允许名
字 作用域 嵌套的语言称为具有 分程序结构语言 的语言,
PASCAL是典型的 分程序结构语言 之一,
对于嵌套的 作用域,同名变量在不同处代表了不同的实
体,因此,需 采用分层建立和处理符号表的方式,
查填表方案
若一标识符在某分程序首部已作说明,则它在整个
分程序内均有定义,除非它在某内层分程序被再次
定义,即 它的作用域是整个分程序,是本层分程序及
内层分程序的 全局量 ;
1,当在一分程序首部某 说明中扫描到一个标识符时,以此标识
符查相应于本层分程序的 符号表,若表中已有此项,则它被
重复说明,出错 ;否则,在表中新登记一项,将该符号及其相
关信息填入,
2,在分程序 执行语句中遇一标识符时,首先查本层表,若找不
到,则查直接外层的 符号表,如此等等,若在某层查到,则可
使用相关信息 ;若遍查所有外层均未找到,则无定义,出错,
各分程序的符号表登记项 按 B2,B4,B3,B1的顺
序 连续存放,
① OUTERN 指明分程序 直接外层分程序的编号 ;
② ECOUNT 记录分程序 在符号表登记项个数 ;
③ POINTER 指向分程序 在符号表中的起始位置 ;
使用 栈 存放临时符号表,
当遇到一分程序的 END时,j
将出现在栈顶的相应符号移
至正式表中,
将表本身的空白区用作栈,
并用 TOPENT及 LASENT指
明临时栈的栈顶及符号表的
当前最末项,
用 CURRBL,LASTBL指明当
前正在处理的分程序编号及
已处理完的最高层分程序的
编号,
构造符号表的算法
1.初始化, CURRBL =0;
LASENT=0; LASTBL=0;
TOPENT=0; /*注,以上各量
在下面的程序中分别简记为
CB,LE,LT,TE*/
2.(1)当进入分程序的首符号或
过程时,
B[++LT].OUTERN=CB;
B[LT].ECOUNT=0;
B[LT].POINTER=TE;
CB=LT;
(2) 遇到分程序中的定义性出现
时, TP--;S[TE]=相关信息 ;
B[CR].ECOUTN++;
B[CR].POINTER=TE;
(3)遇到 END时,
B[CB].POINTER=LE+1;
for(k=1; k<=B[CB].EC;
k++) S[++LE]=S[TE++];
CB=B[CB].OUTERN;
3.重复 2.,直到扫描结束,
对于前面的程序结构，其构造符
号表的过程见教材中 P266图
6-5
6.3 非分程序结构语言符号表的建立
FORTRAN是块结构语言,FORTRAN程序由一或多个
相对独立的程序段组成,其中有唯一的主程序段,其余为
子程序段 (FUNTION,SUBROUTINE,BLOCK DATA),
程序段间的 信息传递 是由 形实结合及公共数据区 实现
的,因此,程序段名及公共区名是全局量,而各段中定义
的变量均是局部量,
FORTRAN语言的编译一般是把每个段视为独立程序
单元进行的,为各段产生相应的代码,再连接装配成一完
整的目标程序,
一程序段编译完毕,该段的局部量已完成使命,可从表中
删除,但全局量仍需保留,
建立两个表,全局符号表 及 局部符
号表,其中 局部表是可重复使用的 ;
较灵活的方法是,将表数据区从两
头使用,用指针 AVAIL1及 AVAIL2
分别指向局部名表空白区和全局名
表空白区,
需指出,有时为实现程序全局优化,
局部名表要保留到优化结束才释放,
名字 信息栏
局部名表
1,.,
2,.,
3,.,
2,.,
1,.,
全局名表
AVAIL1
AVAIL2
结束语
符号表管理 是编译程序很重要的组成部分,在整个编译过程
都要使用,因此,应考虑如何 设置表信息栏的内容 这一因素,
对常见程序设计语言而言,变量表信息栏一般含有如下内容,
种属 (简单变量,数组,结构等 ),类型 (整型,实型等 ),数据区地
址 (相对,绝对 ),内情向量地址 (对数组而言 ),分量首址 (结构
类型 ),是否是形参,公共链及等价链,定义性及引用性出现,是
否赋过值,等等,
过程名表,是否外部,函数类型,是否处理过其定义,是否递归,
形参信息 等等,
编译程序工作的过程中,需要 不断收集、
记录和使用源程序中一些语法符号的类
型和特征等相关信息,
这些信息一般以表格形式存储于系统中,
如 常数表、变量名表、数组名表、过程
名表、标号表 等等，统称为 符号表 。
符号表 组织、构造和管理 方法的好坏会
直接影响 编译系统 的运行效率。
6.1 符号表的组织
对符号表的访问常见操作有,
(1)判定一给定的名字是否在表中 ;
(2)在表中填入一个新名字 ;
(3)访问与给定名字相关的信息 ;
(4)为给定的名字填入或更新其某些信息 ;
(5)从表中删除一个或一组名字
在很多程序设计语言中,对名字的作用域有相应的规定,
即同一名字的标识符,在不同的作用域里标识了不同的
对象,且占用了不同的存储空间,
因此,在组织符号表时,应能反映各个标识符的作用域,
6.2 分程序结构语言 符号表的建立
分程序结构语言 用其所写的 程序单元 (program unit)
中,可以再包含嵌套的 程序单元,且其中每个 程序单元 均
可定义属于自己的一组 局部变量,如 PASCAL中的过程
说明,C中花用括 {}号括起来的分程序或复合语句等,
程序单元 的嵌套导致了变量 作用域 的嵌套,故把允许名
字 作用域 嵌套的语言称为具有 分程序结构语言 的语言,
PASCAL是典型的 分程序结构语言 之一,
对于嵌套的 作用域,同名变量在不同处代表了不同的实
体,因此,需 采用分层建立和处理符号表的方式,
查填表方案
若一标识符在某分程序首部已作说明,则它在整个
分程序内均有定义,除非它在某内层分程序被再次
定义,即 它的作用域是整个分程序,是本层分程序及
内层分程序的 全局量 ;
1,当在一分程序首部某 说明中扫描到一个标识符时,以此标识
符查相应于本层分程序的 符号表,若表中已有此项,则它被
重复说明,出错 ;否则,在表中新登记一项,将该符号及其相
关信息填入,
2,在分程序 执行语句中遇一标识符时,首先查本层表,若找不
到,则查直接外层的 符号表,如此等等,若在某层查到,则可
使用相关信息 ;若遍查所有外层均未找到,则无定义,出错,
各分程序的符号表登记项 按 B2,B4,B3,B1的顺
序 连续存放,
① OUTERN 指明分程序 直接外层分程序的编号 ;
② ECOUNT 记录分程序 在符号表登记项个数 ;
③ POINTER 指向分程序 在符号表中的起始位置 ;
使用 栈 存放临时符号表,
当遇到一分程序的 END时,j
将出现在栈顶的相应符号移
至正式表中,
将表本身的空白区用作栈,
并用 TOPENT及 LASENT指
明临时栈的栈顶及符号表的
当前最末项,
用 CURRBL,LASTBL指明当
前正在处理的分程序编号及
已处理完的最高层分程序的
编号,
构造符号表的算法
1.初始化, CURRBL =0;
LASENT=0; LASTBL=0;
TOPENT=0; /*注,以上各量
在下面的程序中分别简记为
CB,LE,LT,TE*/
2.(1)当进入分程序的首符号或
过程时,
B[++LT].OUTERN=CB;
B[LT].ECOUNT=0;
B[LT].POINTER=TE;
CB=LT;
(2) 遇到分程序中的定义性出现
时, TP--;S[TE]=相关信息 ;
B[CR].ECOUTN++;
B[CR].POINTER=TE;
(3)遇到 END时,
B[CB].POINTER=LE+1;
for(k=1; k<=B[CB].EC;
k++) S[++LE]=S[TE++];
CB=B[CB].OUTERN;
3.重复 2.,直到扫描结束,
对于前面的程序结构，其构造符
号表的过程见教材中 P266图
6-5
6.3 非分程序结构语言符号表的建立
FORTRAN是块结构语言,FORTRAN程序由一或多个
相对独立的程序段组成,其中有唯一的主程序段,其余为
子程序段 (FUNTION,SUBROUTINE,BLOCK DATA),
程序段间的 信息传递 是由 形实结合及公共数据区 实现
的,因此,程序段名及公共区名是全局量,而各段中定义
的变量均是局部量,
FORTRAN语言的编译一般是把每个段视为独立程序
单元进行的,为各段产生相应的代码,再连接装配成一完
整的目标程序,
一程序段编译完毕,该段的局部量已完成使命,可从表中
删除,但全局量仍需保留,
建立两个表,全局符号表 及 局部符
号表,其中 局部表是可重复使用的 ;
较灵活的方法是,将表数据区从两
头使用,用指针 AVAIL1及 AVAIL2
分别指向局部名表空白区和全局名
表空白区,
需指出,有时为实现程序全局优化,
局部名表要保留到优化结束才释放,
名字 信息栏
局部名表
1,.,
2,.,
3,.,
2,.,
1,.,
全局名表
AVAIL1
AVAIL2
结束语
符号表管理 是编译程序很重要的组成部分,在整个编译过程
都要使用,因此,应考虑如何 设置表信息栏的内容 这一因素,
对常见程序设计语言而言,变量表信息栏一般含有如下内容,
种属 (简单变量,数组,结构等 ),类型 (整型,实型等 ),数据区地
址 (相对,绝对 ),内情向量地址 (对数组而言 ),分量首址 (结构
类型 ),是否是形参,公共链及等价链,定义性及引用性出现,是
否赋过值,等等,
过程名表,是否外部,函数类型,是否处理过其定义,是否递归,
形参信息 等等,
