符号表和错误处理

1、第10章 符号表和错误处理本章学习目标v为了检查语义的正确性和生成代码，需要知道源程序中所使用的各种标识符的属性。这些属性常常由编译程序集中起来并存放在一个标识符表或符号表中。本章的主要内容有：v符号表的组织和内容v符号表的构造和查找v分程序的结构10.1符号表的组织和内容v在编译的各个阶段经常要收集和使用出现在源程序中的各种信息，为了方便，通常把这些信息用一些表格进行记录、存储和管理，如常量表、数组信息表、保留字表和标识符表等，这些表统称为符号表。符号表主要保存各类标识符的属性，它在翻译过程中有两个方面的重要作用，一是检查语义的正确性，二是辅助生成代码。也就是说在实现语义检查和代码生成时，需

2、要不断插入和检索符号表中标识符的属性来实现。v在进行词法分析时，从字符串源程序中分离出标识符后，首先检查保留字表，如果在保留字表中没有，就是标识符，词法分析程序就输出标识符符号，同时记住该标识符符号和属性值。v在编译时，源程序中每出现一次标识符，就要和符号表打一次交道，主要工作是查表和存取操作，因此与符号表交互占据了大量的编译时间。所以如何有效地组织和快速查找符号表直接影响编译的效率。v符号表可以在词法分析时创建，也可以在语义分析时创建。在编译程序中，符号表在词法分析时创建，此时符号表中只含有标识符的名字，其他属性要在语义分析阶段填入。而变量在符号表中的位置信息将作为标识符符号的属性出现，构成

3、词法分析器所产生的单词符号的一部分；语法分析阶段只检查源程序语法的正确性，一般不使用符号表；语义分析程序对该编码形式进行语义正确性分析，遇到声明语句时会填入有关标识符的属性。在 符号表中的标识符的属性信息会在代码生成阶段用于产生目标代码。因此，直到语义分析和代码生成阶段，许多与变量有关的属性才能相继填入符号表。v在编译程序中，符号表主要用来存放源程序中各种有用的信息。在编译阶段要不断对这些信息进行访问、增加和更新。因此，需要合理组织符号表使符号表占用尽量少的内存空间，同时还要提高访问符号表的效率。符号表中具体需要设计哪些属性也部分的取决于程序设计语言的特点。v1表的属性v（1）标识符的名字。一

4、个标识符可以是一个变量的名字、一个函数的名字或一个过程的名字。v（2）符号的类型。除过程标识符之外的函数和变量都具有数据类型。v（3）符号的存储类别。大多数语言的存储类别有两种方式，一种是公共存储区的变量，另一种是私有存储变量。v（4）符号的作用域及可视性。一个符号变量在程序中起作用的范围，称为作用域。一般来讲，定义该符号的位置及存储类关键字决定了该符号的作用域。但是在出现函数的形式参数和分程序的时候，就要考虑可视性的问题。关于变量的作用域和可视性可以结合C语言进行考虑。vint a;vint func(a,b)vfloat a;vint b;vvva/*此时的 a为形式参数的a*/vvv分程

5、序的情况：vv int a;vvchar a;vv float a;v vvva/引用的是char a;/ vvv（5）符号变量的存储分配信息。通常一个编译程序有两类存储区，即静态存储区和动态存储区。v（6）符号表的其他属性v符号表还有其它方面的重要信息。v1）数组的内情向量在程序设计语言中，数组是一种重要的数据类型。编译程序处理数组主要是把数组的内情向量表登录在符号表中，这些属性信息确定了存储分配时数组占据多大的内存空间。v2）记录结构型的成员信息。一个结构体类型的变量，是由若干成员项组成的，因此记录类型的变量在存储空间的大小是由它的成员项来决定。v3）函数及过程的形参。函数和过程的形参作为

