第9章符号表.ppt
《第9章符号表.ppt》由会员分享,可在线阅读,更多相关《第9章符号表.ppt(57页珍藏版)》请在三一文库上搜索。
1、第9章 符号表,9.1符号表的作用和地位 9.2符号的主要属性及作用 9.3符号表的组织 9.4 符号表的管理,符号表的作用和地位: 收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据,9.1符号表的作用和地位, 收集符号属性 编译程序扫描说明部分收集有关标识符的属性,并在符号表 中建立符号的相应属性信息。例如,编译程序分析到下述两 个说明语句 int A; float B5; 则在符号表中收集到关于符号A的属性是一个整型变量,关于符号B 的属性是具有5个浮点型元素的一维数组。, 上下文语义的合法性检查的依据: 在语义分析中,符号表所登记的内容将用于语义检查(如检查
2、一个 名字的使用和原先的说明是否一致)和产生中间代码。通过符号表中属性记录可进行相应上下文的语义检查。 例如,在一个C语言程序中出现 int i 35; /定义整型数组i float i42; /定义实型数组i,重定义冲突 int i 35; /定义整型数组i,重定义冲突 编译过程首先在符号表中记录了标识符i的属性是35个整型元素的数组,而后在分析第二、第三这两个定义说明时编译系统可通过符号表检查出标识符i的二次重定义冲突错误。本例还可以看到不论在后二句中i的其它属性与前一句是否完全相同,只要标识符名重定义,就将产生重定义冲突的语义错误。,在目标代码生成阶段,当对符号名进行地址分配时,符号表是
3、地址分配的依据。, 作为目标代码生成阶段地址分配的依据,一张符号表的的组成:包括两项,即名字栏和信息栏。 信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏。主栏的内容称为关键字(key word)。,在整个编译期间,对于符号表的操作大致可归纳为五类: 对给定名字,查询名字是否已在表中; 往表中填入一个新的名字; 对给定名字,访问它的某些信息; 对给定名字,填写或更新它的某些信息; 删除一个或一组无用的项。 上述五个方面只是一些基本的共同操作。,符号表的主要属性(信息),几种通常都是需要的。 1 名字 2 类型 3 存储类别 4 作用域及可视性 5 存储分配信息 6 其
4、它属性 () 数组内情向量 () 记录结构型的成员信息 () 函数及过程的形参,9.2符号的主要属性及作用, 符号名 符号表中设置一个符号名域,存放该标识符,该域通常就是符号表的关键字域。, 符号的类型 标识符中除过程标识符之外,函数和变量标识符都具有数据类型(data type)属性。对于函数的数据类型指的是该函数值的数据类型。基本数据类型有整型、实型、字符型、逻辑型(布尔型)及位组型等,符号的类型属性是在该符号的定义时得到。变量符号的类型属性决定了该变量的数据在存储空间的存储格式,还决定了在该变量上可以施加的运算操作。, 符号的存储类别 大多数语言对变量的存储类别定义采用二种方式。 一种是
5、用关键字指定: 例如在C语言中用Static定义是属于文件的静态存储变量或属于函数内部的静态存储变量,用regist定义使用寄存器存储的变量。 另一种方式是根据变量说明在程序中的位置来决定: 例如在C语言中,在函数体外缺省存储类关键字所定义的变量是外部变量,即程序的公共存储变量,而在函数体内缺省存储类关键字所定义的变量是内部变量,即属于该函数所独有的私有存储变量, 符号的作用域及可视性 一个符号变量在程序中起作用的范围,称谓它的作用域。一般来说,定义该符号的位置及存储类关键字决定了该符号的作用域。C语言中一个外部变量的作用域是整个程序,因此一个外部变量符号的定义在整个程序中只能出现一次。,一般
6、来说一个变量的作用域就是该变量可以出现的场合,这就是变量可视性的作用域规则。但是变量可视性不仅仅取决于它的作用域,还有两种情况影响到一个变量的可视性。, 函数的形式参数:影响变量可视性的举例 int a; / 外部定义的整型变量a int func(a,b) float a; / 函数内部定义的局部整型变量a, 屏闭了外部定义的整型变量a int b; a / 引用的是函数内部定义(此处是形参)的局部整型变量a 函数的形式参数可以和该函数外层定义的变量(包括外部变量)重名,这时两个重名的变量其类型定义可以是完全不同的。, 分程序(或复合语句)结构: 影响变量可视性的举例 int a; / 第一
7、层头,定义的局部整型变量a char a; / 第二层头,定义的局部字符型变量a / 第三层头 float a; / 第四层头,定义的局部实型变量a / 第四层尾 a / 引用第二层定义的局部字符型变量a / 第三层尾 / 第二层尾 / 第一层尾 图中第三层所引用的a,既不是第四层的float a;也不是第一层int a;而是第二层char a;也就可以说从第三层向外,看到的第一个定义a的变量定义即char a。 为确立符号的作用域和可视性。符号表属性中除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次。符号表中设置一个表达符号所在层次的属性域,存放该符号的定义层次。一般来说,
8、若把外部变量视为0层的话,则函数内部作为第1层,依次向内嵌套定义的分程序分别为2,3,层。, 符号变量的存储分配信息 通常一个编译程序有两类存储区,即静态存储区和动态存储区; 静态存储区 该存储区单元经定义分配后成为静态单元,即在整个语言程序运行过程中是不可改变的。作静态分配的符号变量是具有整个程序运行过程的生命周期。因此编译程序可以设置一个固定的空间作为静态存储区。 但由于不同的静态变量具有不同的可视性,编译程序也可以设置几个不同的固定空间作为静态区。根据变量存储类别及作用域规则,这类静态存储区通常又可分为公共静态区和若干个局部静态区。 一个语言程序中的公共变量或称外部变量是被指定分配到该公
9、共静态存储区中。例Pascal或C语言中的外部量就属于这类共静态存储区的分配。在公共静态区中的变量具有的生命周期是该程序运行的全过程,且其作用域亦是整个语言程序(注意:当它被同名局部量屏蔽时,该变量成为不可视的)。, 动态存储区 根据变量的局部定义和分程序结构,编译程序设置动态存储区来适应这些局部变量的生存和消亡。 局部动态变量的生存期是定义该变量的局部范围,即在该定义范围之外此变量已经没存在的必要。及时撤销时这些单元的分配可以回收,从而提高程序运行时的空间效率。,符号的其它属性 数组内情向量 内情向量包括数组类型,维数,各维的上、下界及数组首地址,这些属性信息是确定存储分配时数组所占空间的大
10、小和数组元素位置的依据。 记录结构型的成员信息 一个记录结构型的变量,在存储分配时所占空间大小要由它的全体组成成员来确定,另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。 函数及过程的形参 每个函数或过程的形参个数、形参的排列次序及每个形参的类型,都体现了调用该函数或过程时的属性,它们都应该反映在符号表的函数或过程标识符的项中。,9.3 符号表的组织,总体组织和表项属性信息组织 (P197198页的图) 第一种: 把属性种类完全相同的那些符号组织在一起,构造出表项是分别为等长的多个符号表 第二种: 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表 第三种
11、折衷方式是根据符号属性相似程度分类组织成若干张表,每张表中记录的符号都有比较多的相同属性。,9.3.1 符号表的总体组织,编译程序按名字的不同种属分别使用许多符号表,如常数表、变量名表、过程名表等等。,9.3.2 符号表项的排列,符号表作为一个多元组,表中元组的排列组织是构造符号表的重要成分。在编译程序的整个工作过程中,符号表被频繁地用来建立表项,找查表项,填充和引用表项的属性。因此表项的排列组织对该系统运行的效率起着十分重要的作用。在编译程序中,符号表项的组织传统上采用三种构造方法。即线性法,二分法及散列法。, 线性组织 这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录。,例如有一程
12、序中出现符号的情况如下: a /第一次出现a的地方 b /第一次出现b的地方 a /第二次出现a的地方 d /第一次出现d的地方 c /第一次出现c的地方 b /第二次出现b的地方 则符号表中表项排列将如图所示: 其中h表示该符号表之表头,是表的开始位置,p表示该符号表的表项是符号表当前的结束位置。, 排序组织及二分法 语言中的每一个符号,排序组织的符号表,就是在符号表中的表项按其符号的字符代码串(可以看成一个整数值)的值的大小从大到小(或从小到大)排列的。对上述例子中的符号出现情况按排序组织得到的符号表将如图所示:,编译扫描的次序是a,b,d,c。由于c代码小于d代码,因此c应在d表项之前。
13、关于排序表的表项建立及符号查找,通常采用“二分法“。, 散列组织 一个符号在散列表中的位置,是由对该符号(即字符代码串)进行某种函数操作(通常称为“杂凑函数“)所得到的函数值来确定的。所得到的函数值与该表项在表中位置的对应关系,是通过对函数值的“求整“以及相对于表长的“求余“得到的。符号表的散列组织相对来说具有较高的运行效率,因而绝大多数编译程序中的符号表采用散列组织。,但是经过杂凑运算后,就有可能得到相同的杂凑值,这种不同符号散列到同一表项位置的现象,我们称它为散列冲突。大多数编译程序中,解决冲突采用的多次散列方法如下。从冲突点位置向下寻找空表项,找到的第一个空表项即为发生冲突的符号所散列的
14、位置。如若一直到表底,没有找到空表项,则循环从表头开始寻找空表项,如若一直到冲突点仍设有空表项,则说明该语言程序中的符号太多,符号表已不能容纳全部符号登入,这时编译程序将发出符号表溢出的系统出错消息。,9.3.3 关键字域的组织,符号表的关键字域(段)就是符号名称 等长关键字域(段)符号表 不等长关键字段符号表-采用关键字池的索引结构。,为使得符号表中存放标识符的关键字段等长,可设置关键字段为标识符的最大长度。譬如上述C语言的关键字段长度可以是32个,图示如下。,等长关键字域(段)符号表,由于程序中的标识符长短不一,有时可能差别很大,用等长结构会产生溢出或冗余。,不等长关键字段符号表-采用关键
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 符号
链接地址:https://www.31doc.com/p-2596927.html