编译原理课件06符号表的组织与管理.ppt

《编译原理课件06符号表的组织与管理.ppt》由会员分享，可在线阅读，更多相关《编译原理课件06符号表的组织与管理.ppt（92页珍藏版）》请在三一办公上搜索。

1、第6章 符号表的组织与管理,6.1 符号表的作用6.2 符号表的组织6.3 符号表的建立和查找本章小结,知识结构,6.1 符号表的作用,一.符号表作用存放语言程序中出现的有关标识符的属性信息。编译程序护理标识符时主要涉及两部分信息：标识符本身与标识符相关的信息，如标识符的类型、种属、作用域等等,二.符号表的功能,收集有关标识符的属性，并在符号表中建立符号的相应属性信息例如：int A;float B5;上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性例如，在C语言中同一个标识符可作引用说明和定义说明int i3,5;/定义说明iextern float i;/引用说明i,

2、例如：int i3,5;float i4,2;int i3,5;,3.作为目标代码生成阶段地址分配的依据除语言中规定的临时分配存储的变量i外，每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）符号变量由它被定义的存储类别或被定义的位置来确定首先要确定其被分配的区域其次是根据变量出现的次序而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中,符号的主要属性及作用,语言符号可分为：关键字符号、操作符符号、标识符符号1.符号名：标识符：变量的名字、函数的名字、过程的名字通常把一个标识符在符号表中的位置的整数值称之为该标识符的内部代码在经过分析处理的语言

3、程序中标识符不再是一个字符串而是一个整数值,2.符号的类型：除过程标识符之外函数和变量标识符都具有数据类型属性对于函数的数据类型指的是该函数值的数据类型。基本数据类型有整型、实型、字符型、逻辑型及位组型等，符号的类型属性是在语言程序中该符号的定义中得到变量符号的类型属性决定了该变量的数据在存储空间的存储格式，还决定了该变量上可以施加的运算操作例如t*2n、a+b,3.符号的存储类别：一种是用关键字指定，例如在FORTRAN中用COMMAN来定义公共存储区变量，用SAVE来定义函数或过程的内部静态存储变量，在C语言中用static定义是属于文件的静态存储变量或属性函数内部的静态存储变量，用reg

4、ist定义使用寄存器存储的变量,另一种方式是根据定义变量说明在程序中的位置来决定，例如在C语言中，在函数体外默认存储类关键字所定义的变量是外部变量，即程序的公共存储变量，而在函数体内默认存储类关键字所定义的变量是内部变量，即属性该函数所独有的私有存储变量,4.符号的作用域及可视性：一个符号变量在程序中起作用的范围，称为它的作用域一般来说，定义该符号的位置及存储类关键字决定了该符号的作用域C语言中一个外部变量的作用域是整个程序FORTRAN语言中的公共变量的作用域并不是整个语言程序，而仅是那些定义说明了它所在公共块的函数及过程。除非程序中所有函数及过程中全部说明了该公共块时，该公共变量的作用域才

5、是整个程序,C语言中，函数外说明的定义的静态变量的作用域是定义该静态变量的文件，而在函数内部定义的静态变量与FORTRAN的SAVE变量一样，其作用域仅仅是该变量定义所在的函数或过程中一般来说，一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可引用的，这就是变量可视性的作用域规则。但是变量可视性不仅仅取决于它的作用域,还有两种情况影响到一个变量的可视性,（1）函数的形式参数：通常函数的形式参数是作为函数的内部变量处理的。例如：int a;int func(a,b)float a;int b;a/引用float a,上例改写为：int a;int func(a,b

6、)float a;int b;a/引用float a:a/引用int a,（2）复合语句分程序结构：在一个函数中可以建立一个程序块，该程序块中有自己的说明部分和执行部分，且这程序块还可以具层次的嵌套结构，例如：int a;char a;float a;a/引用char a;符号表属性中除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次,5.符号变量的存储分配信息：根据符号变量的存储类别定义及它们出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置,（1）静态存储区：该存储区单元经定义分配后成为静态单元，即在整个语言程序运行过程中是不可改变的。作静态分配的符号变量是

7、具有整个程序运行过程的生命周期。分为：公共静态区、若干个局部静态区,（2）动态存储区：根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡。通常在符号表中存放具体位置的信息是按该变量的存储区类分别依出现先后的次序排列下相对该存储区表头的相对位移量来表示的,例如，对于外部量（C语言为例）：int a;float b;struct cc int d;float e;c;,其中a,b,c是3个外部量，d,e是结构分量，则在符号表中，这5个变量项有关存储位置的属性信息如图9.1所示：,6.符号的其他属性：（1）数组内情向量：包括数组类型、维数、各维的上下界、数组首地址（

