编译原理第九章

1、2v符号表用来存放源程序中出现的有关名字的属性信息，这些信息集中反映了名字的语义特征属性。v符号表在编译全过程的地位和作用非常重要，是进行上下文合法性检查和语义处理及代码生成的依据。v符号表总体结构的设计和实现是与源语言的复杂性（包括词法结构、语法结构的复杂性）有关，还与对于编译系统在时间效率和空间效率方面的要求有关。31 符号表的作用和地位 v符号表用来存放语言程序中出现的有关标识符的属性信息-信息集中反映了标识符的语义特征属性。在词法分析及语法在分析过程中不断积累和更新表中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。不论编译策略是否分趟，符号表的作用和地位

2、是完全一致的。 4v 收集符号属性收集符号属性 v 上下文语义的合法性检查的依据上下文语义的合法性检查的依据v 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 5 收集符号属性收集符号属性v编译程序扫描说明部分收集有关标识符的属性，并在符号表中建立符号的相应属性信息。例如，编译程序分析到下述两个说明语句 int A;float B5;收集到关于符号A的属性是一个整型变量，关于符号B的属性是具有5个浮点型元素的一维数组。6 上下文语义的合法性检查的依据上下文语义的合法性检查的依据v同一个标识符可能在不同地方出现，而有关该符号的属性是在这些不同情况下收集的。特别是在多趟编译及

3、程序分段编译（在PASCAL及C中以文件为单位）的情况下，更需检查标识符属性在上下文中的一致性和合法性。例如，在一个C语言程序中出现int i 3,5; /定义整型数组ifloat i4,2; /定义实型数组i,重定义冲突int i 3,5; /定义整型数组i,重定义冲突 首先在符号表中记录了标识符i的属性是35个整型元素的数组，而后在分析第二、第三这两个定义说明时编译系统可通过符号表检查出标识符i的二次重定义冲突错误。v只要标识符名重定义，就将产生重定义冲突的语义错误。7 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据v每个符号变量在目标代码生成时需要确定其在存储分配的

4、位置（主要是相对位置）。语言程序中的符号变量由它被来确定。v首先要确定其被分配的区域。公共区（extern）、文件静态区（extern static）、函数静态区（函数中static）、还是函数运行时的动态区（auto）等。其次是根据变量出现的次序,决定该变量在某个区中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。82 符号的主要属性及作用符号的主要属性及作用v符号表中的标识符一般设置的属性项目以及它们的功能v符号名符号名 v符号的类型符号的类型 v 符号的存储类别符号的存储类别 v符号的作用域及可视性符号的作用域及可视性 v符号变量的存储分配信息符号变量的存储分配信息 v符号的

5、其它属性符号的其它属性 9符号名符号名 v语言中的一个标识符可以是一个变量的名字、一个函数的名字或一个过程的名字。每个标识符通常由若干个字符（非空格字符）组成的字符串来表达 v符号表中设置一个符号名域，存放该标识符，该域通常就是符号表的关键字域关键字域 v在符号表中符号名作为表项之间的唯一区别一般不允许重名 10v可以用一个符号在表中的位置来替换该符号名。通常把一个标识符在符号表中的位置的整数值称之谓该标识符的内部代码。v在经过分析处理的语言程序中标识符是一个整数值，便于识别比较 缩短了表达的长度11v程序中出现的重名标识符重名标识符定义将按照该标识符在程序中的作用域和可视性规则进行相应的处理

6、 v重载的标识符要通过它们的参数个数和类型以及函数返回值类型来区别，以达到它们在符号表中的唯一性 12符号的类型符号的类型 v标识符中除过程标识符之外函数和变量标识符都具有数据类型数据类型属性 v符号的类型属性是在语言程序中该符号的定义中得到；变量符号的类型属性决定了该变量的数据在存储空间的存储格式，还决定了在该变量上可以施加的运算操作当一个变量为整型时 为实型时 13v目前大多数语言已定义了在基本数据类型基础上扩充的复合数据类型 v数组或记录结构中的每个基本元素可以是基本数据类型，也可以是其它任何一种组合式数据类型，构成嵌套式数据类型定义 指针类型所指向的变量同样可以是基本数据类型，也可以是

