第五章符号表 在编译程序的工作过程中,经常需要收集和记录源程序 中的一些信息,这些信息往往保存在称为符号表的表中,根据 不同的需要可建立如常数表,标识符表各种用途的符号表等 由于每使用一个标识符就需要査表,在整个编译过程中编译 程序对这些表格的操作是很频繁的。因此,如何提高填査表 的效率直接影响到编译程序的工作效率。 编译程序使用的数据结构从使用的目的来看,可分为査 找型数据结构和分配型数据结构。査找型数据结构在编译程 序中用于构造不同的信息表,保存源程序中不同实体的属性 信息。这种结构的特点是每个实体的项只创建一次,但可以 查询多次。因此,査询效率很重要。分配型数据结构主要用 于处理嵌套结构的程序。其特点是分配给实体的内存地址对 实体用户是可知的。因此,不会对其进行查询操作,但分配 和回收的速度及内存的使用效率却是十分重要的。这里结合 查找型数据结构重点讨论符号表
第五章 符号表 在编译程序的工作过程中，经常需要收集和记录源程序 中的一些信息,这些信息往往保存在称为符号表的表中，根据 不同的需要可建立如常数表，标识符表各种用途的符号表等。 由于每使用一个标识符就需要查表，在整个编译过程中编译 程序对这些表格的操作是很频繁的。因此，如何提高填查表 的效率直接影响到编译程序的工作效率。 编译程序使用的数据结构从使用的目的来看，可分为查 找型数据结构和分配型数据结构。查找型数据结构在编译程 序中用于构造不同的信息表，保存源程序中不同实体的属性 信息。这种结构的特点是每个实体的项只创建一次，但可以 查询多次。因此，查询效率很重要。分配型数据结构主要用 于处理嵌套结构的程序。其特点是分配给实体的内存地址对 实体用户是可知的。因此，不会对其进行查询操作，但分配 和回收的速度及内存的使用效率却是十分重要的。这里结合 查找型数据结构重点讨论符号表
51分配型数据结构 5.1.1栈 栈是一种先进后出,后进先出的数据结构;访问栈一般访 问的是栈顶元素。栈在编译程序中也起着重要的作用,如递 归过程(或函数)中说明的动态的局部变量(非静态变量), 每进入一次如递归过程(或函数)就需分配相应的一块存储 单元,而这种存储单元的分配却符合栈这种先进后出,后进 先出特性
5.1 分配型数据结构 5.1.1 栈 栈是一种先进后出，后进先出的数据结构；访问栈一般访 问的是栈顶元素。栈在编译程序中也起着重要的作用，如递 归过程（或函数）中说明的动态的局部变量（非静态变量）， 每进入一次如递归过程（或函数）就需分配相应的一块存储 单元，而这种存储单元的分配却符合栈这种先进后出，后进 先出特性
例:设有 PASCAL程序 program calco var a, b, sum: integer; procedure add(var x, y: integer) begin sum =X+y end begin add(3,5) write(sum) end
例：设有PASCAL程序 program calc(); var a,b,sum:integer; procedure add(var x,y:integer); begin sum:=x+y; …… end; begin add(3,5); write(sum); end
则编译语句sum:=X+y时过程add的符号和主程序calc 的符号都在符号表中,当过程add编译后其符号没有意义, 可以从符号表中退去,如图显示。 TOP add RB sulIn a calc SB
则编译语句 sum:=x+y 时过程add的符号和主程序calc 的符号都在符号表中，当过程add编译后其符号没有意义， 可以从符号表中退去，如图显示
为了方便地入栈和退栈,把原来的栈顶元素的地址也放入 符号表。如图: TOP一 y add RB一 sun calc SB一
为了方便地入栈和退栈，把原来的栈顶元素的地址也放入 符号表。如图：
如果一个层次的符号结构看作一个记录的话,有分配符号表 和回收符号表的动作: 分配时动作: (1)TOP:=TOP+1;/分配存放原记录底的单元* (2)TOP*:=RB;将原记录底放入栈中* (3)RB: =TOP /RB指向新记录的底* (4)TOP:=TOP+n;鬥将栈指针指向分配后的栈顶* 回收时动作: (1)TOP:=RB-1;/恢复栈顶* (2)RB:=RB*;/*将保存的原记录底取出*
如果一个层次的符号结构看作一个记录的话，有分配符号表 和回收符号表的动作： 分配时动作： (1) TOP：=TOP+1；/*分配存放原记录底的单元*/ (2) TOP*:=RB; /*将原记录底放入栈中*/ (3) RB:=TOP; /*RB指向新记录的底*/ (4) TOP:=TOP+n; /*将栈指针指向分配后的栈顶*/ 回收时动作： (1) TOP：=RB-1；/*恢复栈顶*/ (2) RB:=RB*; /*将保存的原记录底取出*/
分配和收回示意图如下: TOP TOP TOP RB RB RB.SB一 SB SB
分配和收回示意图如下：
5.12堆 堆是一种非线性结构,它允许随机分配和回收实体。分 配请求返回的是指向所分配区域的指针,删除(回收)请求 需提供指向回收区域的指针。堆不提供任何访问被分配实体 的方式,它假设被分配实体的用户保留了指向分配区域的指 针 例:执行以下C程序后堆的状态如图所示: int ptr1, ptr 2, float* ptr 3 ptr1=(int*calloc(3, sizeof(int) ptr 2=(int *)calloc(2, sizeof(int) ptr 3=( float *)calloc(3, sizeof(float)) free(ptr2)
5.1.2 堆 堆是一种非线性结构，它允许随机分配和回收实体。分 配请求返回的是指向所分配区域的指针，删除（回收）请求 需提供指向回收区域的指针。堆不提供任何访问被分配实体 的方式，它假设被分配实体的用户保留了指向分配区域的指 针。 例：执行以下C程序后堆的状态如图所示： int * ptr1,* ptr2; float * ptr3; ptr1=(int *)calloc(3,sizeof(int)); ptr2=(int *)calloc(2,sizeof(int)); ptr3=(float *)calloc(3,sizeof(float)); free(ptr2);
head eth域 tr2 pt3匚·eth域了 eth域 enth
3个内存区在调用calc后被分配出去,指针ptr1,ptr2 ρtr3分别指向这些区域。fre释放了pt2指向的区域,这就产 生了一个“洞”。每个要被分配的区域都假设在分配前包含 length域。 在使用堆这种数据结构中,反复在堆中分配,释放会造成 不少空闲区(洞或碎片)。如何回收这些空闲区,进行合理 再分配,以提高内存的利用率是评判内存管理的标准。 要回收这些空闲区域,首先必须标明空闲区域,目前常用 的技术有引用计数和回收集两种。在引用计数技术中,系统 为每个内存区都关联一个引用计数器来指出引用的次数。当 新的用户访问该区域时,计数值增加,访问结束后减少。当 计数值为0时表明该区域为空闲。这种技术易于执行,但开 销会不断增大。回收集技术用两次扫描来辨别空闲区。第 次扫描所有已分配区的指针,标记那些已使用的内存区域; 第二次扫描标出所有未标记区,确认它们为空闲区。该技术 的开销不会逐渐增大
3个内存区在调用calloc后被分配出去，指针ptr1，ptr2， ptr3分别指向这些区域。free释放了ptr2指向的区域，这就产 生了一个“洞”。每个要被分配的区域都假设在分配前包含 length域。 在使用堆这种数据结构中，反复在堆中分配，释放会造成 不少空闲区（洞或碎片）。如何回收这些空闲区，进行合理 再分配，以提高内存的利用率是评判内存管理的标准。 要回收这些空闲区域，首先必须标明空闲区域，目前常用 的技术有引用计数和回收集两种。在引用计数技术中，系统 为每个内存区都关联一个引用计数器来指出引用的次数。当 新的用户访问该区域时，计数值增加，访问结束后减少。当 计数值为0时表明该区域为空闲。这种技术易于执行，但开 销会不断增大。回收集技术用两次扫描来辨别空闲区。第一 次扫描所有已分配区的指针，标记那些已使用的内存区域； 第二次扫描标出所有未标记区，确认它们为空闲区。该技术 的开销不会逐渐增大