16.第八章-符号表

2020/6/61第8章符号表管理2020/6/62主要内容符号表概述符号表的作用符号表的组织结构整理与查找符号表与作用域本章小结2020/6/63符号表概述什么是符号表?在编译过程中,编译程序用来记录源程序中各种名字的特性信息,所以也称为名字特性表。名字:程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等。特性信息:上述名字的种类、类型、维数、参数个数、数值及目标地址（存储单元地址）等。2020/6/64符号表的作用编译的各个阶段都有可能会用到符号表中登记的信息协助进行语义检查(如检查一个名字的引用和之前的声明是否相符)和中间代码生成在目标代码生成阶段，当需要为名字分配地址时，符号表中的信息将是地址分配的主要依据编译器用符号表来记录、收集和查找出现在源程序中的各种名字及其语义信息。2020/6/65符号表上的操作在声明部分，向表中插入一个新标识符。在表达式或语句中，对于给定一个标识符：①查找是否在表中；②访问它在表中的相关信息；③在表中填写或更新它的某些信息。更新或删除一个或一组标识符，体现嵌套作用规则和局部化。2020/6/66何时建立和访问符号表在词法分析时创建只能在符号表中将标识符的名字填入符号表，而其他属性则要在语义分析和代码生成阶段填入。语法分析阶段只检查源程序语法的正确性，一般不使用符号表。在语义分析时创建如果在语义分析阶段创建符号表，那么与符号表打交道的就仅局限于语义分析和代码生成部分。2020/6/67x简单变量整型a简单变量整型b简单变量整型L标号何时建立和访问符号表例：intx,a,b;.....L:x:=a+b;...建表分配存储1.语法分析和语义分析•说明语句、赋值语句的语法规•上下文有关分析：是否声明•类型一致性检查2.生成目标代码LOADa的地址ADDb的地址STOx的地址符号表数据区2020/6/68何时建立和访问符号表填表：当分析到程序中的说明或定义语句时，应将说明或定义的名字，以及与之有关的信息填入符号表中。例：ProcedureP()查表：(1)填表前查表，检查在程序的同一作用域内名字是否重复定义；(2)检查名字的种类是否与说明一致；(3)对于强类型语言，要检查表达式中各变量的类型是否一致；(4)生成目标指令时，要取得所需要的地址。.........2020/6/69符号表的内容(1)符号表的结构与内容符号表的基本结构:名字特性(信息)“名字”域:存放名字，一般为标识符的符号串,也可为指向标识符字符串的指针。2020/6/610符号表的内容“特性”域:可包括多个子域,分别表示标识符的有关信息，如:名字(标识符)的种类:简单变量、函数、过程、数组、标号、参数等类型：如整型、浮点型、字符型、指针等性质：变量形参、值形参等值：常量名所代表的数值地址：变量所分配单元的首址或地址位移大小：所占的字节数作用域的嵌套层次:2020/6/611符号表的内容对于数组:维数、上下界值、计算下标变量地址所用的信息（数组信息向量）以及数组元素类型等。对于记录（结构、联合）：域的个数，每个域的域名、地址位移、类型等。对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等。对于指针：所指对象类型等。2020/6/612符号表的组织方式存储符号表的方法定长存贮方法：为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中，特点是简单且存取速度快，缺点是空间利用率低，标识符长度不能超过名字域的宽度。集中存贮方法：开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。特点是存储效率高，标识符无长度限制，但存取效率低。ComputerX1FORM1名字位置名字长度其它属性1892115……集中存储符号表2020/6/613符号表的组织方式NAMEINFORMATIONCAT......地址a......维数首地址界差d1...界差dn上界I1...上界In下界u1...下界un内情向量表通过符号表访问内情向量表2020/6/614符号表的组织方式SAMPLE的属性SAMPLE4N字2N字INFORMATION：04(i-1)2(i-1)NAME：0分两个字表的符号表安排2020/6/615整理与查找符号表的三种构造法和处理法：线性查找二叉树杂凑技术（hash技术）2020/6/616线性表最简单按照出现的顺序填表每次查找从第一个开始顺序查找指示器AVAILABLE总是指向空白区的首地址NAMEINFORMATIONJ1...XYZ...I...BC...线性符号表项数1234AVAILABEL查表操作的平均长度为(n+1)/22020/6/617对折查找为了提高查表速度，可在建表同时按名字大小排序。NAMEINFORMATIONBC...I...J1...XYZ...线性符号表项数1234AVAILABEL•查表操作的平均长度为•但该方法对于一遍扫描来说没有太大的用处N2log12020/6/618二叉树变通方法：二叉树令每项为一个结点，每个结点附设两个指示器栏，LEFT（左枝），RIGHT（右枝），要求任何结点P的右枝的所有结点值小于结点P的值，而左枝的所有结点值大于结点P的值。J10XYZ0BC00I02020/6/619杂凑技术(hashtable或哈希表)线性表：填表快，查表慢对折法：填表慢，查表快哈希表：折中哈希表主要问题：分布尽量要均匀解决“地址冲突”问题2020/6/620杂凑技术(hashtable或哈希表)Hash表的基本思想：为符号表设置一个足够大的空间N，即符号表的长度为N；为符号Ki构造一个散列函数Hash(Ki)，使得0≤Hash(Ki)≤N-1，其中i=1，2，…，n；Hash(Ki)就决定了符号Ki在符号表中的位置。2020/6/621杂凑技术(hashtable或哈希表)用“质数除余法”来构造散列符号表的方法（1）根据各符号名中的字符确定正整数H，即将标识符中的每个字符转换为一个非负整数，将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来）。（2）将上一步确定的整数H除以符号表的长度N（N是质数），然后取其余数。这个余数就作为符号的散列位置。（3）处理冲突可采用链接法，即将出现冲突的符号用指针连接起来。2020/6/622例：假设现有5个符号C1、C2、C3、C4、C5，分别转换成正整数为87、55、319、273和214，符号表的长度是5，那么，利用质数除余法得到的散列地址为：2、0、4、3、4，结果如图所示。散列符号表2020/6/623例：请判断输出结果？为什么？intmain(){intabc;abc=1;{intabc;abc=2;printf(“abcis%d\n”,abc);}printf(“abcis%d\n”,abc);}运行结果为：abcis2abcis1说明abc在不同的范围内有效。这个有效范围就是符号的作用域2020/6/624符号的作用域问题：如何组织符号表，使得同一个标识符在不同的作用域中能得到正确的引用，而不会产生混乱？最近嵌套作用域规则2020/6/625最近嵌套作用域示例(1)intmain()(2){(3)inta=0;(4)intb=0;(5){(6)intb=1;(7){(8)inta=2;(9)printf(“%d%d\n”,a,b);(10)}(11){(12)intb=3;(13)printf(“%d%d\n”,a,b);(14)}(15)printf(“%d%d\n”,a,b);(16)}(17)printf(“%d%d\n”,a,b);(18)}输出结果：210301002020/6/626Pascal的符号表组织过程结构：在一个过程（或函数）里说明了的名字被认为是局部与这个过程（或函数）的。最近嵌套作用域原则：一个名字的作用域是包含了这个名字的说明的最小过程（或函数）。Pascal过程的结构是嵌套的。2020/6/627Pascal的符号表组织办法：将其符号表设计为栈符号表，先进后出。引入一个显示（DISPLAY）层次关系表，称为过程的嵌套层次表。在符号表的信息栏中引入一个指针域，用以链接它在同一过程内的前一域名字在表中的下标。2020/6/628programB1(input,output;)consta=10;varb,c:integer;e:real;procedureB2(x:real);varf,g:real;procedureB3(y:real);constb=5;varh:boolean;procedureB4(Z:integer);vari:char;begin...ife0thenB4(f);...end{B4}begin...;B4(a);...;end{B3}begin...;B3(c);...;end{B2}begin...;B2(e);...;end{main}2020/6/629NAMEinformationpreviouse...0c...4b...3a...2栈符号表（编译到B1时的常量和变量的说明时栈符号表）54321SPTOP1栈符号表DISPLAY符号表首地址2020/6/630继续编译，栈符号表的变化：编译到B4过程说明之前的栈1413121110987654321SP栈符号表DISPLAY符号表首地址1061NAMEinformationpreviousB4...0h...13b...12y...11B3...0g...9f...8x...7B2...0e...5c...4b...3a...2TOP2020/6/631编译到B4过程体之前时的栈符号表继续编译，栈符号表的变化：16151413121110987654321SP栈符号表DISPLAY符号表首地址141061NAMEinformationpreviousi0z15B4...0h...13b...12y...11B3...0g...9f...8x...7B2...0e...5c...4b...3a...2TOP2020/6/632例：画出编译到C程序中a、b、c、d处的栈式符号表。realx,y;charname;……………………………aintfun1(intind){intx;……………………………bx=m2(ind+1);}intfun2(intj){{intf[10];booltest1;…………………c}}main(){charname;………………………dx=2;y=5;printf(%d\n,fun1(x/y));}2020/6/633a、b、c、d处的栈式符号表如下Test1fjfun2fun1nameyx50TOPnamemainfun2fun1nameyx60TOPxindfun1nameyx40TOPnameyx0TOP(a)(b)(c)(d)栈式符号表321054321076543210765432102020/6/634本章小结符号表用来存放编译器各阶段收集来的各种名字的类型和特征等有关信息，并供编译程序用于语法检查、语义检查、生成中间代码及生成目标代码等；符号表需要记录哪些名字和属性符号表的组织和高效管理：线性表、二叉树、哈希表等符号的作用域