8、2）记录结构型的成员信息：成员及成员排列次序确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置（3）函数及过程的形参：每个函数或过程的形参个数、形参的排列次序及每个形参的类型都体现了调用该函数或过程属性。有关函数及过程的形参属性信息用来作调用过程的匹配处理和语义检查,6.2 符号表的组织,一.符号表的总体组织第1种：按照属性种类完全相同的那些符号组织在一起优点：每个符号表中存放符号的属性个数和结构完全相同缺点：一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度,第2种：把所有语言中的符号都组织在一张符号表中优点：总体管理非常集中单一，且不同种类符号的共同属性可一致地管

9、理和处理缺点：增加了符号表管理的复杂度,假设有下列3类符号及其所需之属性：,第1种组织方法得到三张符号表如图9.2所示：,第2种组织方法得到一张符号表如图9.3所示：,第3种：折中方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性按折中方式重新组织上例中的3类符号，可构成2张符号表如图9.4所示：,属性值3、4合并后如图9.5所示：,二.符号表项的排列1.线性组织：这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录,例如，有一程序中出现符号的情况如下：abadcb,则符号表中表项排列将如图9.6所示：h表示该符号表之表头，是表的开始位置p表示该符号表的表

10、项是符号表当前的结束位置,2.排序组织及二分法：排序组织的符号表，就是在符号表中的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的关于排序表的表项建立及符号查找，通常采用“二分法”,对上述例子中的符号出现情况按排序组织得到的符号表将如图9.7所示：,3.散列组织：一个符号在散列表中的位置，是由对该符号进行某种函数操作（杂凑函数）所得到的函数值来确定的假设选定杂凑函数fhash，对符号代码值杂凑运算之后得到杂凑值是Vhash，可表示为：Vhash=fhash()设符号的散列位置Lhash则有：Lhash=mod(Vhash,N)，其中N为散列表的表长一个具有符

11、号代码值为Vsymbol的表项散列如图9.8：,散列冲突：不同符号散列到同一表项位置的现象解决办法：表长N取一个素数、多次散列杂凑函数的选取是构造散列表的关键目前编译程序中，一般采用对符号代码的位操作作为杂凑函数，见得最多的是符号代码的字符段叠加或加权叠加以及符号代码的对折或多折等位操作,三.关键字域的组织在编译程序中，符号表的关键字域就是符号本身，它可以是语言的保留字，操作符号或标识符（包括变量名、函数名、记录结构标志等）规定外部规则的目的是考虑到操作系统、汇编程序及其需要联系的系统之间的匹配，而规定内部规则的目的是考虑到编译程序本身对标识符的识别和区分,比如上述C语言的关键字段长度可以是3

12、2个（其中31个是存放名字，余下一个是存放字符串结束标志，这是C语言处理所需要的），如图9.9所示：,既要保证关键字段的等长，又要减少甚至消除冗余，采用关键字池的索引结构是可取的例如，一组标识符：anexemplarof key-wordsfield,关键字段的组织结构如图9.10所示：,四.其他域的组织1.等长属性值域组织：可以取相应的数据类型表达属性值表示该符号布尔性质的属性域，可用1个bit位来表示，也可用1个布尔量表示：defined 1表示已定义defined 0表示没定义defined true 表示已定义defined false表示没定义表示符号的基本数据类型可以用3个bit位

13、来表示，也可用 1个整型量来表示（C语言为例）：,data-type 3个bit位 char 0 0 0 short 0 0 1int 0 1 0 long 0 1 1unsigned 1 0 0 float 1 0 1double 1 1 0,data-type 整型值char 0 short 1int 2 long 3unsigned 4 float 5double 6,若一个函数是无参的，则该函数符号项中“函数形参”指针域值为“空”，若某个形式参数是它所属函数的最后一个形式参数，则该形参符号项中“函数形参”指针域值为“空”例如，有函数：func1(para1,para2,para3)fu

14、nc2(),在符号表中得到如图9.11的表示：,若某个成员是一个结构量的最后一个成员，则该成员符号项中“结构成员”属性域值为空,例如，有一个结构：struct tag1 memb1 memb2 struct tag2 memb3 memb4 memb5 memb6 memb7 stv;,它在符号表中如图9.12所示：,2.不等长属性值域的组织：数组内情向量属性分成：维数的个数、每个维的元素个数设有下列两个数组：array1(subscrip1,subscrip2)array2(subscrip3,subscrip4,subscrip5,subscrip6)数组符号在符号表项中可以设立一个指向内