7、其它任何一种组合式数据类型 14符号的存储类别符号的存储类别 v多数语言对变量的存储类别定义采用二种方式：v一种是用关键字指定 v一种方式是根据定义变量说明在程序中的位置来决定 v区别符号存储类型的属性是编译过程语义处理、检查和存储分配的重要依据。符号的存储类别还决定了符号变量的作用域、可视性和它的生命周期等 15符号的作用域及可视性符号的作用域及可视性 v作用域：一个符号变量在程序中起作用的范围v定义该符号的位置及存储类关键字一般决定了该符号的作用域 C语言中一个外部变量 16v一般来说一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可引用的，这就是变量可视性

8、的作用域规则 v两种情况影响到一个变量的可视性 1。函数的形式参数 多数语言中规定该函数中仅能引用作为 该函数形式参数的那个变量 2。分程序（或复合语句）结构 符号表中设置一个表达符号所在层次的属性域， 存放该符号的定义层次 17符号变量的存储分配信息符号变量的存储分配信息 v根据符号变量的存储类别定义及它们出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置，用相对区头的位移量表示。 18v通常一个编译程序有两类存储区，即静态存静态存储区储区和动态存储区动态存储区 v静态存储区静态存储区 该存储区单元经定义分配后成为静态单元，即在整个语言程序运行过程中是不可改变的 v动态存储区

9、动态存储区 根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡 19v作静态分配的符号变量是具有整个程序运行过程的生命周期。编译程序可以设置一个固定的空间作为静态存储区也可以设置几个不同的固定空间作为静态区 v一个语言程序中的公共变量或称外部变量是被指定分配到该公共静态存储区中 Pascal或C语言中的外部量 在公共静态区中的变量具有的生命周期是该程序运行的全过程，且其作用域亦是整个语言程序 注意：当它被同名局部量屏蔽时，该变量成为不可视的 20v为局部静态量可设立若干个局部静态区。对外部静态量，为每个程序文件建立一个局部静态区，对内部静态量，则为每个具有内部

10、静态量定义的函数或过程，建立一个局部静态区 21v根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡。局部动态变量的生存期是定义该变量的局部范围，即在该定义范围之外此变量已经没存在的必要。及时撤销时这些单元的分配可以回收，从而提高程序运行时的空间效率 22v对变量存储分配的属性除了存储类别之外还要确定其在所在存储区的具体位置的属性信息。v通常在符号表中存放具体位置的信息是按该变量的存储区类分别依出现先后的次序（扫描源程序的次序）排列下相对该存储区表头的相对位移量来表示的 23vC语言为例int a; / 外部定义的整型变量afloat b; / 外部定义的实型

11、变量bstruct cc int d; / 外部定义的结构类型cc, cc的第一个结构分量d float e; / cc的第二个结构分量tc; / 外部定义的结构型变量c2425符号的其它属性符号的其它属性 v数组内情向量： 包括数组类型，维数，各维的上、下界及数组首地址，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据 26v记录结构型的成员信息 一个记录结构型的变量，在存储分配时所占空间大小要由它的全体组成成员来确定，另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。这二种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置。27v函数及过程的形

12、参 每个函数或过程的形参个数、形参的排列次序及每个形参的类型，都体现了调用该函数或过程时的属性，它们都应该反映在符号表的函数或过程标识符的项中 283 符号表的组织符号表的组织v编译的整个过程中，符号表是连贯上下文进行语义检查、语义处理，生成代码和存储分配的主要依据，因此符号表的组织直接关系到这些语义功能的实现和语义处理的时空效率 29符号表的总体组织可有符号表的总体组织可有选择选择v第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表 v最大优点是每个符号表的属性个数和结构完全相同 v主要缺点是一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度

13、。而且对各类符号共同属性的管理必须设置重复的运行机制。使得符号表的管理显得臃肿 30v第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表v最大优点是总体管理非常集中单一，且不同种类符号的共同属性可一致地管理和处理 v缺点是必将出现不等长的表项，以及表项中属性位置的交错重叠的复杂情况，这就极大地增加了符号表管理的复杂度 31v为使表项等长且实现属性位置的唯一性，可以把所有符号的可能属性作为符号表项属性。这种组织方法可能有助于降低符号表管理复杂性，但对某个具体符号，可能增加了无用的属性空间，从而增加了空间开销 32v假设有下列三类符号及其所需之属性v第一类符号