6、函数或过程的局部变量，又是对外的接口。因此，形式参数的个数、排列次序和类型都必须反映在符号表中。它还是过程调用和语义检查的依据。名字目标地址类型维数声明行引用行指针omputer02129,4,57X1410312,140FORM83246B2481051ANS521054M566062v（1）名字。就是指标识符的名字属性。v（2）目标地址。标识符主要做变量的名字，程序中每个变量都必须有一个相应的目标地址，该地址是为该变量分配的相对内存地址。当声明一个变量时，就要为该变量分配内存空间，并将其分配的地址填入符号表中。当该变量在程序的其他处被引用时，可以从符号表中查询该变量，并填入存取该变量值的目

7、标代码中。对于采用静态存储分配的语言如FORTRAN，地址是连续分配的。对于采用动态存储分配的语言，每个程序块的变量是连续分配的，这是一个相对地址。运行时还要根据该程序块分配的数据区的起始地址和变量的相对地址计算出该变量的绝对内存地址。如果标识符表示的是函数名，则目标地址就是该函数代码的起始地址，是数组名则为数组模板的起始地址。v（3）类型。不同数据类型的变量占据不同大小的内存空间，另外类型检查是语义分析的一项重要工作，所以符号表中要保存每个标识符的数据类型，以便分配内存和进行类型检查。v（4）维数和参数的个数。这两个属性都是对类型检查很重要的因素。在数组引用时，其引用元素的维数与数组声明中所

8、定义的维数一致，类型检查阶段必须进行一致性的检查。另外，维数也用于数组元素地址的计算。过程调用时，实参和形参的个数一致。指针属性在后面的章节再做介绍。v3符号表的总体组织v在前面的分析中可以看到，不同的标识符属性不同。但有些标识符属性比较接近，例如语言的关键字和变量的标识符的属性差距不大。但是变量和过程或函数的属性差距较大。因此，一个编译程序对符号表的总体组织可以有以下3种选择。v（1）属性完全相同的符号组织在一起。这样构造出多个符号表，每个符号表的优点是符号表中存放符号的属性个数和结构完全相同，表项是等长的，而且每个符号栏中的属性值都是有效的。例如所有的变量标识符放在一起，所有的保留字放在一

9、起，所有的过程或函数的名字放在一起，数组标识符放在一起。这样组织的缺点是系统会有多个符号表，增加了总体管理的工作量和复杂度。v（2）把所有语言的各种符号都组织在一张表中。这样组织的最大优点是总体管理非常集中和单一，缺点是由于不同种类的属性不同，必然会出现一些属性值不等长的情况和无用属性空间。比如过程或函数标识符与变量标识符、保留字放在一张表中。v（3）第三种是以上两种情况折衷。根据符号属性的相似性，分成若干表格，每张表格中记录的符号都有比较多的相同属性，也有些部分的属性差距不大。v4符号表中项的排列v设计好符号表的整体结构后，表中的符号是如何排列，也是需要考虑的内容。在编译程序的整个工作过程中

10、，符号表要被频繁的用来建立表项，填充和引用表项的属性。符号项的排列和组织传统上采用3种构造方式，即线性法、二分法和散列法。v（1）线性组织。构造符号表最容易的方法是线性造表法。它按照标识符出现的先后顺序填写各个表项，而不做任何整理表项次序的工作。它从符号表的表头依次向表尾方向填写，把当前要填入的新表项填到符号表中，这样构造的表称为线性表，线性表，如图10-1所示。v例如：main()vint i,m,k;vi=1;m=1;vk=i+m;vprintf(“%d”,k);vv（2）排序组织和二分法v排序组织的符号表是根据语言中符号的ASC或EBCDIC代码字符拼写而成的。排序组织的符号表的表项按符

11、号的字符串的值的大小从大到小排列。在上面的程序例子中，用排序组织出来的符号表就变为图10-2，在标识符的插入过程中，要求有次序。二分法主要是为了保持符号表的顺序而采用的一种插入算法，该插入算法的执行可以参看数据结构的有关内容。v（3）符号表的散列组织方法相对来说具有较高的运行效率，因而绝大多数编译程序中的符号表是采用散列组织。散列符号表又称哈希符号表，其关键在于引进了一种函数 哈希函数，并将程序中出现的标识符通过哈希函数进行映射，将得到的函数值作为该标识符在符号表中的位置。v哈希函数一般具有如下的性质：v（1）函数只依赖于对应的标识符。v（2）函数的计算简单并且高效。v（3）函数值能比较均匀分

