电子科技大学计算机科学与工程学院编译原理课件第13章 运行时存储空间的组织.ppt

第13章 运行时存储空间的组织 第一节 程序的存储空间 1. 代码空间和数据空间 1.1 程序投入运行的必要条件 程序要投入运行，必须在内存中分配一定的存储空间，并将程序装入其中，包括： 可运行的代码（代码空间） 代码运行的环境（数据空间） 1.2 代码空间（C） 内容：线性存放着目标指令序列。当前执行的指令位置由指令指针ip指示。 1.3 数据空间（D） 内容：变量、常数、控制信息、描述符等。 静态分配：在运行前就可确定数据空间的大小, 在编译时刻就能进行的存储分配。 动态分配：运行时才能进行的存储分配。 2. 活动记录 程序由程序单元（函数、子程序）组成，因此程序的数据空间由相应程序单元的数据空间组成。 一个程序单元的数据空间叫做该程序单元的活动记录。 一个程序单元在执行过程中所需要的数据信息、管理信息都是通过它的活动记录来存放的。 一个程序单元的每一次激活，都应在内存中建立相应的活动记录。 2.1 活动记录的内容 (1) 返回地址 (2) 动态连接 (3) 静态连接 (4) 现场保护 (5) 参数区 (6) 变量区 2.2 活动记录的特点 除了变量存储区外，其余部分存储长度编译时可以确定，所以变量 i 的地址可用下式表示： D + offset(i) 其中， D是活动记录的首地址；offset(i)是变量 i 在活动记录中的位移。 2.3 变量的类型 1) 静态变量 编译时可以确定活动记录的首地址D和变量的相对位置offset(i) 。不管在程序单元的哪一次激活中，变量的存储位置均为：D+offset(i)。 2) 半静态变量 编译时可确定变量i的相对位置offset(i)，单元激活时可确定活动记录的首地址D。则每一次激活，变量对应一个不同的存储位置：D+offset(i)。 3) 半动态变量 编译时不能确定变量 i 的相对位置offset(i)，但能确定 i 的存储格式。 可在活动记录中为 i 建立一个描述符，用于记录 i 在内存中的存储格式，并在描述符中建立一个指针域，用于记录 i 在运行时的具体存储地址。 例：动态数组 int a[1..m]; int b[1..m][1..n]; 4) 动态变量 编译时不能确定变量 i 的相对位置offset(i)，也不能确定 i 的存储格式。 即描述符需要到运行时才能确定，因此可在活动记录中为 i 设置两个指针，一个记录运行时描述符的地址，另一个记录运行时 i 的地址。 例： 某些语言中类型可变的变量； 某些语言中维数可变的数组。 4. 存储分配模式 4.1 静态分配 可用于静态变量的分配，变量与存储区域的绑定关系在编译时便可建立，并完成存储分配； 不允许递归调用，不允许动态数组，不允许动态类型的数据对象。 4.2 栈式分配 用栈分配活动记录； 各程序单元之间的调用遵循“后进先出”模式； 活动记录的建立和撤消也满足“后进先出”模式； 分配方法：当一个程序单元被激活时, 在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动记录撤销。 例子：某程序中各程序单元的调用顺序为： …… P运行 P调用Q Q调用R …… R退出 Q退出 P退出 …… 4.3 堆分配 由于动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变，所以不可能在栈上为这样的对象分配存储区。对于这些变量，必须分配在堆上。 例如：C中通过malloc分配的变量；某些语言中的动态变量等。 4.4 存储空间的组织 第二节 栈式分配 1. 半静态变量的栈式分配 1.1 特点 变量及活动记录的长度都可静态确定； 一个程序单元可能被多次激活，活动记录是在程序单元激活时动态建立，并与代码段建立联系的。 1.2 处理方法 (1) 设置当前栈指针current，表示当前活动记录的开始位置（活动记录首地址D）； (2) 指针free表示数据存储器下一个可用单元； (3) 变量绑定于它在活动记录中的常数位移 i，变量通过current变址访问； (4) A调用B时，在A活动记录的栈顶之上建立B的当前实例的活动记录； (5) 从B返回时，释放其活动记录。 1.3 动态连接和动态链 动态连接：A调用B时，B的活动记录中保存的A的活动记录地址。 动态链：由动态连接组成的一个调用链。 1.4 CALL P的翻译 (1) D[ free ] := ip + 5（保存返回地址） (2) D[free + 1] := current （保存current ） (3) current := free （建立新的current） (4) free := free + L （调整free） (5) ip := P（转移到P） 例子：过程A调用过程P 1.5 RETURN语