《编译原理实用教程教学课件杨德芳第10章 符号表和错误处理》由会员分享，可在线阅读，更多相关《编译原理实用教程教学课件杨德芳第10章 符号表和错误处理（54页珍藏版）》请在金锄头文库上搜索。
1、第10章 符号表和错误处理,本章学习目标,为了检查语义的正确性和生成代码，需要知道源程序中所使用的各种标识符的属性。这些属性常常由编译程序集中起来并存放在一个标识符表或符号表中。本章的主要内容有： 符号表的组织和内容 符号表的构造和查找 分程序的结构,10.1符号表的组织和内容,在编译的各个阶段经常要收集和使用出现在源程序中的各种信息，为了方便，通常把这些信息用一些表格进行记录、存储和管理，如常量表、数组信息表、保留字表和标识符表等，这些表统称为符号表。符号表主要保存各类标识符的属性，它在翻译过程中有两个方面的重要作用，一是检查语义的正确性，二是辅助生成代码。也就是说在实现语义检查和代码生成时
2、，需要不断插入和检索符号表中标识符的属性来实现。,在进行词法分析时，从字符串源程序中分离出标识符后，首先检查保留字表，如果在保留字表中没有，就是标识符，词法分析程序就输出标识符符号，同时记住该标识符符号和属性值。 在编译时，源程序中每出现一次标识符，就要和符号表打一次交道，主要工作是查表和存取操作，因此与符号表交互占据了大量的编译时间。所以如何有效地组织和快速查找符号表直接影响编译的效率。,符号表可以在词法分析时创建，也可以在语义分析时创建。在编译程序中，符号表在词法分析时创建，此时符号表中只含有标识符的名字，其他属性要在语义分析阶段填入。而变量在符号表中的位置信息将作为标识符符号的属性出现，
3、构成词法分析器所产生的单词符号的一部分；语法分析阶段只检查源程序语法的正确性，一般不使用符号表；语义分析程序对该编码形式进行语义正确性分析，遇到声明语句时会填入有关标识符的属性。在 符号表中的标识符的属性信息会在代码生成阶段用于产生目标代码。因此，直到语义分析和代码生成阶段，许多与变量有关的属性才能相继填入符号表。,10.1.2符号表的组织 在编译程序中，符号表主要用来存放源程序中各种有用的信息。在编译阶段要不断对这些信息进行访问、增加和更新。因此，需要合理组织符号表使符号表占用尽量少的内存空间，同时还要提高访问符号表的效率。符号表中具体需要设计哪些属性也部分的取决于程序设计语言的特点。 1表
4、的属性 （1）标识符的名字。一个标识符可以是一个变量的名字、一个函数的名字或一个过程的名字。 （2）符号的类型。除过程标识符之外的函数和变量都具有数据类型。 （3）符号的存储类别。大多数语言的存储类别有两种方式，一种是公共存储区的变量，另一种是私有存储变量。 （4）符号的作用域及可视性。一个符号变量在程序中起作用的范围，称为作用域。一般来讲，定义该符号的位置及存储类关键字决定了该符号的作用域。但是在出现函数的形式参数和分程序的时候，就要考虑可视性的问题。关于变量的作用域和可视性可以结合C语言进行考虑。,int a; int func(a,b) float a; int b; a /*此时的 a
5、为形式参数的a*/ 分程序的情况： int a; char a; float a; a/引用的是char a;/ ,（5）符号变量的存储分配信息。通常一个编译程序有两类存储区，即静态存储区和动态存储区。 （6）符号表的其他属性 符号表还有其它方面的重要信息。 1）数组的内情向量在程序设计语言中，数组是一种重要的数据类型。编译程序处理数组主要是把数组的内情向量表登录在符号表中，这些属性信息确定了存储分配时数组占据多大的内存空间。 2）记录结构型的成员信息。一个结构体类型的变量，是由若干成员项组成的，因此记录类型的变量在存储空间的大小是由它的成员项来决定。 3）函数及过程的形参。函数和过程的形参作
6、为函数或过程的局部变量，又是对外的接口。因此，形式参数的个数、排列次序和类型都必须反映在符号表中。它还是过程调用和语义检查的依据。,（1）名字。就是指标识符的名字属性。 （2）目标地址。标识符主要做变量的名字，程序中每个变量都必须有一个相应的目标地址，该地址是为该变量分配的相对内存地址。当声明一个变量时，就要为该变量分配内存空间，并将其分配的地址填入符号表中。当该变量在程序的其他处被引用时，可以从符号表中查询该变量，并填入存取该变量值的目标代码中。对于采用静态存储分配的语言如FORTRAN，地址是连续分配的。对于采用动态存储分配的语言，每个程序块的变量是连续分配的，这是一个相对地址。运行时还要
7、根据该程序块分配的数据区的起始地址和变量的相对地址计算出该变量的绝对内存地址。如果标识符表示的是函数名，则目标地址就是该函数代码的起始地址，是数组名则为数组模板的起始地址。,（3）类型。不同数据类型的变量占据不同大小的内存空间，另外类型检查是语义分析的一项重要工作，所以符号表中要保存每个标识符的数据类型，以便分配内存和进行类型检查。 （4）维数和参数的个数。这两个属性都是对类型检查很重要的因素。在数组引用时，其引用元素的维数与数组声明中所定义的维数一致，类型检查阶段必须进行一致性的检查。另外，维数也用于数组元素地址的计算。过程调用时，实参和形参的个数一致。指针属性在后面的章节再做介绍。,3符号
8、表的总体组织 在前面的分析中可以看到，不同的标识符属性不同。但有些标识符属性比较接近，例如语言的关键字和变量的标识符的属性差距不大。但是变量和过程或函数的属性差距较大。因此，一个编译程序对符号表的总体组织可以有以下3种选择。 （1）属性完全相同的符号组织在一起。这样构造出多个符号表，每个符号表的优点是符号表中存放符号的属性个数和结构完全相同，表项是等长的，而且每个符号栏中的属性值都是有效的。例如所有的变量标识符放在一起，所有的保留字放在一起，所有的过程或函数的名字放在一起，数组标识符放在一起。这样组织的缺点是系统会有多个符号表，增加了总体管理的工作量和复杂度。,（2）把所有语言的各种符号都组织
9、在一张表中。这样组织的最大优点是总体管理非常集中和单一，缺点是由于不同种类的属性不同，必然会出现一些属性值不等长的情况和无用属性空间。比如过程或函数标识符与变量标识符、保留字放在一张表中。 （3）第三种是以上两种情况折衷。根据符号属性的相似性，分成若干表格，每张表格中记录的符号都有比较多的相同属性，也有些部分的属性差距不大。,4符号表中项的排列 设计好符号表的整体结构后，表中的符号是如何排列，也是需要考虑的内容。在编译程序的整个工作过程中，符号表要被频繁的用来建立表项，填充和引用表项的属性。符号项的排列和组织传统上采用3种构造方式，即线性法、二分法和散列法。 （1）线性组织。构造符号表最容易的
10、方法是线性造表法。它按照标识符出现的先后顺序填写各个表项，而不做任何整理表项次序的工作。它从符号表的表头依次向表尾方向填写，把当前要填入的新表项填到符号表中，这样构造的表称为线性表，如图10-1所示。 例如：main() int i,m,k; i=1;m=1; k=i+m; printf(“%d”,k); ,（2）排序组织和二分法 排序组织的符号表是根据语言中符号的ASC或EBCDIC代码字符拼写而成的。排序组织的符号表的表项按符号的字符串的值的大小从大到小排列。在上面的程序例子中，用排序组织出来的符号表就变为图10-2，在标识符的插入过程中，要求有次序。二分法主要是为了保持符号表的顺序而采用
11、的一种插入算法，该插入算法的执行可以参看数据结构的有关内容。,（3）符号表的散列组织方法相对来说具有较高的运行效率，因而绝大多数编译程序中的符号表是采用散列组织。散列符号表又称哈希符号表，其关键在于引进了一种函数 哈希函数，并将程序中出现的标识符通过哈希函数进行映射，将得到的函数值作为该标识符在符号表中的位置。 哈希函数一般具有如下的性质： （1）函数只依赖于对应的标识符。 （2）函数的计算简单并且高效。 （3）函数值能比较均匀分布在一定的范围内。 构造散列函数的方法很多，如直接定址法、数字分析法、平方取中法和除留余数法。 在对散列表进行插入时经常会出现冲突，即标识符映射到同一个地址，此时，需
12、要进行调整，调整的方法在数据结构中有详细的介绍，在此不再分析。,5关键字域的组织 关键字域，就是符号本身，它可以是保留字的名字、变量的名字或过程、函数、数组的名字。在高级语言中，各种标识符的命名都有一定的规则，考虑到用户的命名习惯和程序的可读性，标识符的长度是从1到高级语言内部定的任意长度。比如C语言的关键字段可以是32。在符号表的组织中，一个要解决的重要问题是标识符长度的可变问题。对标识符名字的处理，即关键字域要考虑是定长的还是变长的，各个关键字长度差距有多大等。根据标识符的定义特点通常采用的存储方法有两种： （1）定长存储法。即为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中。如图
13、10-3所示。特点是简单，存取速度快，缺点是空间利用率低。标识符长度不能超过名字域的宽度。 （2）集中存储方法。即开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。如图10-4所示特点是存储效率高，标识符无长度限制。,6 其它信息的组织和表示 （1）基本数据类型 表示符号的基本数据类型可以用3个bit 来表示，也可以用个整型量来表示。如果标识符的类型属性是基本数据类型，可以用如表10-2所示。 在符号表的属性中出现基本数据类型时用数字代替比较简单。上面的表示方式可以在编程时提前定义,2）函数名标识符及其参数 有些标识符，象函数名，因为函数本身带有
14、参数，所以可以用指针来表示。在符号表中设计一个“函数形参”属性，指向对应的参数。 例如：func1（para1,para2,para3） func2( ) 当处理到这两个函数的时候，可以在形式参数和函数名字之间建立对应的关系。其结构图如10-5所示。,（3）结构体与成员之间的表示。在C语言中，结构体和成员之间的关系也可以用函数和形参的格式来表示。在符号表中设计一个“结构成员”指针属性，指向结构体成员项。 例如：设有一个结构体 struct tag1memb1 memb2 struct tag2memb3 memb4 memb5memb6 memb7stv; 它的符号表的结构如图10-6所示。,
15、（4）数组变量的表示。前面我们已经分析过，数组的详细信息都登记在内情向量表中。数组符号在符号表中可以设立一个指向内情向量的指针，而在内情向量表中登记关于数组维数个数和每一维的元素个数。 例如，设有两个数组： A1(sub1,sub2) A2(sub1,sub2,sub3,sub4,sub5,sub6) A1为一个二维数组，A2为一个四维数组。 它在符号表中的表示为图10-7所示：,（5）分程序结构中标识符的处理。在程序设计语言的结构中，分程序的分层结构允许同名标识符。为了实现同名标识符的语义功能，在符号表中设计下推链域的组织。下推链域的组织要求在进入一个内层结构并发生重名标识符的定义时，需要把
16、当前符号表中外层的该符号表项下推到下推链中而在符号表被下推的表项处建立内层的同名标识符的表项。,例如：设有一个分程序的结构如下 int i; （1） func( ) （2） float i;（3） （4） int i5;（5） （6） int i;（7） i（8） i（9） 当,编译程序扫描到（1）行时，符号表中建立第0层的int i表项。当扫描到（2）行的 func( )函数定义则程序进入到第1层。因此扫描到（3）行时，遇到符号i的重名项，这时int i的表项被下推到下推链中，而符号表中原int i的表项处登录float i表项。依次类推，编译程序每进入一层，则下推链就被下推一次，得到如图10-8所示的符号表的下推链结构。,10.1.3符号表的内容 对于常见的程序设计语言，其变量名及登记项的信息栏通常包含如下的内容。 1变量名 （1）种属（简单变量、数组、记