14、属性1 属性2 属性3第二类符号 属性1 属性2 属性4第三类符号 属性2 属性5 属性633第一种组织方法得到三张符号表 34第二种组织方法得到一张符号表 35v第三种折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性 v折衷的组织方式在管理复杂性及时空效率方面都取得折衷的效果，并且对复杂性和效率的取舍可由设计者根据自己的经验和要求及目标系统的客观环境和需求进行选择和调整 36按折衷方式重新组织上例中的三类符号 37v第1，2类符号的符号表中，可对不同符号所要求的不同属性值域，采用多态方式的合并 v可以把属性值3和属性值4二栏合并用属性值34来替换，在C

15、语言中可用UNION来实现 v增加符号表管理和运行的复杂性，但减少了空间开销 38分析v第一种组织方法符号表分得太散，对符号表的管理和运行，增加了很大工作量，在实际的语言编译程序中很少采用这种组织方式。v第二种组织方式使符号完全集中，因而对符号表的管理也集中，但是对属性值相差的很大的符号组织在一张表中时，必然将使表的结构及相应的表处理增加了复杂度，在实际的语言编译程序中亦很少采用这种组织方式。v大多数编译系统中采用的第三种符号表组织方法，是上述两种组织方式的折衷 39表项的组织方式 v线性组织线性组织 v排序组织及二分法排序组织及二分法 v散列组织散列组织 40v线性组织线性组织 这种方法规定

16、符号表中表项按它的符号被扫描到的先后顺序登录 v a /第一次出现a的地方b /第一次出现b的地方a /第二次出现a的地方d /第一次出现d的地方c /第一次出现c的地方b /第二次出现b的地方41vh表示该符号表之表头，是表的开始位置，p表示该符号表的表项是符号表当前的结束位置。在编译程序工作过程中，扫描得到之新符号总是登录到p的位置，而p又取下一新位置，编译程序开始工作时p处于h表头位置。v这种组织方式的管理简单但运行效率低，特别当表项数目较大后效率就非常低。因为它没有空白项，因此存储空间效率高，但对于符号个数不确定的情况下，无法事先确定该符号表的总长度。对于事先能确定符号个数且符号个数不

17、大时采用线性表组织是非常合适的 42v排序组织及二分法排序组织及二分法 排序组织的符号表，就是在符号表中的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的 43v关于排序表的表项建立及符号查找，通常采用“二分法”。排序表的空间组织和存储开销与线性表基本相同，但排序表的运行效率要比线性表高，算法复杂性也高于线性表。v排序表有很多变体结构方式，如二叉树结构等，在编译程序中可根据空间开销和运行效率等要求作适当的选取44v散列组织散列组织 一个符号在散列表中的位置，是由对该符号（即字符代码串）进行某种函数操作（通常称为“杂凑函数”）所得到的函数值来确定的。所得到的函

18、数值与该表项在表中位置的对应关系，是通过对函数值的“求整”以及相对于表长的“求余”得到的。v符号表的散列组织相对来说具有较高的运行效率，因而绝大多数编译程序中的符号表采用散列组织。为了提高效率降低算法复杂度，通常杂凑函数采用整数操作。目前编译程序中，一般采用对符号代码的位操作作为杂凑函数，见得最多的是符号代码的字符段叠加或加权叠加以及符号代码的对折或多折等位操作 45Vhashfhash（符号代码值）v散列表的表长通常是一个定值N，为使每一个符号都能散列到这样的符号表中，对于决定该符号散列位置的杂凑值需作进一步的处理。v采用符号的杂凑值对符号表表长求余的处理后，就可使该符号的位置肯定地散列到符

19、号表中了。设符号的散列位置Lhash则有Lhashmod（Vhash，N）4647v经过杂凑运算后，就有可能得到相同的杂凑值 v不同符号散列到同一表项位置的现象，我们称它为散列冲突 v为根本解决冲突，需要采取第二次仍至更多次的散列。大多数编译程序中，解决冲突采用的多次散列方法：从冲突点位置向下寻找空表项，找到的第一个空表项即为发生冲突的符号所散列的位置。如若一直到表底，没有找到空表项，则循环从表头开始寻找空表项，如若一直到冲突点仍设有空表项，则说明该语言程序中的符号太多，符号表已不能容纳全部符号登入，这时编译程序将发出符号表溢出的系统出错消息 48关键字域的组织 v编译程序中标识符的内部规则是

