《编译原理：第8章 符号表管理》由会员分享，可在线阅读，更多相关《编译原理：第8章 符号表管理（30页珍藏版）》请在金锄头文库上搜索。
1、第第8章章 符号表管理符号表管理School of Computer Science & Technology Harbin Institute of Technology重点：重点：符号表的作用符号表的作用, ,符号表的组织结构符号表的组织结构, ,符号符号表与作用域表与作用域。 难点：难点：符号表的组织结构及其性能评价。符号表的组织结构及其性能评价。2024/8/22第第8章章符号表管理符号表管理 8.1 符号表的作用符号表的作用8.2 符号表中存放的信息符号表中存放的信息8.3 符号表的组织结构符号表的组织结构8.4 符号表与作用域符号表与作用域8.5 本章小结本章小结2024/8/23
2、8.1 符号表的作用符号表的作用n编译的各个阶段都有可能会用到符号表中登记编译的各个阶段都有可能会用到符号表中登记的信息的信息n协助进行协助进行语义检查语义检查(如检查一个名字的引用和之前的如检查一个名字的引用和之前的声明是否相符声明是否相符)和中间代码生成和中间代码生成 n在目标代码生成阶段，当需要为名字在目标代码生成阶段，当需要为名字分配地址分配地址时，时，符号表中的信息将是地址分配的主要依据符号表中的信息将是地址分配的主要依据 n编译器用符号表来记录、收集和查找出现在源程序编译器用符号表来记录、收集和查找出现在源程序中的各种名字及其中的各种名字及其语义信息语义信息。2024/8/248.
3、1 符号表的作用符号表的作用n符号表是以名字为关键字来记录其信息的数据符号表是以名字为关键字来记录其信息的数据结构，其上支持的两个最基本操作应该是填加结构，其上支持的两个最基本操作应该是填加表项和查找表项，这两个操作必须是高效的表项和查找表项，这两个操作必须是高效的 2024/8/258.2 符号表中存放的信息符号表中存放的信息n记录源程序中出现的各种名字及其属性信息是记录源程序中出现的各种名字及其属性信息是符号表的首要任务。符号表的首要任务。n显然同一个名字在一段程序中应该表示同一个显然同一个名字在一段程序中应该表示同一个对象，即同一个符号表中不能出现相同的名字，对象，即同一个符号表中不能出
4、现相同的名字，因此名字可以作为符号表的关键字。于是，每因此名字可以作为符号表的关键字。于是，每一个符号表表项中需要存放的基本信息就是符一个符号表表项中需要存放的基本信息就是符号的名字及其属性号的名字及其属性 。图图8.1 符号表的基本格式符号表的基本格式2024/8/268.1.1 符号表中的名字符号表中的名字n名字字段长度固定名字字段长度固定n名字项的长度大小取决于标识符允许的最大长度名字项的长度大小取决于标识符允许的最大长度n不适于标识符长度变化范围较大的语言不适于标识符长度变化范围较大的语言n空间浪费空间浪费 n名字字段长度可变名字字段长度可变n标识符的长度没有限制标识符的长度没有限制
5、n符号表上的操作复杂而低效符号表上的操作复杂而低效 n引入一个单独的字符串表，将符号表中的全部标识符引入一个单独的字符串表，将符号表中的全部标识符集中放在这个字符串表中，而在符号表表项的名字部集中放在这个字符串表中，而在符号表表项的名字部分只要给出相应标识符的首字符在字符串表中的位置分只要给出相应标识符的首字符在字符串表中的位置即可即可 2024/8/278.1.1 符号表中的名字符号表中的名字(a)标识符长度放在符号表中标识符长度放在符号表中2024/8/288.1.1 符号表中的名字符号表中的名字(b) 标识符长度放在字符串中标识符长度放在字符串中2024/8/298.1.1 符号表中的名
6、字符号表中的名字(c) 用0表示标识符的结束2024/8/2108.1.2 符号表中的属性符号表中的属性n符号所表达的含义不同，符号表中需要存放的符号所表达的含义不同，符号表中需要存放的属性也就不同属性也就不同 n数组名字需要存放的属性信息应该包括数组的维数组名字需要存放的属性信息应该包括数组的维数、各维的维长等数、各维的维长等 n函数函数(或过程或过程)的名字应该存放其参数个数、各参数的名字应该存放其参数个数、各参数的类型、返回值的类型等的类型、返回值的类型等 2024/8/2118.1.2 符号表中的属性符号表中的属性n建立多个符号表来管理源程序中出现的各种符建立多个符号表来管理源程序中出
7、现的各种符号，如常数表、变量表、函数表、数组表等号，如常数表、变量表、函数表、数组表等 n可能出现不同种类符号出现重名的问题可能出现不同种类符号出现重名的问题 n建立一张共用的大表来管理各种符号，此时需建立一张共用的大表来管理各种符号，此时需要在符号表中增设一个标志来表明符号的种属要在符号表中增设一个标志来表明符号的种属n不同种类符号所需存放属性信息在数量上的差异不同种类符号所需存放属性信息在数量上的差异将会造成符号表的空间浪费将会造成符号表的空间浪费 8.1.2 符号表中的属性符号表中的属性图图8.3 多种符号共用符号表的一种实现结构多种符号共用符号表的一种实现结构128.1.2 符号表中的
8、属性符号表中的属性图图8.4 用扩展属性链组织函数形参的符号表用扩展属性链组织函数形参的符号表132024/8/2148.1.3 符号的地址属性符号的地址属性n如果采用静态存储分配策略，则符号如果采用静态存储分配策略，则符号x绑定的绑定的地址等于静态分配的基址地址等于静态分配的基址base加上符号加上符号x的偏的偏移量移量offset n如果采用的是栈式存储分配或堆式存储分配等如果采用的是栈式存储分配或堆式存储分配等动态分配策略，则符号是在程序执行过程中和动态分配策略，则符号是在程序执行过程中和地址动态绑定的。地址动态绑定的。 n如栈式存储分配时，如栈式存储分配时，i的地址是以栈指针的地址是以
9、栈指针sp为基址为基址加上加上i相对于活动记录起始地址的偏移量相对于活动记录起始地址的偏移量offseti n符号表中各符号的地址属性就是该符号相对于符号表中各符号的地址属性就是该符号相对于第一个符号的偏移地址第一个符号的偏移地址 2024/8/2158.3 符号表的组织结构符号表的组织结构8.3.1 符号表的线性表实现符号表的线性表实现 n用线性表实现符号表较为直观用线性表实现符号表较为直观n数组实现：插入数组实现：插入n个符号、执行个符号、执行e次查找操作的时次查找操作的时间复杂度为间复杂度为T(n, e) = O(n(n+e) n有序数组实现：插入有序数组实现：插入n个符号、执行个符号、
10、执行e次查找操作次查找操作的时间复杂度为的时间复杂度为T(n, e) = e log n+ + (n+e)log n+O(n2) n有序符号表结构只有在下面的情况下才能取得较有序符号表结构只有在下面的情况下才能取得较好效果：和插入操作次数相比，符号表表项上的好效果：和插入操作次数相比，符号表表项上的查找操作次数占绝对多数，即查找操作次数占绝对多数，即en。 2024/8/2168.3.2 符号表的散列表实现符号表的散列表实现 n引入散列表不仅可以提高引入散列表不仅可以提高lookup操作的效率，操作的效率，同时也可以提高同时也可以提高insert操作的效率，所以在许操作的效率，所以在许多实际编
11、译器的符号表实现中均采用了散列多实际编译器的符号表实现中均采用了散列技术技术图图8.6 一个符号表的散列表实现一个符号表的散列表实现2024/8/2178.3.2 符号表的散列表实现符号表的散列表实现 n引入散列表不仅可以提高引入散列表不仅可以提高lookup操作的效率，操作的效率，同时也可以提高同时也可以提高insert操作的效率，所以在许操作的效率，所以在许多实际编译器的符号表实现中均采用了散列多实际编译器的符号表实现中均采用了散列技术技术n插入插入n个符号，查找个符号，查找e个符号的个符号的lookup操作和操作和insert操作的时间复杂度操作的时间复杂度T(n,e)还将与还将与m有关
12、，记为有关，记为T(n,e,m) ，T(n,e,m)n(n+e)/m nS(n,m)=O(n) n散列函数应在满足散列函数应在满足 的前提下，使的前提下，使达到最小达到最小 2024/8/2188.4 符号表与作用域符号表与作用域 int main() int abc; abc = 1; int abc; abc = 2; printf(“abc is %dn”, abc); printf(“abc is %dn”, abc);图图8.8 一个具有程序块结构的一个具有程序块结构的C语言程序语言程序运行结果为：运行结果为： abc is 2 abc is 1说明说明abc在不同的范围内有效。在不
13、同的范围内有效。这个有效范围就是符号的作用域这个有效范围就是符号的作用域 2024/8/2198.4.1 程序块结构的符号表程序块结构的符号表 变量的作用域满足最近嵌套原则变量的作用域满足最近嵌套原则(1) int main()(2) (3) int a=0;(4) int b=0;(5) (6) int b=1;(7) (8) int a=2;(9) printf(“%d %dn”, a, b );(10) (11) (12) int b=3;(13) printf(“%d %dn”, a, b);(14) (15) printf(“%d %dn”, a, b);(16) (17) prin
14、tf(“%d %dn”, a, b);(18) 图图8.10 一个一个C语言程序块实例语言程序块实例2024/8/2208.4.1 程序块结构的符号表程序块结构的符号表 n为每个程序块建立一个符号表，程序块内的符号记为每个程序块建立一个符号表，程序块内的符号记录在该程序块所对应的符号表中录在该程序块所对应的符号表中,还要建立起这些符还要建立起这些符号表之间的联系号表之间的联系,以刻画出符号的嵌套作用域以刻画出符号的嵌套作用域 图图8.11 图图8.10中的程序所对应的符号表中的程序所对应的符号表2024/8/2218.4.2 程序块结构符号表的其他实现程序块结构符号表的其他实现 n将所有块的符
15、号表放在一个大数组中，然后再引入将所有块的符号表放在一个大数组中，然后再引入一个程序块表来描述各程序块的符号表在大数组中一个程序块表来描述各程序块的符号表在大数组中的位置及其相互关系的位置及其相互关系 图图8.12 图图8.10的另一种符号表结构的另一种符号表结构2024/8/2228.4.2 程序块结构符号表的其他实现程序块结构符号表的其他实现 n将符号所属程序块的编号放在符号表表项中。将符号所属程序块的编号放在符号表表项中。查找某个符号的名字查找某个符号的名字name时，只有当时，只有当name和和符号表中的名字字符串完全匹配，且符号表符号表中的名字字符串完全匹配，且符号表表项中的块编号和
16、当前处理的块编号完全相表项中的块编号和当前处理的块编号完全相同时才算查找成功，否则要新建一个名字为同时才算查找成功，否则要新建一个名字为name且块号为当前块编号的符号表表项。且块号为当前块编号的符号表表项。 n程序块编号可以通过在语法制导定义中的块开始程序块编号可以通过在语法制导定义中的块开始处和块结束处添加适当的语义规则计算得出。处和块结束处添加适当的语义规则计算得出。 2024/8/2238.4.2 程序块结构符号表的其他实现程序块结构符号表的其他实现 n程序块满足最近嵌套原则程序块满足最近嵌套原则n内层程序块中的局部变量只有全部处理完成之后才进内层程序块中的局部变量只有全部处理完成之后
17、才进入外层块入外层块n一旦进入外层程序块，内层块的局部变量就不会再使一旦进入外层程序块，内层块的局部变量就不会再使用了，可以从符号表中将这些符号删除用了，可以从符号表中将这些符号删除n符号表中最前面的符号一定是当前正在处理的块中的符号表中最前面的符号一定是当前正在处理的块中的局部变量局部变量n符号表表项中可以不用存放块编号，而是根据符号表符号表表项中可以不用存放块编号，而是根据符号表表项在符号表中的位置来判断。表项在符号表中的位置来判断。 2024/8/2248.4.2 程序块结构符号表的其他实现程序块结构符号表的其他实现 (a) 处理到语句处理到语句(5)时的符号表时的符号表(b) 处理到语
18、句处理到语句(7)时的符号表时的符号表对图对图8.10中的程序中的程序2024/8/2258.4.2 程序块结构符号表的其他实现程序块结构符号表的其他实现 对图对图8.10中的程序中的程序(c) 处理到语句处理到语句(9)时的符号表时的符号表(d) 处理到语句处理到语句(13)时的符号表时的符号表2024/8/2268.4.3 C语言的符号表语言的符号表 n如果采取将每个函数分别编译成目标代码然后连接装配成一如果采取将每个函数分别编译成目标代码然后连接装配成一个可执行程序的处理方式，则每个函数中的符号经一遍处理个可执行程序的处理方式，则每个函数中的符号经一遍处理即可，而且源程序中的多个函数是一
19、个接一个处理的，不会即可，而且源程序中的多个函数是一个接一个处理的，不会出现交叉，此时可以按图出现交叉，此时可以按图8.16的方式组织符号表。的方式组织符号表。 图图8.16 一个完整一个完整C程序的符号表程序的符号表2024/8/2278.4.4 嵌套过程的符号表嵌套过程的符号表 Pascal等允许在过程中嵌套定义其它过程等允许在过程中嵌套定义其它过程 program sort(input, output); procedure readarray; begin end readarray ; procedure exchange( i, j : integer ); begin end e
20、xchange ; procedure quicksort( m, n : integer ); function partition( x, y : integer ); begin end partition ; begin end quicksort ; begin end sort ;2024/8/2288.4.4 嵌套过程的符号表嵌套过程的符号表 2024/8/229本章小结本章小结n符号表用来存放编译器各阶段收集来的各种名字的符号表用来存放编译器各阶段收集来的各种名字的类型和特征等有关信息，并供编译程序用于语法检类型和特征等有关信息，并供编译程序用于语法检查、语义检查、生成中间代码
21、及生成目标代码等；查、语义检查、生成中间代码及生成目标代码等；n源程序中会出现各种各样的名字，如函数名、函数源程序中会出现各种各样的名字，如函数名、函数参数名、函数中的局部变量名、全局变量名、数组参数名、函数中的局部变量名、全局变量名、数组名、结构名、文件名等，相应的属性可以是种属、名、结构名、文件名等，相应的属性可以是种属、类型、地址等。类型、地址等。n根据符号所需的属性个数和类型的不同，可以组成根据符号所需的属性个数和类型的不同，可以组成不同的符号表，也可以组成统一的符号表，在组成不同的符号表，也可以组成统一的符号表，在组成统一符号表时，需要采用恰当的组织结构，以便可统一符号表时，需要采用
22、恰当的组织结构，以便可以对其进行高效处理。以对其进行高效处理。2024/8/230本章小结本章小结n随着程序规模的扩大，符号名的数量会很大，随着程序规模的扩大，符号名的数量会很大，因而必须关注符号表的组织和高效管理。无因而必须关注符号表的组织和高效管理。无序线性符号表、有序线性符号表、散列表示序线性符号表、有序线性符号表、散列表示符号表具有不同性能的组织形式。符号表具有不同性能的组织形式。n符号表管理中必须关注到语言所规定的符号符号表管理中必须关注到语言所规定的符号的作用域，特别是在嵌套结构的程序中，符的作用域，特别是在嵌套结构的程序中，符号的作用域是分层的。号的作用域是分层的。nC语言符号表的管理。语言符号表的管理。
