《第9章符号表.ppt》由会员分享，可在线阅读，更多相关《第9章符号表.ppt（57页珍藏版）》请在三一文库上搜索。
1、第9章 符号表,9.1符号表的作用和地位 9.2符号的主要属性及作用 9.3符号表的组织 9.4 符号表的管理,符号表的作用和地位: 收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据,9.1符号表的作用和地位, 收集符号属性 编译程序扫描说明部分收集有关标识符的属性，并在符号表 中建立符号的相应属性信息。例如，编译程序分析到下述两 个说明语句 int A; float B5; 则在符号表中收集到关于符号A的属性是一个整型变量，关于符号B 的属性是具有5个浮点型元素的一维数组。, 上下文语义的合法性检查的依据： 在语义分析中，符号表所登记的内容将用于语义检查（如检查
2、一个 名字的使用和原先的说明是否一致）和产生中间代码。通过符号表中属性记录可进行相应上下文的语义检查。 例如，在一个C语言程序中出现 int i 35; /定义整型数组i float i42; /定义实型数组i,重定义冲突 int i 35; /定义整型数组i,重定义冲突 编译过程首先在符号表中记录了标识符i的属性是35个整型元素的数组，而后在分析第二、第三这两个定义说明时编译系统可通过符号表检查出标识符i的二次重定义冲突错误。本例还可以看到不论在后二句中i的其它属性与前一句是否完全相同，只要标识符名重定义，就将产生重定义冲突的语义错误。,在目标代码生成阶段，当对符号名进行地址分配时，符号表是
3、地址分配的依据。, 作为目标代码生成阶段地址分配的依据,一张符号表的的组成：包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。,在整个编译期间，对于符号表的操作大致可归纳为五类： 对给定名字，查询名字是否已在表中； 往表中填入一个新的名字； 对给定名字，访问它的某些信息； 对给定名字，填写或更新它的某些信息； 删除一个或一组无用的项。 上述五个方面只是一些基本的共同操作。,符号表的主要属性(信息）,几种通常都是需要的。 1 名字 2 类型 3 存储类别 4 作用域及可视性 5 存储分配信息 6 其
4、它属性 （） 数组内情向量 （） 记录结构型的成员信息 （） 函数及过程的形参,9.2符号的主要属性及作用, 符号名 符号表中设置一个符号名域，存放该标识符，该域通常就是符号表的关键字域。, 符号的类型 标识符中除过程标识符之外，函数和变量标识符都具有数据类型（data type）属性。对于函数的数据类型指的是该函数值的数据类型。基本数据类型有整型、实型、字符型、逻辑型（布尔型）及位组型等，符号的类型属性是在该符号的定义时得到。变量符号的类型属性决定了该变量的数据在存储空间的存储格式，还决定了在该变量上可以施加的运算操作。, 符号的存储类别 大多数语言对变量的存储类别定义采用二种方式。 一种是
5、用关键字指定： 例如在C语言中用Static定义是属于文件的静态存储变量或属于函数内部的静态存储变量，用regist定义使用寄存器存储的变量。 另一种方式是根据变量说明在程序中的位置来决定： 例如在C语言中，在函数体外缺省存储类关键字所定义的变量是外部变量，即程序的公共存储变量，而在函数体内缺省存储类关键字所定义的变量是内部变量，即属于该函数所独有的私有存储变量, 符号的作用域及可视性 一个符号变量在程序中起作用的范围，称谓它的作用域。一般来说，定义该符号的位置及存储类关键字决定了该符号的作用域。C语言中一个外部变量的作用域是整个程序，因此一个外部变量符号的定义在整个程序中只能出现一次。,一般
6、来说一个变量的作用域就是该变量可以出现的场合，这就是变量可视性的作用域规则。但是变量可视性不仅仅取决于它的作用域，还有两种情况影响到一个变量的可视性。, 函数的形式参数：影响变量可视性的举例 int a； / 外部定义的整型变量a int func(a,b) float a； / 函数内部定义的局部整型变量a, 屏闭了外部定义的整型变量a int b； a / 引用的是函数内部定义(此处是形参)的局部整型变量a 函数的形式参数可以和该函数外层定义的变量（包括外部变量）重名，这时两个重名的变量其类型定义可以是完全不同的。, 分程序（或复合语句）结构： 影响变量可视性的举例 int a； / 第一
7、层头,定义的局部整型变量a char a； / 第二层头,定义的局部字符型变量a / 第三层头 float a； / 第四层头,定义的局部实型变量a / 第四层尾 a / 引用第二层定义的局部字符型变量a / 第三层尾 / 第二层尾 / 第一层尾 图中第三层所引用的a，既不是第四层的float a；也不是第一层int a；而是第二层char a；也就可以说从第三层向外，看到的第一个定义a的变量定义即char a。 为确立符号的作用域和可视性。符号表属性中除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次。符号表中设置一个表达符号所在层次的属性域，存放该符号的定义层次。一般来说，
8、若把外部变量视为0层的话，则函数内部作为第1层，依次向内嵌套定义的分程序分别为2，3，层。, 符号变量的存储分配信息 通常一个编译程序有两类存储区，即静态存储区和动态存储区； 静态存储区 该存储区单元经定义分配后成为静态单元，即在整个语言程序运行过程中是不可改变的。作静态分配的符号变量是具有整个程序运行过程的生命周期。因此编译程序可以设置一个固定的空间作为静态存储区。 但由于不同的静态变量具有不同的可视性，编译程序也可以设置几个不同的固定空间作为静态区。根据变量存储类别及作用域规则，这类静态存储区通常又可分为公共静态区和若干个局部静态区。 一个语言程序中的公共变量或称外部变量是被指定分配到该公
9、共静态存储区中。例Pascal或C语言中的外部量就属于这类共静态存储区的分配。在公共静态区中的变量具有的生命周期是该程序运行的全过程，且其作用域亦是整个语言程序（注意：当它被同名局部量屏蔽时，该变量成为不可视的）。, 动态存储区 根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡。 局部动态变量的生存期是定义该变量的局部范围，即在该定义范围之外此变量已经没存在的必要。及时撤销时这些单元的分配可以回收，从而提高程序运行时的空间效率。,符号的其它属性 数组内情向量 内情向量包括数组类型，维数，各维的上、下界及数组首地址，这些属性信息是确定存储分配时数组所占空间的大
10、小和数组元素位置的依据。 记录结构型的成员信息 一个记录结构型的变量，在存储分配时所占空间大小要由它的全体组成成员来确定，另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。 函数及过程的形参 每个函数或过程的形参个数、形参的排列次序及每个形参的类型，都体现了调用该函数或过程时的属性，它们都应该反映在符号表的函数或过程标识符的项中。,9.3 符号表的组织,总体组织和表项属性信息组织 （P197198页的图） 第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表 第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表 第三种
11、折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。,9.3.1 符号表的总体组织,编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。,9.3.2 符号表项的排列,符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。在编译程序的整个工作过程中，符号表被频繁地用来建立表项，找查表项，填充和引用表项的属性。因此表项的排列组织对该系统运行的效率起着十分重要的作用。在编译程序中，符号表项的组织传统上采用三种构造方法。即线性法，二分法及散列法。, 线性组织 这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录。,例如有一程
12、序中出现符号的情况如下： a /第一次出现a的地方 b /第一次出现b的地方 a /第二次出现a的地方 d /第一次出现d的地方 c /第一次出现c的地方 b /第二次出现b的地方 则符号表中表项排列将如图所示： 其中h表示该符号表之表头，是表的开始位置，p表示该符号表的表项是符号表当前的结束位置。, 排序组织及二分法 语言中的每一个符号，排序组织的符号表，就是在符号表中的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的。对上述例子中的符号出现情况按排序组织得到的符号表将如图所示：,编译扫描的次序是a，b，d，c。由于c代码小于d代码，因此c应在d表项之前。
13、关于排序表的表项建立及符号查找，通常采用“二分法“。, 散列组织 一个符号在散列表中的位置，是由对该符号（即字符代码串）进行某种函数操作（通常称为“杂凑函数“）所得到的函数值来确定的。所得到的函数值与该表项在表中位置的对应关系，是通过对函数值的“求整“以及相对于表长的“求余“得到的。符号表的散列组织相对来说具有较高的运行效率，因而绝大多数编译程序中的符号表采用散列组织。,但是经过杂凑运算后，就有可能得到相同的杂凑值，这种不同符号散列到同一表项位置的现象，我们称它为散列冲突。大多数编译程序中，解决冲突采用的多次散列方法如下。从冲突点位置向下寻找空表项，找到的第一个空表项即为发生冲突的符号所散列的
14、位置。如若一直到表底，没有找到空表项，则循环从表头开始寻找空表项，如若一直到冲突点仍设有空表项，则说明该语言程序中的符号太多，符号表已不能容纳全部符号登入，这时编译程序将发出符号表溢出的系统出错消息。,9.3.3 关键字域的组织,符号表的关键字域（段）就是符号名称 等长关键字域（段）符号表 不等长关键字段符号表-采用关键字池的索引结构。,为使得符号表中存放标识符的关键字段等长，可设置关键字段为标识符的最大长度。譬如上述C语言的关键字段长度可以是32个，图示如下。,等长关键字域（段）符号表,由于程序中的标识符长短不一,有时可能差别很大,用等长结构会产生溢出或冗余。,不等长关键字段符号表-采用关键
15、字池的索引结构。,例如我们有一组标识符 an exempler of key-wrds field 关键字段的组织结构如图。 在此结构中，关键字池可以是一个字符数组，也可以是一个字符串空间。如果关键字池是字符数组时，符号表中关键字段可以是一个整型数值段，整型值表示该关键字在池中位置的下标。若关键字是一个字符串，则符号表中关键字段可以是一个指向字符的指针，指针指向该关键字在池中的位置。P是指向池的空区。,9.3.4 其它域的组织 符号表属性域的组织，根据属性性质大致分成两类：1、等长属性值域组织 可以取相应的数据类型表达属性值。,（1）表示该符号布尔性质的属性域，可用1个bit位来表示；也 可用
16、1个布尔量来表示。如,（2）表示符号的数据类型可以用若干个bit位来表示；也可用1个整型量来表示（C语言为例）,或,有一些是表示符号之间关系的属性，可用指针或指针链来构造这些属性域。如函数符号与它的形参符号之间就需要建立关系，可以在符号表中设置一个“函数-形参”指针域。 对函数符号：在该属性域中存放指向该函数第一个形参的符号所在符号表中位置的指针。 而对形式参数符号：在该属性域中存放指向它的下一个形式参数符号所在符号表中的位置的指针。 若一个函数是无参的，则该参数符号项中“函数形参”指针域值为“空”。 若某个形式参数是它所属函数的最后一个形式参数，则该形参符号项中“函数形参”指针域值亦为“空”
17、。 举例如下：有函数 func1 (para1, para2, para3) func2 (),C语言的结构量中结构标志与成员之间也有上述函数与形参之间的相似关系，也可以在符号表中设立一个“结构-成员”指针域。 对于结构标志符号：在该属性域中存放指向该结构第一个成员的符号在符号表中的位置的指针， 而对于成员符号：在该属性域中存放指向它的下一个成员的符号在符号表中位置的指针。 若某个成员是一个结构量的最后一个成员：则该成员符号项中“结构成员“属性域值为空。,struct tag1 memb1; /第一层结构定义, tag1的第一个成员 memb2; /tag1的第二个成员 struct tag2
18、 memb3; /第二层结构定义, /tag2的第一个成员 memb4; /tag2的第二个成员 memb5;/tag2的第n个成员 memb6; /tag1的第三个成员 memb7; stv;/tag1的第m个成员,2、不等长属性值域的组织 符号的某些属性值是不等长的，例如数组内情向量属性值是典型的不等长属性值。对于不等长属性值的属性域，一般不把所有属性值都存放在符号表项的某个域内，而另设相关空间存放属性值。 一个数组的内情向量属性可分成两种值，数组维数的个数及每维的元素个数。,设有下列两个数组 array1(subscrip1,subscrip2) array2(subscrip3,sub
19、scrip4,subscrip5,subscrip6),数组符号在符号表项中可以设立一个指向内情向量空间的指针，而在内情向量空间记录关于该数组的维数个数和每一维的元素个数，下页图表示了array1及array2两个数组在符号表中内情向量的组织。,内情向量空间最后一行“0“值用来表示下标到此为止，,9.3.5下推链域的组织 为了实现这种同名标识符的语义功能，符号表中需设立一个下推链域组织。,例：有一个C程序： int i ; .(1) . func( ) (2) float i; . (3) . (4) int i5 ;（5） . (6) int i;(7) i(8) .i(9) ,下推链域要求
20、:在进入内层结构并发生重名标识符定义时，需把当前符号中外层的该符号下推到下推链中，而在符号表被下推的表项处，建立内层的同名标识符表项。,9.4 符号表的管理 在编译程序工作过程中，符号表所起的作用反映了符号表的行为特征，符号表的行为通常主要是符号表的初始化、符号的登录、符号的查找和有关分程序结构的符号表层次管理。对符号表的这些管理除初始化之外，都是动态进行的。,1、符号表的初始化 表符号的初始化，就是在对语言程序开始编译的时刻，定义建立符号表的初始状态。符号表的不同组织方法，要求不同的初始化方法。通常有以下两种情况：, 符号表的表长是渐增变化的情况 线性组织和二分法组织的符号表，其表的长度反映
21、已登录表项个数，在编译开始时通常为“0“，而随着符号的逐步登录，表长增长。按这类方法组织的符号表，其初始化方法只需将表尾推向表头即可。,渐增符号表初态, 符号表的表长是确定的情况,例：散列组织的符号表，其表长通常是确定的，这时的表长并不反映已登录的表项个数，是否已有表项登录是取决于该符号表中是否存在已有表项值的表项。因此对这类符号表的初始化方法，需要将表中全部表项值清除。,定长符号表初态,2 符号的登录 当编译程序从语言程序中获得一个标识符符号并确定该符号在符号表中尚不存在时，就要将此符号登录到符号表中。,登录符号到符号表中，首先要确定登录的位置。但对于线性方法组织的符号表，首先要在符号表中创
22、立一个新的表项，通常该表的尾指针指向的表项是作为新创建的表项，而尾指针向下一个备用表项。对于线性组织的符号表，该新创建的表项就是登录符号的表项。,对于二分法组织的符号表，在创建了新的表项后，根据登录符号在符号表中按词典排序所确定的位置，把该位置以后的所有原表项下移一个表项的位置，然后在选定位置登录新符号。,排序符号表登录前后,对于散列表，新符号的登录是通过杂凑算法决定登录表项的位置。,3、符号的查找 每当编译程序从语言源程序获得一个符号，首先要确定该符号的类别。根据类别分别在相应的符号表中进行查找。,通常先在保留字表和运算符表中查找该符号是否保留字或运算符。若是，则相应地把该符号转换为保留字或
23、运算符的内部代码。若不是，则再在标识符表中进行查找。若在标识符表中查到同名符号，则表示该符号已在符号表中登录，若查不到，则表示该符号是一个新的需要登录的符号。,查找符号表的目的:是建立或确认该符号的语义属性。 (1)对查到的符号来说，可获得该符号已登录的语义属性，从而进行语义上下文的检查， (2)在有些情况下登录该符号的新的属性内容 (3)对没查到的符号，则进行符号及其属性的登录。,符号表中分程序结构层次的管理,对于具有分程序型结构的语言程序，不同层次分程序中定义的标识符号具有不同的作用域和不同的可视性规则。通常对于具有分程序结构的语言可用两种方式组织它们的符号表： 一是对每个分程序建立一个独
24、立的分表结构的符号表； 一是把各分程序符号组织在一张单表结构的符号表中。 下面给出了一个分程序结构的例子。,(1) 分表结构 分表结构的组织管理，其基本思想是，每当编译程序扫描到一个分程序结构开始时，为该分程序建立一张符号表，在该分程序中定义的标识符，都被登录在该符号表中。而当编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符号表。这种符号表的分表结构与源程序的分程序层次结构是完全一致的，这种层次结构是编译过程中动态建立和动态消亡的。,分程序结构的分表组织,根据分程序作用域和可视规则。符号的查找是首先在该分程序符号表中进行；若没有查到，再根据分程序的层次结构，逐层向外地依次查找
25、各层符号表。一直到查到为止。 第四层分程序的表达式a=b+c+d中a是第二层定义的float a,b是第一层定义的float b,c是第三层定义的float c，d是第四层定义的float d。,(2) 单表结构 单表结构的组织管理其基本思想是，所有分程序中定义的标识符都集中在单张符号表中。为了实现分程序构造中标识符的作用域和可视性规则的要求。在这种单表组织的符号表中，由于分层的分程序结构，因此需要强调三个主要的特定要求。,首先，为了标志一个符号所属的分程序层次，在符号表中可设立一个属性域用来登录符号所在分程序的层次。,其次，进入分程序时，层次要增加一层.在退出一个分程序时，层次降低一层，且需
26、要把符号表中，所有在退出的分程序中登录的符号项清除。,最后，对于具有分程序结构的源程序，在不同的分程序中(指嵌套的分程序中)允许定义重名的标识符，在单表结构下，重名标识符可用下推链来组织,说明部分的分析与处理,对每个过程说明的对象（变量，常量和过程）造名字表 填写标识符的所在层次、属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成。,说明部分的分析与处理（程序）,说明类型的定义： object= (constant, variable,procedur) （定义纯量/枚举类型）（P413） 名字表的定义（ P414) table:array0txmax
27、 of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size:integer);,例程序说明部分为： CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G ；,名字 类型 层次/值 地址 存储空间,Const（常量）无层次,对应名字表,主函数中调用block函数。 Block函数定义见P417 Block的过程体见P424,例如：对变量定义的语法处理 语法：: := var ， ； 程序：(P424),变量说明处理程序
28、： (P 418),过程ENTER的实现程序：(P417),case k of constant: begin if numamax then begin error(31); num:=0; end; val:=num;(* tabletx.val:=num;常量的值记录在table表中 *) end; variable: begin level:=lev;（*表示tabletx.level:=lev变量定义的所在层次记录 在table表中 *） adr:=dx;（*表示tabletx.adr:=dx给变量分配的位置记录在table表中 *） dx:=dx+1;（*给变量分配位置的指示器加1，指向下一个变量的位置*） end; procedur: level:=lev； (* 表示tabletx.level:=lev;过程定义的所在层次记录在table表中 *） end(* case *);,end end(*enter*);,PL/0编译程序,Table表的下标指针tx补充说明：,主程序,BLOCK,第1次调用block BLOCK（0，0，）,0,0,.,BLOCK,BLOCK（LEV+1,TX，） (递归进入分程序),LEV,tx,LEV,tx,（6）,6 （9）,1,tx是BLOCK的 实际值参,