12、布在一定的范围内。v构造散列函数的方法很多，如直接定址法、数字分析法、平方取中法和除留余数法。v在对散列表进行插入时经常会出现冲突，即标识符映射到同一个地址，此时，需要进行调整，调整的方法在数据结构中有详细的介绍，在此不再分析。 v5关键字域的组织v关键字域，就是符号本身，它可以是保留字的名字、变量的名字或过程、函数、数组的名字。在高级语言中，各种标识符的命名都有一定的规则，考虑到用户的命名习惯和程序的可读性，标识符的长度是从1到高级语言内部定的任意长度。比如C语言的关键字段可以是32。在符号表的组织中，一个要解决的重要问题是标识符长度的可变问题。对标识符名字的处理，即关键字域要考虑是定长的还

13、是变长的，各个关键字长度差距有多大等。根据标识符的定义特点通常采用的存储方法有两种：v（1）定长存储法。即为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中。如图10-3所示。特点是简单，存取速度快，缺点是空间利用率低。标识符长度不能超过名字域的宽度。v（2）集中存储方法。即开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。如图10-4所示特点是存储效率高，标识符无长度限制。v6 其它信息的组织和表示v（1）基本数据类型v表示符号的基本数据类型可以用3个bit 来表示，也可以用个整型量来表示。如果标识符的类型属性是基本数据类型，可以用如表1

14、0-2所示。v在符号表的属性中出现基本数据类型时用数字代替比较简单。上面的表示方式可以在编程时提前定义v2）函数名标识符及其参数v有些标识符，象函数名，因为函数本身带有参数，所以可以用指针来表示。在符号表中设计一个“函数形参”属性，指向对应的参数。v例如：func1（para1,para2,para3）v func2( )v当处理到这两个函数的时候，可以在形式参数和函数名字之间建立对应的关系。其结构图如10-5所示。v（3）结构体与成员之间的表示。在C语言中，结构体和成员之间的关系也可以用函数和形参的格式来表示。在符号表中设计一个“结构成员”指针属性，指向结构体成员项。v例如：设有一个结构体v

15、struct tag1memb1vmemb2vstruct tag2memb3v memb4v memb5memb6vvmemb7stv;v它的符号表的结构如图10-6所示。v（4）数组变量的表示。前面我们已经分析过，数组的详细信息都登记在内情向量表中。数组符号在符号表中可以设立一个指向内情向量的指针，而在内情向量表中登记关于数组维数个数和每一维的元素个数。v例如，设有两个数组：vA1(sub1,sub2)vA2(sub1,sub2,sub3,sub4,sub5,sub6)vA1为一个二维数组，A2为一个四维数组。v它在符号表中的表示为图10-7所示：v（5）分程序结构中标识符的处理。在程序设

16、计语言的结构中，分程序的分层结构允许同名标识符。为了实现同名标识符的语义功能，在符号表中设计下推链域的组织。下推链域的组织要求在进入一个内层结构并发生重名标识符的定义时，需要把当前符号表中外层的该符号表项下推到下推链中而在符号表被下推的表项处建立内层的同名标识符的表项。v例如：设有一个分程序的结构如下vvint i; （1）vvfunc( ) （2）vv float i;（3）v v （4）vint i5;（5）v v（6）vint i;（7）v vvi（8）vvi（9）vv当v编译程序扫描到（1）行时，符号表中建立第0层的int i表项。当扫描到（2）行的 func( )函数定义则程序进入到

17、第1层。因此扫描到（3）行时，遇到符号i的重名项，这时int i的表项被下推到下推链中，而符号表中原int i的表项处登录float i表项。依次类推，编译程序每进入一层，则下推链就被下推一次，得到如图10-8所示的符号表的下推链结构。符号内情向量指针 int 3层数下推指针 int 2 3 0 5 float 1 int类型符号表项下推链 图10-8符号表的下推链结构v对于常见的程序设计语言，其变量名及登记项的信息栏通常包含如下的内容。v1变量名v（1）种属（简单变量、数组、记录结构）。v（2）类型（整形、实型、双精度、逻辑型、字符串型、标号或指针）。v（3）所分配的数据区的地址。v（4）若