15、情向量空间的指针，而在内情向量空间记录关于该数组的维数个数和每一维的元素个数,图9.13表示了array1、array2在符号表中内情向量的组织,一个数组在C语言中被定义为（具有n维时）：type arraysubscrip1subscrip2subscripnarraynumb1,arraynumb1numb2,arraynumb1numbn-1arraynumb1是指向n-1维的数组的指针，指向的目标长为:subscrip2*subscripn*sizeof(type)arraynumb1numb2是指向n-2维的数组的指针，指向的目标长为:subscrip3*subscripn*size

16、of(type)arraynumb1numb2numbn-1是指向一维的数组的指针，指向的目标长为:subscripn*sizeof(type),在C语言中可以定义如下一个数组：type arraysubscrip2subscripn例如，int abc34的排列和各种指针所指向的位置，如图9.14所示：,对于C语言中一个一般形式定义的数组：type arrays1s2snarray 指针值addr目标长l1array0 指针值addr 目标长l2array00 指针值addr 目标长l3 array000 指针值addr 目标长ln其中：addr是数组分配的地址：lk=sk*sk+1*sn*

17、sizeof(type)k=1,2,n而array000是该数组的第1个元素,有关指针值的计算是：arrayi1=array0+i1arrayi1i2=array00+(i1*s2+i2)arrayi1i2i3=array000+(i1*s2+i2)*s3+i3)arrayi1i2ik=array00+(i1*s2+i2)*s3+ik)(k=1,2,n-1)数组元素的地址计算：arrayi1i2in=array00+(i1*s2+i2)*s3+in)*sizof(type),用成员的索引结构来构造结构量，这时结构标志符号在符号表项中设一个指向成员索引区的指针，索引区包含两种属性信息：该结构的空

18、间尺寸、成员索引信息上述结构例子struct tag1的不等长索引结构可用图9.15所示的组织,在一个符号表中若有若干个用位信息表示的属性时，可把他们组织到一起，甚至可用一个整型数来表达这样的几个位信息属性。这种组织与上述合并不同的是各属性有各自的表项中的位置,例如，有下列的一些符号属性：该变量符号是否已初始化该符号是否是结构成员该符号是否是标号该符号是否是保留字,这些属性都可用1个信息位表示，在符号表中可以把它们组织在一个整型字段中作为一个属性域，而其中相应的信息位置表示上述相应的属性，我们称这种域为复合属性域，如图9.16所示：,五.下推链域的组织为实现这种同名标识符的语义功能，符号表中需

19、要设立下推链域的组织下推链域的组织要求在进入一个内层结构并发生重名标识符定义时，需把当前符号表中外层的该符号表项下推到下推链中而在符号表被下推的表项处建立内层的同名识符的表项例如，设有一个程序（C语言程序）如图9.17所示：,当逐个退出分程序时，下推链被逐次回推到符号表项中，其具体结构如图9.18所示：,6.3 符号表的建立和查找,一.符号表的初始化在编译过程中某个时刻，符号表的状态反映了该时刻被编译的语言程序正被编译的位置的状态。具体来说主要是反映了在该时刻语言程序中可视标识符的状态符号表的初始化，就是在对语言程序开始编译的时刻，定义建立符号表的初始状态,1.符号表的表长是渐增变化的情况：在

20、中提到的线性组织和二分法组织的符号表，其表的长度在编译开始时通常为0,而随着符号的逐步登录，表长增长按这类方法组织的符号表，其初始化方法只需将表尾推向表头即可，如图9.19所示：,2.符号表的表长是确定的情况：在中提到的散列组织的符号表，其表长通常是确定的，这时表长并不反映已登录的表项个数，是否已有表项登录是取决于该符号表中是否存在已有表项值的表项因此，对这类符号表的初始化方法，需要将表中全部表项值清除。由于通常表示表项值的关键因素是登录标识符的符号栏（也可能是指向符号的指针），因此在清除表项值时，实际上可仅清除符号栏,图9.20表示定长符号表初始化的状态：,二.符号的登录当编译程序从语言程序

