Bonky Zhu
If someone is able to show me that what I think or do is not right, I will happily change, for I seek the truth, by which no one was ever truly harmed. It is the person who continues in his self-deception and ignorance who is harmed.

编译原理 – 存储分配

运行存储分配策略

  • 静态存储分配:在编译时刻就可以确定大小的数据对象,可以在编译时刻就为它们分配存储空间。
  • 动态存储分配:编译时无法完全确定数据对象的大小,在运行时刻,再动态地分配数据对象的存储空间。主要有栈和堆式存储分配。

image-20191125104735054

活动记录

使用编译器通常以过程(函数,方法)为单位分配存储空间,过程体的每次执行称为该过程的一个活动。

过程每执行一次,就为它分配一块连续存储区,用来管理过程一次执行所需的信息,这块连续存储区称为活动记录。活动记录的形式一般如下:

image-20191125105814330

静态存储分配

在静态存储分配中,编译器为每个过程确定其活动记录在目标程序中的位置。这样,过程中每个名字的存储位置就确定了。 

因此,这些名字的存储地址可以被编译到目标代码中。过程每次执行时,它的名字都绑定到同样的存储单元。

适合静态存储分配的语言必须满足以下条件:

  • 数组上下界必须是常数 
  • 不允许过程的递归调用 
  • 不允许动态建立数据实体

满足这些条件的语言有BASIC和FORTRAN等。分配方法主要有顺序分配法和层次分配法。

顺序分配法

按照过程出现的先后顺序逐段分配存储空间 各过程的活动记录占用互不相交的存储空间。

image-20191125112117371

层次分配法

通过对过程间的调用关系进行分析,凡属无相互调用关系的并列过程,尽量使其局部数据共享存储空间

image-20191125112205667

动态存储分配

栈式存储分配

当一个过程被调用时,该过程的活动记录被压入栈;当过程结束时,该活动记录被弹出栈。

活动树

用来描述程序运行期间控制进入和离开各个活动的情况的树。

例:下面是一个快速排序的活动树:

image-20191125114400314

下面是当执行到 q(2,3) 的控制栈,注意,这个栈是从上向下的。

image-20191125114448201

一般来说,控制栈的设计如下:

image-20191125115958633

  • 临时变量:编译产生的,用于暂存值的变量
  • 保存机器状态:调用过程的活动在调用点的机器状态,包括计数器,各种寄存器的值
  • 静态链:指向本活动要访问的非局部数据所在的活动记录。
  • 控制链:指向主调过程的活动记录的首地址

调用序列和返回序列

调用序列

调用者计算实际参数的值,将返回地址放到被调用者的机器状态字段中。将原来的top-sp(栈顶指针寄存器,指向局部数据开始的位置)值放到被调用者的控制链中。 然后,增加top-sp的值,使其指向被调用者局部数据开始的位置。

被调用者保存寄存器值和其它状态信息,初始化其局部数据并开始执行。

返回序列

被调用者将返回值放到与参数相邻的位置,然后恢复top-sp和其它寄存器,最后跳转到由调用者放在机器状态字段中的返回地址。

image-20191125210638128

变长数据的存储分配

在现在的高级语言中,在编译时刻不能确定大小的对象将被分配在堆区。但是,如果它们是过程的局部对象,也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因:可以避免对它们的空间进行垃圾回收,也就减少了相应的开销。

屏幕快照 2019-11-25 下午9.35.44

非局部数据的访问

语言可以分为两种类型:

  • 支持过程嵌套声明的语言,即可以在一个过程中声明另一个过程,如 Pascal
  • 不支持过程嵌套声明的语言,不可以在一个过程中声明另一个过程。如 C 系列

无过程嵌套声明时的数据访问

  • 全局变量被分配在静态区,使用静态确定的地址访问它们
  • 其它变量一定是栈顶活动的局部变量。可以通过运行时刻栈的top_sp指针访问它们

有过程嵌套声明时的数据访问

访问链:可以在相互嵌套的过程的活动记录之间建立访问链,使得内嵌的过程可以访问外层过程中声明的对象。

访问链的建立:实质上就是指向自己的父亲的活动记录。

堆式存储分配

堆式存储分配是把连续存储区域分成块,当活动记录或其它对象需要时就分配。

申请

设当前自由块总长为M,欲申请长度为n

如果存在若干个长度大于或等于n的存储块,可按以下策略之一进行存储分配。

  • 取长度m满足需求的第1个自由块,将长度为m-n的剩余部分仍放在自由链中(首次优先)
  • 取长度m满足需求的最小的自由块(最佳优先)
  • 取长度m满足需求的最大的自由块(最大优先)

如果不存在长度大于或等于n的存储块

  • 如果M≥n,将自由块在堆中进行移位和重组
  • 如果M<n,则应采用更复杂的策略来解决堆的管理问题

释放

只需将被释放的存储块作为新的自由块插入自由链中, 并删除已占块记录表中相应的记录即可

符号表

为每个程序块建立一个独立的符号表。

image-20191125221014408

首先看一下主过程,首先,符号表有一个头部,其中第三行是主过程所需要的存储空间。

对于变量,第一列是变量名,第二列是变量类型,第三列是变量的相对地址。对于所定义的函数,有一个指针指向所定义函数的符号表,相应的,对应的函数的头部有一个指针指向主函数。

当我们需要某个符号的时候,就会跟着访问链向上访问,直到找到某个符号。(可以根据这个判断局部变量的传递)

def foo():
  a = 3 
  def bar():
    print(a)
  bar()

foo()


上面的代码执行就是 3

Share

You may also like...

发表评论