18、为数组类型，应填写其内情向量并给出内情向量的首址。v（5）若为记录结构，则应把该登记项与其分量按某种方式连接起来。v（6）是否为形式参数，则记录类型。v（7）设置某些标志。v2过程名v（1）是否为程序的外部过程。v（2）若为函数，指明它的类型。v（3）是否处理过相应的过程或函数定义。v（4）是否递归定义。v（5）指出过程的形参，并按形参排列的顺序将它们的类型等信息与过程名字相联系，以便在其后检查实参和形参是否相一致。v10.2符号表的操作和错误处理v在编译程序的工作过程中，对符号表的操作一般有如下几种：对符号表进行初始化、符号登录、符号查找以及有关分程序的符号表层次的管理等。v符号表的初始化，

19、指对语言程序开始编译时，定义符号表的初始状态。符号表的组织方式不同，初始化的方式也不同。一般分为以下两种情况。一种是符号表随着符号的逐步登录逐渐增长，开始为0。另一种是符号表的长度是固定的。这两种形式的符号表的初始化方法不同，其格式如图10-9和10-10 所示。一种采用指针的方式，一种采用数组的方式。v当编译程序从语言程序中获得一个标识符并确定这个标识符不在符号表中时，就要将符号表登录到符号表中。要想将标识符登录到符号表中，首先要确定登录位置。位置的确定有符号表的组织结构决定。如果是线性的符号表的结构，则顺序登录，如果是排序过的符号表则采用二分法找到位置。对于散列表则是由散列函数计算位置，如

20、果发生碰撞，则按数据结构介绍的方法解决碰撞。v每当编译程序从语言源程序获得一个符号时，首先要确定该符号的类别。通常先在保留字表和运算符表中查找是否有该标识符。若有，则将该标识符转换为保留字或运算符的内部代码。若没有，从标识符表中查找时，若找到同名的标识符，则该标识符无须登录。如果找不到就将该标识符登录上。v查找符号表的目的是为了进行语义分析。进行静态语义的检查。v符号表的查找方法与符号表的组织有很大的关系，关于顺序查找、折半查找和散列查找的方法在数据结构书中已经讲述了 v在程序设计语言中，分程序具有独特的结构特点。对于分程序结构的程序，它的符号表的建立有两种方式。一种是一个分程序建立一个独立的

21、符号表，另一种是将各分程序符号组织在一起，放在一个表中。v1分表结构。基本思想是：编译程序扫描到一个分程序的开始，就为该分程序建立一张符号表，该分程序的所有的标识符都登记在这张符号表中。扫描完该分程序，则释放该符号表。v例如：vint a;vfloat b,d;v int c;v float a;v int d;v float c;v float d;vva=b+c+d;vvvv vv该分程序的分表结构如图10.11所示。图10-11分程序结构的分表组织int dfloat c第3层分程序符号表float d第4层分程序符号表int afloat bfloat d第1层分程序符号表int cf

22、loat a第2层分程序符号表v2单表结构v 基本思想是：将所有的分程序标识符都集中在一张表中，为了实现分程序中作用域和可视域的要求，表的结构设置如下：v（1）当编译程序进入到第一层时符号表的结构为：v每一项包括（变量名，类型，层次）v（2）在编译程序扫描进入到下一个分程序时，表示分程序层次的状态量增加一层。v（3）当退出一个分程序时，要将该分程序的符号项清除掉。v例如：vint a;vfloat b,d;v int c;v float a;v int d;v float c;v float d;vva=b+c+d;vvvv v符号表abdintfloatfloat111符号表abdfloat

23、floatfloat211（b）进入分程序第2层时符号表的层次表达下推链aint1cint2符号表abdfloatfloatint213(c)进入分程序第3层时符号表的层次表达下推链aint1cfloat3下推链cint2下推链dfloat1符号表abdfloatfloatint214(d)进入分程序第4层时符号表的层次表达下推链aint1cfloat3下推链cint2下推链dint 3dfloat 110.3错误处理v由编译程序处理的源程序总是会或多或少地含有错误。因此，一个好的编译程序应具有较强的查错或改错的能力。所谓查错，是指编译程序在工作过程中能够准确、及时地将源程序中的各种错误查找出

