编译原理课件：Chapter-7 运行时的存储组织及管理.ppt

8/3/202418/3/20241第七章第七章 运行时的存储组织及管理运行时的存储组织及管理•7.1 7.1 概述•7.2 7.2 静态存储分配•7.3 7.3 动态存储分配18/3/202428/3/202427.1 概述概述(1) 运行时的存储组织及管理运行时的存储组织及管理 目标程序运行时所需要存储空间的组织与目标程序运行时所需要存储空间的组织与管理以及源程序中变量存储空间的分配管理以及源程序中变量存储空间的分配c 简单变量简单变量 realb 简单变量简单变量 reala 简单变量简单变量 real符号表数据区例：例：real a, b, c ; ... a:= b c ; 取取b   c 送送 a 28/3/202438/3/20243(2) 静态存储分配和动态存储分配静态存储分配和动态存储分配 在在编译阶段编译阶段由由编译程序编译程序实现对存储空间的管理实现对存储空间的管理,和为源程序中的变量分配存储的方法和为源程序中的变量分配存储的方法静态存储分配静态存储分配条件条件 如果在编译时能够确定源程序中变量在运行时如果在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变，那么就可以的数据空间大小，且运行时不改变，那么就可以采用静态存储分配方法。

采用静态存储分配方法但是并不是所有数据空间大小都能在编译过程中确定！但是并不是所有数据空间大小都能在编译过程中确定！38/3/202448/3/20244动态存储分配动态存储分配 在在目标程序目标程序运行阶段运行阶段由由目标程序目标程序实现对存储实现对存储空间的组织与管理，和为源程序中的变量分配存空间的组织与管理，和为源程序中的变量分配存储的方法储的方法特点特点• 在目标程序运行时进行分配在目标程序运行时进行分配• 编译时要生成进行动态分配的目标指令编译时要生成进行动态分配的目标指令48/3/202458/3/202457.2 静态存储分配静态存储分配(1) 分配策略分配策略 由于每个变量所需空间的大小在编译时已知，由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址因此可以用简单的方法给变量分配目标地址• 开辟一数据区首地址在加载时确定）开辟一数据区首地址在加载时确定）• 按编译顺序给每个模块分配存储按编译顺序给每个模块分配存储• 在模块内部按顺序给模块的变量分配存储，一般用相对在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型确定。

地址，所占数据区的大小由变量类型确定• 目标地址填入变量的目标地址填入变量的 符号表中符号表中58/3/202468/3/20246名字名字类型类型维数维数地址地址数据区数据区264r05088TOTINT假设整数占假设整数占4个字节大小，个字节大小，实数占实数占8个字节大小，则符个字节大小，则符号表中各变量在数据区中所号表中各变量在数据区中所分配的地址为：分配的地址为：例：有下列fortran 程序段 real MAXPRN, RATE integer IND1, IND2 real PRINT(100),YPRINT(5,100),TOTINT MAXPRNr0264RATEr0272IND1i0280IND2i0284PRINTr1288YPRINTr2108827228028428810885088+8×100+8×100×568/3/202478/3/20247(2) 模块（模块（FORTRAN子程序）的完整数据子程序）的完整数据区区编译程序除了要给源程序（模块）中的各种变编译程序除了要给源程序（模块）中的各种变量分配数据区以外，对子程序来说还要在数据区中量分配数据区以外，对子程序来说还要在数据区中保留保留返回地址，返回地址，对形式参数也要分配存储以存放相对形式参数也要分配存储以存放相应的实参的信息。

另外在编译时还要分配应的实参的信息另外在编译时还要分配临时变量临时变量空间（如存放表达式计算的中间结果等）空间（如存放表达式计算的中间结果等）78/3/202488/3/20248下面给出下面给出FORTRAN子程序的典型数据区子程序的典型数据区隐式参数区隐式参数区形式参数区形式参数区局部变量和局部变量和临时变量区临时变量区模块模块n－－1模块模块n模块模块n＋＋1隐式参数区：返回地址隐式参数区：返回地址 函数返回值函数返回值形式参数区：存放相应实参形式参数区：存放相应实参信息（值或地址）信息（值或地址）88/3/202498/3/202497.3 动态存储分配动态存储分配 由于编译时还不能具体确定某些数据空间的大小，故由于编译时还不能具体确定某些数据空间的大小，故对它们分配存储空间必须在程序运行时进行这时，编译对它们分配存储空间必须在程序运行时进行这时，编译程序生成有关存储分配的目标代码，实际上的分配要在目程序生成有关存储分配的目标代码，实际上的分配要在目标程序运行时进行这种分配方式称为标程序运行时进行这种分配方式称为动态存储分配。

