编译技术编译原理 (39).pdf
编译技术运行时存储全局栈式存储分配全局栈式存储分配调用序列调用序列过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等过程调用序列过程返回序列过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间一般把临时数据域放在局部数据域的后面把参数域和可能有的返回值域放在紧靠调用者活动记录的地方用同样的代码来执行各个活动的保存和恢复全局栈式存储分配全局栈式存储分配过程p调用过程q的调用序列01全局栈式存储分配全局栈式存储分配过程p调用过程q的调用序列01全局栈式存储分配全局栈式存储分配返回值和参数 top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的调用序列01(1)p计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。top_sp的值在此过程中被改变全局栈式存储分配全局栈式存储分配返回值和参数返回值和参数 top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的调用序列01(2)p把返回地址压入q的活动记录，把控制转移到q全局栈式存储分配全局栈式存储分配返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的调用序列01(3)q将要保存寄存器的值和其它机器状态信息压入栈，把base_sp的当前值（pbase_sp）压入栈，并把当前top_sp的值作为自己base_sp的值。全局栈式存储分配全局栈式存储分配返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的调用序列01(4)q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体全局栈式存储分配全局栈式存储分配临时数据局部数据返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 调用者p和被调用者q之间的任务划分01全局栈式存储分配全局栈式存储分配临时数据局部数据返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 被调用者q的责任调用者p的责任调用者p的活动记录被调用者q的活动记录过程p调用过程q的返回序列02全局栈式存储分配全局栈式存储分配(1)q把返回值置入活动记录中存放返回值的地方 参数个数可变场合难以确定存放返回值的位置，因此通常用寄存器传递返回值临时数据局部数据返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的返回序列02全局栈式存储分配全局栈式存储分配(2)q对应调用序列的步骤(4)，q增加top_sp的值返回值和参数返回值和参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的返回序列02全局栈式存储分配全局栈式存储分配(3)q恢复寄存器(包括base_sp)和机器状态，把控制返回p返回值和参数返回值和参数 top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程p调用过程q的返回序列02全局栈式存储分配全局栈式存储分配(4)p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值返回值和参数 top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程的参数个数可变的情况03全局栈式存储分配全局栈式存储分配(1)函数返回值改成用寄存器传递临时数据局部数据参数参数 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程的参数个数可变的情况03全局栈式存储分配全局栈式存储分配(2)编译器产生将实参表达式逆序计算并将结果进栈的代码自上而下依次是参数1,参数n(3)被调用函数能准确地知道第一个参数的位置(4)被调用函数根据第一个参数到栈中取第二、第三个参数等等临时数据局部数据参数1,参数n参数1,参数n 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 过程的参数个数可变的情况03全局栈式存储分配全局栈式存储分配C语言的printf函数就是按此方式，用C语言编写的下面语句的输出？printf(“%d,%d,%dn”);临时数据局部数据参数1,参数n参数1,参数n 控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 全局栈式存储分配全局栈式存储分配栈上可变长数据活动记录的长度在编译时不能确定的情况例：局部数组的大小要等到过程激活时才能确定备注：Java语言的实现是将它们分配在堆上访问动态分配的数组(1)编译时，在活动记录中为这样的数组分配存放数组指针的单元访问动态分配的数组(2)运行时，这些指针指向分配在栈顶的数组存储空间(3)运行时，对数组A和B的访问都要通过相应指针来间接访问只有作用范围在一个过程只有作用范围在一个过程中，且返回后不可访问的中，且返回后不可访问的数据对象才能分配在栈上。数据对象才能分配在栈上。访问动态分配的数组栈式分配的动态释放空间引起悬空引用：引用某个已被释放的存储单元全局栈式存储分配全局栈式存储分配main()int dangle()int q;int j=20;q=dangle();return&j;栈式分配的动态释放空间引起悬空引用：引用某个已被释放的存储单元全局栈式存储分配全局栈式存储分配main()int dangle()int q;int j=20;q=dangle();return&j;运行时存储空间的组织和管理运行时存储空间的组织和管理堆式分配栈式分配策略在下列情况下行不通：栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流不遵守栈式规则的有Pascal语言和C语言的动态变量Java禁止程序员自己释放空间运行时存储空间的组织和管理运行时存储空间的组织和管理堆式分配内存分配与释放按照任意次序进行堆中可能包含交错的正在使用的和已经释放的区域堆式分配与栈式分配的区别堆式分配与栈式分配的区别mq(1,9)r活动树活动树栈栈q(1,9)s控制链控制链控制链控制链q(1,9)r控制链控制链控制链控制链控制链控制链s堆堆
