第九章 符号表.ppt

1、指导教师:杨建国 二零零七年十一月,编 译 原 理,重点掌握：符号表的主要属性、作用和组织方法,学习目标,第9章符号表,第一节 符号表的作用和地位,第二节 符号的主要属性及作用,第三节 符号表的组织,教学内容,第四节 符号表的管理,知识结构,9.1符号表的作用和地位,一.符号表的定义,二.符号表的作用,符号表是连接声明与引用的桥梁。一个名字在声明时，相关信息被填写进符号表，而在引用时，根据符号表中的信息生成相应的可执行语句。 它的作用主要有： 辅助语义的正确性检查 辅助代码生成,在编译过程中,编译程序用来记录源程序中 各种名字的特性信息, 所以也称为名字特性表。,三.符号表与编译各阶段的关系,

2、开始，扫描器识别到一个名字后，查阅符号表，填表,在语法分析和语义分析中陆续填入有关信息,在语义分析时用到表中信息进行语义检查，生成中间 代码,在目标代码生成阶段，依据符号表对符号名分配地址,例1.int x, a, b; . . L: x := a + b; .,1. 语法分析和语义分析 说明语句、赋值语句的语法规则 上下文有关分析：是否声明 类型一致性检查 2. 生成目标代码 LOAD a的地址 ADD b的地址 STO x的地址,四.符号表的组成,符号表由若干个登记项（表项）组成，每个表项 分两部分，其中前者是标识符的名字（或在符号表中的 地址），而后者是属性部分（不同种类的标识符属 性不

3、同）。,符号表=名字栏+信息栏,“名字”域:存放名字，一般为标识符的符号串,也可 为指向标识符字符串的指针。,“信息”域:可包括多个子域,分别表示标识符的有关信息，如:,名字(标识符)的种类:简单变量、函数、过程、 数组、标号、参数等 类型：如整型、浮点型、字符型、指针等 性质：变量形参、值形参等 值： 常量名 地址：变量所分配单元的首址或地址位移 大小：所占的字节数 作用域的嵌套层次:,对于数组: 维数、上下界值、计算下标变量地址 所用的信息以及数组元素类型等。 对于记录（结构、联合）：域的个数，每个域名、 地址位移、类型等。 对于过程或函数：形参个数、所在层次、函数 返回值类型、局部变量所

4、占 空间大小等。 对于指针：所指对象类型等。,五.符号表的功能,1.收集符号属性,2.上下文语义的合法性检查的依据,3.作为目标代码生成阶段地址分配的依据,六.符号表的分类,静态表：事先构造好的表，如保留字表、标准 函数名表等。需要时去查相应的此类 表,动态表：编译程序在编译过程中根据需要构造的 表，如标识符表、标号表、数组信息表、 记录信息表和过程信息表等。,9.2符号的主要属性及作用,语言符号可分为：关键字符号、操作符符号、标识符符号,符号名 符号的类型 符号的存储类别 符号的作用域及可视性 符号变量的存储分配信息 符号的其它属性,符号表中的标识符一般设置的属性项目以及它们的功能,一.符号

5、名,标识符：变量的名字、函数的名字、过程的名字 通常把一个标识符在符号表中的位置的整数值称之为该标识符的内部代码 在经过分析处理的语言程序中标识符不再是一个字符串而是一个整数值,二.符号的类型,标识符中除过程标识符之外函数和变量标识符都具有数据类型属性 符号的类型属性是在语言程序中该符号的定义中得到；变量符号的类型属性决定了该变量的数据在存储空间的存储格式，还决定了在该变量上可以施加的运算操作,目前大多数语言已定义了在基本数据类型基础上扩充的复合数据类型 数组或记录结构中的每个基本元素可以是基本数据类型，也可以是其它任何一种组合式数据类型，构成嵌套式数据类型定义 指针类型所指向的变量同样可以是

6、基本数据类型，也可以是其它任何一种组合式数据类型,三.符号的存储类别,多数语言对变量的存储类别定义采用两种方式： 一种是用关键字指定 一种方式是根据定义变量说明在程序中的位置来决定 区别符号存储类型的属性是编译过程语义处理、检查和存储分配的重要依据。符号的存储类别还决定了符号变量的作用域、可视性和它的生命周期等,四.符号的作用域及可视性,作用域：一个符号变量在程序中起作用的范围 定义该符号的位置及存储类关键字一般决定了该符号的作用域 C语言中一个外部变量,一般来说一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可引用的，这就是变量可视性的作用域规则 两种情况影响

