编译第八章.ppt

1、第八章 符号表 8.1 符号表的组织与作用 8.2 整理与查找 8.3 名字的作用范围 8.4 符号表的内容 复习题,8.1 符号表的组织与作用 一、符号表的作用 在编译程序工作的过程中，需要不断收集、记录、查证和使用源程序中的一些语法符号(简称为符号)的类型和特征等相关信息。为方便起见，一般的做法是让编译程序在其工作过程中建立并保存一批表格，如常数表、变量名表、数组内情向量表、过程或子程序名表及标号表等，将它们统称为符号表或名字表。,语义分析时，符号表中的信息可用于语义检查；代码优化时，编译程序利用符号表提供的信息选出恰当的代码进行优化；目标代码生成时，编译程序将依据符号表中的符号名来分配目

2、标地址。可见，几乎在编译程序工作的全过程中，都需要对符号表进行频繁地访问(查表或填表)，其耗费的时间在整个编译过程中占有很大的比例。因此，合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。,二、符号表的组成 一张符号表的每一项（入口）包含两大栏（区段，字域），即名字栏和信息栏。 表格的形式： 第1项（入口1） 第n项（入口n）,三、符号表的使用（基本操作） 1对给定名字，查询此名是否已在表中（查表） 2填入新名（填表） 3对给定名字，访问它的信息（访表信息） 4对给定名字，往表中填写或更新它的某些信息 （更新） 5删除一个或一组无用的项（删除）,四、符号表的组织方式 由

3、于处理对象的作用和作用域可以有多种，所以符号表也有多种组织方式。按照处理对象的特点，符号表的组织方式一般可分为直接方式和间接方式。 1.直接方式 直接方式是指在符号表中直接填入源程序中定义的标识符及相关信息(如图8-1所示)。在图81所示的符号表中，Name(名字)栏的长度是固定的，这种栏目长度固定的表格易于组织、填写或查找，因而是最简单的一种符号表组织方式， 它适合于规定标识符长度的程序语言。,图8-1 直接组织方式的符号表,然而，并不是所有高级语言都规定标识符的长度，如果对标识符长度不加限制，则上述定长方式必须按最大长度来定长，这显然浪费存储空间。因此，对不定长标识符一般采用间接方式来组织

4、符号表。,2.间接方式 间接方式是指单独设置一个字符串数组来存放所有的标识符，并在符号表的名字栏中设置两项内容：一是指针，用来指向标识符在数组中的起始位置；二是一整数值，用来表示该标识符的长度。图82给出了符号表的间接组织方式。,图8-2 间接组织方式的符号表,另一种组织方式是按标识符的种属，如简单变量、数组、过程等分别建立不同的符号表，如简单变量名表、数组名表、过程名表等。例如，下面的函数： int f(int a,int b) int c; if(ab) c=1; else c=0; return c; ,图8-3 按标识符种属组织的各种符号表 (a) 简单变量名表；(b) 常数表；(c)

5、 函数入口名表,根据符号表名字栏的组织特点，符号表信息栏的组织方式也分为两类：固定信息内容和仅记录信息存放地址。 如果名字栏中的标识符按种属分类，则因同类标识符其基本特征一致，故可将这些信息一一记录在信息栏中。 如果符号表的名字不分种属，则由于不同种属的标识符其特征不一致，也即它们所需存储的信息不一致，因而不容易确定一个固定长度的空间来统一安排。这时，可在符号表外另设一组存储空间，并在符号表信息栏中放一指针来指向这个存储空间始址。,例如，对数组标识符需要存储有关数组维数，每维上、下界值，数组类型及数组存放的起始地址等信息。如果将信息与名字一起全部放在符号表中，则因维数不同而使记录该信息的空间大

6、小不易确定，因此，通常给它们另外安排一个内情向量表来记录数组的全部信息，同时在符号表的信息栏设置一指针指向内情向量的入口地址(见图8-4)。此外，对像函数名、过程名等含有较多信息且不容易规范信息长度的名字都可以采取这种办法。,图8-4 记录数组内情向量的符号表,8.2 整理与查找 符号表的三种构造法和处理法： 线性表 办法最简单，效率低 二叉树 效率高，实现困难 杂 凑 效率最高，实现复杂,消耗额外存储 空间,一、线性表 1构造 按关键字出现顺序填写各个项， “先来者先 填” 2查找 从第一项开始顺序查找，若一直查找到AVAILBLE项还未找到，说明该名字不在表中,AVAILBAE,3提高线性

7、表查找效率（自适应线性表） 给每项附设一个指示器，这些指示器把所有的项按“最新最近”访问原则连接成一条链，使得在任何时候，这条链的第一个元素所指的项是那个最新最近被查询过的项，第二个元素所指的项是那个次新次近被查询过的项如此等等,二、对折查找与二叉树 1.整理 为了提高查表的速度，可以在造表的同时把表格中的项按名字的“大小”顺序整理排列。 2.对折查找（折半查找） n项 n/2 +1 小 中 大 顺序化整理极费时间,3.符号表组织成二叉树 令每项是一个结点，每个结点附设两个指示器栏，分别为LEFT，RIGHT。每个结点主栏内码值被看成是代表该结点的值，任何结点P右枝所有结点值均应小于结点P的值

8、，而左枝任何结点值均应大于结点P的值。 4.二叉树形成过程 令第一个碰到的名字作为“根“结点，它的左，右指示器均置为null.当要加入新结点时，首先把它和根结点值作比较，小者放在右枝上，大者放在左枝上，如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较，重复直至把新结点插入使它成为二叉树的一个端末结点（叶子）为止。,三、杂凑技术 填表快，查表慢 1.方法 构造一个地址函数H，对任何名字SYM，H（SYM）取值于0N-1，不论对SYM查表或填表，都希望能从 H（SYM）获得它在表中的位置。 2.Hash函数构造方法 （1） 直接定址法 取关键字或关键字的某个线性函数值为Hash地址 H

9、(key)=key或H(key)=akey+b （2）数字分析法 若关键字是以r为基的数，且Hash表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成Hash地址,(3)折迭法 将关键字分割成位数相同的几部分，然后取这几部分的迭加和作为Hash地址 (4)除留余数法 取关键字被某个不大于哈希表表长m的数P除后所得余数为 Hash地址 H(key) = key MOD P (Pm) (5)平方取中法 取关键字平方的中间几位为Hash地址 (6)随机数法 选择一个随机函数，取关键字的随机函数值为它的Hash地址,3处理冲突的方法 （1）开放定址法 Hi=(H(key)+di) MOD

10、m i=1,2,.,k(km-1) （2）再哈希法 Hi=R Hi(key) i=1,2,k （3）链地址法 将所有关键字为同义词的记录存储在同一线性链中 （4）建立一个公共溢出区,8.3名字的作用范围 最近嵌套作用域原则： 一个名字的作用域是那个包含了这个名字的说明的最小过程（函数）。,8.4符号表的内容 对于常见的程序设计语言而言，其变量名及过程名登记项的信息栏通常包含如下信息： (1) 变量名： 种属(简单变量、数组、记录结构等)； 类型(整型、实型、双精度实型、逻辑型、字符串型、标号或指针等)；, 所分配的数据区地址(一般为相对地址)； 若为数组，应填写其内情向量并给出内情向量的首址； 若为记录结构，则应把该登记项与其各分量(即域)按某种方式连接起来； 是否为形式参数，若是则应记录其类型； 定义性出现或引用性出现标志(指标号)； 是否对该变量进行过