第7章 符号表

1、v 解释符号表的作用解释符号表的作用v 阐明符号表的内容阐明符号表的内容v 介绍符号表的基本操作介绍符号表的基本操作v 介绍符号表的组织结构介绍符号表的组织结构v 说明符号表的构造与查找方法说明符号表的构造与查找方法v 解释名字的作用范围解释名字的作用范围7.1 7.1 符号表的作用与内容符号表的作用与内容7.2 7.2 符号表的组织与管理符号表的组织与管理7.3 7.3 名字的作用范围名字的作用范围7.4 7.4 本章小结本章小结符号表的作用符号表的作用 1符号表的内容与操作符号表的内容与操作 2 在编译程序工作的过程中，需要不断收集、记录、查证和使用源程序中的一些语法符号（简称为符号）的类

2、型和特征等相关信息。为方便起见，一般的做法是让编译程序在其工作过程中建立并保存一批表格，如常数表、变量名表、数组内情向量表、过程或子程序名表及标号表等，将它们统称为符号表或名字表。 语义分析时，符号表中的信息可用于语义检查；代码优化时，编译程序利用符号表提供的信息选出恰当的代码进行优化；目标代码生成时，编译程序将依据符号表中的符号名来分配目标地址。可见，几乎在编译程序工作的全过程中，都需要对符号表进行频繁地访问(查表或填表)，其耗费的时间在整个编译过程中占有很大的比例。因此，合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。（1）符号表的组成一张符号表的每一项（入口）包

3、含两大栏（区段，字域），即和。第1项（入口1）第2项（入口2）第n 项（入口n）（2）符号表的基本操作 对给定名字，查询此名是否已在表中（对给定名字，查询此名是否已在表中（） 填入新名（填入新名（） 对给定名字，访问它的信息（对给定名字，访问它的信息（） 对给定名字，往表中填写或更新它的某些信息（对给定名字，往表中填写或更新它的某些信息（） 删除一个或一组无用的项（删除一个或一组无用的项（）返回符号表的组织结构符号表的组织结构 1符号表的构造与查找符号表的构造与查找 2（1）名字栏组织方式按照处理对象的特点，符号表的组织方式一般可分为和。也。直接方式 直接方式是指在符号表中直接填入源程序中定义

4、的标识符及相关信息。在下图所示的符号表中，名字栏的长度是固定的，这种栏目长度固定的表格易于组织、填写或查找，因而是最简单的一种符号表组织方式， 它适合于规定标识符长度的程序语言。 间接方式 用一个独立的字符串数组，把所有标识符都连续存放在其中。在符号表的主栏放一个指示器和一个整数，或在主栏仅放一个指示器，在标识符前放一个整数。指示器指出标识将在字符串数组中的位置，整数代表此标识符的长度。 按标识符的种属建立不同的符号表 如对简单变量、数组、过程等分别建立简单变量名表、数组名表、过程名表等。例如，下面的函数： int f(int a,int b) int c; if(ab) c=1; else

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

6、起全部放在符号表中，则因维数不同而使记录该信息的空间大小不易确定，因此，通常给它们另外安排一个来记录数组的全部信息，同时在符号表的信息栏设置一指针指向内情向量的入口地址(见图8-4)。此外，对像函数名、过程名等含有较多信息且不容易规范信息长度的名字都可以采取这种办法。符号表主要有三种构造和处理方式：、和。（1）线性表构造 按关键字出现顺序填写各个项， “先来者先填”。查找 从第一项开始顺序查找，若一直查找到AVAILBLE项还未找到，说明该名字不在表中。对于一张含n项的线性表来说，欲从中查找一项，平均来说需要做 n/2 次的比较。提高线性表查找效率（自适应线性表）给每项附设一个指示器，这些指示

7、器把所有的项按“最新最近”访问原则连接成一条链，使得在任何时候，这条链的第一个元素所指的项是那个最新最近被查询过的项，第二个元素所指的项是那个次新次近被查询过的项如此等等，每次查表时都按这条链所指的顺序，一旦查到之后就即时改造这条链，使得链头指向刚才查到的那个项。每当填入新项时，总让链头指向这个最新项。含有这种链的线性表叫做。（2）对折查找与二叉树整理为了提高查表的速度，可以在造表的同时把表格中的项按名字的“大小”顺序整理排列。对折查找（折半查找）对于这种经顺序化整理了的表格的查找可用对折法。假定表中已含有n项，要查找某项SYM时，首先把SYM和中项（即第 项）作比较： 若相等，则宣布查到。若

