编译原理 符号表13.ppt

《编译原理 符号表13.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章符号表管理技术(P149)7.1何时建立和访问符号表7.2符号表的组织和内容7.3符号表上的操作7.4非块程序结构语言的符号表结构7.5块程序结构语言的符号表组织学习重点符号表的作用符号表的内容符号表上的操作符号表的组织第7章符号表管理技术符号表：它是记录、存储和管理源程序中的各种信息的一些表格，如常量表、数组信息表、保留字表和标识符表等。符号表的作用：（1）收集符号的各种信息（2）语义检查的依据（3）目标代码生成阶段地址分配的依据7.1何时建立和访问符号表（P149）何时建立和访问符号表：在词法分析时创

2、建只能在符号表中将标识符的名字填入符号表，而其他属性则要在语义分析和代码生成阶段填入。语法分析阶段只检查源程序语法的正确性，一般不使用符号表。在语义分析时创建如果在语义分析阶段创建符号表，那么与符号表打交道的就仅局限于语义分析和代码生成部分。7.2符号表的组织和内容（P150）符号表的内容：名字域用来存放符号的名字。属性域用来记录与该名字相对应的各种属性和特征。7.2符号表的组织和内容名字目标地址类型维数声明行引用行指针Computer02129,4,57X1410312,140FORM83246B248105

3、1ANS521054M566062FIRST641073符号表示例（P150）名字域属性域7.2符号表的组织和内容符号表的总体组织：（1）多张把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表。（2）一张把所有符号都组织在一张符号表中，组成一张包括了所有属性的庞大的符号表。（3）前两种的折中根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。7.2符号表的组织和内容存储符号表的方法：（1）定长存贮方法：为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中，

4、特点是简单且存取速度快，缺点是空间利用率低，标识符长度不能超过名字域的宽度。（2）集中存贮方法：开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。特点是存储效率高，标识符无长度限制，但存取效率低。ComputerX1FORM1名字位置名字长度其它属性1892115……集中存储符号表7.2符号表的组织和内容符号表的分类（从编译系统建造符号表的过程来划分）：（1）静态表在编译前就已经构造好了的符号表，如保留字表、标准函数名表等。（2）动态表在编译过程中根据需要构造的符

5、号表，如变量表、数组信息表、过程信息表等。7.3符号表上的操作（P152）符号表上的操作：（1）在声明部分，向表中插入一个新标识符。（2）在表达式或语句中，对于给定一个标识符：①查找是否在表中；②访问它在表中的相关信息；③在表中填写或更新它的某些信息。（3）更新或删除一个或一组标识符，体现嵌套作用规则和局部化。7.4非块程序结构语言的符号表结构（P153）非块程序结构语言：是指用它编写的每一个可独立编译的程序是一个不包含子块的单一模块程序，该模块中声明的所有变量是属于整个模块的。7.4非块程序结构语言的符号表结

6、构非块程序结构语言的符号表的组织方式：（1）无序表（或线性表）根据变量被声明的先后顺序填入符号表。无序表的插入及查找操作简单、易于实现，但查找效率低。适用于符号表较小的情况。（2）有序表有序符号表的表项是根据变量名按字母顺序存放的。对于有序表，最常用的查找技术是折半查找法。（3）散列符号表（或哈希符号表）使用哈希函数，将程序中出现的符号通过哈希函数进行映射，得到的函数值作为该符号在表中的位置。插入和查找效率高，为多数编译程序所采用。7.4非块程序结构语言的符号表结构Hash表的基本思想：为符号表设置一个足够大的

7、空间N，即符号表的长度为N；为符号Ki构造一个散列函数Hash(Ki)，使得0≤Hash(Ki)≤N-1，其中i=1，2，…，n；Hash(Ki)就决定了符号Ki在符号表中的位置。7.4非块程序结构语言的符号表结构用“质数除余法”来构造散列符号表的方法(P154)：（1）根据各符号名中的字符确定正整数H，即将标识符中的每个字符转换为一个非负整数，将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来）。（2）将上一步确定的整数H除以符号表的长度N（N是质数），然

8、后取其余数。这个余数就作为符号的散列位置。（3）处理冲突可采用链接法，即将出现冲突的符号用指针连接起来。7.4非块程序结构语言的符号表结构例（P154）假设现有5个符号C1、C2、C3、C4、C5，分别转换成正整数为87、55、319、273和214，符号表的长度是5，那么，利用质数除余法得到的散列地址为：2、0、4、3、4，结果如图所示。散列符号表7.5块程序结构语言的符号表组织（P