《符号表管理和存储组织.ppt》由会员分享，可在线阅读，更多相关《符号表管理和存储组织.ppt（48页珍藏版）》请在三一办公上搜索。
1、第9章符号表管理和错误处理,明确符号表的作用、内容、组织明确错误处理的两种方法：错误校正和局部化处理,教学目标,9.1 符号表管理9.2 错误处理,教学内容,编译程序中使用最多的数据结构是表源程序中的各种信息，以便查询或修改在这些表中，尤以符号表最为重要生存期最长使用最为频繁,9.1符号表管理,9.1.1 符号表的作用和内容,9.1.2 符号表的组织,操作：（1）向表中填入一个新标识符。（2）对于给定一个标识符：查找是否在表中；访问它在表中的相关信息；在表中填写或更新它的某些信息。（3）更新或删除一个或一组无用的项。,9.1.2 符号表的组织,Hash表的基本思想是：为符号表设置一个足够大的空
2、间M为符号构造一个散列函数Hash(Ki)，使得0 Hash(Ki)M-1,i=1，2，n这样查找Ki时，Hash(Ki)就决定了Ki在符号表中的位置,构造Hash函数的方法：将标识符中的每个字符转换为一个非负整数将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来）将结果数调整到0M-1范围内，可以利用取模的方法，Ki%M（M为素数）,解决地址冲突的方法：由于用户定义标识符的随机性，Hash函数值在0M-1范围内不一定唯一若两个标识符具有相同的函数值，则可用开放地址法或链地址法解决冲突，有关内容可以参考数据结构的教材。,词法错误语法错误语义
3、错误违反了语言的环境限制数组维数太大循环嵌套层数太多,6.2错误处理,词法错误、语法错误和语义错误,超越系统限制：(计算机系统和编译系统),1.数据溢出错误，常数太大，计算结果溢出。,2.符号表、静态存储分配数据区溢出。,3.动态存储分配数据区溢出。,语义规则,标识符先说明后引用标识符引用要符合作用域规定过程调用时实参与形参类型一致参与运算的操作数类型一致下标变量的下标不能越界,错误处理方法有两种：错误校正法：根据文法进行错误改正错误局部化法：把错误的影响限制在一个局部的范围，避免错误扩散和影响程序其他部分的分析,错误局部化法,词法分析：发现不合法字符，显示错误，并跳 过该标识符(单词)继续往
4、下分析。,语法语义分析：跳过所在的语法成分(短语或语 句)，一般是跳到语句右界符，然后从新语句继续往下分析。,错误局部化处理的实现（递归下降分析法）,err:全局变量，存放错误信息。,用递归下降分析时，如果发现错误，便将有关错误信息（字符串或者编号）送err，然后转错误处理程序；出错程序先打印或显示出错位置以及出错信息，然后跳出一段源程序,直到跳到语句的右界符或正在分析的语法成分的合法后继符号为止,然后再往下分析。,if_ statement()getsym();/*读下个单词符号*/C();/*表达式处理程序*/if not sym=“then”err:=“缺then”;error();/*
5、出错处理程序*/else getsym();statement();if sym=“else”getsym();statement();,if then else;,error()printf(linecnt,err);do getsym();while(sym!=“;”or sym!=“end”),发现错误立即跳到语句结尾处(语句右界符;或end),这样处理较粗糙,将跳过太多；上例中,缺then,就将跳过整个条件语句,使得then后的语句都被跳过而不分析,其中有错误就发现不了,(3)提高错误局部化程度的方法,设 S1:合法后继符号集(某语法成分的后继符号)S2:停止符号集(跳读必须停止的符号
6、集),error(S1,S2)printf(linecnt,err);do getsym();while(sym not in S1 or not in S2),若有错,则可跳到then若statement有错,则可跳到else,if then else;,编译程序在其工作过程中使用最多的数据结构是表，在这些表中，符号表最为重要，它的生存期最长、使用最频繁。掌握符号表的作用、内容、组织（多采用散列法）明确错误处理的两种方法：错误校正和局部化处理了解局部化处理方法的实现,小结,第10章目标程序运行时的存储组织,1.全面了解目标程序运行时存储区的整体布局；每种存储区的组织方式和管理方法；2.参数传
7、递的几种方式,教学目标,第十章 目标程序运行时的存储组织,10.1 数据空间的使用与管理,数据空间的使用和管理方法分成二种：静态存储分配动态存储分配栈式动态存储分配堆式动态存储分配,如果一个名字的性质通过说明语句或隐式或显式规则而定义，则称这种性质是“静态”确定的。在编译时就能确定目标程序运行中所需的全部数据空间的大小，并安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，这种分配策略为静态存储分配。,10.1.1 静态存储分配,动态存储管理技术有两种方式：栈式（stack）堆式（heap）,10.1.2 动态存储分配,如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和
8、释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变数组。,栈式动态存储分配策略适用于PASCAL，C/C+，ALGOL之类具有递归结构的语言的实现。,将整个程序的数据空间设计为一个栈。在具有递归结构的程序中，当调用一个过程时，所需的数据空间分配在栈顶，当过程结束时释放空间。,栈式动态存储分配,栈式动态存储分配,过程所需数据空间包括两部分：,（1）生存期在本过程这次活动中的数据对象（2）用以管理过程活动的记录信息。
9、即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返回地址）、寄存器的值等，都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动继续,如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制，如+中的new，delete等机制，或者不仅有过程而且有进程的程序结构的情况下，空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。通常使用一种称为堆式的动态存储分配方案。,堆式动态存储分配,定长块管理变长块管理,堆式动态储分配的实现,定长块管理 堆式动态存储分配最简单的实现是按定长
10、块进行。（1）初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针available指向链表中的第一块。（2）分配时每次都分配指针available所指的块，然后available指向相邻的下一块。（3）归还时，把所归还的块插入链表。考虑插入方便，可以把所归还的块插在available所指的块之前，然后available指向新归还的块。,变长块管理可以根据需要，分配长度不同的存储块，可以随要求而变（1）按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块能和现有的
11、空间能合并，则合并成一块；（2）如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，或者从该块上分割一小块分配出去。,首次满足法最优满足法最差满足法,？若空闲块表中有若干个满足需要的空闲块，该分配哪一块呢？通常有三种不同的分配策：,（1）首次满足法只要在空闲块链表中找到满足需要的一块，就进行分配。如果该块很大，则按申请的大小进行分割，剩余的块仍留在空闲块链表中如果该块不很大，比如说，比申请的块大不了几个字节，则整块分配出去，以免使空闲链表中留下许多无用的小碎块。,（2）最优满足法将空闲块链表中一个不小于申请块且最接近于申请块的
12、空闲块分配给用户。系统在分配前首先对空闲块链表从头至尾描一遍，从中找出一块不小于申请块且最接近于申请块的空闲块分配。在用最优满足法进行分配时，为避免每次分配都要扫描整个链表，通常将空闲块链表空间的大小从小到大排序。这样，只要找到第一块大小申请块的空闲块即可进行当然，在回收时将释放的空闲块插入到链表的适当位置上去。,（3）最差满足法将空闲块表中不小于申请块且是最大的空闲块的一部分分配给用户。假设空闲块链表按大小从大到小排序，每次分配只需删除第一个结点，将其中一部分分配给用户，其它部分作为新的结点插入到空闲块表的适当置上去。,三种分配策略比较1.从空间上来看：最优满足法适用于请求分配的内存大小范围
13、较广的系统。按最优满足法分配时，总是找大小最接近于请求的空闲块，可能产生一些存储量很小而无法利用的小片内存，保留那些很大的内存块以备响应后面可能发生的内存量较大的请求。最差满足法每次都是从内存最大的结点开始分配，从而使链表中的结点趋于均匀。因此，它适用于请求分配的内存大小范围较窄的系统。首次满足法的分配是随机的，介于两者之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息情况。,2.从时间上来看首次满足法在分配时需查询空闲块链表，而回收时仅需插入到表头即可。最差满足法恰好相反，分配时无需查表，回收时则为将新的空闲块插入表中适当的位置，需先进行查找。最优满足法则不论分配与回收，均
14、需查找链表，因此最费时间。不同的情况应采用不同的方法。在选择时需考虑下列因素：用户的要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性,10.2 参数传递,当一个过程调用其它过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递。,10.2 参数传递,过程exchangel既使用了非局部量数组a，又使用了形式参i和j，将ai和aj的值进行交换。带有非局部变量和形参的PASCAL过程(1)procedure exchangel(i，j:integer);/过程exchangel的头，带有形式参数i，j(2)var x:integer;(3)begin;x=ai;ai=a
15、j;aj=x/数组a是非局部变量(5)end;,如语句exchangel(m，n);表示了对过程exchangel的一次调用，其中m，n为实在参数，简称实参。讨论的问题是：为执行exchangel(m，n)，i，j应按何种方式同实参m，n相联，换句话说，如何把实在参数传递给相应的形式参数呢？有几种方法：值调用，地址调用，名字调用以及宏扩展,带有过程swap的PASCAL程序(1)program reference(input,output);(2)var a,b;integer;(3)procedure swap(var x,y:integer);(4)var temp：integer;(5)
16、begin(6)temp：=x;(7)x：=y;(8)y：=temp(9)end;(10)begin(11)a：=1;b：=2;(12)swap(a,b);(13)writeln(a=,a);writeln(b=,b)(14)end.,输出：a=2，b=1。如将第3行的var去掉，则输出：a=1，b=2。,有var时，PASCAL语言的参数传递使用的方式是传地址；去掉var，则使用的方式是传值。PASCAL语言的变量参数是在参数前加关键字var。这种参数的传递方式是传地址例如：swap(var x,y:integer);swap(a,b)；调用结果：a,b的值被改变。在参数前不加关键字var时
17、是值调用。这种参数的传递方式是传值。例如：swap(x,y:integer);swap(a,b)；结果：a,b调用前的值不被改变。,10.2.1 传值传值，也称值调用。在被调过程的活动记录中开辟形参的存储空间，这些存储位置即是形参或形式单元。调用过程计算实参值，并将它们的右值放在为形式单元开辟的空间中。被调用过程执行时，就像使用局部变量一样使用这些形式单元。这种调用方式不影响调用过程的活动记录。,10.2.2 传地址调用过程传给被调过程的是指针，指向实参存储位置的指针。如实参是一个名字或是具有左值的表达式，则左值本身传递过去。如实参是一表达式，比方a+b或2，而没有左值，则表达式先求值，并存入
18、某一位置，然后该位置的地址传递过去。被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。通过值调用的过程可以由非局部量或由指针而对调用过程发生影响。,10.2.3 过程参数 一个过程(函数)可以作为参数传递，比如图10.22的PASCAL程序中，过程c把f作为参数传递给b，而b通过引用形参h调用f。我们要注意的是：函数f有一非局部量m，图中特地将m圈起来。但m的作用域并不包括b的过程体。b中的语句writeln（h（2）激活f，是因为形参h引用f，writeln打印的是调用f（2）的结果。那么b激活f时，怎样设置f活动记录的存取链（display）呢？答案是，当一个
19、嵌套过程作为参数传递时，必须连同它的存取链（display）一同传递过去。图10.23说明了这点，当过程c传递f时，c可以决定f的存取链，或者说f的存取链或display可以根据c的存取链或display来建立。c必须把f连同f的存取链一起传给b，那么在b中激活f时，b活动记录的存取链就可以正确设置了。,嵌套过程作为参数传递(1)program param(input，output);/例程param的头(2)procedure b(function h(n:integer):integer);/嵌套过程b的头，其形式参数是一个具有一个整型形参n的整型函数h(3)begin writeln(h
20、(2)end b;/b的过程体(4)procedure c;/嵌套过程c的头(5)var m:integer;(6)function f(n:integer):integer;/过程c中嵌套定义的具有一个整型形参n的整型函数f(7)begin f=m+n endf;/f的函数体(8)begin m=0;b(f)endc;/c的过程体，其中b(f)调用b函数，/而实参是函数f，调用时替换形参函数h(9)begin(10)c(11)end,连同存取链一起传递过程实参,一般来讲，过程P把过程T做为实参传递给Q时，也是一种传地址方式，P可以先建立两个相继的临时单元，第一个单元B1存放过程T的入口地址；第二单元B2存放现行display地址或存取链地址。然后把第一临时单元地址传送给Q（即放置于Q活动记录的形式单元，比方说Z中）。假定过程Q执行到引用形参Z时，Z中已含有上述B1的地址，则B1的内容将用来作为转子指令的目的地址（即转进过程T）。B2的内容将传送给T。除了实参是过程的情况外，还有实参为数组的情况，实参为标号的情况以及实参为形式参数的情况。,
