第6章符号表的组织与管理PPT课件.ppt

第6章 符号表的组织与管理 符号表是编译程序中主要的数据结构之一。它主要用来存放程序语言中出现的有关标识符的信息。编译程序处理标识符时主要涉及两部分内容，其一是标识符自身，其二是与标识符相关的信息。这些信息又包括：标识符的类型，如实型、整型、布尔型等；标识符的种属，如数组名、变量名、过程名、函数名等；标识符的作用域，如全局变量或局部变量等。在对程序语言进行编译的过程中，常常需要处理出现在程序语言中的标识符及相关信息。如在词法分析中每识别到一个标识符，编译程序就要查阅符号表，若符号表中没有该标识符的定义，就将标识符及其相关信息登录在符号表中。在语义分析时，符号表中的内容可以用于语义检查。代码优化时，编译程序将利用符号表提供的信息选出恰当的代码进行优化。目标代码生成时，编译程序将依据符号表中的符号名分配目标地址。由此可见，编译过程的各个阶段都要访问符号表。因此合理地组织和管理这些符号表显得尤为重要。符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作。符号表设计的基本要求：目标是合理存放信息和快速准确查找。正确存储各类信息。适应不同阶段的需求；便于有效地进行查找、插入、删除和修改等操作；空间可以动态扩充；本章教学内容符号表的作用，内容，组织和管理。一、符号表的作用符号表的作用：收集符号属性；上下文语义的合法性检查的依据；作为目标代码生成阶段地址分配的依据。二、符号表的内容语言符号可分为关键字（保留字）符号，操作符符号及标识符符号。它们之间的主要属性有较大差别。因此通常为它们建立不同的符号表，但有些编译程序也将关键字符号与标识符符号建立在同一符号表中。符号表条目逻辑上讲：每个声明的名字在符号表中占据一栏，称为一个条目，用于存放名字的相关信息。符号表中的内容：保留字、标识符、特殊符号（包括算符、分隔符等）等等。不同类别的符号存放在不同的子表中，如变量名表、过程名表、保留字表等。存放方式：关键字属性。关于组合关键字：.int x;double x;struct x float y,z;为C+构造的符号表中，组合关键字至少应该包括三项：名字作用域类型。当一个名字x在同一作用域中允许有多于一个的声明，则对x的引用时需要根据上下文确定x到底属于哪个对象。因此程序设计语言在语法上规定了不允许这样的声明，以简化编译时的处理。符号表的每一项(入口)包含两大栏:名字栏，也称主栏，关键字栏信息栏，记录相应的不同属性，分为若干子栏符号的组织方式:1.安排各项各栏的存储单元为固定长度2.用间接方式安排各栏存储单元 构成名字的字符串的存储 定长数据变长数据直接存放间接存放 名字（直接存储）属性sort proc,.a int,.readarray proc,.draw_a_red_line_for_object_aboolean,.名字（间接存储）属性101(或101/4)proc,.106(或105/1)int,.108(或106/9)proc,.118(或105/28)boolean,.sort#a#readarray#draw_a_red_line_for_object_a#101 sortareadarraydraw_a_red_line_for_object_a101 间接存储的方法实际上解决了复杂信息的存储问题，将其推广到属性，则任何一个复杂的属性，均可以为其另辟空间（空间本身可以是复杂结构，如数组的内情向量等），而仅需要将指向此空间的指针放在此属性在符号表中的对应位置即可。符号表中的标识符一般设置的属性项目有：符号名 符号的类型 符号的存储类别 符号的作用域及可视性 符号变量的存储分配信息 符号的其它属性下面三个方面亦是符号表中表达标识符属性的重要信息。数组内情向量：数组是一种重要的数据类型。编译程序处理数组说明的主要工作是，把描述数组属性信息的内情向量登录到符号表中。内情向量包括数组类型，维数，各维的上、下界及数组首地址，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据。NameInformation入口地址入口地址array内情向量表内情向量表维数维数首地址首地址界差界差d1界差界差dn上界上界i1上界上界in下界下界u1下界下界un记载数组内情向量的符号表 记录结构型的成员信息：一个记录结构型的变量，在存储分配时所占空间大小要由它的全体组成成员来确定，另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。这二种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置。函数及过程的形参：函数和过程的形参作为该函数或过程的局部变量，但它又是该函数或过程对外的接口。每个函数或过程的形参个数、形参的排列次序及每个形参的类型，都体现了调用该函数或过程时的属性，它们都应该反映在符号表的函数或过程标识符的项中。有关函数及过程的形参属性信息用来作调用过程的匹配处理和语义检查。按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、符号表的存放次序:1.把每一项置于连续K存储单元中，构成一张K*N的表2.把整个符号表分成m个子表，如T1,T2,Tm，每个子表含有N项例:PASCAL程序段：PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.三、符号表的组织 线性组织 这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录。排序组织及二分法 语言中的每一个符号，都是由一个或几个ASCII或EBCDIC代码字符拼写而成的，每一个符号在机器内都是由这种字符代码串来表示。排序组织的符号表，就是在符号表中的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的。散列组织 一个符号在散列表中的位置，是由对该符号（即字符代码串）进行某种函数操作（通常称为杂凑函数）所得到的函数值来确定的。所得到的函数值与该表项在表中位置的对应关系，是通过对函数值的求整以及相对于表长的求余得到的。符号表的散列组织相对来说具有较高的运行效率，因而绝大多数编译程序中的符号表采用散列组织。为了提高效率降低算法复杂度，通常杂凑函数采用整数操作。目前编译程序中，一般采用对符号代码的位操作作为杂凑函数，见得最多的是符号代码的字符段叠加或加权叠加以及符号代码的对折或多折等位操作。四、符号表的操作在一个符号表上可以进行下列操作：（1）往表中填入一个新标识符。（2）对给定标识符，查找它是否已在表中。访问它的某些信息。往表中填入或更新某些信息。（3）更新或删除一个或一组无用的项。对符号表进行操作的时机：定义性出现使用性出现整理和查找1.线性查找按关键字出现的顺序填写各项。填表快，查找慢。结构简单，节省空间，效率低，查找时间复杂度：O(n)。改进：自适应线性表2.二分查找表格中的项按名字的“大小”顺序整理排列。填表慢,查找快。查找时间复杂度:O(Log2n)改进：组织成二叉树。3.杂凑查找(HASH技术)杂凑函数H(SYM)：0N-1 N：符号表的项数。要求：1.计算简单高效 2.函数值分布均匀填表快，查找快示例：PL 语言编译程序的符号表1.表格的定义n名字表(nametab)n程序体表(btab)n层次显示表(display)n数组信息表(atab)n中间代码表(code)1)名字表(nametab)名字表nametab：登记程序中出现的各种名字及其属性名字标识符名字种类，可以是常量(constant)、变量(variable)、类型(type)、过程(procedure)名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依次类推名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表(btab)中的位置；其他情况ref为0adr,当名字为变量名时(包括形参，存入该变量(或形参)在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址val,当名字为变量名时，填入他们的相应值size,当名字为类型名时，填入该类型数据所需存贮单元的数目指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0(2)程序体表btab和层次显示表display程序体表btab：记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名字表进行管理指向本程序体中最后一个形式参在nametab中的位置指向本程序体中最后一个名字在nametab中的位置本程序体所有形参所需体积、包括连接数据所占空间本程序体所有局部数据所需空间大小层次显示表display：描述正在处理的各嵌套层，对程序体表进行管理btab(3)数组信息表atab数组的下标类型数组元素类型当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0数组下限数组上限数组元素的体积数组本身的体积type a=array1.10,1.10 of integer;nametabatab(4)中间代码表codecode：用于存放编译程序所产生的每条中间代码。8.3 名字的作用范围在许多程序语言中,名字都有一个确定的作用范围.两种程序体结构:并列结构，如FORTRAN嵌套结构，如PASCAL，ADAPROGRAM MAIN integer X，YCOMMON/C/A，B ENDSUBROUTINE SUB1 real X，ZCOMMON/C/A1，B1 ENDprogram P;var a,b:integer;procedure P1(i1,j1:integer);var c,d:integer end;procedure P2(i2,j2:integer);var a,c:integer;procedure P21;var b1,b2:boolean;end;end;end.1.FORTRAN的符号表组织一个FORTRAN程序由一个主程序段和若干个辅程序段组成.把局部名和全局名分别存在不同的地方.2.嵌套结构语言的符号表组织如PASCAL、ALGOL、ADA作用域遵循最近嵌套原则.PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识符在不同的过程中代表不同的名字。名字作用域规则-最近嵌套原则一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。program main var A,B:real;procedure P1 var B:boolean;begin end procedure P2 var A:integer;begin endbegin endA(real)B(real)B(bool)A(integr)两种做法:引入过程编号属性。查找时，先查找本过程编号的名字，查不到则查找外层过程编号的名字，等等.按栈式思想组织符号表。查找时，从后往前查找，碰到的第一个名字就是所需查找的名字.PL语言的中间代码指令格式：opcod l aopcod：操作码l：第一操作数，程序体层数a：第一操作数，相对地址编译是如何确定变量的层数(地址)？运行是如何根据指令中变量的层数和相对地址确定变量的存储单元？program P;var a,b:integer;procedure P1(i1,j1:integer);var c,d:integer end;procedure P2(i2,j2:integer);var a,c:integer;procedure P21;var b1,b2:boolean;end;end;end.program P;var a,b:integer;procedure P1(i1,j1:integer);var c,d:integer end;procedure P2(i2,j2:integer);var a,c:integer;procedure P21;var b1,b2:boolean;end;end;end.program P;var a,b:integer;procedure P1(i1,j1:integer);var c,d:integer end;procedure P2(i2,j2:integer);var a,c:integer;procedure P21;var b1,b2:boolean;end;end;end.function position(id:alfa):integer;var i,j:integer;begin nametab0.name:=id;j:=level;repeat i:=btab displayj.last;while nametabi.nameid do i:=nametabi.link;j:=j-1 until(j0)or(i0);if(i=0)then error(10);position:=i end;position b1:=a+bPL语言的中间代码指令格式：opcod l aOpcod：操作码l：第一操作数，程序体层数a：第一操作数，相对地址编译是如何确定变量的层数(地址)？运行时如何根据指令中变量的层数和相对地址确定变量的存储单元？名字的作用域 程序设计语言的名字可以出现在不同的范围内，并且可以具有不同的意义。两种划分范围的方式：并列的和嵌套的。不同的语言采用不同的方式：如Pascal的过程定义可以是嵌套的，而C的过程定义是并列的，但是C允许程序块是嵌套的。名字的作用域：名字在哪个范围内起作用。并列的两个范围内的名字作用域互不相干，但是分别在嵌套的两个范围内的名字，其作用域的问题就需要制定规则来限定，以使得任何一个名字在任何范围内涵义都是无二义的。名字的作用域规则：规定一个名字在什么样的范围内应该表示什么意义。名字的作用域（续1）静态作用域原则（static-scope rule）：编译时就可以确定名字的作用域，也可以说，仅从静态读程序就可确定名字的作用域。最近嵌套原则（most closely nested）：以程序块为例，也适用于过程。程序块B中声明的作用域包括B；如果名字x不在B中声明，那么B中x的出现是在外围程序块B的x声明的作用域中，使得(a)B有x的声明，并且(b)B比其它任何含x声明的程序块更接近被嵌套的B。通俗地讲，名字的声明在离其最近的内层起作用，即在名字引用处从内向外看，它处在所遇到的第一个该名字声明的作用域。例子：找人张三；软件学院的张三；计算机学院的张三；西电软件学院的张三 名字的作用域（续2）例4.10 说明符合作用域规则的C+程序。void main()int a=0,b=0;/*B0层*/int b=1;/*B1层，被B0嵌套*/int a=2,c=4,d=5;/*B2层，被B1嵌套*/printf(%d%dn,a,b);/*结果为：2，1*/int b=3;/*B3层，与B2并列*/printf(%d%dn,a,b);/*结果为：0，3*/printf(%d%dn,a,b);/*结果为：0，1*/printf(%d%dn,a,b);/*结果为：0，0*/声明与作用域：声 明作用域int a=0 B0-B2int b=0 B0-B1int b=1B1-B3int a=2 B2int b=3B3 线性表 线性表应是一个栈，以正确反映名字的作用域，即符号的加入和删除，均在线性表的一端进行。线性表上的操作：关键字：名字作用域；查找：从表头(栈顶)开始，遇到的第一个名字；插入：先查找，再插入在表头；1 void main()2 int a=0,b=0;/B03 int b=1;/B14 int a=2,c=4,d=5;/B27 int b=3;/B311 线性表（续1）1 void main()2 int a=0,b=0;/B03 int b=1;/B14 int a=2,c=4,d=5;/B27 int b=3;/B311 线性表上操作的效率（n个条目）：一个名字的查找：成功查找(平均)：(n+1)/2；不成功查找：n+1建立n个条目的符号表(最坏)：=(n+1)(n+2)/2删除：(a)暂时：将在同一作用域的名字同时摘走，适当保存；(b)永久：将在同一作用域的名字同时摘走，不再保存。修改：与查找类似，修改第一个遇到的名字的信息。修改可以用插入删除代替。散列表 散列表的构成 将线性表分成m个小表。构造hash函数，使名字均匀地散布在m个子表中。如果散列均匀，则时间复杂度会降到原线性表的1/m。每个名字挂在两个链上(便于删除操作)：哈希链(hash link)：链接所有具有相同hash值的元素，表头在表头数组中；作用域链(scope link)：链接所有在同一作用域中的元素，表头在作用域链中。其中：S1、S2、S4在同一作用域 S3在另一作用域 散列表上的操作 散列表（续1）1查找：首先计算散列函数，然后从散列函数所指示的入口进入某个线性表，在线性表中沿hash link，象查找单链表中的名字一样进行查找。2插入：首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hash link和scope link插入到两个链中，方法均是插在表头，即两个表均可看作是栈。3删除：把以作用域链连在一起的所有元素从当前符号表中删除，保留作用域链所链的子表，为后继工作使用（如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可）。散列表（续2）设：hash(s)=ord(s)-ord(a)1 void main()2 int a=0,b=0;/B03 int b=1;/B14 int a=2,c=4,d=5;/B27 int b=3;/B311 分析在B2中：退出B2进入B3：散列函数的计算 hash:string integer 减少冲突，分布均匀 充分考虑程序设计语言的特点 若有变量：V001,V002,V300，且首字母的值作为hash值。会发生什么？一种可行的hash函数计算方法：从串s=c1c2ck的字符ci确定正整数h：令：h0=0,计算：hi=hi-1+ci,1ik,得到：h=hk =1或是素数，如=65599。思考题：根据上述方法，设计一个hash函数并测试之。根据测试结果讨论各参数值对函数结果的影响。取一素数m,令 h=h mod m。散列函数的计算（续1）思考题（P108）：对于下列函数：#include const int PRIME=211;const int EOS=0;int hashpjw(char*s)char*p;unsigned h=0,g;for(p=s;*p!=EOS;p+)h=(h24);h=hg;return h%PRIME;(1)为每行语句写注释；(2)写出此函数的计算公式；(3)若参数是abcd，试给出返回值。结 束