第7章 符号表管理,哈工大王宏志

《第7章 符号表管理,哈工大王宏志》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章符号表管理SchoolofSoftwareHarbinInstituteofTechnology重点：符号表的作用,符号表的组织结构,符号表与作用域。难点：符号表的组织结构及其性能评价。6/14/20212第7章符号表管理7.1符号表的作用7.2符号表中存放的信息7.3符号表的组织结构7.4符号表与作用域7.5本章小结6/14/202137.1符号表的作用编译的各个阶段都有可能会用到符号表中登记的信息协助进行语义检查(如检查一个名字的引用和之前的声明是否相符)和中间代码生成在目标代码生成阶段，当需要为名字分配地址时，符

2、号表中的信息将是地址分配的主要依据编译器用符号表来记录、收集和查找出现在源程序中的各种名字及其语义信息。6/14/202147.1符号表的作用符号表是以名字为关键字来记录其信息的数据结构，其上支持的两个最基本操作应该是填加表项和查找表项，这两个操作必须是高效的6/14/202157.2符号表中存放的信息记录源程序中出现的各种名字及其属性信息是符号表的首要任务。显然同一个名字在一段程序中应该表示同一个对象，即同一个符号表中不能出现相同的名字，因此名字可以作为符号表的关键字。于是，每一个符号表表项中需要存放的基本信息就是符号的名

3、字及其属性。图7.1符号表的基本格式6/14/202167.1.1符号表中的名字名字字段长度固定名字项的长度大小取决于标识符允许的最大长度不适于标识符长度变化范围较大的语言空间浪费名字字段长度可变标识符的长度没有限制符号表上的操作复杂而低效引入一个单独的字符串表，将符号表中的全部标识符集中放在这个字符串表中，而在符号表表项的名字部分只要给出相应标识符的首字符在字符串表中的位置即可6/14/202177.1.1符号表中的名字标识符长度放在符号表中6/14/202187.1.1符号表中的名字(b)标识符长度放在字符串中6/14/

4、202197.1.1符号表中的名字(c)用’’表示标识符的结束6/14/2021107.1.2符号表中的属性符号所表达的含义不同，符号表中需要存放的属性也就不同数组名字需要存放的属性信息应该包括数组的维数、各维的维长等函数(或过程)的名字应该存放其参数个数、各参数的类型、返回值的类型等6/14/2021117.1.2符号表中的属性建立多个符号表来管理源程序中出现的各种符号，如常数表、变量表、函数表、数组表等可能出现不同种类符号出现重名的问题建立一张共用的大表来管理各种符号，此时需要在符号表中增设一个标志来表明符号的种属不

5、同种类符号所需存放属性信息在数量上的差异将会造成符号表的空间浪费7.1.2符号表中的属性图7.3多种符号共用符号表的一种实现结构127.1.2符号表中的属性图7.4用扩展属性链组织函数形参的符号表136/14/2021147.1.3符号的地址属性如果采用静态存储分配策略，则符号x绑定的地址等于静态分配的基址base加上符号x的偏移量offset如果采用的是栈式存储分配或堆式存储分配等动态分配策略，则符号是在程序执行过程中和地址动态绑定的。如栈式存储分配时，i的地址是以栈指针sp为基址加上i相对于活动记录起始地址的偏移量off

6、seti符号表中各符号的地址属性就是该符号相对于第一个符号的偏移地址6/14/2021157.3符号表的组织结构7.3.1符号表的线性表实现用线性表实现符号表较为直观数组实现：插入n个符号、执行e次查找操作的时间复杂度为T(n,e)=O(n(n+e))有序数组实现：插入n个符号、执行e次查找操作的时间复杂度为T(n,e)=elogn++≤(n+e)logn+O(n2)有序符号表结构只有在下面的情况下才能取得较好效果：和插入操作次数相比，符号表表项上的查找操作次数占绝对多数，即e>>n。6/14/2021167.3.2符号表

7、的散列表实现引入散列表不仅可以提高lookup操作的效率，同时也可以提高insert操作的效率，所以在许多实际编译器的符号表实现中均采用了散列技术图7.6一个符号表的散列表实现6/14/2021177.3.2符号表的散列表实现引入散列表不仅可以提高lookup操作的效率，同时也可以提高insert操作的效率，所以在许多实际编译器的符号表实现中均采用了散列技术插入n个符号，查找e个符号的lookup操作和insert操作的时间复杂度T(n,e)还将与m有关，记为T(n,e,m)，T(n,e,m)≈n(n+e)/mS(n,m)=

8、O(n)散列函数应在满足的前提下，使达到最小6/14/2021187.4符号表与作用域intmain(){intabc;abc=1;{intabc;abc=2;printf(“abcis%d”,abc);}printf(“abcis%d”,abc);}图7.8一个具有程序块结构的C