20、符号表关键字组织的基础和依据。v用户程序中的标识符，标识符的长度是从1到内部规则规定长度之间任意字符个数。为使得符号表中存放标识符的关键字段等长，可设置关键字段为标识符的最大长度 49vC语言的ANSI标准中规定了内部名必须至少能由前31个字符唯一地区分 v其中31个是存放名字，余一个是存放字符串结束标志凵 50v标识符长短不一,有时可能差别很大,用等长结构会产生溢出或冗余。希望既保证关键字段的等长，又要减少甚至消除冗余，可采用关键字池的索引结构 v一组标识符anexemplerof key-wrdsfield51其它域的组织其它域的组织v符号表属性域的组织，根据属性性质大致分成两类：v一类是

21、符号表中符号的属性值具有相同的类型且是等长的，则该属性域的类型结构就可用这个长度及类型来定义。v另一类属性值可能具有相同类型但长度不同，则该属性域的定义不能用简单的数据类型来定义。52v等长属性值域组织等长属性值域组织 可以取相应的数据类型表达属性值 defined1表示已定义defined0表示尚未定义或 definedtrue表示已定义definedfalse表示尚未定义53data-type 3个bit位Char000Short001int010long011unsigned100float101double110或 data-type整型值char0short1int2long3uns

22、iqned4float554v符号变量存储分配时，每个变量的存储分配具有两个属性信息，即存储类别和相对存储区头的位移量。存储类别域可与数据类型一样构造，而位移量是用相对存储区头的字节数表示的，因此可以用整型量构造位移量的属性域 55v有一些是表示符号之间关系的属性，可用指针或指针链来构有一些是表示符号之间关系的属性，可用指针或指针链来构造这些属性域造这些属性域 v函数符号与它的形参符号之间就需要建立关系，可以在符号函数符号与它的形参符号之间就需要建立关系，可以在符号表中设置一个表中设置一个函数函数-形参形参指针域指针域 func1 (para1, para2, para3)func2 ()56

23、 v结构标志符号，在该属性域中存放指向该结构第一个成员的符号在符号表中的位置的指针 v成员符号，在该属性域中存放指向它的下一个成员的符号在符号表中位置的指针 57 58v不等长属性值域的组织不等长属性值域的组织v符号的某些属性值是不等长的，例如数组内符号的某些属性值是不等长的，例如数组内情向量属性值是典型的不等长属性值。对于情向量属性值是典型的不等长属性值。对于不等长属性值的属性域，一般不把所有属性不等长属性值的属性域，一般不把所有属性值都存放在符号表项的某个域内，而另设相值都存放在符号表项的某个域内，而另设相关空间存放属性值。关空间存放属性值。一个数组的内情向量属性可分成两种值，一个数组的内

24、情向量属性可分成两种值，数组维数的个数及每维的元素个数。数组维数的个数及每维的元素个数。 59v设有下列两个数组array1(subscrip1,subscrip2)array2(subscrip3,subscrip4,subscrip5,subscrip6)v数组符号在符号表项中可以设立一个指向内情向量空间的指针，而在内情向量空间记录关于该数组的维数个数和每一维的元素个数 6061v一个数组在C语言中被定义为（具有n维时）type arraysubscrip1subscrip2subscripn它是元素为type定义的类型的一个N维数组,它的下标界分别为subscrip1,subscrip2

25、,subscripn。v在C语言中array符号可以看成是指向该数组整体的一个指针出现在程序中，该指针指向的目标是数组，其长度是整个数组的长度。C语言中除了array numb1 numb2numbn是表示为一个数组元素外，其它的表示方法arraynumb1,arraynumb1numb2, arraynumb1numbn-1。都认为是一个数组名，在程序中被作为指针。varraynumb1是指向n-1维的数组的指针，其目标长为：subscrip2 * * subscripn * sizeof(type)arraynumb1numb2是指向n-2维的数组的指针，其目标长为:subscrip3 *

26、 subscripn* sizeof(type)arraynumb1numb2numbn-1是指向一维数组的指针,其目标长为:subscripn * sizeof(type) 62v一个具体数组int abc 342;的排列及各种指针所指向的位置 63v在等长属性值域的组织中讨论了用成员链来组织C语言的结构量符号。也可用成员的索引结构来构造结构量-这时结构标志符号在符号表项中设一个指向成员索引区的指针，索引区包含两种属性信息，即该结构的空间尺寸及成员索引信息 64 65v在一个符号表中有若干个用位信息表示的属性时，可把他们组织到一起，甚至可用一个整型数来表达这样的几个位信息属性 66v下推链域