21、中获得一个标识符符号并确定该符号在符号表中还不存在，就要将此符号登录在符号表中登录符号到符号表中，首先要确定登录的位置,但对于线性方法和二分方法组织的符号表，首先要在符号表中创立一个新的表项，通常该表的尾指针指向的表项是作为新创建的表项，而尾指针推向下一个备用表项对于线性组织符号表，该新创建的表项就是登录符号的表项,图9.21表示登录新符号symbol i的前后情况：,对于二分法组织的符号表，在创建了新的表项后，根据登录符号在符号表中按词典排序所确定的位置，把该位置以后的所有原表项下移一个表项的位置，然后在选定位置登录新符号,图9.22表示登录新符号symbol k的前后情况：,symbol

22、k,对于散列表，新符号的登录是通过杂凑算法决定登录表项的位置一个符号表项的登录基本的是该符号的名字登录，还有属性登录，名字属性大都取决于编译程序获得某个符号时编译所处的程序扫描点的状态,下例中符号a的属性取决于编译程序扫描到anm时的有关状态：,类型属性：存储类别属性：符号作用域属性：存储分配属性：数组内情向量属性：,三.符号的查找查找符号表的目的是建立或确认该符号的语义属性符号表的查找算法：顺序查找、折半查找、杂凑查找,四.符号表中分程序结构层次的管理（1）分表结构：分表结构的组织管理的基本思想：每当编译程序扫描到一个分程序结构开始时，为该分程序建立一张符号表，在该分程序中定义的标识符，都被

23、登录在该符号表中。而当编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符号表,编译程序扫描到某个分程序时，符号的登录是在为该分程序所建立的符号表中进行，而符号的查找是首先在该分程序符号表中进行；若没有查到，再根据分程序的层次结构，逐层向外地依次查找各层符号表。一直到查到为止。若所有符号表都已查完仍未找到，则表示有词法错误,图9.23给出了一个分程序结构的例子：,图9.24给出了相应的分表结构组织：,（2）单表结构：单表结构的组织管理的基本思想是：所有分程序中定义的标识符都集中在单张符号表中在这种单表组织的符号表中，有三个主要的特定要求：首先，为了标志一个符号所属的分程序层次，在

24、符号表中可设立一个属性域用来登录符号所在分程序的层次,其次，在编译程序扫描进入一个分程序时，表示分程序层次的状态量要增加一层，使进入分程序后定义的标识符登录符号表时，有相应的层次量作为层次属性登录最后，对于具有分程序结构的源程序，在不同的分程序中（指嵌套的分程序中）允许定义重名的标识符,编译过程中符号表的动态管理过程如下：图9.25表示编译程序扫描进入第1层分程序后单表结构的符号表情况,图9.26表示编译程序扫描进入第2层分程序后单表结构的符号表情况：,图9.27表示编译程序扫描进入第3层分程序后单表结构的符号表情况：,图9.28表示编译程序扫描进入第4层分程序后单表结构的符号表情况：,【本章

25、小结】符号表在编译全过程的地位和重要作用登录源程序中定义的标识符的所有属性。对源程序中标识符的定义和引用，进行上下文合法性检查。作为语义处理及代码生成的依据。符号的作用域关系到标识符的生存期，符号的可视性关系到标识的可引用性。两者密切相关，但又不完全相同。标识符的数据类型通过类型声明来定义（默认除外）。而标识符的存储类别不但取决于存储类别声明，而且还取决于该标识符声明在程序构造中的位置。,符号表总体组织的选择应考虑语言文本的复杂性（包括词法结构、语法结构的复杂性），还应考虑到对于编译系统在时间效率和空间效率方面的要求。符号表中属性域的构造原则上是定长的。对于复杂属性可采用索引扩展方式构造。采用

26、复合属性域组织，提高了符号表的空间效率，但增加了表处理的复杂度。采用单表结构时,下推链域的构造用来处理解决分程序构造中同名标识符声明的可视性规则，采用分表结构不存在下推问题。分表结构很适合基于对象的语言的编译系统。,第9章习题第1题：根据你所了解的某个FORTRAN语言的实现版本，该语言的名字作用域有哪几种?第2题：C语言中规定变量标识符的定义可分为extern,extern static,auto,local static和register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登录的存储类属性，在编译过程中支持什么样的语义检查。,第3题：对分程序结构的语言，为其符号表建立重名动态下推链的目的是什么?概述编译过程中重名动态下推链的工作原理。第4题：某BASIC语言的变量名字表示为字母开头的字母或数字两个字节的标识符,该语言的符号表拟采用杂凑法组织，请为其设计实现一个有效散列的杂凑算法，并为解决散列冲突，设计实现一个再散列算法。,第9章作业题P229：2.3.4.,