8、相等，则宣布查到。 若若SYM小于中项，则继续在小于中项，则继续在 的各项中去查找。的各项中去查找。 若若SYM大于中项，则就到大于中项，则就到 的各项中去查找。的各项中去查找。使用这种查找法每查找一项最多只需作 次比较12n2n1n22nNlog12符号表组织成二叉树令每项是一个结点，每个结点附设两个指示器栏，分别为LEFT，RIGHT。每个结点主栏内码值被看成是代表该结点的值，任何结点P右枝所有结点值均应小于结点P的值，而左枝任何结点值均应大于结点P的值。二叉树形成过程令第一个碰到的名字作为“根“结点，它的左，右指示器均置为null.当要加入新结点时，首先把它和根结点值作比较，小者放在右枝

9、上，大者放在左枝上，如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较，重复直至把新结点插入使它成为二叉树的一个端末结点（叶子）为止。（3）杂凑技术方法构造一个地址函数H，对任何名字SYM，H（SYM）取值于0N-1，不论对SYM查表或填表，都希望能从H（SYM）获得它在表中的位置。Hash函数构造方法u直接定址法直接定址法取关键字或关键字的某个线性函数值为Hash地址。H(key)=key或H(key)=akey+bu数字分析法数字分析法若关键字是以r为基的数，且Hash表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成Hash地址。u折迭法折迭法将关键字分割成位数相同

10、的几部分，然后取这几部分的迭加和作为Hash地址。u除留余数法除留余数法取关键字被某个不大于哈希表表长m的数P除后所得余数为Hash地址。 H(key) = key MOD P (Pm)u平方取中法平方取中法 取关键字平方的中间几位为Hash地址。u随机数法随机数法选择一个随机函数，取关键字的随机函数值为它的Hash地址。处理冲突的方法u开放定址法开放定址法Hi=(H(key)+di) MOD m i=1,2,.,k(km-1)u再哈希法再哈希法 Hi=R Hi(key) i=1,2,ku链地址法链地址法 将所有关键字为同义词的记录存储在同一线性链中。u建立一个公共溢出区建立一个公共溢出区返回

11、（1）名字的作用域分析程序语言中，名字往往有一个确定的作用范围，一般是和它所处的那个过程（它在这个过程中被说明了的）相联系的。这意味着，在一个程序里，同一个标识符在不同的地方可能被说明为标识不同的对象，也就是说，同一个标识符，具有不同的性质，要求分配不同的存储空间。于是便产生了这样的问题，如何组织符号表，使得同一个标识符在不同的作用域中能得到正确地引用，而不会产生混乱？这就是名字的作用域分析要解决的问题。 （2）编程语言中的作用域规则使用前说明（declaration before use）在C，Java和Pascal等众多程序设计语言中广泛使用，要求程序中出现的名字要在对它的任何引用之前进行

12、说明。使用前说明允许符号表在分析期间建立，当程序中遇到对名字的引用时进行查找，如果查找失败，意味着未经说明就直接使用了，这是一种说明错误，编译器给出相应的出错消息。因此可以看出，使用前说明有助于实现一遍编译。 （2）编程语言中的作用域规则最近嵌套规则（most closely nest rule）一种语言是块结构的，如果它允许在块的内部嵌入块，并且一个块中说明的作用域限制在本块以及包含在本块的其它块中，服从最近嵌套规则；为同一个名字可以给定几个不同的说明，被引用的说明是最接近引用的那个嵌套块。 （3）实现最近嵌套作用域规则的办法对每个过程指定一个惟一的编号，即过程的顺序号，以便跟踪过程里的局部

13、名字。一个过程的编号（层次）作为本过程中说明的全部局部量的组成部分，即编号被看成是名字的一个组成部分。于是，在符号表中表示局部名字用一个二元组：（名字，过程编号）。这种办法意味着我们把整个符号表按不同的过程逻辑地划分为相应的不同段落。在查找每个名字时，先查对过程编号，确定所属的表区段落，然后，再从此段落中查对标识符。也就是说，对一个名字查找符号表是指：只有当表项中的名字其字符逐个匹配，并且该记录相关的编号和当前所处理的过程的编号匹配时，才能确定查找成功。 （3）实现最近嵌套作用域规则的办法下面以C语言中的符号表的组织为例，以说明块结构语言的名字作用域分析。 （3）实现最近嵌套作用域规则的办法以散列组织符号表：处理完过程f的声明之后、进入复合语句A之前 （3）实现最近嵌套作用域规则的办法处理完f体内的复合语句B之后： （3）实现最