27、的组织下推链域的组织下推链域组织要求在进入一个内层结构并发生重名标识符定义时，需把当前符号表中外层的该符号表项下推到下推链中而在符号表被下推的表项处建立内层的同名标识符的表项 676869符号表的管理 v符号表所起的作用反映了符号表的行为特征，符号表的行为通常主要是符号表的初始化、符号的登录、符号的查找和有关分程序结构的符号表层次管理 v除初始化之外，都是动态进行的 70v符号表的初始化 v符号表的初始化，就是在对语言程序开始编译的时刻，定义建立符号表的初始状态 v在编译过程中某个时刻，符号表的状态反映了该时刻被编译的语言程序正被编译的位置的状态。具体来说主要是反映了在该时刻语言程序中可视标识

28、符的状态 71v符号表的不同组织方法，要求不同的初始化方法。编译开始时符号表的状态应该没有任何可视标识符的状态 符号表的表长是渐增变化的情况符号表的表长是渐增变化的情况 线性组织和二分法组织的符号表，其表的长度(反映已登录表项个数)在编译开始时通常为0，而随着符号的逐步登录，表长增长。按这类方法组织的符号表，其初始化方法只需将表尾推向表头即可 7273 符号表的表长是确定的情况符号表的表长是确定的情况 散列组织的符号表，其表长通常是确定的，这时的表长并不反映已登录的表项个数，是否已有表项登录是取决于该符号表中是否存在已有表项值的表项 v 对这类符号表的初始化方法，需要将表中全部表项值清除 v实

29、际上可仅清除符号栏 74v这种散列表的表长确定的说法是相对于那种随着表项增加而渐增地变化而言的。为了提高编译程序的处理能力，在某些编译程序中也采用了可扩展表长的散列表组织。为了缓解散列冲突，在散列堆聚严重的位置，另开辟解决冲突的表项或者增加主表的长度。但通常这种方式的扩充不是一个一个表项的增加而是根据情况一组一组地增加。增加的表项必须首先清除其表项值 75符号的登录 v当编译程序从语言程序中获得一个标识符符号并确定该符号在符号表中尚不存在时，就要将此符号登录到符号表中。 v登录符号到符号表中，首先要确定登录的位置 76v对于线性方法和二分法组织的符号表，首先创建一个新表项v通常该表的尾指针指向

30、的表项是作为新创建的表项，而尾指针推向下一个备用表项。v对于线性组织的符号表，该新创建的表项就是登录符号的表项 7778v对于二分法组织的符号表，在创建了新的表项后，根据登录符号在符号表中按词典排序所确定的位置，把该位置以后的所有原表项下移一个表项的位置，然后在选定位置登录新符号 v对于散列表，新符号的登录是通过杂凑算法决定登录表项的位置。 7980v一个符号表项的登录最基本的是该符号的名字登录。除此之外还有关于该名字的属性的登录。名字属性大都取决于编译程序获得某个符号时编译所处的程序扫描点的状态。vfunc(x,y)struct tag int anm,v Yv t; 81v编译程序在 处得

31、到一个标识符号a，当时程序处理的状态决定了符号a的如下一些属性v 类型属性 存储类别属性 符号作用域属性 存储分配属性： 结构成员属性 由于t结构量是函数func中的Auto变量 数组内情向量属性v除了上述这些属性在扫描到该符号时就已具备，并可立即登录之外，还有些符号的属性需要在以后的语法分析过程中逐步获得并登入 82符号的查找符号的查找v每当编译程序从语言源程序获得一个符号，首先要确定该符号的类别。根据类别分别在相应的符号表中进行查找。 v通常先在保留字表和运算符表中查找该符号是否保留字或运算符。若是，则相应地把该符号转换为保留字或运算符的内部代码。若不是，则再在标识符表中进行查找。若在标识符表中查到同名符号，则表示该符号已在符号表中登录，若查不到，则表示该符号是一个新的需要登录的符号 83v查找符号表的目的是建立或确认该符号的语义属性。对查到的符