编译原理简明教程(第2版)[冯秀芳,崔冬华,段富][电子教案]第10章

1、编译原理简明教程普通高等教育“十二五”规划计算机教材-太原理工大学-计算机科学与技术学院-冯秀芳、崔冬华、段富等目目 录录第第1010章章 符号表符号表学习目标学习目标 符号表在整个编译期间的作用主要有两条：符号表在整个编译期间的作用主要有两条：一是辅助语义的（即上下文有关的）正确性检一是辅助语义的（即上下文有关的）正确性检查；二是辅助代码生成。查；二是辅助代码生成。 着重需要掌握以下内容着重需要掌握以下内容 符号表的作用符号表的作用 符号表中的内容符号表中的内容 嵌套结构语言的栈式符号表嵌套结构语言的栈式符号表符号表符号表 ：用表格形式存储源程序中的：用表格形式存储源程序中的 各种信息。各种

2、信息。作用作用 ： 辅助语义的正确性检查。辅助语义的正确性检查。 辅助目标代码的生成。辅助目标代码的生成。目目 录录 1010.1 .1 符号表的组织与内容符号表的组织与内容 1010.2 .2 符号表的结构与存放符号表的结构与存放 1010.3 .3 符号表的管理符号表的管理 符号表是一个包含程序中的变量、子程序符号表是一个包含程序中的变量、子程序 、常量、常量、过程定义、数组信息等内容的过程定义、数组信息等内容的数据库数据库。 一般地，符号表由一些表项组成二维表格。一般地，符号表由一些表项组成二维表格。 名字域名字域 存放符号或其内部码存放符号或其内部码 每个表项每个表项 属性域属性域 存

3、放属性和特征存放属性和特征 例如例如 ： 名字域名字域属性域属性域名字名字1属性属性1.名字名字n属性属性n符号表的组织方式：符号表的组织方式： 最简单：固定名字域和属性域的长度。如最简单：固定名字域和属性域的长度。如 FORTRAN语言标识符长度不超过语言标识符长度不超过6 个字符，可定为个字符，可定为6位。位。 间接方式：在符号表的名字域中存放一个指针间接方式：在符号表的名字域中存放一个指针 或一个指针和一个整数，把标识或一个指针和一个整数，把标识 符存放到一个字符串数组中。见图符存放到一个字符串数组中。见图10.2符号表的内容符号表的内容 属性域的内容因符号表名字域内容不同而不同。属性域

4、的内容因符号表名字域内容不同而不同。 例如例如 数组：维数、下标界偶、存储区域等信息数组：维数、下标界偶、存储区域等信息 数组信息向量表数组信息向量表 如图如图10.3 静态表静态表（编译前事先构造好）：保留（编译前事先构造好）：保留 符号表符号表 字表、标准函数名表等。字表、标准函数名表等。 动态表动态表（编译过程中根据需要构造的（编译过程中根据需要构造的 表）：变量名表、数组信息表）：变量名表、数组信息 表、过程信息表等。表、过程信息表等。变量表变量表 如图如图10.410.2 符号表的结构和存放符号表的结构和存放10.2.1 线性符号表线性符号表 线性表线性表(无序符号表无序符号表) :

5、 按程序中符号出现的先后按程序中符号出现的先后 次序建立的表。如图次序建立的表。如图 10.5 查找查找 : 只能线性查找，只能线性查找，(查找效率低查找效率低)，结构简，结构简 单，节省空间，适合于比较小的表。单，节省空间，适合于比较小的表。10.2.2 有序符号表有序符号表 按一定顺序按一定顺序(如字典顺序如字典顺序)排列符号。排列符号。 如图如图 10.6 、10.7 查找查找 : 折半查找法折半查找法 , , 查找效率较高。查找效率较高。 但填入表时会增加移动开销。但填入表时会增加移动开销。 1010.2.3 .2.3 散列符号表（哈希符号表）散列符号表（哈希符号表） 利用哈希函数值确

6、定符号在表中的位置。利用哈希函数值确定符号在表中的位置。 hash函数性质：函数性质： 函数值只依赖于对应符号函数值只依赖于对应符号 函数计算简单、高效函数计算简单、高效 函数值能较均匀分布函数值能较均匀分布 如如: 除法散列函数、乘法散列函数、多项式除法散列函数、乘法散列函数、多项式 除法散列函数、平方取中散列函数等。除法散列函数、平方取中散列函数等。 “质数除余法质数除余法” 见图见图10.8 查询效率较高，但要解决散列冲突问题。查询效率较高，但要解决散列冲突问题。10.2.4 栈式符号表栈式符号表 设计一个栈，新符号出现从栈顶压入。设计一个栈，新符号出现从栈顶压入。 查找时从栈顶查找时从

7、栈顶 栈底栈底例例 PASCAL语言分程序嵌套结构语言分程序嵌套结构例例10-1 程序的栈式符号表如图程序的栈式符号表如图10.9、10.10、10.11 查找时，最新加入的符号总是最先查找。查找时，最新加入的符号总是最先查找。 适合嵌套结构的程序设计语言，但表太大适合嵌套结构的程序设计语言，但表太大时，查找速度较慢。时，查找速度较慢。 10.3 符号表的管理符号表的管理10.3.1 符号表的建立符号表的建立 渐增符号表。如渐增符号表。如 线性表、线性表、 符号表的初始化符号表的初始化 有序表有序表 定长符号表。如定长符号表。如 散列表散列表 初始时，表的内容为空。初始时，表的内容为空。 一般

8、符号表在词法分析时创建，其它阶段都一般符号表在词法分析时创建，其它阶段都 可能要填表。如图可能要填表。如图 10.12、10.13 10.3.2 符号表的查填符号表的查填 对符号表的操作：对符号表的操作： 对给定符号，查看是否是在表中对给定符号，查看是否是在表中 对没查到的符号，向表中填入对没查到的符号，向表中填入 对已查到的符号，查询有关信息对已查到的符号，查询有关信息 对已查到的符号，增加或更新有关信息对已查到的符号，增加或更新有关信息 删除一个或一组无用表项删除一个或一组无用表项 查填符号表可分两种情况查填符号表可分两种情况 1、隐式说明语言的符号表查填、隐式说明语言的符号表查填 如如 FORTRAN “ I N ”规则规则 语句中每出现一个符号均需查表，当第一次出语句中每出现一个符号均需查表，当第一次出 现时填表。现时填表。 2、显式说明语言的符号表查填、显式说明语言的符号表查填 如如 Pascal、C语言语言 说明部分：出现的符号，先查表，若没有，则填表。说明部分：出