动态存储分配 对于分程序结构，而且允许递归调用的语言，常使用对于分程序结构，而且允许递归调用的语言，常使用栈式动态存储分配栈式动态存储分配，即使用一个类似于堆栈的，即使用一个类似于堆栈的“运行栈运行栈”来实现数据区的分配来实现数据区的分配分配策略是分配策略是: 整个数据区为一个堆栈整个数据区为一个堆栈 (1) 当进入一个过程时，在栈顶为其分配一个数据区当进入一个过程时，在栈顶为其分配一个数据区 (2) 当退出一个过程时，撤消该过程的数据区当退出一个过程时，撤消该过程的数据区98/3/2024108/3/202410例例1: BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END12341234108/3/2024118/3/202411 BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; END END M2; CALL M1( X / Y )END运行中数据区的分配情况：运行中数据区的分配情况：X,Y,NAME数据区数据区AR1(a)X,Y,NAME数据区数据区AR1X和参数和参数IND数据区数据区AR2(b)X,Y,NAME数据区数据区AR1X和参数和参数IND数据区数据区AR2参数参数JAR3(c)X,Y,NAME数据区数据区AR1X和参数和参数IND数据区数据区AR2参数参数JAR3F，，TEST1数据区数据区AR4(d)X,Y,NAME数据区数据区AR1X和参数和参数IND数据区数据区AR2参数参数JAR3(e)X,Y,NAME数据区数据区AR1X和参数和参数IND数据区数据区AR2(f)X,Y,NAME数据区数据区AR1(g)118/3/2024128/3/2024127.3.1 活动记录活动记录一个典型的活动记录可以分为三部分：一个典型的活动记录可以分为三部分：局部数据区局部数据区参数区参数区display区区(1) 局部数据区：局部数据区：存放模块中定义的各个局部变量。

存放模块中定义的各个局部变量128/3/2024138/3/202413(2) 参数区：参数区： 存放隐式参数和显式参数存放隐式参数和显式参数形参数据区形参数据区prev abpret value参数区参数区显式参数区显式参数区(出现在用户源程序中出现在用户源程序中)隐式参数区隐式参数区(不出现在用户源程序中不出现在用户源程序中)ret addr：：返回地址，即调用语句的下一条执行指令地址返回地址，即调用语句的下一条执行指令地址prev abp：：存放调用模块记录基地址函数执行完时，释存放调用模块记录基地址函数执行完时，释 放其数据区，数据区指针指向调用前的位置放其数据区，数据区指针指向调用前的位置ret value ：：函数返回值（无值则空）函数返回值（无值则空）形参数据区：形参数据区：每一形参都要分配数据空间，形参单元中存每一形参都要分配数据空间，形参单元中存 放实参值或者实参地址放实参值或者实参地址局部数据区局部数据区参数区参数区display区区ret addr138/3/2024148/3/202414(3) display区：区： 存放各外层模块活动记录的基地址。

存放各外层模块活动记录的基地址 变量二元地址（变量二元地址（BL、、ON））BL：：变量声明所在的层次可以用它找到该层数据区变量声明所在的层次可以用它找到该层数据区开始地址开始地址 （注意为嵌套层次，并列过程具有相同层次）（注意为嵌套层次，并列过程具有相同层次）ON：：相当于显示参数区开始位置的位移（相对地址）相当于显示参数区开始位置的位移（相对地址） 对于例对于例1中所举的程序段，模块中所举的程序段，模块4可以引用可以引用模块模块1和模块和模块3中所定义的变量，故在模块中所定义的变量，故在模块4的的display区，应包括区，应包括AR1和和AR3的基地址的基地址局部数据区局部数据区参数区参数区display区区1234148/3/2024158/3/202415 高层（内层）模块可以引用低层（外层）高层（内层）模块可以引用低层（外层）模块中的变量，例如在模块中的变量，例如在M1中可引用外层模块中中可引用外层模块中定义的变量定义的变量 Y 在在 M1 中引用中引用Y时，可通过其时，可通过其 display 区找区找到程序块到程序块 1 的活动记录基地址，加上的活动记录基地址，加上 Y 在该数在该数据区的相对地址就可以求得据区的相对地址就可以求得 y 的绝对地址。

的绝对地址例如：程序模块例如：程序模块1 过程块过程块M1 x（（1，，0）） IND（（2，，0）） y（（1，，1）） x（（2，，1）） NAME（（1，，2）） BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; END END M2; CALL M1( X / Y )END(1)(2)(4)(3)158/3/2024168/3/202416例：下面给出源程序的目标例：下面给出源程序的目标程序运行时，运行栈（数据程序运行时，运行栈（数据区栈）的跟踪情况。

