《编译原理与技术 运行环境.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术 运行环境.ppt（52页珍藏版）》请在三一办公上搜索。
1、2023/4/26,编译原理与技术运行环境,1,编译原理与技术,运行环境,2023/4/26,编译原理与技术运行环境,2,运行环境,存储组织与分配 程序单元、运行时内存划分与活动记录 静态/动态存储分配 动态栈式的过程调用/返回 非局部名字的访问参数传递 参数传递的方式及其实现,2023/4/26,编译原理与技术运行环境,3,存储组织与分配,程序单元FORTRAN的子例程(subroutine)PASCAL的过程/函数(procedure/function)C的函数程序单元的激活（调用）与终止（返回）程序单元的执行需要：代码段活动记录（程序单元运行所需的额外信息，如参数，局部数据，返回地址等）
2、,2023/4/26,编译原理与技术运行环境,4,运行时内存划分,代码段,静态数据区,栈（stack）,堆（heap）,大小可以静态确定,全局/局部静态变量,活动记录栈,动态分配的数据,2023/4/26,编译原理与技术运行环境,5,活动记录,活动记录AR（Activation Record）是一连续存储区域，用于管理与存放和程序单元执行相关的重要信息。AR中的内容 临时区域。用以保存临时计算结果 局部数据区。源程序中程序单元声明的局部变量对应在此区域。机器状态保存区。存有机器的寄存器，程序指令计数器 ip（返回地址）等。,2023/4/26,编译原理与技术运行环境,6,活动记录,AR中的内容
3、 访问链（静态链）。当前程序单元可以访问的（静态程序中）外围程序单元的活动记录链。控制链（动态链）。程序单元的活动记录按它们的生成（或调用）次序串成链。实在参数 返回值,2023/4/26,编译原理与技术运行环境,7,活动记录的内容,返回值（return value）实在参数（actual parameter）控制链（control link）可选的访问链（optional access/static link）机器状态（saved machine status）局部数据（local data）临时区（temporaries）,2023/4/26,编译原理与技术运行环境,8,活动记录内容的存取
4、,返回值 实在参数 控制链（old bp）可选的访问链 机器状态 局部数据 临时区,AR的基地址bp,2023/4/26,编译原理与技术运行环境,9,活动记录内容的存取,返回值 实在参数 控制链（old bp）可选的访问链 机器状态 局部数据 临时区,bp,偏移,d1,偏移d2,地址：bp+d1,地址：bp+d2,d1、d2谁正谁负？,2023/4/26,编译原理与技术运行环境,10,静态存储分配,全局变量的存储绑定、AR均在编译时确定且在整个程序执行中保持。不支持：1）动态数据结构2）过程递归调用 实现静态分配的语言：（早期）FORTRAN,2023/4/26,编译原理与技术运行环境,11,
5、CALL sub SUBROUTINE subCALL sub DATA I/10END WRITE(*.*)I I=100 END第一次调用sub，输出10第二次调用sub，输出100,e.g.1 FORTRAN静态存储分配,第一次调用前,第一次调用后,第二次调用后,2023/4/26,编译原理与技术运行环境,12,动态存储分配,栈式分配 AR在过程被调用（激活）时才在栈（stack）上分配；而在被调用过程（返回）终止时从栈上撤销。过程中（非静态）局部变量的存储绑定在过程执行时有效；过程终止时失效。支持过程递归调用。每次递归调用时，局部变量绑定到不同的存储。,2023/4/26,编译原理与技
6、术运行环境,13,动态存储分配,栈式分配下的AR内容布局,返回值 实在参数 可选的访问链 返回地址调用者 bp可选机器状态局部数据 临时区,bp,高地址,低地址,长度固定的区域放在AR中间,长度可变的区域放在AR低端,参数/返回值区域放在AR高端靠近调用者过程的活动记录，既便于双方存取，又适应参数可变情况,栈顶sp,2023/4/26,编译原理与技术运行环境,14,栈式分配下的过程调用与返回 过程调用：分配被调过程的AR并填入相关信息，然后程序控制转移到被调过程入口；过程A 调用 过程B 的过程调用序列：A的“调用”准备操作：1）3）1）A 计算实在参数并放入（对应栈操作push）B的活动记录
7、中；（亦可考虑返回值存放空间）2）A将可选的访问链放入（push）B的活动记录；3）A将返回地址放入B的活动记录并跳转到过程B的代码入口，开始B的执行；（一般通过A中的代码指令“call B”来完成这一步）4）,2023/4/26,编译原理与技术运行环境,15,栈式分配下的过程调用与返回 过程A 调用 过程B 的过程调用序列：B的入口代码：4）6）4）在B自己的AR中保存A的活动记录的基址（即当前bp，对应操作 push bp）并且将这个位置作为B自己AR的基址（对应操作）mov sp,bp 即 bpsp）5）保存可选的机器状态（寄存器）6）为局部数据分配空间，（对应操作）sub local_
8、size，sp，即sp sp local_size7）“开始”B的执行。（至此，B的AR建好）,2023/4/26,编译原理与技术运行环境,16,栈式分配下的过程调用与返回 过程返回：回收分配的被调过程的AR，并将程序控制转移回调用过程继续执行；过程A 调用 过程B 的过程返回序列：B的出口代码：1）2）1）B回收局部数据空间；恢复原先保存的机器状态2）B恢复A的AR基址；取出返回地址将程序控制交回到A。对应操作：mov bp,sp spbppop bp/恢复调用者A的bpret/B执行结束并返回注：X86-Linux中的leave 和ret组合亦能达到目的。至此，B的AR中除了参数/返回值区
9、域，其余区域全部回收（撤销）了。,2023/4/26,编译原理与技术运行环境,17,栈式分配下的过程调用与返回 过程A 调用 过程B 的过程返回序列：A的“调用”善后代码：3）4）3）A取回返回值以及引用型参数（有的话）4）A调整栈顶sp（主要根据参数个数以及可能有的访问链和可能有的返回值）。对应操作：add para_size,sp 即spsp+para_size至此，B的AR区域全部回收（撤销）了。,2023/4/26,编译原理与技术运行环境,18,e.g.2 栈式存储分配,有C程序如下：void g()int a;a=10;void h()int a;a=100;g();main()in
10、t a=1000;h();,2023/4/26,编译原理与技术运行环境,19,过程g被调用时，活动记录栈的（大致）内容,e.g.2 栈式存储分配,返回地址,old bp,a:1000,main程序的AR,返回地址,old bp,a:100,函数h的AR,返回地址,old bp,a:10,函数g的AR,bp,sp,2023/4/26,编译原理与技术运行环境,20,e.g.3 有参函数的活动记录,void func(int a,int b)int c,d;c=a;d=b;,bp,bp+8,bp+12,bp4,bp8,.file ar.c.text.globl func.type func,func
11、tionfunc:pushl%ebp movl%esp,%ebp subl$8,%esp movl 8(%ebp),%eax movl%eax,-4(%ebp)movl 12(%ebp),%eax movl%eax,-8(%ebp)leave ret,2023/4/26,编译原理与技术运行环境,21,有如下C程序：main()int i;float f;int j;scanf(“%d%f”,e.g.4.scanf的可变参数,2023/4/26,编译原理与技术运行环境,22,e.g.4.scanf的可变参数,&f,&i,格式串1指针,返回地址,老bp,&j,格式串2指针,返回地址,老bp,sca
12、nf的第一次调用时AR,scanf的第二次调用时AR,由于C语言采用逆序传递参数，格式串参数将被放在AR中的“固定”位置，即bp+8。而由此参数即可确定待输入值的参数（变量）的个数。从而适应参数个数变化的情况。,bp,bp+8,2023/4/26,编译原理与技术运行环境,23,e.g.5 悬空引用,有C程序如下：main()int*dangle()int*p=dangle();int i;return,2023/4/26,编译原理与技术运行环境,24,非局部变量访问,静态作用域规则 vs.动态作用域规则“最接近嵌套”vs.现行单元活动（调用次序）分程序 含有声明和语句；如C的 分程序具有以下特
13、征：-可以嵌套；-没有参数；-控制流沿静态文本进入、流出-采用“最接近嵌套”的规则,2023/4/26,编译原理与技术运行环境,25,非局部变量访问,e.g.6 分程序main()int a=0;int b=0;/local VAR of main int b=1;/block 1 int a=2;printf(“%d%dn”,a,b);/block 2 int b=3;printf(“%d%dn”,a,b);/block 3 printf(“%d%dn”,a,b);printf(“%d%dn”,a,b);,2023/4/26,编译原理与技术运行环境,26,分程序的实现,1）按无参过程方式来实
14、现控制流进入分程序时，在栈上分配局部变量空间，退出时撤销上述空间。e.g.6中各变量存储如下：,a0=0,b0=0,b1=1,a）进入block 1,未进入block 2,b）进入block 2,未进入block 3,a1=2,a0=0,b0=0,b1=1,c）退出block 2,进入block 3,b2=3,a0=0,b0=0,b1=1,d）退出block 3,进入block 1,a0=0,b0=0,b1=1,e）退出block 1,进入main,a0=0,b0=0,2023/4/26,编译原理与技术运行环境,27,分程序的实现,2）按过程为单位统一分配将分程序中的局部变量独立地看成过程的局
15、部变量。e.g.6中各变量存储如下：（两种方案）,a0=0,b0=0,b1=1,a）a1和b2将先后被分配在同一空间，因为它们的生存期（作用域）不重叠、不嵌套。,a1=2,b2=3,a0=0,b0=0,b1=1,b）a1和b2将被分配在不同的空间。,a1=2,b2=3,2023/4/26,编译原理与技术运行环境,28,program dynamic_static_link;procedure A;var i:integer;procedure B;var j:integer;procedure C;begin B;end;begin j:=i;C;end;begin B;end;begin A
16、;end.,过程嵌套定义语言中非局部名字访问,C,B,A,主程序,主程序:0,A：1,B：2,C：3,i：2,j：3,嵌套深度：1,嵌套深度：2,嵌套深度：3,嵌套深度：4,e.g.7 嵌套的过程定义,2023/4/26,编译原理与技术运行环境,29,过程嵌套定义语言中非局部名字访问,设嵌套深度的初值为0。在“读过”程序单元的名字后，进入程序单元过程或函数时嵌套深度加1。任何名字（包括变量名和程序单元过程或函数的名字）的嵌套深度是包围该名字声明或定义的最内层的程序单元体（body）所在的嵌套深度。过程或函数的参数与其局部声明的嵌套深度相同。,2023/4/26,编译原理与技术运行环境,30,使
17、用静态访问链来存取非局部名字非局部变量a的嵌套深度为na，而该变量的使用或引用点的嵌套深度为np：沿当前过程或函数的访问链追踪|np-na|次，即可到达包含变量a的过程或函数的活动记录；进一步可存取变量a。运行时栈上操作如下：1）（bp+访问链单元的偏移）Reg/追踪1次2）（Reg+访问链单元的偏移）Reg/追踪2次/追踪（np na）次最后，通过（Reg+变量a的偏移）来存取变量a（局部变量访问无需追踪访问链！）e.g.7中下划线部分：j:=i 为非局部名字i的一个引用（j为局部变量）。为此，需要追踪过程B的访问链1次即可到达过程A的AR从而获取i的值。由定义非局部变量a的过程或函数（名）
18、的嵌套深度，以及由使用该变量的过程或函数（名）的嵌套深度，也能计算出追踪访问链的次数（why？）,2023/4/26,编译原理与技术运行环境,31,过程嵌套定义语言中非局部名字访问,访问链的建立在嵌套深度为np的过程X调用嵌套深度为na的过程Y：1）npna 此时 np na 1;即调用者X是父（即最接近的外围）过程，而被调者Y为其子过程，这时将过程Y的AR中的访问链置为X的AR的基址对应的运行时栈的操作：push bp/调用者（父过程）将自己的bp压入栈,2023/4/26,编译原理与技术运行环境,32,过程嵌套定义语言中非局部名字访问,访问链的建立2）npna 这属于内层过程X调用外围过程
19、Y；或者两个兄弟过程X、Y之间的调用（也可能是相同过程，即递归的情况）。这时由X的AR追踪访问链（np na+1）次，即可到达嵌套深度为（na 1）的过程Z的AR；显然，过程Z是过程Y的父过程，将这个Z的AR的基址填入Y的访问链域。对应运行时栈上的操作：1）（bp+访问链单元的偏移）Reg/追踪1次2）（Reg+访问链单元的偏移）Reg/追踪2次/追踪（np na+1）次最后，push Reg/过程Z的活动记录基址入栈,2023/4/26,编译原理与技术运行环境,33,e.g.7 嵌套的过程定义,过程的调用次序主程序 A B C B1 过程B第一次被过程C调用时，C需追踪2次访问链才能为找到过
20、程B1的父过程A的AR。具体如下：,2023/4/26,编译原理与技术运行环境,34,控制链：bp(系统),主程序AR,e.g.7 嵌套的过程定义,运行时栈：主程序,2023/4/26,编译原理与技术运行环境,35,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),局部名字：i,主程序AR,过程A的AR,e.g.7 嵌套的过程定义,运行时栈：主程序 A 主程序负责建立A（活动记录中）的访问链。此时该链指向主程序运行时的活动记录（why？）。此访问链的位置（或偏移）是多少？,访问链的地址表示：bp+8在此活动记录中的偏移为8,2023/4/26,编译原理与技术
21、运行环境,36,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,主程序AR,过程A的AR,过程B的AR,e.g.7 嵌套的过程定义,运行时栈：主程序 A BB中语句j:=i如何执行的？,j:=i执行如下：取过程A的活动记录地址：(bp+8)-R取A中局部变量i的值：(R 4)-R将该值赋给B的局部变量j：R-(bp 4),2023/4/26,编译原理与技术运行环境,37,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),
22、返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,访问链：bp(B),返回地址3,控制链：bp(B),主程序AR,过程A的AR,过程B的AR,过程C的AR,运行时栈：主程序 A B C,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,访问链：bp(B),返回地址3,控制链：bp(B),访问链：bp(A),返回地址4,控制链：bp(C),局部名字：j1,主程序AR,过程A的AR,过程B的AR,过程C的AR,过程B的AR,1,2,运行时栈：主程序 A B C B1,过
23、程C为过程B1建立访问链：1：(bp+8)R 2：(R+8)R3：push R,2023/4/26,编译原理与技术运行环境,39,参数传递,实参与形参 存储单元（左值）存储内容（右值）根据所传递的实参的“内容”，参数传递可分为：传值调用：传递实参的右值到形参单元；引用调用：传递实参的左值到形参单元；值-结果调用：传递实参的右值；在控制返回时将右值写回到实参相应左值单元（如果有的话）；换名调用：传递实参的“正文”。,2023/4/26,编译原理与技术运行环境,40,e.g.8 参数传递,procedure swap(a,b)a,b:int;temp:int;begintemp:=a;a:=b;b
24、:=temp;end.,讨论下面程序在不同参数传递方式下输出：1)x:=10;y:=20;swap(x,y);print(x,y);2)i:=10;a i:=20;swap(i,a i);print(i,a i);,2023/4/26,编译原理与技术运行环境,41,e.g.8 参数传递,讨论下面程序在不同参数传递方式下输出：1)x:=10;y:=20;swap(x,y);print(x,y);,10,5000:x,20,4000:y,2004:a,2000:b,1990:temp,实参x,y和过程swap中形参a,b,和局部数据temp的存储分布示意,2023/4/26,编译原理与技术运行环境
25、,42,e.g.8 参数传递传值调用,过程调用swap(x,y)传参形、实结合,10,5000:x,20,4000:y,2004:a,2000:b,1990:temp,10,20,2023/4/26,编译原理与技术运行环境,43,e.g.8 参数传递传值调用,过程调用swap(x,y)过程执行temp:=a,10,5000:x,20,4000:y,10,2004:a,20,2000:b,10,1990:temp,2023/4/26,编译原理与技术运行环境,44,e.g.8 参数传递传值调用,过程调用swap(x,y)过程执行a:=b,10,5000:x,20,4000:y,20,2004:a,
26、20,2000:b,10,1990:temp,2023/4/26,编译原理与技术运行环境,45,e.g.8 参数传递传值调用,过程调用swap(x,y)过程执行b:=temp,10,5000:x,20,4000:y,20,2004:a,10,2000:b,10,1990:temp,2023/4/26,编译原理与技术运行环境,46,e.g.8 参数传递传值调用,过程swap(x,y)执行后print(x,y)10,20,10,5000:x,20,4000:y,20,2004:,10,2000:,10,1990:,2023/4/26,编译原理与技术运行环境,47,e.g.8 参数传递引用调用,过程
27、调用swap(x,y)传参形、实结合,10,5000:x,20,4000:y,2004:a,2000:b,1990:temp,5000,4000,2023/4/26,编译原理与技术运行环境,48,e.g.8 参数传递引用调用,过程调用swap(x,y)过程执行temp:=a,10,5000:x,20,4000:y,2004:a,2000:b,1990:temp,5000,4000,10,2023/4/26,编译原理与技术运行环境,49,e.g.8 参数传递引用调用,过程调用swap(x,y)过程执行a:=b,10,5000:x,20,4000:y,2004:a,2000:b,10,1990:t
28、emp,5000,4000,2023/4/26,编译原理与技术运行环境,50,e.g.8 参数传递引用调用,过程调用swap(x,y)过程执行a:=b,20,5000:x,20,4000:y,2004:a,2000:b,10,1990:temp,5000,4000,2023/4/26,编译原理与技术运行环境,51,e.g.8 参数传递引用调用,过程调用swap(x,y)过程执行b:=temp,20,5000:x,10,4000:y,2004:a,2000:b,10,1990:temp,5000,4000,2023/4/26,编译原理与技术运行环境,52,e.g.8 参数传递引用调用,过程swap(x,y)执行后print(x,y)20,10,20,5000:x,10,4000:y,2004:,2000:,1990:,
