编译原理 第7章 符号表管理技术

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