第7章符号表

编译原理第7章符号表安庆师范学院计算机与信息学院本章目标解释符号表的作用阐明符号表的内容介绍符号表的基本操作介绍符号表的组织结构说明符号表的构造与查找方法解释名字的作用范围教学内容7.1符号表的作用与内容7.2符号表的组织与管理7.3名字的作用范围7.4本章小结7.1符号表的作用与内容符号表的作用1符号表的内容与操作21、符号表的作用在编译程序工作的过程中，需要不断收集、记录、查证和使用源程序中的一些语法符号（简称为符号）的类型和特征等相关信息。为方便起见，一般的做法是让编译程序在其工作过程中建立并保存一批表格，如常数表、变量名表、数组内情向量表、过程或子程序名表及标号表等，将它们统称为符号表或名字表。语义分析时，符号表中的信息可用于语义检查；代码优化时，编译程序利用符号表提供的信息选出恰当的代码进行优化；目标代码生成时，编译程序将依据符号表中的符号名来分配目标地址。可见，几乎在编译程序工作的全过程中，都需要对符号表进行频繁地访问(查表或填表)，其耗费的时间在整个编译过程中占有很大的比例。因此，合理地组织符号表并选择好的查表、填表方法是提高编译程序工作效率的有效办法。返回2、符号表的内容与操作（1）符号表的组成一张符号表的每一项（入口）包含两大栏（区段，字域），即名字栏和信息栏。名字（NAME）信息（INFORMATION）…………第1项（入口1）第2项（入口2）第n项（入口n）……2、符号表的内容与操作（2）符号表的基本操作①对给定名字，查询此名是否已在表中（查表）②填入新名（填表）③对给定名字，访问它的信息（访表信息）④对给定名字，往表中填写或更新它的某些信息（更新）⑤删除一个或一组无用的项（删除）返回7.2符号表的组织与管理符号表的组织结构1符号表的构造与查找21、符号表的组织结构（1）名字栏组织方式按照处理对象的特点，符号表的组织方式一般可分为直接方式和间接方式。也按标识符的种属分别建立不同的符号表。①直接方式直接方式是指在符号表中直接填入源程序中定义的标识符及相关信息。在下图所示的符号表中，名字栏的长度是固定的，这种栏目长度固定的表格易于组织、填写或查找，因而是最简单的一种符号表组织方式，它适合于规定标识符长度的程序语言。名字信息Sentence…Data………1、符号表的组织结构②间接方式用一个独立的字符串数组，把所有标识符都连续存放在其中。在符号表的主栏放一个指示器和一个整数，或在主栏仅放一个指示器，在标识符前放一个整数。指示器指出标识将在字符串数组中的位置，整数代表此标识符的长度。名字信息·8·4sentencedata符号表名字信息··sentencedata符号表841、符号表的组织结构③按标识符的种属建立不同的符号表如对简单变量、数组、过程等分别建立简单变量名表、数组名表、过程名表等。例如，下面的函数：intf(inta,intb){intc;if(ab)c=1;elsec=0;returnc;}NAMEINFORMATIONabc整型，变量，形参整型，变量，形参整型，变量VALUE01NAMEINFORMATIONf二目子程序，入口地址（a）简单变量名表（b）常数表（c）函数入口名表1、符号表的组织结构（2）信息栏组织方式根据符号表名字栏的组织特点，符号表信息栏的组织方式也分为两类：固定信息内容和仅记录信息存放地址。如果名字栏中的标识符按种属分类，则因同类标识符其基本特征一致，故可将这些信息一一记录在信息栏中。如果符号表的名字不分种属，则由于不同种属的标识符其特征不一致，也即它们所需存储的信息不一致，因而不容易确定一个固定长度的空间来统一安排。这时，可在符号表外另设一组存储空间，并在符号表信息栏中放一指针来指向这个存储空间始址。1、符号表的组织结构例如，对数组标识符需要存储有关数组维数，每维上、下界值，数组类型及数组存放的起始地址等信息。如果将信息与名字一起全部放在符号表中，则因维数不同而使记录该信息的空间大小不易确定，因此，通常给它们另外安排一个内情向量表来记录数组的全部信息，同时在符号表的信息栏设置一指针指向内情向量的入口地址(见图8-4)。此外，对像函数名、过程名等含有较多信息且不容易规范信息长度的名字都可以采取这种办法。符号表名字信息种属地址数组···……·内情向量表维数数组首地址界差界差上界上界下界下界1dnd1lnlnu1u………返回2、符号表的构造与查找符号表主要有三种构造和处理方式：线性查找、二叉树和杂凑技术。（1）线性表①构造按关键字出现顺序填写各个项，“先来者先填”。②查找从第一项开始顺序查找，若一直查找到AVAILBLE项还未找到，说明该名字不在表中。对于一张含n项的线性表来说，欲从中查找一项，平均来说需要做n/2次的比较。NAMEINFORMATIONdatalinkpointerx1234AVAILABLE…………项数线性符号表AVAILABLE总是指向空白区的首地址2、符号表的构造与查找③提高线性表查找效率（自适应线性表）给每项附设一个指示器，这些指示器把所有的项按“最新最近”访问原则连接成一条链，使得在任何时候，这条链的第一个元素所指的项是那个最新最近被查询过的项，第二个元素所指的项是那个次新次近被查询过的项如此等等，每次查表时都按这条链所指的顺序，一旦查到之后就即时改造这条链，使得链头指向刚才查到的那个项。每当填入新项时，总让链头指向这个最新项。含有这种链的线性表叫做自适应线性表。（2）对折查找与二叉树①整理为了提高查表的速度，可以在造表的同时把表格中的项按名字的“大小”顺序整理排列。2、符号表的构造与查找②对折查找（折半查找）对于这种经顺序化整理了的表格的查找可用对折法。假定表中已含有n项，要查找某项SYM时，首先把SYM和中项（即第项）作比较：若相等，则宣布查到。若SYM小于中项，则继续在的各项中去查找。若SYM大于中项，则就到的各项中去查找。使用这种查找法每查找一项最多只需作次比较12n2n~1n~22nNlog122、符号表的构造与查找③符号表组织成二叉树令每项是一个结点，每个结点附设两个指示器栏，分别为LEFT，RIGHT。每个结点主栏内码值被看成是代表该结点的值，任何结点P右枝所有结点值均应小于结点P的值，而左枝任何结点值均应大于结点P的值。④二叉树形成过程令第一个碰到的名字作为“根“结点，它的左，右指示器均置为null.当要加入新结点时，首先把它和根结点值作比较，小者放在右枝上，大者放在左枝上，如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较，重复直至把新结点插入使它成为二叉树的一个端末结点（叶子）为止。pointer··NULLNULLdataNULLxlinkNULLNULL·2、符号表的构造与查找（3）杂凑技术①方法构造一个地址函数H，对任何名字SYM，H（SYM）取值于0~N-1，不论对SYM查表或填表，都希望能从H（SYM）获得它在表中的位置。②Hash函数构造方法直接定址法取关键字或关键字的某个线性函数值为Hash地址。H(key)=key或H(key)=a·key+b数字分析法若关键字是以r为基的数，且Hash表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成Hash地址。2、符号表的构造与查找折迭法将关键字分割成位数相同的几部分，然后取这几部分的迭加和作为Hash地址。除留余数法取关键字被某个不大于哈希表表长m的数P除后所得余数为Hash地址。H(key)=keyMODP(P≤m)平方取中法取关键字平方的中间几位为Hash地址。随机数法选择一个随机函数，取关键字的随机函数值为它的Hash地址。2、符号表的构造与查找③处理冲突的方法开放定址法Hi=(H(key)+di)MODmi=1,2,….,k(k≤m-1)再哈希法Hi=RHi(key)i=1,2,…,k链地址法将所有关键字为同义词的记录存储在同一线性链中。建立一个公共溢出区返回7.3名字的作用范围（1）名字的作用域分析程序语言中，名字往往有一个确定的作用范围，一般是和它所处的那个过程（它在这个过程中被说明了的）相联系的。这意味着，在一个程序里，同一个标识符在不同的地方可能被说明为标识不同的对象，也就是说，同一个标识符，具有不同的性质，要求分配不同的存储空间。于是便产生了这样的问题，如何组织符号表，使得同一个标识符在不同的作用域中能得到正确地引用，而不会产生混乱？这就是名字的作用域分析要解决的问题。7.3名字的作用范围（2）编程语言中的作用域规则①使用前说明（declarationbeforeuse）在C，Java和Pascal等众多程序设计语言中广泛使用，要求程序中出现的名字要在对它的任何引用之前进行说明。使用前说明允许符号表在分析期间建立，当程序中遇到对名字的引用时进行查找，如果查找失败，意味着未经说明就直接使用了，这是一种说明错误，编译器给出相应的出错消息。因此可以看出，使用前说明有助于实现一遍编译。7.3名字的作用范围（2）编程语言中的作用域规则②最近嵌套规则（mostcloselynestrule）一种语言是块结构的，如果它允许在块的内部嵌入块，并且一个块中说明的作用域限制在本块以及包含在本块的其它块中，服从最近嵌套规则；为同一个名字可以给定几个不同的说明，被引用的说明是最接近引用的那个嵌套块。7.3名字的作用范围（3）实现最近嵌套作用域规则的办法对每个过程指定一个惟一的编号，即过程的顺序号，以便跟踪过程里的局部名字。一个过程的编号（层次）作为本过程中说明的全部局部量的组成部分，即编号被看成是名字的一个组成部分。于是，在符号表中表示局部名字用一个二元组：（名字，过程编号）。这种办法意味着我们把整个符号表按不同的过程逻辑地划分为相应的不同段落。在查找每个名字时，先查对过程编号，确定所属的表区段落，然后，再从此段落中查对标识符。也就是说，对一个名字查找符号表是指：只有当表项中的名字其字符逐个匹配，并且该记录相关的编号和当前所处理的过程的编号匹配时，才能确定查找成功。7.3名字的作用范围（3）实现最近嵌套作用域规则的办法下面以C语言中的符号表的组织为例，以说明块结构语言的名字作用域分析。inti,j;intf(intsize){chari,temp;…A:{doublej;…}…B:{char*j;…}}1B2B3B4B5B7.3名字的作用范围（3）实现最近嵌套作用域规则的办法以散列组织符号表：①处理完过程f的声明之后、进入复合语句A之前i(char)i(int)size(int)j(int)temp(char)f(function)桶同义词表7.3名字的作用范围（3）实现最近嵌套作用域规则的办法②处理完f体内的复合语句B之后：i(char)i(int)size(int)j(int)temp(char)f(function)桶同义词表j(char*)7.3名字的作用范围（3）实现最近嵌套作用域规则的办法③退出函数f以后：i(char)j(int)f(function)桶同义词表7.3名字的作用范围（3）实现最近嵌套作用域规则的办法还有其它的方式可以实现嵌套的作用域。其中的一种策略是对每个作用域建立一张新的符号表，把它们按照作用域自里向外连接起来，这样，查找操作如果不能在当前表中找到一个名字，就自动在外面包含它的表中继续查找。当退出一个作用域时，删除操作就非常简单，只需删除对应作用域的整个表。i(char)j(int)f(function)i(char)size(int)temp(char)j(char*)返回7.4本章小结（1）知识主线符号表的主要内容、组织结构以及构造方法名字的作用域分析7.4本章小结（2）主要内容与基本要求符号表的作用（理解）符号表的主要内容和组织结构（掌握）符号表的基本操作（理解）符号表的构造与查找方法（理解）名字的作用域分析（了解）结束