7、到一个变量的可视性 1.函数的形式参数 多数语言中规定该函数中仅能引用作为该函数形式参数的那个变量 2.分程序（或复合语句）结构 符号表中设置一个表达符号所在层次的属性域，存放该符号的定义层次,五.符号变量的存储分配信息,根据符号变量的存储类别定义及它们出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置，用相对区头的位移量表示。,通常一个编译程序有两类存储区，即静态存储区和动态存储区 静态存储区 该存储区单元经定义分配后成为静态单元，即在整个语言程序运行过程中是不可改变的 动态存储区 根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡,六.符号

8、的其他属性,数组内情向量 包括数组类型，维数，各维的上、下界及数组首地址，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据,记录结构型的成员信息 一个记录结构型的变量，在存储分配时所占空间大小要由它的全体组成成员来确定，另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。这两种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置。,函数及过程的形参 每个函数或过程的形参个数、形参的排列次序及每个形参的类型，都体现了调用该函数或过程时的属性，它们都应该反映在符号表的函数或过程标识符的项中。,9.3符号表的组织,9.3.1 符号表的总体组织,第1种：按照属

9、性种类完全相同的那些符号组织 在一起 优点：每个符号表中存放符号的属性个数和结构完全相同 缺点：一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度,第2种：把所有语言中的符号都组织在一张符号表中 优点：总体管理非常集中单一，且不同种类符号的共同属性可一致地管理和处理 缺点：增加了符号表管理的复杂度，给填表和查表带来很大的不方便,假设有下列3类符号及其所需之属性：,第1种组织方法得到三张符号表如下图所示：,第2种组织方法得到一张符号表如下图所示：,第3种：折中方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性 按折中方式重新组织上例中的3类符号，

