编译原理符号表.ppt

第7章 符号表管理技术(P149) n7.1 何时建立和访问符号表 n7.2 符号表的组织和内容 n7.3 符号表上的操作 n7.4 非块程序结构语言的符号表结构 n7.5 块程序结构语言的符号表组织 学 习 重 点 n符号表的作用 n符号表的内容 n符号表上的操作 n符号表的组织 第7章 符号表管理技术 n符号表：它是记录、存储和管理源程序中的各种 信息的一些表格，如常量表、数组信息表、保留 字表和标识符表等。 n符号表的作用： （1）收集符号的各种信息 （2）语义检查的依据 （3）目标代码生成阶段地址分配的依据 7.1 何时建立和访问符号表（P149） n何时建立和访问符号表： 在词法分析时创建 只能在符号表中将标识符的名字填入符号表， 而其他属性则要在语义分析和代码生成阶段填入。 语法分析阶段只检查源程序语法的正确性，一般不 使用符号表。 在语义分析时创建 如果在语义分析阶段创建符号表，那么与符号 表打交道的就仅局限于语义分析和代码生成部分。 7.2 符号表的组织和内容（P150） n符号表的内容： 名字域 用来存放符号的名字。 属性域 用来记录与该名字相对应的各种属性和特征。 7.2 符号表的组织和内容 名字 目标标地址 类类型 维维数 声明行 引用行 指针针 Computer 0 2 1 2 9,4,5 7 X1 4 1 0 3 12,14 0 FORM 8 3 2 4 6 B2 48 1 0 5 1 ANS 52 1 0 5 4 M 56 6 0 6 2 FIRST 64 1 0 7 3 n符号表示例（P150） 名字域 属性域 7.2 符号表的组织和内容 n符号表的总体组织： （1）多张 把属性种类完全相同的那些符号组织在一起， 构造出表项是分别为等长的多个符号表。 （2）一张 把所有符号都组织在一张符号表中，组成一张 包括了所有属性的庞大的符号表。 （3）前两种的折中 根据符号属性相似程度分类组织成若干张表， 每张表中记录的符号都有比较多的相同属性。 7.2 符号表的组织和内容 n存储符号表的方法： （1）定长存贮方法：为标识符名字域规定一个宽度，标 识符按左对齐方式存放在其中，特点是简单且存取速度快 ，缺点是空间利用率低，标识符长度不能超过名字域的宽 度。 （2）集中存贮方法：开辟一个存放所有标识符的缓冲区 ，而在标识符名字域中只存放标识符在缓冲区中的偏移地 址和标识符的长度。特点是存储效率高，标识符无长度限 制，但存取效率低。 ComputerX1FORM1 名字位置 名字长长度 其它属性 18 92 115 集中存储符号表 7.2 符号表的组织和内容 n符号表的分类（从编译系统建造符号表的过程 来划分）： （1）静态表 在编译前就已经构造好了的符号表，如保留 字表、标准函数名表等。 （2）动态表 在编译过程中根据需要构造的符号表，如变 量表、数组信息表、过程信息表等。 7.3 符号表上的操作（P152） n符号表上的操作： （1）在声明部分，向表中插入一个新标识符。 （2）在表达式或语句中，对于给定一个标识符： p查找是否在表中； p访问它在表中的相关信息； p在表中填写或更新它的某些信息。 （3）更新或删除一个或一组标识符，体现嵌套作 用规则和局部化。 7.4非块程序结构语言的符号表结构（P153） n非块程序结构语言：是指用它编写的每一个可独 立编译的程序是一个不包含子块的单一模块程序， 该模块中声明的所有变量是属于整个模块的。 7.4非块程序结构语言的符号表结构 n非块程序结构语言的符号表的组织方式： （1）无序表（或线性表） 根据变量被声明的先后顺序填入符号表。无序表 的插入及查找操作简单、易于实现，但查找效率低。 适用于符号表较小的情况。 （2）有序表 有序符号表的表项是根据变量名按字母顺序存放 的。对于有序表，最常用的查找技术是折半查找法。 （3）散列符号表（或哈希符号表） 使用哈希函数，将程序中出现的符号通过哈希函 数进行映射，得到的函数值作为该符号在表中的位置 。插入和查找效率高，为多数编译程序所采用。 7.4非块程序结构语言的符号表结构 nHash表的基本思想： 为符号表设置一个足够大的空间N，即符号表的 长度为N； 为符号Ki构造一个散列函数Hash(Ki)，使得0 Hash(Ki) N-1，其中i=1，2，n； Hash(Ki)就决定了符号Ki在符号表中的位置 。 7.4非块程序结构语言的符号表结构 n用“质数除余法”来构造散列符号表的方法(P154)： （1）根据各符号名中的字符确定正整数H，即将标识 符中的每个字符转换为一个非负整数，将得到的各个整 数组合成一个整数（可以将第一个、中间的和最后一个 字符值加在一起，也可以将所有字符的值加起来）。 （2）将上一步确定的整数H除以符号表的长度N （N是 质数），然后取其余数。这个余数就作为符号的散列位 置。 （3）处理冲突可采用链接法，即将出现冲突的符号用 指针连接起来。 7.4非块程序结构语言的符号表结构 n例（P154） 假设现有5个符号C1、C2、C3、C4、C5， 分别转换成正整数为87、55、319、273和214，符号表的 长度是5，那么，利用质数除余法得到的散列地址为：2 、0、4、3、4，结果如图所示。 散列符号表 7.5 块程序结构语言的符号表组织（P155） n按块程序结构语言的规定：变量的作用域是定义 它的块程序；同一块内的变量不能重名，但不同块 以及嵌套块之间的变量可以重名，使用时局部变量 优先于全局变量。 n块程序结构语言：是指程序模块可包含嵌套的子 模块，每一子模块可以有一组自己的局部变量。 n例(P155) 当编译编译 程序编译编译 到该该C程序某处时处时 的相应应的有效变变量: 1.real x,y; 2.char name; 3.int fun1(int ind) 4. int x; 5. x=m2(ind+1); 6. 7.int fun2(int j) 8. 9. int f10; 10. bool test1; 11. 12. 13. main() 14. 15. char name; 16. x=2;y=5; 17. printf(“%dn“,fun1(x/y); 18. name,y,x ind,fun1,name, y,x x,ind, fun1,name, y,x fun1,name, y,x j,fun2, fun1,name, y,x test1,f, j,fun2, fun1,name, y,x j,fun2, fun1,name, y,x fun2, fun1,name, y,x main, fun2, fun1,name, y,x name, main, fun2, fun1,name, y,x 7.5 块程序结构语言的符号表组织 n块程序结构语言的符号表结构为栈式符号表，它包 括一个符号表栈及一个块索引栈。符号表栈记录变量 的属性，块索引栈指出每个块在符号表中的开始位置 。 n栈式符号表的插入操作: （1）开始编译时，设符号表栈顶指针TOP为0，当 第一个标识符出现时，将该标识符的属性入栈，同时 将该标识符的地址0压入块索引栈，然后栈顶指针 TOP为1。 7.5 块程序结构语言的符号表组织 n栈式符号表的插入操作: （2）后面再遇到标识符时，如果新的标识符与栈顶的 标识符在同一块中，则只需将新记录压入符号表栈顶单 元，然后，栈顶指针TOP加1。如果新的标识符与栈顶 的标识符不在同一块中，表示刚才处理的程序块嵌套着 一个程序块，而现在进入了这个嵌套的程序块中，则要 进行定位操作，即将栈顶指针TOP入块索引栈，再将该 标识符属性压入符号栈，然后栈顶指针TOP加1。 （3）当编译遇到程序块的结尾时要进行重定位操作， 即将块索引栈的栈顶单元出栈并将内容赋给栈顶指针 TOP。 n注意：栈顶指针TOP始终指向符号表栈顶第一个空闲 的存储单元。 7.5 块程序结构语言的符号表组织 n栈式符号表的查找操作: 符号表从栈顶单元(TOP-1)开始到块索引栈的栈顶 单元所指的单元，逐一检查，并进行相应的存取操作 。特别地，如果查找到有与要插入的变量同名，则表 示源程序中存在变量重复声明的错误；如果没有，才 可将该标识符的属性入栈。 n查表操作要对符号栈进行从顶(TOP-1)到底进行线性 搜索，这样确保找到的变量满足局部变量优先于全局 变量的规则。由于栈式符号表中记录是无序的，因而 查询效率比较差。 n 例7-1(P156) 画出编译到C程序中a、b、c、d处的栈式符号表 。 real x,y; char name;a int fun1(int ind) int x; b x=m2(ind+1); int fun2(int j) int f10; bool test1; c main() char name; d x=2;y=5; printf(“%dn“,fun1(x/y); 解：a、b、c、d处的栈式符号表栈式符号表见下图的 (a)、(b)、(c)、(d)。 Test1 f j fun2 fun1 name y x 6 5 0 TOP name main fun2 fun1 name y x 6 0 TOP x ind fun1 name y x 4 0 TOP name y x 0 TOP (a) (b) (c) (d) 栈式符号表 3 2 1 0 小 结 1.符号表的作用：辅助语义分析和代码生成。 2.符号表的内容：名字域和属性域。 3.符号表上的操作：插入和查找等。 4.符号表的组织：无序表、有序表或散列符号 表。 习 题(P157) 1. 给出编译下面程序的有序