第五章符号表在编译程序的工作过程中，经常需要收集和记录源程序中的一些信息,这些信息往往保存在称为符号表的表中，根据不同的需要可建立如常数表，标识符表各种用途的符号表等。由于每使用一个标识符就需要查表，在整个编译过程中编译程序对这些表格的操作是很频繁的。因此，如何提高填查表的效率直接影响到编译程序的工作效率。编译程序使用的数据结构从使用的目的来看，可分为查找型数据结构和分配型数据结构。查找型数据结构在编译程序中用于构造不同的信息表，保存源程序中不同实体的属性信息。这种结构的特点是每个实体的项只创建一次，但可以查询多次。因此，查询效率很重要。分配型数据结构主要用于处理嵌套结构的程序。其特点是分配给实体的内存地址对实体用户是可知的。因此，不会对其进行查询操作，但分配和回收的速度及内存的使用效率却是十分重要的。这里结合查找型数据结构重点讨论符号表。5.1分配型数据结构5.1.1栈栈是一种先进后出，后进先出的数据结构；访问栈一般访问的是栈顶元素。栈在编译程序中也起着重要的作用，如递归过程（或函数）中说明的动态的局部变量（非静态变量），每进入一次如递归过程（或函数）就需分配相应的一块存储单元，而这种存储单元的分配却符合栈这种先进后出，后进先出特性。例：设有PASCAL程序programcalc();vara,b,sum:integer;procedureadd(varx,y:integer);beginsum:=x+y;……end;beginadd(3,5);write(sum);end.则编译语句sum:=x+y时过程add的符号和主程序calc的符号都在符号表中，当过程add编译后其符号没有意义，可以从符号表中退去，如图显示。为了方便地入栈和退栈，把原来的栈顶元素的地址也放入符号表。如图：如果一个层次的符号结构看作一个记录的话，有分配符号表和回收符号表的动作：分配时动作：(1)TOP：=TOP+1；/*分配存放原记录底的单元*/(2)TOP*:=RB;/*将原记录底放入栈中*/(3)RB:=TOP;/*RB指向新记录的底*/(4)TOP:=TOP+n;/*将栈指针指向分配后的栈顶*/回收时动作：(1)TOP：=RB-1；/*恢复栈顶*/(2)RB:=RB*;/*将保存的原记录底取出*/分配和收回示意图如下：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);3个内存区在调用calloc后被分配出去，指针ptr1，ptr2，ptr3分别指向这些区域。free释放了ptr2指向的区域，这就产生了一个“洞”。每个要被分配的区域都假设在分配前包含length域。在使用堆这种数据结构中，反复在堆中分配，释放会造成不少空闲区（洞或碎片）。如何回收这些空闲区，进行合理再分配，以提高内存的利用率是评判内存管理的标准。要回收这些空闲区域，首先必须标明空闲区域，目前常用的技术有引用计数和回收集两种。在引用计数技术中，系统为每个内存区都关联一个引用计数器来指出引用的次数。当新的用户访问该区域时，计数值增加，访问结束后减少。当计数值为0时表明该区域为空闲。这种技术易于执行，但开销会不断增大。回收集技术用两次扫描来辨别空闲区。第一次扫描所有已分配区的指针，标记那些已使用的内存区域；第二次扫描标出所有未标记区，确认它们为空闲区。该技术的开销不会逐渐增大。为了管理空闲区，系统将空闲区组成空闲链，并设立了一个链头指针，每个空闲区域的第一个字为本区域的长度。第二个字为一个指针指向下一个空闲区。如图所示，以满足分配请求。还可以通过内存重整理，使若干个由链相联系的空闲区合并成一个连续的空闲区以提高内存的使用率。使用空闲链结构时，完成分配请求可采用首次适配法和最佳适配法。5.2查找型数据结构由于在语法分析中采用的是上下文无关的方法,而实际算法语言往往是上下文有关的。如：标识符的前说明后使用问题函数的参数个数和类型匹配。如何解决这些问题一般采用通过填查符号表来决定的。因此如何组织和查找符号表对编译程序的效率有着重大的影响。下面介绍以查找型数据结构的符号表。5.2.1表的组织在编译程序中符号表用来存放语言程序中出现的有关标识