24、来，并以简明的形式报告错误的性质及出错位置。所谓改错，就是当编译程序发现源程序中的错误时，适当做一些修补工作，使得编译工作不至于因错误而中止，以便在一次编译过程中尽可能多地发现源程序中的错误。然而，更正所发现的错误并不是一件容易的事。许多编译程序实际上并不做改正错误的工作。v源程序中的错误通常分为语法错误和语义错误两类。所谓语法错误，是指编译程序在词法分析阶段和语法分析阶段所发现的错误，如关键字拼写错误、语法成分不符合语法规则等。一般来说，编译程序检查此类错误比较容易，并且也能准确地确定出错的位置。至于语义错误，则主要来源于对源程序中某些变量不正确的使用，如使用了未经说明的变量，某些变量被重复

25、说明或不符合有关作用域的规定，运算的操作数类型不相容、实参与形参种属或类型不一致等，都是典型的语义错误。这些错误也能被编译程序查出。此外，由于编译实现的技术原因，或为目标计算机的资源条件所限，在实现某一个程序语言时，编译系统对语言的使用又提出了进一步的限制。例如对各类变量数值范围的限制，对数组维数、形参个数、循环嵌套层数的限制。对于违反这些限制出现的语义错误只有到目标程序运行时才能查出，但此时的源程序已被翻译成目标代码程序，所以要确定源程序中的错误位置比较困难。v对源程序错误的处理通常有两种不同的方法。一种方法是对错误进行适当的修补，以便编译工作能够继续下去；另一种方法是跳过有错误的那个语法成

26、分，以便把错误限制在尽可能小的局部范围内，从而减少因某一错误而引起的一连串假错；第二类方法称为错误的局部化。v1单词错误的校正v词法分析的主要任务是把字符串形式的源程序转换为一个单词系列。由于每一类单词都可以用某一正规式表示，故在识别源程序中的单词符号时，通常采用了一种匹配最长子串的策略。如果在识别单词的过程中发现当前余留的输入字符串的任何前缀都不能和所有词型相匹配，则调用单词出错程序处理。然而，由于词法分析阶段不能收集足够的源程序信息，因此让词法分析程序担负校正单词错误的工作是不恰当的。事实上，还没有一种适用于各种词法错误的校正方法。最直接的做法是，每当发现一个词法错误时就跳过其后的字符，直

27、到出现下一个单词为止。v2自上而下分析中的错误校正v编译过程中大部分查错和改错工作集中在语法分析阶段。由于程序语言的语法通常是上下文无关文法描述，并且该语言可通过语法分析器得到准确的识别。因此，源程序中的语法错误总是被语法分析程序自动查出，即当分析器根据当前的状态判断不存在下一个合法的分析动作时，就查出了源程序中的一个语法错误。此时，编译程序应准确地确定出错位置并校正错误，然后根据当前的状态进行相应的修改，使语法工作得以继续进行。v首先讨论自上而下分析中的错误校正问题。在语法分析过程中的每一个时刻，总可以把源程序输入符号串a1a2an划分成如下的格式：va1a2an=w1aiw2v首先讨论自上

28、而下分析中的错误校正问题。在语法分析过程中的每一个时刻，总可以把源程序输入符号串a1a2an划分成如下的格式：va1a2an=w1aiw2v其中，w1是已经扫描和加工过的部分，ai为现行输入符号，而w2则是输入串的余留部分。假定编译程序现在发现了源程序中的一个语法错误，这对自上而下分析来说，也就意味着分析器目前已为输入串建立了一棵部分语法树，并且此部分语法树已经覆盖了子串w1，但却无法再扩大而覆盖ai。此时，就必须确定如何修改源程序来“更正”这个错误。v可以采用如下的修改措施：v（1）删去符号ai再进行分析v（2）在w1和ai之间插入一终结符符号串x，把上面的式子改为：w1xaiw2v（3）在