10、可构成2张符号表如下图所示：,属性值3、4合并后如下图所示：,例2. PROCEDURE INCWAP（M，N） BEGIN 10：KM1 MM4 NK END 经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT,符号名表SNT NAME INFORMATION （1）M 参数，整数，变量 （2）N 参数，整数，变量 （3）K 整数，变量 常数表CT 值（VALUE） (1) 1 (2) 4,入口名表ENT NAME INFORMATION （1）INCWAP 二目子程序，入口QT(1) /*记录入口名INCWAP的入口地址 标号表LT L

11、ABLE INFORMATION （1）10 QT(4) /*记录了标号10对应的四元式序列号 四元式表,9.3.2 符号表项的排列,线性法 二分法 散列法,效率高，被多数编译程序采用,一.线性组织,这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录,例如： a /第一次出现a的地方b /第一次出现b的地方a /第二次出现a的地方d /第一次出现d的地方c /第一次出现c的地方b /第二次出现b的地方,则符号表中表项排列将如下图所示： h表示该符号表之表头，是表的开始位置 p表示该符号表的表项是符号表当前的结束位置,线性组织的符号表,二.排序组织及二分法,排序组织的符号表，就是在符号表中

12、的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的 关于排序表的表项建立及符号查找，通常采用“二分法”,对上述例子中的符号出现情况按排序组织得到的符号表将如下图所示：,排序组织的符号表,三.散列组织,一个符号在散列表中的位置，是由对该符号进行某种函数操作（杂凑函数）所得到的函数值来确定的 假设选定杂凑函数fhash，对符号代码值杂凑运算之后得到杂凑值是Vhash，可表示为： Vhash=fhash() 设符号的散列位置Lhash则有： Lhash=mod(Vhash,N)，其中N为散列表的表长,一个具有符号代码值为Vsymbol的表项散列如下图：,散列冲突：

13、不同符号散列到同一表项位置的现象 解决办法：表长N取一个素数、多次散列 杂凑函数的选取是构造散列表的关键 目前编译程序中，一般采用对符号代码的位操作作为杂凑函数，见得最多的是符号代码的字符段叠加或加权叠加以及符号代码的对折或多折等位操作,9.3.3 关键字域的组织,在编译程序中，符号表的关键字域就是符号本身，它可以是语言的保留字，操作符号或标识符（包括变量名、函数名、记录结构标志等） 规定外部规则的目的是考虑到操作系统、汇编程序及其需要联系的系统之间的匹配，而规定内部规则的目的是考虑到编译程序本身对标识符的识别和区分,比如上述C语言的关键字段长度可以是32个（其中31个是存放名字，余下一个是存

14、放字符串结束标志，这是C语言处理所需要的），如下图所示：,既要保证关键字段的等长，又要减少甚至消除冗余，采用关键字池的索引结构是可取的 例如，一组标识符： an exemplar of key-words field,关键字段的组织结构如下图所示：,关键字池组织的符号表,1.等长属性值域组织： 可以取相应的数据类型表达属性值 表示该符号布尔性质的属性域，可用1个bit位来表示，也可用1个布尔量表示： defined 1表示已定义 defined 0表示没定义 defined true 表示已定义defined false表示没定义,9.3.4 其他域的组织,data-type 3个bit位 c

15、har 0 0 0 short 0 0 1 int 0 1 0 long 0 1 1 unsigned 1 0 0 float 1 0 1 double 1 1 0,表示符号的基本数据类型可以用3个bit位来表示， 也可用1个整型量来表示（C语言为例）：,data-type 整型值 char 0 short 1 int 2 long 3 unsigned 4 float 5 double 6,若一个函数是无参的，则该函数符号项中“函数形参”指针域值为“空” 若某个形参是它所属函数的最后一个形参，则该形参符号项中“函数形参”指针域值为“空” 例如，有函数： func1 (para1,para2,

16、para3) func2 ( ),函数形参链属性表达,若某个成员是一个结构量的最后一个成员，则该成员符号项中“结构成员”属性域值为空,例如，有一个结构： struct tag1 memb1 memb2 struct tag2 memb3 memb4 memb5 memb6 memb7 stv;,结构成员链属性表达,2.不等长属性值域的组织： 特例：数组内情向量属性分成维数和每维元素个数 设有下列两个数组： array1 (subscrip1,subscrip2) array2 (subscrip3, subscrip4, subscrip5, subscrip6) 数组符号在符号表项中可以设立

17、一个指向内情向量空间的指针，而在内情向量空间记录关于该数组的维数和每维元素个数,数组内情向量属性表达,具体实例：int abc342的排列和各种指针所指向的位置见下图：,对于C语言中一个一般形式定义的数组： type arrays1s2sn array 指针值addr目标长l1 array0 指针值addr 目标长l2 array00 指针值addr 目标长l3 array000 指针值addr 目标长ln 其中：addr是数组分配的地址： lk=sk*sk+1*sn*sizeof(type) k=1,2,n 而array000是该数组的第1个元素,有关指针值的计算是： arrayi1=arr

18、ay0+i1 arrayi1i2=array00+(i1*s2+i2) arrayi1i2i3=array000+(i1*s2+i2)*s3+i3) arrayi1i2ik=array00+(i1*s2+i2)*s3+ik) (k=1,2,n-1) 数组元素的地址计算： arrayi1i2in= array00+(i1*s2+i2)*s3+in)*sizof(type),用成员的索引结构来构造结构量，这时结构标志符号在符号表项中设一个指向成员索引区的指针，索引区包含两种属性信息：该结构的空间尺寸和成员索引信息,上述结构例子struct tag1的不等长索引结构可 用下图所示的组织,在一个符号表

19、中若有若干个用位信息表示的属性时，可把他们组织到一起，甚至可用一个整型数来表达这样的几个位信息属性。这种组织与上述合并不同的是各属性有各自的表项中的位置,例如，有下列的一些符号属性： 该变量符号是否已初始化 该符号是否是结构成员 该符号是否是标号 该符号是否是保留字,这些属性都可用1个信息位表示，在符号表中可以把它们组织在一个整型字段中作为一个属性域，而其中相应的信息位置表示上述相应的属性，我们称这种域为复合属性域。,为实现这种同名标识符的语义功能，符号表中需要设立下推链域的组织 下推链域的组织要求在进入一个内层结构并发生重名标识符定义时，需把当前符号表中外层的该符号表项下推到下推链中而在符号

20、表被下推的表项处建立内层的同名标识符的表项,9.3.5 下推链域的组织,例如，设有一个C语言程序如下所示：,0,1,2,3,当依次退出分程序时，下推链被逐次回推到符号表项中,符号表的初始化，就是在对语言程序开始编译的时刻，定义建立符号表的初始状态,9.4符号表的管理,9.4.1 符号的初始化,初始化方法与符号表的组织方式有关,线性组织和二分法组织的符号表，其表的长度在编译开始时通常为0,而随着符号的逐步登录，表长增长 也叫线性方式组织的符号表，其初始化为表尾和表头位置相同,增长,一.变长符号表,散列组织的符号表的表长是确定的，其是否已有表项登录仅取决于该符号表中是否存在已有表项值的表项 也叫散列方式组织的符号表，其初始化要清除表中所有表项值。,二.定长符号表,下图表示定长符号表初始化的状态：,通过查找符号表，如果编译程序从语言程序中获得的一个标识符符号不在符号表中，就要将此符号登录在符号表中,登录符号到符号表中，首先要确定登录的位置,特别指出：线性方法和二分方法组织的符号