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