符号表与错误处理-sxw

《符号表与错误处理-sxw》由会员分享，可在线阅读，更多相关《符号表与错误处理-sxw（31页珍藏版）》请在金锄头文库上搜索。

1、第8章 符号表与错误处理 第8章 符号表与错误处理 8.1 符号表 第8章 符号表与错误处理 8.1 符 号 表 在编译程序工作的过程中，需要不断收集、记录、查证和使用源程序中的一些语法符号(简称为符号)的类型和特征等相关信息。为方便起见，一般的做法是让编译程序在其工作过程中建立并保存一批表格，如常数表、变量名表、数组内情向量表、过程或子程序名表及标号表等，将它们统称为符号表或名字表。 8.1.1 符号表的作用第8章 符号表与错误处理 符号表中的每一项包括两个部分：一部分填入名字(标识符)；另一部分是与此名字有关的信息，这些信息将全面地反映各个语法符号的属性以及它们在编译过程中的特征，诸如 名

2、字的种属(常数、变量、数组、标号等)、名字的类型(整型、实型、逻辑型、字符型等)、特征(当前是定义性出现还是使用性出现等)、给此名字分配的存储单元地址及与此名语义有关的其它信息等。第8章 符号表与错误处理 对于编译程序所用的符号表来说，它所涉及的基本操作大致可以归纳为五类：(1) 判断一个给定的名字是否在表中；(2) 在表中填入新的名字；(3) 对给定的名字访问它在表中的有关信息；(4) 对给定的名字填入或更新它在表中的某些信息；(5) 从表中删去一个或一组无用的项。第8章 符号表与错误处理 8.1.2 符号表的组织由于处理对象的作用和作用域可以有多种，所以符号表也有多种组织方式。按照处理对象

3、的特点，符号表的组织方式一般可分为直接方式和间接方式。(1)直接方式是指在符号表中直接填入源程序中定义的标识符及相关信息(如图8-1所示)。第8章 符号表与错误处理 (2)间接方式是指单独设置一个字符串数组来存放所有的标识符，并在符号表的名字栏中设置两项内容：一是指针，用来指向标识符在数组中的起始位置；二是一整数值，用来表示该标识 符的长度。图82给出了符号表的间接组织方式。第8章 符号表与错误处理 (3)按标识符的种属，如简单变量、数组、过程等分别建立不同的符号表，如简单变量名表、数组名表、过程名表等。例如，下面的函数：int f (int a,int b)int c;if(ab) c=1;

4、else c=0;return c;第8章 符号表与错误处理 图8-3 按标识符种属组织的各种符号表(a) 简单变量名表；(b) 常数表；(c) 函数入口名表第8章 符号表与错误处理 根据符号表名字栏的组织特点，符号表信息栏的组织方式也分为两类：固定信息内容和仅记录信息存放地址。如果名字栏中的标识符按种属分类，则因同类标识符其基本特征一致，故可将这些信息一一记录在信息栏中。如果符号表的名字不分种属，则由于不同种属的标识符其特征不一致，也即它们所需存储的信息不一致，因而不容易确定一个固定长度的空间来统一安排。这时，可在符号表外另设一组存储空间，并在符号表信息栏中放一指针来指向这个存储空间始址。第

5、8章 符号表与错误处理 对数组标识符需要存储有关数组维数，每维上、下界值， 数组类型及数组存放的起始地址等信息。如果将信息与名字一 起全部放在符号表中，则因维数不同而使记录该信息的空间大 小不易确定，因此，通常给它们另外安排一个内情向量表来记 录数组的全部信息，同时在符号表的信息栏设置一指针指向内 情向量的入口地址(见图8-4)。第8章 符号表与错误处理 所谓分程序结构的语言，是指用这种语言编写的分程序中可以再包含嵌套的分程序，并且可以定义属于它自己的一组局部变量。由于分程序的嵌套导致名字作用域的嵌套，故有时也将允许名字作用域嵌套的语言称为具有分程序结构的语言。函数体可以是一个嵌套的分程序，因