29、w1和ai之间插入一终结符符号串x，但是从ai开始分析；v（4）从w1的尾部删除若干符号v3LR分析中的错误校正vLR分析器是根据分析表来确定各个分析动作。当分析器处于某一状态S并面临输入符号为a时，就以符号对(S,a)查LR分析表。如果分析表中ACTIONS,a栏为“空”，就表明已经发现了一个语法错误，此时分析器应调用相应的出错处理子程序进行处理。因此，可以在ACTION表的每一个空白项中填入一个指向相应出错处理子程序的指示字，至于每一出错处理子程序所完成的操作则可以根据各类语法错误所在语法结构的特点预先进行设计。通常各出错处理子程序所要完成的校错操作无非是从分析栈或余留输入字符串插入、删除

30、或修改一些符号；然后，由于LR分析器的各个归约动作总归是正确的，故在设计出错处理程序时，应避免将那些与非终结符相对应的状态从栈中逐出。v由于程序设计语言的语义描述不存在一种被广泛接受的形式化方法，因此也就给语义错误的校正带来了较大的困难，以致没有一种较为系统且行之有效的出错处理方法。v语义错误主要来源于源程序中错用了标识符或表达式。校正此种错误的一种简单的方法，是用一个“正确”的标识符或表达式去代替出错的标识符或表达式，并把新的标识符登入符号表，同时根据出错处的上下文尽可能将与之相关联的一些属性填入相应的登记项内，然后修改源程序中有关的指示字使之指向这个新的登记项。10.4一个符号表的设计实例

31、v在第3章的词法分析中已经介绍了词法分析，知道高级语言的单词分为保留字、标识符、常数、分隔符以及运算符。单词要有类别和相应的值，对于标识符可以分成多种类型，有变量名、常量名、数组名和函数名。在编译过程中，还要登记各种信息，这些信息有时也需要一些表来登记，下面就介绍一个设计符号表的例子了解以下符号表的实现。v保留字和特殊符号表v保留字和特殊符号表如表10-3 所示。单词代码名字intcharfloatvoidconstifelsethen单词代码101112131415161718名字repeatuntilreadwriteend单词代码192021222324252627名字+*/()单词代码

32、282930313233343536名字=，；：单词代码373839404142434445名字？代码种类保留字变量结构常量结构数组结构代码种类函数结构全局变量出错结构（回车）vstruct b1v vchar name20;/*变量名字*/vint type;/*变量类型*/vint start; /*相对地址*/vint line20; /*在源代码中出现的行号*/vint layer; /*所处的层次*/vstruct b1 *next; /*变量的结构指针*/vv常量结构（代码2）：vstruct c1vvchar name20;/*名字*/vint type;/*常量类型*/vint

33、 a; /*常量为整型，则a 存放其值*/vfloat b; /*常量为实型，则b存放其值*/vchar c80; /*常量为字符型，则c存放其值*/vint line20; /*在源代码中出现的行号*/vint layer; /*所处的层次*/vstruct c1 *next; /*常量的结构指针*/vv数组结构（代码3）：vstruct shzv vchar name20;/*名字*/vint type;/*类型*/vint start; /*相对地址*/vint line20; /*在源代码中出现的行号*/vint layer; /*所处的层次*/vstruct shz *next; /

34、*数组的结构指针*/vv函数结构（代码4）：vstruct hshv vchar name20;/*名字*/vint type;/*类型*/vint line20; /*在源代码中出现的行号*/vint layer; /*所处的层次*/vstructvvoid p;/*指向参数变量结点的指针*/vint style;/*参数变量结点的类型，即所指指针结点的结构类型*/vcsh5;/*指向参数的指针数组*/vstruct b1 *a; /*常量结构指针*/vstruct c1 *b; /*变量结构指针*/vstruct shz *c; /*数组结构指针*/vstruct hsh *next;/*函数结构指针*/vv全局变量结构（代码5）：vstruct cjblv vint layer; /*所处的层次*/vstruct b1 *a; /*常量结构指针*/vstruct c1 *b; /*变量结构指针*/vstruct shz *c; /*数组结构指针*/vstru