嵌套过程语言的栈式存储分配-编译原理与实践

简单栈式存储分配适用于过程定义不嵌套的程序设计语言，而对于允许过程定义嵌套的语言（如Pascal语言）来说，则需要一种较为复杂的栈式存储分配方式，这就是本节将要讨论的内容。

图7-18给出了一个Pascal语言的程序结构，并对程序里各个过程的嵌套关系以及各个变量的作用域做了注释。

图7-18　一个Pascal语言程序

在图7-18中，假定主程序P的层数为0，于是可称主程序为第0层过程。由于过程Q是在层数为0的过程P内定义的，并且P是包围Q的最小过程，因此，Q的层数就为1。此时，P被称作直接外层过程，Q被称作P的内层过程。同理，S的层数也为1，R的层数则为2。当编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。过程层数的确定可使用计数器level来进行，初始时置为0，每当遇到procedure begin时，将其累增1，每当碰到procedure end时，则将其递减1。另外，过程S和R都引用了最外层过程P的变量a，过程Q则引用了过程P的变量x，而过程R则又引用了其直接外层过程Q的变量b。程序在运行时，过程中每个局部变量和形参在栈上的存储地址的确定可以采用7.6.1节的办法，但是，对于嵌套过程的非局部变量的访问则要复杂得多。因此，下面主要对非局部变量访问的实现方法予以探讨。

一个过程X可以引用包围它的任一外层过程Y所定义的变量或数组，也就是说，程序运行时，过程X可能引用它的任一外层过程Y的最新活动记录中的某些数据，这些数据被看作是过程X的非局部量。为了在活动记录中查找非局部名字所对应的存储空间，过程X运行时必须设法跟踪每个外层过程的最新活动记录的位置。跟踪方法有很多，这里仅讨论display表（显示表）法。

display表具有栈的结构，用来存放所有嵌套的外层过程的现行活动记录的基地址。程序运行时，每进入一个过程，就会在建立它的活动记录区的同时建立一张display表。如果过程的嵌套层数为i，则该表将包含i+1个单元。例如，在如图7-18所示的程序中，过程R的外层为Q，Q的外层为P，则R运行时display表的内容如下：

过程的层数是可以静态确定的，因此，每个过程的display表的大小在编译时也可以确定。于是，根据非局部变量说明所在的静态层数与其活动记录的相对地址即可得到如下的绝对地址计算公式：

绝对地址=display[静态层数]+相对地址

为方便起见，可把display表看作是活动记录的一部分，如图7-19所示。

图7-19　活动记录结构

由于每个过程的形式单元数目在编译时是知道的，因此，display表的相对地址d（相对于活动记录起点）在编译时也是确定的。假定在现行过程中引用了某一层数为k的外层过程的变量V，那么，V的值可以利用以下两条变址指令得到：

（1）将第k层过程的最新活动记录地址放入寄存器R1中(www.xing528.com)

MOV R1,(d+k)[SP]

（2）把X的值传给寄存器R2

MOV R2,V[R1]

图7-20给出了图7-18程序运行时栈的变化过程及可访问的display表的内容。

图7-20　程序运行时可访问的display表的内容

由上可以看出，通过display表的一个域即可确定任意外层活动记录的指针，然后沿着该指针便可找到处于外层活动记录的非局部变量，因此，该方法是快速访问非局部变量的一个较好选择。

当过程P1调用过程P2而进入P2后，P2究竟该如何建立自己的display表呢？若要建立display表，P2必须知道其直接外层过程（记为P0）的display表。下面分两种情形进行讨论。

（1）当P2是一个真实的过程时，此时，P0要么是Pl自身，要么既是P1外层又是P2的直接外层，如图7-21所示。不论哪种情形，只要在进入P2后能够知道P1的display表，就能够知道P0的display表，从而可直接构造出P2的display表。实际上，只需从P1的display表中自底而上地取过i2个单元，i2为P2的层数，再添上进入P2后新建立的SP值就构成了P2的display表。在这种情况下，只需把P1的display表的地址作为连接数据之一传送给P2就能够建立P2的display表。

图7-21　P1调用P2的两种不同嵌套

（2）当P2是一个形式参数时，调用P2意味着调用P2当前相应的实在过程，此时，P0应是该实在过程的直接外层过程。假定P0的display表地址可从形式单元P2所指示的地方获得，为了能在P2中获得P0的display表地址，必须在Pl调用P2时设法把P1的display表地址作为连接数据之一（称为全局display表地址）传送给P2。于是，连接数据变为由旧SP值、返回地址以及全局display表地址3项构成，从而形成了如图7-19所示的活动记录结构。

需要说明的是，0层过程，也就是主程序的display表仅含有一项内容，它就是主程序开始工作时所建立的第一个SP值。