6、而其中所涉及的各个局部变量的作用域也具有嵌套特征。对于嵌套的作用域，同名的变量在不同层次出现可能有不同的类型。因此，为了使编译程序在语义及其它有关处理上不致于发生混乱，可采用分层建立和处理符号表的方式。8.1.3 分程序结构语言的符号表建立第8章 符号表与错误处理 在PASCAL程序中，标识符的作用域是包含说明(定义)该标识符的一个最小分程序；也即PASCAL程序中的标识符(或标号)的作用域总是与说明(定义)这些标识符的分程序的层次相关联。为了表征一个PASCAL程序中各个分程序的嵌套层次关系，可将这些分程序按其开头符号在源程序中出现的先后顺序进行编号。 这样，在从左至右扫描源程序时就可以按分

7、程序在源程序中的这种自然顺序(静态层次)，对出现在各个分程序中的标识符进行处理，具体方法如下：第8章 符号表与错误处理 (1) 当在一个分程序首部某说明中扫描到一个标识符时，就以此标识符查找相应于本层分程序的符号表，如果符号表中已 有此名字的登记项，则表明此标识符已被重复说明(定义)，应按语法错误进行处理；否则，应在符号表中新登记一项，并 将此标识符及有关信息(种属、类型、所分配的内存单元地址 等)填入。(2) 当在一分程序的语句中扫描到一个标识符时，首先在该层分程序的符号表中查找此标识符；若查不到，则继续在其外 层分程序的符号表中查找。如此下去，一旦在某一外层分程 序的符号表中找到此标识符，

8、则从表中取出有关的信息并作 相应的处理；如果查遍所有外层分程序的符号表都无法找到 此标识符，则表明程序中使用了一个未经说明(定义)的标识符，此时可按语法错误予以处理。第8章 符号表与错误处理 为了实现上述查、填表功能，可以按如下方式组织符号表：(1) 分层组织符号表的登记项，使各分程序的符号表登记项连续地排列在一起，而不许为其内层分程序的符号表登记项所分割。(2) 建立一个“分程序表”，用来记录各层分程序符号表的有关信息。分程序表中的各登记项是在自左至右扫描源程序中按分程序出现的自然顺序依次填入的，且对每一分程序填写一个登记项。因此，分程序表各登记项的序号也就隐含地表征了各分程序的编 号。分程

9、序表中的每一登记项由三个字段组成：OUTERN字段用来指明该分程序的直接外层分程序的编号；COUNT字段用来记录该分程序符号表登记项的个数；POINTER字段是一个指示器，它指向该分程序符号表的起始位置。第8章 符号表与错误处理 建立符号表的算法描述如下：(1) 给各指示器赋初值。(2) 自左至右扫描源程序： 每当进入分程序的首符号或过程(函数)时，就在分程序表中登记一项，并使之成为当前的分程序。 当扫描到当前分程序中一个定义性出现的标识符时，将该名字及其有关信息填入临时工作栈的顶部(当然，在填入前应在临时工作栈本层分程序已登入的项中检查是否已有重名 问题)；然后在分程序表中，把当前分程序相应

10、登记项的COUNT值加1且使POINTER指向新的栈顶。 第8章 符号表与错误处理 当扫描到分程序的结束符END时，将记入临时工作栈的本层 分程序全部登记项移至正式的符号表中，且修改POINTER值使其指向本层分程序全部名字登记项在符号表中的起始位置。此 外，在退出此层分程序时，还应使它的直接外层分程序成为当 前的分程序。(3) 重复上面的步骤(2)，直至扫描完整个源程序为止。对一遍扫描的编译程序而言，在它工作过程中，当遇到某 分程序的结束符END时，该分程序中的全部标识符已经完成它们的使命。因此，只需将它们从栈中逐出，也即将栈顶部指示 器回调至刚进入本分程序时的情况即可，而不再需要把这些登

11、记项上移。事实上，如上所述的工作栈就完全可作为编译程序 的符号表来使用，我们将这种符号表称为栈式符号表。第8章 符号表与错误处理 PROGRAM PP (input,output);COUNT norw=13;VAR ll,kk:integer;word:ARRAY1.norw OF char;PROCEDURE getsym;VAR i,j: integer;PROCEDURE getch;BEGINEND; getch例8.1 一示意性源程序如下：BEGINj:=1;kk:=i+jEND; getsymBEGINEND. pp第8章 符号表与错误处理 当编译程序扫描上述源程序时，生成栈式符

