编译原理课件Chapter10

1第十章目标程序运行时的存储组织10.1概述10.2数据表示（略）10.3目标程序运行时的栈式存储组织10.4参数传递10.5堆式存储组织的讨论（略）210.1概述任务：在目标代码生成之前，编译程序对目标程序的运行环境进行设计和数据空间进行分配，如通常存储空间的典型划分：目标代码区静态数据区StackHeap3数据空间的使用方法存储分配策略：静态存储分配栈式动态存储分配堆式动态存储分配栈式存储分配方案基本思想：运行时每当进入一个过程，就在栈顶为该过程分配所需的数据空间，当一个过程工作完毕之后，它在栈顶的数据空间也将被释放。活动记录活动记录活动记录运行栈4例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区嵌套调用次序后进先出生存期限于本次调用自动释放5活动记录：是一个连续的存储区，用以存放一个过程的一次执行所需要的信息。•表达式计算所需的临时变量•局部数据•寄存器、程序计数器（返回地址）•保存实在参数的值或地址•存放返回值•保存调用者活动记录地址•用于存取非局部名访问链控制链返回值实在参数机器状态局部变量临时变量610.3.1简单的栈式分配方案•程序结构特点：过程可递归调用，可含可变数据结构，但不允许嵌套定义，没有分程序结构。•例:main(){……}(main)voidR(){……}(R)voidQ(){……}(Q)7Main----Q----RMain---Q----QTOP-----R的活动记录Q的活动记录SP------Q的活动记录Q的活动记录主程序全局主程序全局数据区数据区TOP----临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（计数器，寄存器值)返回地址实参（形式单元）和参数个数SP-----控制链（老SP）TOP：始终指向已占用的栈顶单元;SP：总是指向当前执行过程活动记录的起点。8TOPR的数组区SPR的活动记录Q的活动记录主程序全局数据区910.3.2嵌套过程语言的栈式存储分配方案1、主要特点：•（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。•（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。102、关键技术：解决对非局部变量的引用(存取)也就是说，设法跟踪每个外层过程的最新活动记录AR的位置。3、跟踪办法：1.用静态链/存取链（如PL/0的SL）。2.用DISPLAY表。11目标代码解释执行时数据栈的布局（运行栈的存储分配）每个过程的AR有3个联系单元：–SL：静态链(存取链)，指向定义该过程的直接外过程（或主程序）运行时最新活动记录的基地址。–DL：动态链(控制链)，指向调用该过程前正在运行过程的数据段基地址。–RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。局部变量中间结果12consta=10;varb,c;procedurep;beginc:=b+a;end;begin/*main*/read(b);whileb#0dobegincallp;write(2*c);read(b);endend./*main*/(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03过程p入口,为过程p开辟空间(3)lod13取变量b的值到栈顶(4)lit010取常数10到栈顶(5)opr02次栈顶与栈顶相加(6)sto14栈顶值送变量c中(7)opr00退栈并返回调用点(16)(8)int05主程序入口开辟5个栈空间(9)opr016从命令行读入值置于栈顶(10)sto03将栈顶值存入变量b中(11)lod03将变量b的值取至栈顶(12)lit00将常数值0进栈(13)opr09次栈顶与栈顶是否不等(14)jpc024等时转(24)（条件不满足转）(15)cal02调用过程p(16)lit02常数值2进栈(17)lod04将变量c的值取至栈顶(18)opr04次栈顶与栈顶相乘(2*c)(19)opr014栈顶值输出至屏幕(20)opr015换行(21)opr016从命令行读取值到栈顶(22)sto03栈顶值送变量b中(23)jmp011无条件转到循环入口(11)(24)opr00结束退栈13目标代码的解释执行运行栈•M调用过程PSRADLSLb..ttbPM14解决对非局部变量的引用（存取）用Display表Display表——嵌套层次显示表当前执行过程的层次为K（主程序层为0层），它的Display表含有K+1个单元，依次存放着现行层，直接外层（定义外层）…直至最外层的每一过程的最新活动记录的基地址。15例：programsort;……procreadarray;……end/*readarray*/procexchange;……end/*exchange*/procquicksort;……procpartition;……end/*partition*/……end/*quicksort*/……end/*sort*/程序结构图Sortreadarrayexchangequicksortpartition16用Display表的方案(1)sort---(2)quicksort---(3)partition---(4)exchanged[1]（2）d[0]spdisplaytop（1）sort的活动记录spdisplaytopquicksort的活动记录sort的活动记录d[0]17用Display表的方案(1)sort---(2)quicksort---(3)partition---(4)exchange（3）d[2]spsort的活动记录quicksort的活动记录partition的活动记录topd[1]d[0]（4）sptopexchange的活动记录partition的活动记录quicksort的活动记录sort的活动记录d[0]d[1]18DISPLAY表的维护和建立当过程的层次为n，它的DISPLAY为n+1个值。一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。全局DISPLAY地址...简单变量数组内情向量临时变量dDISPLAY4形式单元...3参数个数2全局DISPLAY地址1返回地址0老SP1910.3.3分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成“无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。(1)每逢进入一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。(2)当从内层分程序向外层转移时，可能同时要结束若干个分程序。20按照过程处理办法，意味着必须一层一层地通过“返回”来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从DISPLAY中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层分程序进入时的TOP呢？唯一的办法是从5,4,3和2各层顺序退出。但这种办法是很浪费时间的。21为了解决上述问题，可采取两种措施：第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器,每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。22每个过程被当作是0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第1层分程序。这样，每个过程的活动记录所含的内容有：1、过程的TOP值，它指向过程活动记录的栈顶位置。2、连接数据，共四项：(1)老SP值；(2)返回地址；(3)全局DISPAY地址；(4)调用时的栈顶单元地址，老TOP。233、参数个数和形式单元4、DISPAY表。5、过程所辖的各分程序的局部数据单元。对于每个分程序来说，它们包括：(1)分程序的TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的TOP值）；(2)分程序的局部变量，数组内情向量和临时工作单元。24变量eB5的TOP数组C的内情向量变量e和dB4的TOPB2的TOP数组B的内情向量变量zKB1的TOPDDISPLAY6形式单元m,n5参数个数：24调用时的栈顶地址（老TOP）3全局DISPLAY地址2返回地址1老SP0过程的TOP，指向活动记录之顶25B的内情向量ZB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(a)(b)(a)到达标号B1处;(b)进入分程序B1;ZTO26数组B数组BedB22的TOPB的内情向量B的内情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(c)(d)(c)数组B分配之后；（d）进入分程序B22;27数组C数组C数组B数组BC的向量内情eB5的TOPC的内情向量B4的TOPB4的TOPB的内情向量B的内情向量zZB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(e)(f)(e)进入分程序B4分配数组C之后；(f)进入分程序B5。2810.4参数传递A)传值调用call-by-value–过程调用时计算实参，将值存到活动记录–形式参数绑定于活动记录的实在参数域•例：–C语言、Pascal语言的值参29传值的实现1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。30传值调用例题voidinc2(intx){++x;++x;}voidmain(){inta=1;inc2(a);}31B)传地址调用call-by-address实际上，形参是实参的别名（alias）–如果实在参数具有左值，则存放其左值到活动记录中；否则按传值处理–表达式的左值：处于赋值符左侧时表示的存储地址–表达式的右值：处于赋值符右侧时表示的值•例：–Pascal语言的变参、C/C++语言的引用类型32传地址的实现1实在参数是一个名字，或具有左值的表达式(a=b+c)--传递左值2实在参数是无左值的表达式--计算值，放入一存储单元，传此存储单元地址3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用33传地址调用例题voidinc2(int*x){++x;++x;}voidmain(){inta=1;inc2(&a);}34C)传值结果调用call-by-result实际上，不把形参作为实参的别名–在函数中复制和使用实参的值到形参；–返回时，将形参的终值复制回实参•例：–Ada的传入（in）和传出（out）的参数机制35传值结果调用例题voidp(intx，inty){++x;++y;}voidmain(){inta=1;p(a,a);}传地址：a为3；传值结果：a为2不确定性：参数传递次序！36d)传名字调用call-by-name•即换名，将形参名字换成实参名字–延迟赋值（delayedevaluation）–太复杂，已被传地址取代。–有些老师把“传地址”误以为“换名”！–采用的语言：ALGOL60•例：voidp(intx){++x;}若调用p(a[i])，结果是计算++(a[i])37又例：inti；inta[10]；voidp(intx){++i;//i=2++x;//a