区栈）的跟踪情况BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); Y := 1.0; END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END1234 1 X, Y, NAME 2 M1: (IND); X; CALL M2; 3 M2: (J); 4 ARRAY F(J); TESTI; CALL M1NAMEYXabp局部数据区局部数据区(a) 进入模块进入模块1活动记录活动记录AR1(Active Record)168/3/2024178/3/202417XINDprev abpret addr(1)AR1AR2abp局部数据区局部数据区display区区参数区参数区(b) M1被调被调用用BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END1234abp(1) 1 X, Y, NAME 2 M1: (IND); X; CALL M2; 3 M2: (J); 4 ARRAY F(J); TESTI; CALL M1178/3/2024188/3/202418Jprev abpret addr(2)abp(1)AR2AR3abpAR1参数区参数区(c) M2被调用被调用BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END1234display区区188/3/2024198/3/202419display区区参数区参数区数组数组FTEST1F的模块的模块Prev abpRet addrabp(3)abp(1)AR3AR2AR1AR4abp局部数据区局部数据区(d) 进入内模块进入内模块4BBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END1234198/3/2024208/3/202420地址地址内容内容说明说明abp(4) →数组数组F程序进入第程序进入第4个模块个模块后。

后TEST1F的模块的模块Prev abpRet addrabp(3)abp(1)abp(3) →J在模块在模块2中通过执行中通过执行CALL M2(IND+1)进入第进入第3个模块，但个模块，但尚未进入第尚未进入第4个内层个内层模块时Prev abpRet addrabp(1)abp(2) →X通过最外层模块中通过最外层模块中调用调用CALL M1(X/Y)进入第进入第2个模块，尚个模块，尚未执行未执行CALL M2(IND+1)语句INDPrev abpRet addrabp(1)abp(1) →NAME系统进入第系统进入第1个模块，个模块，尚未执行到尚未执行到CALL M1(X/Y)时时YXBBLOCK; REAL X, Y; STRING NAME; M1: PBLOCK( INTEGER IND ) ; INTEGER X; CALL M2( IND + 1 ); END M1; M2: PBLOCK( INTEGER J ); BBLOCK; ARRAY INTEGER F( J ); LOGICAL TESTI; … END END M2; CALL M1( X / Y ) END1234abp(0) →main的数据的数据进入进入main函数的情况函数的情况（空）（空）OS（空）（空）208/3/2024218/3/202421（（e））当模块当模块4执行完，则执行完，则abp:=prev abp，，这样这样abp恢复恢复到进入模块到进入模块4时情况，运行栈情况如（时情况，运行栈情况如（c）。

f））当当M2执行完，则执行完，则abp:=prev abp，，这样这样abp恢复到恢复到进入模块进入模块M2时情况，运行栈情况如（时情况，运行栈情况如（b）g）当）当M1执行完，则执行完，则abp:=prev abp，，这样这样abp恢复到恢复到进入模块进入模块M1时情况，运行栈情况如（时情况，运行栈情况如（a）h）当）当最外层模块执行完，运行栈恢复到进入模块时最外层模块执行完，运行栈恢复到进入模块时的情况，运行栈空的情况，运行栈空218/3/2024228/3/2024227.3.2 建造建造display区的规则区的规则从从i层层模块进入模块进入(调用调用) j 层模块：层模块：(1) 若若j＝＝i＋＋1ijcallorij内内模块模块复制复制 i 层的层的display，，然后增加一个指向然后增加一个指向 i 层模块记录基地址的指针层模块记录基地址的指针 ：：第第i－－1层层abp第第1层层abpi层模块的层模块的displayj 层模块的层模块的display第第i层层abp228/3/2024238/3/202423(2) 若若j≤i 即调用外层模块或同层模块即调用外层模块或同层模块jicallorjicall将将i层模块的层模块的display区中的前面区中的前面j－－1个复制到第个复制到第j层模块的层模块的display区区 第第i－－2层层abp第第i－－1层层abp第第i层的层的display第第1层层abp：： ：：第第j－－1层层abp第第1层层abp第第j层的层的display238/3/2024248/3/2024247.3.3 运行时的地址计算运行时的地址计算作业：作业：P166 第第2题题假设要访问的变量的二元地址为假设要访问的变量的二元地址为：（：（BL，，ON））Ø在在LEV层模块中引用层模块中引用BL层模块定义的变量层模块定义的变量地址计算公式：地址计算公式：if BL = LEV thenaddr := abp + (BL - 1) + nip + ONelse if BL < LEV thenaddr := display[BL] + (BL - 1) + nip + ONelsewrite(“地址错误，不合法的模块层次地址错误，不合法的模块层次”)display区大小区大小隐式参数区大小隐式参数区大小局部数据区局部数据区参数区参数区display区区24。