12、号表，试就此符号表回答以下问题：(1) 画出“扫描到getsym过程体之前”的栈符号表；(2) 画出“扫描完getsym过程说明(即扫描完END; getsym)”时的栈符号表。解答 假定所有的名字在数据区中都只需要一个单元。(1)“扫描到getsym过程体之前”的栈符号表如图8-5所示。(2)“扫描完getsym过程说明”时的栈符号表如图8-6所示。第8章 符号表与错误处理 图8-5 “扫描到getsym过程体之前”的栈符号表 第8章 符号表与错误处理 图8-6 “扫描完getsym过程说明”的栈符号表 第8章 符号表与错误处理 典型的非分程序结构语言就是FORTRAN语言。FORTRAN语

13、言是一种块结构的程序设计语言，一个FORTRAN可执行程序由一个或若干个相对独立的程序段组成，其中有且仅有一个主程序段，其余的则是子程序段。程序段之间的数据传送主要是通过过程调用时的形参与实参的结合，或访问公共区中的元 素来进行的。对于一个FORTRAN程序来说，除了程序段名和公共区名的作用域是整个程序之外，其余的变量名、数组名、语句函数名以及标号等，都分别是定义它们的那个程序段中的局部量。此外，由于语句函数定义句中的形参与程序段中的其它变量名毫不相干，因此，它们的作用域就是该语句函数定义句本身。8.1.4 非分程序结构语言的符号表建立第8章 符号表与错误处理 根据FORTRAN程序中各类名字

14、作用域的特点，原则上可把程序中每一程序段均视为一个可独立进行编译的程序单元，即对各程序段分别进行编译并产生相应的目标代码，然后再连接装配成一个完整的目标程序。这样，当一个程序段编译完成后，该程序段的全部局部名登记项即完成了使命，可以将它们从符号表中删除。至于全局名登记项，因为它们还可能为其它 程序段所引用，故需继续保留。因此，对于FORTRAN编译程序而言，可分别建立一张全局符号表和一张局部符号表，前者供编译各程序使用，后者则只用来登记当前正编译的程序段中的局部符号名。一旦将该程序段编译完成，就可将局部符号表空白区首地址指针再调回到开始位置，以便腾出空间供下一个要编译的程序段建立局部符号表使用

15、。第8章 符号表与错误处理 在考虑全局优化的多遍扫描编译系统中，由于一般并不是在编译当前程序段时就产生该程序段的目标代码，而是先生成各程序段的相应中间代码，待进行优化处理之后再产生目标代码。因此，当一个程序段被处理完之后，不能立即将相应的局部名表撤消，而应将它们暂存起来。在生成中间代码时，对于各程序段中的局部变量名，如果都用该名字的名表登记项序号去代替，那么局部名表的名字栏就用不着再继续保留，因为只要知道了登记项的序号就同样可以查到该登记项的有关信息。然而，对于同一个登记项序号而言，所在的局部名表的不同将代表完全不同的登记项。第8章 符号表与错误处理 由于在整个编译过程中需要不断地访问符号表，

16、因而如何构造符号表以及如何查填符号表就成为编译程序设计的重要问题之一。除了上述我们介绍的用于嵌套结构程序语言的栈式符号表外，还有其它几种常用符号表结构。8.1.5 常用符号表结构第8章 符号表与错误处理 1线性符号表符号表中最简单且最容易实现的数据结构是线性表，它是按程序中标识符出现的先后次序建立的符号表，编译程 序不做任何整理次序的工作。线性符号表如图87所示。第8章 符号表与错误处理 2有序符号表为了提高查表速度，可以在造表的同时把各标识符按照一定的顺序进行排列。显然，这样的符号表是有序的，对图 87所示的线性符号表排序后的情况如图88所示。查找长度为1+lbN。第8章 符号表与错误处理 对于动态查找的符号表，可以采用二叉树结构来组织有序符号表 。二叉排序树的平均查找长度为1+4lbN。第8章 符号表与错误处理 3散列符号表散列符号表是大多数编译程序采用的一种符号表。符号表采用散列技术，相对来讲具有较高的运行效率，特别适用 于边填写边引