符号表管理技术.ppt

第7章 符号表管理技术,在编译的各个阶段经常要收集、使用出现在源程序中的各种信息，为了方便，通常把这些信息用一些表格进行记录、存储和管理，如常量表、数组信息表等等，这些表统称为符号表。符号表主要保存各类标识符的属性，它在翻译过程中有两个方面的重要作用 1）检查语义的正确性2)辅助生成代码 达到这两个目的的途径是通过插入和检索符号表中记录的标识符属性来实现的。这些属性(如名字、类型、维数等)在声明语句中可直接找到，有些可根据程序中标识符出现的上下文间接地获得。第三章介绍词法分析时提到，从字符串源程序中分离出标识符后，首先查保留字表，如果没有，则确认为标识符，词法分析输出标识符符号，同时还要记住该标识符符号的属性值。在编译时，源程序中每出现一次标识符，就要与符号表打一次交道，主要工作是查表和存取操作，因此，与符号表的交互占据了大量的编译时间。所以，如何有效地操作符号表直接影响编译的效率。,7.1 何时建立和访问符号表,符号表可在词法分析时创建，也可在语义分析时创建。有的编译程序中，符号表在词法分析遍内创建，符号表此时只含有标识符的名字，其它属性要在语义分析阶段填入，而变量在符号表中的位置信息将作为标识符符号的属性出现，构成词法扫描器所产生的单词符号的一部分；语法分析阶段只检查源程序语法的正确性，一般不使用符号表；语义分析程序对该编码形式进行语义正确性分析，遇到声明语句时会填入有关标识符的属性。在符号表中记录的标识符的属性信息会在代码生成阶段用于产生目标代码的指令序列。因此，直到语义分析和代码生成阶段，许多与变量有关的属性才能够相继填入符号表。有的编译程序，只在语义分析时才创建符号表，这样，词法分析只输出标识符符号，而标识符名字作为标识符符号的属性输出。这样，在语义分析阶段根据标识符的属性创建符号表记录，并同时填入其它的属性信息。总之，如果在词法分析阶段创建符号表，只能在符号表中将标识符的名字填入符号表，而其他属性则要在语义分析和代码生成阶段填入。如果在语义分析阶段创建符号表，那么与符号表打交道的就仅局限于语义分析和代码生成部分。,7.2 符号表的组织和内容,符号表的管理程序应该具有快速查找、快速删除、易于使用、易于维护的特点。符号表具体包含那些内容，属性的种类和多少在一定程度上取决于程序设计语言的性质。同样，符号表的组织方式还要根据内存和存取速度的限制做相应的改变。符号表基本上都是由一些表项组成的二维表格，每个表项可分为两部分：第一部分是名字域，用来存放符号的名字；第二部分是属性域，用来记录与该名字相对应的各种属性和特征。,变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域,表7.1 符号表示例,第7章 符号表管理技术,名字：名字必须常驻在表中，因为它是在语义分析和代码生成中识别一个具体标识符的依据。在符号表的组织中，一个要解决的重要问题是标识符长度的可变问题。对标识符名字的处理要考虑语言中对标识符长度的规定是定长还是不定长。根据标识符的定义特点，通常采用的存储方法有两种：.定长存贮方法，即为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中，特点是简单且存取速度快，缺点是空间利用率低，标识符长度不能超过名字域的宽度。.集中存贮方法，即开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。特点是存贮效率高，标识符无长度限制，但存取效率低。如图7.1所示。,ComputerX1FORM1,图7.1集中存贮方法符号表,第7章 符号表管理技术,目标地址：标识符主要作为变量名字。程序中每个变量都必须有一个相应的目标地址，该地址是为该变量分配的内存地址(可能是相对的)。当声明一个变量时，就要为该变量分配内存地址，并将其分配的地址填入符号表中。当该变量在程序的其它处被引用时，可以从符号表中查询该地址，并填入存取该变量值的目标代码中。对于采用静态存储分配的语言(如FIRTRAN)，分配的地址是按连续的顺序分配的。对于采用动态存储分配的语言，每个程序块内的变量连续分配，这是一个相对地址，运行时还要根据该程序块分配的数据区的起始地址和变量的相对地址计算出变量的绝对内存地址。如果标识符表示的是函数名或子程序名，则目标地址是该函数或子程序代码的开始地址。如果是数组名，则应为数组模板的起始地址。类型：不同数据类型的变量占据不同大小的内存空间，另外类型检查是语义分析的一项重要工作，所以符号表中要保存每个标识符的数据类型，以便分配内存和进行类型检查。维数及参数个数：这两个属性对类型检查都是重要的。在数组引用时，其维数应当与数组声明中所定义的维数一致，类型检查阶段必须对这种一致性进行检查，另外，维数也用于数组元素地址的计算。过程调用时，实参个数也必须与形参个数一致。实际上，在符号表组织中，把参数的个数看成它的维数是很方便的，因此可以将两个属性合并成一个，另外这种方法也是协调的，因为对这两种属性所做的类型检查是类似的。,第7章 符号表管理技术,（交叉引用表：是一个由编译程序提供的十分重要的程序设计辅助工具。该表包含前面已经讨论过的许多属性，加上声明该变量或首次引用该变量的语句行号以及所有引用该变量的语句行号。链域：列在符号表中的最后一个属性，通常称之为链域，其作用是为了便于产生按字母顺序排序的变量交叉引用表。如果编译程序不产生交叉引用表。则符号表中的链域以及语句的行号属性都可从表中删去。,原则上，一个编译程序使用一张符号表就够了，但是，在源程序中，由于不同种类的符号起着不同的作用，相应于各类符号所需记录的属性往往不同，因此，多数编译程序都是根据符号的不同种类，分别建立不同的符号表，如常数表、变量名表、数组信息表、过程信息表、保留字表、特殊符号表、标准函数名表等等，这样处理起来更方便一些。从编译系统建造符号表的过程来划分，符号表可分为静态表和动态表两大类：一是静态表，即在编译前就已经构造好了的符号表，如保留字表、标准函数名表等。二是动态表，即在编译过程中根据需要构造的符号表，如变量表、数组信息表、过程信息表等等。,7.3 符号表上的操作,在符号表上最常执行的操作是插入和查找，这些操作根据所编译的语言是否具有显示声明而稍有不同。,1、强类型语言所谓强类型语言，即指所有变量都必须显式说明。插入操作发生在变量声明时，即处理一个变量声明语句的时候。在进行插入操作前，首先要查符号表，以确定符号表中无该变量记录，即变量不是重复声明。如果符号表是有序表，则插入之前还要找到需插入变量的正确位置，以便将变量插入符号表的适当位置；如果符号表不是有序表，则可直接将变量附加在符号表尾部。查找符号表操作发生的次数很多。除了插入前要先查符号表外，每次变量引用时都要查找符号表。如果查到，那么查找出的信息将用于语义检查和代码生成，同时可根据变量的上下文对未声明(或预先声明的)变量的有关属性进行推测，发出错误或警告信息、或相应的改正信息；如果没有查到，说明存在变量没有声明就引用的错误，应报告相应的错误信息。,第7章 符号表管理技术,2、弱类型语言所谓弱类型语言，即允许对变量做隐式说明。插入和查询同时发生在每一次变量出现时，因为声明不是显式和强制的，所以任一变量引用都需处理成首次引用。因为无法知道此变量是否已经存在于符号表中，所以对变量的引用都需先查表，如存在，则直接获取变量的全部属性，否则进行插入操作，而且需要从上下文中推测出隐式变量的全部属性。例如，程序中首次出现a=5和x=3.14时，可根据常量5和3.14确定为a为整型变量、x为实型变量。,对于具有块程序结构的语言，允许不同块之间的变量同名，这就要求每个程序块都有一个符号子表，一个程序块内的所有变量属性保存在一个子表中，这就允许不同程序块使用相同的变量名，而在一个程序块内，变量则不允许同名。这种情况下，符号表是一个栈式结构，而在进入块程序和离开块程序时，需要两种附加操作，即定位和重定位(详见下一小节)。,7.4非块程序结构语言的符号表结构,所谓非块程序结构语言，是指用它编写的每一个可独立编译的程序是一个不包含子块的单一模块程序，该模块中声明的所有变量是属于整个模块的。非块程序结构语言的符号表有几种组织方式，其中比较简单的是无序表和有序表。,1、无序表无序符号表也称为线性表。构造一个符号表最简单的方法是变量的属性项按变量被声明的先后顺序填入表中。无序表插入和查找操作比较简单，但查找效率低。在编译过程中，当需要查找某个符号时，只能采用线性查找的方法，即从表的第一项开始，一项一项地顺序查找，直到找到需要的符号，否则要一直查到表尾。如果符号表内容较多，采用该方法查找效率很低。对于一个含有N项的符号表，查找其中某个符号的内容，平均要做N/2次比较。但如果符号表较小，采用无序表则非常合适。无序表的优点是结构简单、节省空间，添加及查找操作简单、易于实现。,7.4非块程序结构语言的符号表结构,2、有序表在编译过程中，由于查找符号表的次数远大于插入符号表的次数，所以如何提高符号表的查找效率直接影响编译的效率。有序符号表的表项是根据变量名按字母顺序存放的。因此，每次插入符号表前，首先要进行查表工作，以确定要插入的符号在符号表中的位置，然后将符号插入。这样难免会造成原有一些符号的移动，所以，这种符号表结构在插入符号时开销较大。对于有序表，最常用的查找技术是折半查找法。折半查找首先把变量名与符号表的中间记录比较，结果或是找到该变量名，或是指出下一步要在那半张表中进行查找，重复此过程，直到找到该变量名或确定该变量名不在表中为止。,7.4非块程序结构语言的符号表结构,3、散列符号表(略讲）散列符号表是多数编译程序采用的符号表，这种符号表的插入和查找效率都比较高。散列符号表又称哈希(hash)符号表，其关键在于使用一种函数哈希函数，将程序中出现的符号通过哈希函数进行映射，得到的函数值作为该符号在表中的位置。散列函数(哈希函数)具有如下性质：1）函数值只依赖于对应的符号。2）函数的计算简单且高效。3）函数值能比较均匀地分布在一定范围内。构造散列函数的方法很多，有除法散列函数、乘法散列函数、多项式除法散列函数、平方取中散列函数等等。散列表的表长通常是一个定值N，因此，散列函数应该将符号名的编码散列成0到N-1之间的某一个值，以便每个符号都能散列到这种符号表中。由于用户使用的符号名是随机的，所以很难找到一种散列函数使得符号名与函数值一一对应。如果有两个或两个以上的不同符号散列到同一个位置，则称为散列冲突。散列冲突是不可避免的，因此，如何解决冲突是构造散列符号表主要考虑的问题之一。常用的处理冲突的办法有：顺序法、倍数法和链表法。,7.4非块程序结构语言的符号表结构,用“质数除余法”来构造散列符号表。1）根据各符号名中的字符确定正整数h，这可以利用将字符转换成整数的函数来实现(如ASC函数)。2）将上一步确定的整数除以符号表的长度N，然后取其余数。这个余数就作为符号的散列位置。如果N是质数，散列的效果较好，即冲突较少。3）处理冲突可采用链接法，即将出现冲突的符号用指针连接起来。假设现有5个符号C1、C2、C3、C4、C5，分别转换成正整数为87、55、319、273和214，符号表的长度是5，那么，利用质数除余法得到的散列地址为：2、0、4、3、4，如图7.2所示。,图7.2 散列符号表,7.4非块程序结构语言的符号表结构,使用散列表的查表过程是：如果查找符号S，首先计算hash(S)，根据散列函数值即可确定符号表中的对应表项。如果该表项是S，即为所求，否则通过链指针继续查找，直到找到或到达链尾为止。显然，采用散列技术查询效率较高，因为查找时只需进行少量比较、甚至无需比较即可定位。到目前为止，散列符号表可以说是构造符号表最常用的结构。,7.5 块程序结构语言的符号表组织,7.5.1 块程序结构语言的概念所谓块程序结构语言是指程序模块可包含嵌套的子模块，每一子模块可以有一组自己的局部变量。按块程序结构语言的规定：变量的作用域是定义它的块程序；同一块内的变量不能重名，但不同块以及嵌套块之间的变量可以重名，因而某变量的声明可与嵌套块的内层变量同名，使用时局部变量优先。,7.5.1 块程序结构语言的概念,下面为一段C程序，右边给出当编译程序编译到此处时的有效变量。real x,y;char name;name,y,xint fun1(int ind)ind,fun1,name,y,x int x;x,ind,fun1,name,y,x x=m2(ind+1);fun1,name,y,xint fun2(int j)j,fun2,fun1,name,y,x int f10;bool test1;test1,f,j,fun2,fun1,name,y,x j,fun2,fun1,name,y,x fun2,fun1,name,y,xmain()main,fun2,fun1,name,y,x char name;name,main,fun2,fun1,name,y,x x=2;y=5;printf(%dn,fun1(x/y);,7.5.1 块程序结构语言的概念,当编译完第2行时，符号表中应含有变量name,y,x的记录。编译到第4行时，符号表中应含有变量x,ind,fun1,name,y,x的记录，此时，符号表同时含有两个变量x的记录，而在函数fun1内有效的变量是局部变量x，即第4行声明的变量。而编译到第6行时，符号表中有变量fun1,name,y,x的记录，x,ind失效。编译到第10行时，有效变量为test1,f,j,fun2,fun1,name,y,x。而编译到第11行时，符号表中有变量j,fun2,fun1,name,y,x的记录，test1,f失效。编译到第15行时，符号表中应含有变量name,main,fun2,fun1,name,y,x的记录，此时，在主函数main内使用的变量x和y都是全局变量。,7.5.2 栈式符号表,对于块程序结构语言，其最简单的符号表结构为栈式符号表，它包括一个符号表栈及一个块索引栈。符号表栈记录变量的属性，块索引栈指出每个块的符号表的开始位置。栈式符号表操作过程十分简单，当遇到变量声明时，将包含变量的属性压入堆栈；当遇到块程序开始时，将当前的符号表栈顶位置压入块索引栈，从而开始一个新块的变量处理；当到达块程序结尾时，则根据块索引栈指出的本块的开始为位置，将该块程序中声明的所有变量记录弹出堆栈，从而使局部声明的变量在块外不再存在。,栈式符号表的插入操作并不难。首先，刚开始编译时，设符号表栈顶指针TOP为0，当第一个标识符出现时，将该标识符的属性入栈，同时将该标识符的地址0压入块索引栈，然后栈顶指针TOP为1。后面再遇到标识符时，如果新的标识符与栈顶的标识符在同一块中，则只需将新记录压入符号表栈顶单元，然后，栈顶指针TOP加1(图7.3a)。如果新的标识符与栈顶的标识符不在同一块中，表示刚才处理的程序块嵌套着一个程序块，而现在进入了这个嵌套的程序块中，则要进行定位操作，即将栈顶指针TOP入块索引栈，再将该标识符属性压入符号栈，然后栈顶指针TOP加1(图7.3b、c)。当编译遇到程序块的结尾时要进行重定位操作，即将块索引栈的栈顶单元出栈并将内容赋给栈顶指针TOP。注意：栈顶指针TOP始终指向符号表栈顶第一个空闲的存储单元。,7.5.2 栈式符号表,块结构语言程序中允许存在重名变量的声明，但重名变量不能出现在同一块中，因此所有标识符插入前要检查当前处理的块中是否有同名变量。其方法是：从栈顶单元(TOP-1)开始到块索引栈的栈顶单元所指的单元，逐一检查，如果有与要插入的变量同名，则表示源程序中存在变量重复声明的错误；如果没有，才可将该标识符的属性入栈。查表操作要对符号栈进行从顶(TOP-1)到底进行线性搜索，这样确保找到的变量满足局部变量优先于全局变量的规则。由于栈式符号表中记录是无序的，因而查询效率比较差。,7.5.2 栈式符号表,例7.1，有一段C程序如下，画出编译到a、b、c、d处的栈式符号表。real x,y;char name;aint fun1(int ind)int x;b x=m2(ind+1);int fun2(int j)int f10;bool test1;c main()char name;dx=2;y=5;printf(%dn,fun1(x/y);,7.5.2 栈式符号表,解：a、b、c、d处的栈式符号表栈式符号表见图7.3的a、b、c、d。,TOP,TOP,TOP,TOP,(a)(b)(c)(d)图7.3 栈式符号表,习题,7.1 给出编译下面程序的有序符号表。main()int m,n5;real x;char name;7.2 按“质数除余法”，给出编译上题程序的散列符号表。7.3 给出编译到下面程序a、b、c处的栈式符号表。real x,y;char str;a int fun1(int ind)int x;b x=m2(ind+1);main()char y;c x=2;y=5;printf(%dn,fun1(x/y);,