编译原理课程设计之第七章 运行时环境

1、mcy1w课程内容课程内容第一章第一章 概论概论第二章第二章 词法分析词法分析第三章第三章上下文无关文法及分析上下文无关文法及分析第四章第四章自上而下的语法分析自上而下的语法分析第五章第五章自下而上的语法分析自下而上的语法分析第六章第六章语义分析语义分析第七章第七章运行时环境运行时环境第八章第八章代码生成代码生成mcy2第第7 7章章 运行时环境运行时环境( (存储空间存储空间) )l当源程序的目标代码被运行时，在内存中不当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息，如仅有目标代码，而且还要保存各种信息，如必须为源程序中所出现的一些量（常量、变必须为源程序中所出现的

2、一些量（常量、变量及某些数组等）分配运行时的存储空间。量及某些数组等）分配运行时的存储空间。即编译器要从操作系统得到一块存储区，用即编译器要从操作系统得到一块存储区，用于被编译过的目标程序的运行。于被编译过的目标程序的运行。mcy3w存储分配是在运行阶段进行的，但存储分配是在运行阶段进行的，但编译程序编译程序在编译阶段要为其设计好存储组织形式，并在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出将这种组织形式通过生成的目标代码体现出来。来。( (举例说明：举例说明：函数调用分析函数调用分析. .txttxt) )w目标代码运行时，目标代码运行时，存储空间的组织存储空间

3、的组织称为目标称为目标代码的代码的运行时环境运行时环境。mcy4w运行时环境有三个类型：完全静态环境运行时环境有三个类型：完全静态环境(fully static environment)、基于栈的环境、基于栈的环境(stack-based environment)，以及完全动态环境以及完全动态环境(fully dynamic environment)。这这3种类型种类型的混合形式也是可能的。的混合形式也是可能的。mcy57.1 7.1 程序执行时的存储器组织程序执行时的存储器组织7.2 7.2 完全静态的运行时环境完全静态的运行时环境7.3 7.3 基于栈的运行时环境基于栈的运行时环境7.4

4、7.4 动态存储器动态存储器7.5 7.5 参数存储机制参数存储机制mcy67.17.1程序执行时的存储器组织程序执行时的存储器组织目标代码运行时目标代码运行时, ,操作系统为目标代码的运行分配操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分的存储空间按用途可划分为下面几个部分: :mcy7 代码区域：目标代码的存储区域，由于代码区在执行之前是代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，所以在编译时所有目标代码的地址都是可计算的；固定的，所以在编译时所有目标代码的地址都是可计算的； 全程全程/ /静态区域：静态数据区用来存放那些具有绝对地址的静态区域：静态数据区

5、用来存放那些具有绝对地址的数据和变量数据和变量( (如静态变量和全程变量如静态变量和全程变量) )；编译器可以确定其所编译器可以确定其所占用存储空间的大小；占用存储空间的大小； 栈区：在运行时分配存储空间的数据就分配在栈区；编译器栈区：在运行时分配存储空间的数据就分配在栈区；编译器知道存在栈中的具体数据大小和存活时间；知道存在栈中的具体数据大小和存活时间； 堆区：供用户动态申请存储空间，编译器不需要知道究竟得堆区：供用户动态申请存储空间，编译器不需要知道究竟得从从heapheap中分配多少空间，也不需要知道从中分配多少空间，也不需要知道从heapheap上分配的空间上分配的空间究竟需要存在多久

6、。究竟需要存在多久。 由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。栈和堆共用一空白存储空间。mcy8 在在语言中语言中, ,通常采用以过程为单位的动态存通常采用以过程为单位的动态存储分配方案：储分配方案：当一过程当一过程( (函数函数) )被调用时，就在栈顶为该过程分配所需的被调用时，就在栈顶为该过程分配所需的数据空间数据空间( (过程活动记录过程活动记录) )，当一个过程工作完毕返

7、回时，当一个过程工作完毕返回时，它在栈顶的数据空间它在栈顶的数据空间( (过程活动记录过程活动记录)也即释放。也即释放。 过程的活动记录过程的活动记录( (activation record,AR) )是一段连续的存是一段连续的存储区，用于存放过程的一次执行所需要的信息，当调储区，用于存放过程的一次执行所需要的信息，当调用或激活过程或函数时，必须为被调用过程的活动记用或激活过程或函数时，必须为被调用过程的活动记录分配空间。录分配空间。 活动记录存放的信息至少应包括以下几个部分：活动记录存放的信息至少应包括以下几个部分：mcy9存放主调过程为被调过程存放主调过程为被调过程提供的实参信息提供的实参

8、信息;存放目标程序临时变存放目标程序临时变量的值量的值;存放本次执行中的局部数据存放本次执行中的局部数据用于指向主调过程的活动记用于指向主调过程的活动记录的控制链和返回地址录的控制链和返回地址;mcy10b:2a:1该函数调用结束该函数调用结束时的返回地址时的返回地址(00401353)主调函数的控主调函数的控制链制链语言所调用函语言所调用函数的活动记录数的活动记录示例示例( (函数调用函数调用分析中的举例分析中的举例) )c:3栈底栈底栈顶栈顶mcy11第第7 7章章 运行时环境运行时环境7.1 7.1 程序执行时的存储器组织程序执行时的存储器组织7.2 7.2 完全静态的运行时环境完全静态

9、的运行时环境7.3 7.3 基于栈的运行时环境基于栈的运行时环境7.4 7.4 动态存储器动态存储器7.5 7.5 参数存储机制参数存储机制mcy127.2 7.2 完全静态的运行时环境完全静态的运行时环境 在完全静态环境中，不仅全局变量，所有的变量都在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即是静态分配，即整个程序所需数据空间的总量在编整个程序所需数据空间的总量在编译时是完全确定的译时是完全确定的，从而每个数据名的地址就可静，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的态地进行分配，适于静态分配的语言，要求满足的条件是：条件是： 每个数据名所需的存储空

10、间的大小都是常量每个数据名所需的存储空间的大小都是常量 不允许采用动态的数据结构，即在程序运行过程不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构中申请或释放的数据结构 过程不可递归调用过程不可递归调用mcy13整个程序存储器如下所示：整个程序存储器如下所示：mcy14w程序所需的数据空间在程序运行前就可确定，称为_管理技术。a.静态存储b.动态存储c.栈式存储d.堆式存储mcy15u静态存储分配允许程序出现_。a.递归过程b.可变体积的数据项目c.静态变量d.待定性质的名字mcy16第第7 7章章 运行时环境运行时环境7.1 7.1 程序执行时的存储器组织程序执行时的存储器组

11、织7.2 7.2 完全静态的运行时环境完全静态的运行时环境7.3 7.3 基于栈的运行时环境基于栈的运行时环境7.4 7.4 动态存储器动态存储器7.5 7.5 参数存储机制参数存储机制mcy177.3 7.3 基于栈的运行时环境基于栈的运行时环境7.3.1没有局部过程的基于栈的环境没有局部过程的基于栈的环境 在一个在一个所有过程都是全局的所有过程都是全局的、过程定义不允许嵌套过程定义不允许嵌套，但允许过程的递归调用的程序设计语言但允许过程的递归调用的程序设计语言( (例如例如C C语言语言) )中，基于栈的动态运行时环境有两个指针中，基于栈的动态运行时环境有两个指针：sp:栈顶部栈顶部( (

12、top of stack) )指针；对于指针；对于x86x86系统来说，系统来说，它采用它采用spsp或或espesp寄存器存储栈顶部的地址；寄存器存储栈顶部的地址；mcy18fp(frame point)指向当前活动记录的控制链的指向当前活动记录的控制链的指针指针，对于对于x86系统，它采用系统，它采用bp或或ebp寄存器寄存器存存储储当前活动记录的控制链的地址，其作用如下：当前活动记录的控制链的地址，其作用如下：1.1.通过该指针可以访问当前执行函数的局部变量；通过该指针可以访问当前执行函数的局部变量；2.2.通过该指针可以访问主调程序的活动记录；通过该指针可以访问主调程序的活动记录；3.

13、3.允许在当前的被调函数执行完毕时，用它来恢复允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。主调函数的活动记录。mcy19b:2a:1该函数调用结束该函数调用结束时的返回地址时的返回地址(cs:eip) 00401353主调函数的控主调函数的控制链制链(main.fp)语言当前执行语言当前执行函数的活动记录函数的活动记录示例示例( (函数调用函数调用分析中的举例分析中的举例) )c:3spfp栈底栈底栈顶栈顶mcy20当一个过程被调用时，当一个过程被调用时，在栈顶为该过程分配所在栈顶为该过程分配所需的数据空间需的数据空间( (过程活动记录过程活动记录) )如下：如下：1)1)

14、将将实参实参的值压入在该函数对应的的值压入在该函数对应的新活动记录新活动记录中。中。2)2) 将被调函数执行完毕后的将被调函数执行完毕后的返回地址返回地址压入在压入在新的活动记录新的活动记录中。中。3)3) 完成到被调用的过程的代码一个转移。完成到被调用的过程的代码一个转移。4)4) 将主调函数的将主调函数的fpfp作为作为控制链压入到新的活动记录控制链压入到新的活动记录中。中。5)5) 改变改变fpfp以使其以使其指向新的活动记录指向新的活动记录( (将将spsp复制到该复制到该fpfp中中) )6)6) 将该函数的将该函数的局部变量局部变量和和局部临时变量局部临时变量压入到新的活动记录中。

15、压入到新的活动记录中。mcy21b:2a:1该函数调用结束该函数调用结束时的返回地址时的返回地址(cs:eip) 00401353主调函数的控主调函数的控制链制链(main.fp)语言当前执语言当前执行函数的活动行函数的活动记录示例：记录示例：c:3sp栈底栈底栈顶栈顶fpmcy22当被调函数执行完毕返回时，其对应当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：的活动记录从栈中弹出的过程： 将将fpfp复制到复制到spsp中。中。 将控制链装载到将控制链装载到fpfp中。中。 完成到返回地址主调函数的一个转移。完成到返回地址主调函数的一个转移。 改变改变spsp以弹出实参。以弹出实

16、参。mcy23例：计算两个非负整数的最大公约数的例：计算两个非负整数的最大公约数的c c代码如下：代码如下：#include int x,y;int gcd(int u,int v) if(v= =0) return u; else return gcd(v,u%v)main() scanf(“%d%d”,&x,&y); printf(“%dn”,gcd(x,y); return 0;mcy24x:15x:15y:10y:10全局全局/ /静态区域静态区域mainmain的活动记录的活动记录sp,fpsp,fpv:10v:10u:15u:15返回地址返回地址mainmain的的

17、fpfp第一次调用第一次调用gcdgcd时的活动记录时的活动记录sp,fpsp,fp第二次调用第二次调用gcdgcd时的活动记录时的活动记录v:5v:5u:10u:10返回地址返回地址第一次调用第一次调用gcdgcd时的时的fpfp第三次调用第三次调用gcdgcd时的活动记录时的活动记录v:0v:0u:5u:5返回地址返回地址第二次调用第二次调用gcdgcd时的时的fpfpsp,fpsp,fpsp,fpsp,fp栈生长方向栈生长方向自由空间自由空间mcy25例：考虑下列程序清单的例：考虑下列程序清单的c c代码。代码。int x=2;void g(int);void f(int n)stati

18、c int x=1; g(n); x- -;void g(int m)int y=m-1;if (y0) f(y); x- -; g(y); main()g(x); return 0;画出第二次对画出第二次对g调用时，程调用时，程序的运行时环境：序的运行时环境：mcy26x:2x:2x x（from ffrom f）:1:1全局全局/ /静态区域静态区域mainmain的活动记录的活动记录sp,fpsp,fpm:2m:2返回地址返回地址mainmain的的fpfp y:1y:1第一次调用第一次调用g g时时的活动记录的活动记录fpfpspsp第一次调用第一次调用f f时时的活动记录的活动记录n

19、:1n:1 返回地址返回地址第一次调用第一次调用g g时的时的fpfpsp,fpsp,fp第二次调用第二次调用g g时的时的活动记录活动记录m:1m:1 返回地址返回地址第一次调用第一次调用f f时的时的fpfp y:0y:0fpfpspsp栈生长方向栈生长方向自由空间自由空间mcy27w目标代码的生成必须支持变量和临时变量的目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的实际定位，并增加支持运行时环境所必需的代码代码。对名字的访问对名字的访问如何处理可变长度的问题如何处理可变长度的问题局部临时变量局部临时变量嵌套声明嵌套声明mcy28对名字的访问：对名字的访问：w

20、在没有局部过程的基于栈的运行时环境中，所有的在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的非局部的名字都是全局的，因此也就是静态的，都，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。具有一个固定的静态地址，可以被直接访问。w对函数参数和局部变量而言，在大多数的语言中，对函数参数和局部变量而言，在大多数的语言中，每个局部声明的偏移量仍是可有编译程序静态地计每个局部声明的偏移量仍是可有编译程序静态地计算出来算出来，因为过程的声明在编译时是固定的，而且，因为过程的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而为每个声明分配的存储器大小也根据其

21、数据类型而固定。固定。mcy29m:2 m:2 返回地址返回地址控制链控制链 y:1y:1fpfpmOffsetmOffsetyOffsetyOffsetmOffsetmOffset=+8=+8yOffsetyOffset=-4=-4高端地址高端地址低端地址低端地址mcy30例：考虑下面的例：考虑下面的C C过程过程ViodViod f(intf(int x,char c) x,char c) intint a10; a10; double y; double y; 对对f f调用的活动记录为：调用的活动记录为：c cx x 返回地址返回地址控制链控制链a9a9a1a1a0a0y yfpfpx

22、OffsetxOffsetaOffsetaOffsetcOffsetcOffsetyOffsetyOffsetxOffsetxOffset=+8=+8cOffsetcOffset=+12=+12aOffsetaOffset=-40=-40yOffsetyOffset=-48=-48现在对现在对aiai访问，要求计算地址：访问，要求计算地址：(-40+4(-40+4* *i)(fpi)(fp) )mcy31w目标代码的生成必须支持变量和临时变量的目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的实际定位，并增加支持运行时环境所必需的代码代码。对名字的访问对名字的访问如何

23、处理可变长度的问题如何处理可变长度的问题局部临时变量局部临时变量嵌套声明嵌套声明mcy32处理可变长度的数据处理可变长度的数据有时编译程序必须处理数据变化的可能性，表现在数据有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的两种情况如下：环境的语言中的两种情况如下： 调用中的自变量的数量可根据调用的不同而不同。调用中的自变量的数量可根据调用的不同而不同。 数组参数或局部数组变量的大小可根据调用的不同数组参数或局部数组变量的大小可根据调用的不同而不同。而不同。printf(%d%s%cpr

24、intf(%d%s%c, n, prompt, , n, prompt, chch););printf(Helloprintf(Hello, worldn);, worldn);通常，通常，C C编译程序一般通过把调用的自变量按相反顺序编译程序一般通过把调用的自变量按相反顺序( (in reverse order)in reverse order)压入到运行时栈来处理这一点。压入到运行时栈来处理这一点。mcy33w目标代码的生成必须支持变量和临时变量的目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的实际定位，并增加支持运行时环境所必需的代码代码。对名字的访问对名字的

25、访问如何处理可变长度的问题如何处理可变长度的问题局部临时变量局部临时变量嵌套声明嵌套声明mcy34局部临时变量：局部临时变量： 考虑考虑C C表达式：表达式： xi=(i+j) xi=(i+j)* *(i/k+f(j)(i/k+f(j) 在这个表达式从左到右的求值计算中，在对在这个表达式从左到右的求值计算中，在对f f的调的调用过程中需要保存中间结果：用过程中需要保存中间结果： xixi的地址、的地址、i+ji+j的的和、和、i/ki/k的商。的商。 这些中间值可计算到寄存器中，根据寄存器进行保这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者存和恢复；或者可将它们作为临时变量存储在对

26、可将它们作为临时变量存储在对f f调用之前的运行时栈中调用之前的运行时栈中。如下所示：。如下所示：mcy35 返回地址返回地址控制链控制链xixi的地址的地址i+ji+j的结果的结果i/ji/j的结果的结果fpfp( (栈的其余部分栈的其余部分) )spsp临时栈临时栈调用调用f f（将要创建的）时的将要创建的）时的新活动记录新活动记录包含表达式过程的活动记录包含表达式过程的活动记录自由空间自由空间mcy36w目标代码的生成必须支持变量和临时变量的目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的实际定位，并增加支持运行时环境所必需的代码代码。对名字的访问对名字的访问

27、如何处理可变长度的问题如何处理可变长度的问题局部临时变量局部临时变量嵌套声明嵌套声明mcy37嵌套声明：嵌套声明：嵌套声明也出现了与局部临时变量同样的问题。考虑以下的嵌套声明也出现了与局部临时变量同样的问题。考虑以下的C C代码：代码：Void Void p(intp(int x,double y) x,double y) char a; char a; intint i; i; A:double x; A:double x; intint j; j; B:char B:char * *a;a; intint k; k; mcy38一个简单的处理办法是按照与临时表达式相类似的办法一个简单的处理

28、办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。在嵌套的块中处理声明，并在进入块时在栈中分配它们。x:x:y:y: 返回地址返回地址 控制链控制链a:a:i:i:x x: :j j: :fpfp( (栈的其余部分栈的其余部分) )spsp块块A A的分配区的分配区调用调用p p时的活动记录时的活动记录自由空间自由空间当进入块当进入块A A后，运行时栈如下所示：后，运行时栈如下所示：mcy39x:x:y:y: 返回地址返回地址控制链控制链a:a:i:i:a a: :k k: :fpfp( (栈的其余部分栈的其余部分) )spsp块块B B的分配区的分配区调用调

29、用p p时的活动记录时的活动记录自由空间自由空间当进入块当进入块B B后，运行时栈如下所示：后，运行时栈如下所示：mcy40第第7 7章章 运行时环境运行时环境7.1 7.1 程序执行时的存储器组织程序执行时的存储器组织7.2 7.2 完全静态的运行时环境完全静态的运行时环境7.3 7.3 基于栈的运行时环境基于栈的运行时环境7.4 7.4 动态存储器动态存储器7.5 7.5 参数存储机制参数存储机制mcy417.4.1对象类型对象类型在大多数面向对象的语言中，对象都有构造函数和在大多数面向对象的语言中，对象都有构造函数和析构函数，它们分别在创建对象和释放对象时被调析构函数，它们分别在创建对象

30、和释放对象时被调用。如果这就是全部内容的话，那么对象的实现将用。如果这就是全部内容的话，那么对象的实现将非常简单。假定我们有一对象类非常简单。假定我们有一对象类A A，它有方法它有方法m1,m2m1,m2以及字段以及字段a1a1和和a2a2。那么类那么类A A对象的运行时表示有包含对象的运行时表示有包含字段字段a1a1和和a2a2记录组成：记录组成：a1a1a2a2m1_Am1_Am2_Am2_A另外，编译程序维护着一张类另外，编译程序维护着一张类A A的编译时方法表：的编译时方法表：7.4 7.4 动态存储器动态存储器mcy42在上述简单的模块中，字段选择可以像记录字段选择一样在上述简单的模

31、块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方一个指向对象的指针，方法可以像函数一样实现。因此方法法m2_Am2_A可以翻译为可以翻译为c c语言中的函数。语言中的函数。 void m2_A(class_A void m2_A(class_A * *this,intthis,int i) i) 方法方法m2_Am2_A的程序体，通过的程序体，通过this-xthis-x访问任一对象字段访问任一对象字段x x 方法的调用方法的调用a .m2(3)a .m2(

32、3)可以翻译成可以翻译成m2_A(&a,3)m2_A(&a,3)mcy43继承特性继承特性现在假定类现在假定类B B通过增添方法通过增添方法m3m3和字段和字段b1b1来扩展类来扩展类A,A,那么类那么类B B的运行时表示如下：的运行时表示如下：a1a1a2a2m1_Am1_Am2_Am2_Ab1b1另外类另外类B B的方法编译时表如下：的方法编译时表如下：m3_Bm3_Bmcy44方法重载方法重载假定上例中类假定上例中类B B重新定义了方法重新定义了方法m2m2，那么那么A A中方法中方法m2m2的定义既是它唯一的声明也是它的第一次定义，而的定义既是它唯一的声明也是它的第一次

33、定义，而它在类它在类B B中的定义为重定义。为使名字既可以反映声中的定义为重定义。为使名字既可以反映声明它的类，也可以反映定义它的类。方法的名字可明它的类，也可以反映定义它的类。方法的名字可有三部分组成：方法名、声明方法的类名、定义方有三部分组成：方法名、声明方法的类名、定义方法类名。各部分之间用下划线（法类名。各部分之间用下划线（）分开。因此在）分开。因此在类类A A中声明在类中声明在类B B中定义的方法中定义的方法m2m2其名字记为其名字记为m2_A_Bm2_A_B。方法重载影响方法的编译时表，现在类方法重载影响方法的编译时表，现在类A A的方法的编的方法的编译时表如下：译时表如下：m1_

34、A_Am1_A_Am2_A_Am2_A_Am1_A_Am1_A_Am2_A_Bm2_A_Bm3_B_Bm3_B_B类类B B的方法的的方法的编译时表如右：编译时表如右：mcy45现在假定现在假定a a是类是类A A的一个对象，而的一个对象，而b b是类是类B B的一个对的一个对象。方法调用象。方法调用a.m2(a.m2() )将翻译成对将翻译成对m2_A_Am2_A_A的调用，的调用，而方法调用而方法调用b.m2(b.m2() )将翻译成对将翻译成对m2_A_Bm2_A_B的调用。的调用。m2_A_Am2_A_A在类在类A A中声明和定义。中声明和定义。m2_A_Bm2_A_B在类在类A A中

35、生明，中生明，在类在类B B中定义。如果继承是语言中唯一的面向对象中定义。如果继承是语言中唯一的面向对象的特征，那么的特征，那么m2_A_Am2_A_A翻译形式为：翻译形式为：void m2_A_A(Class_A void m2_A_A(Class_A * *this,intthis,int i); i);而而m2_A_Bm2_A_B的翻译形式为：的翻译形式为：void m2_A_B(Class_B void m2_A_B(Class_B * *this,intthis,int i); i);mcy46多态性多态性当类当类B B继承类继承类A A并且该语言允许并且该语言允许“类类B B的指针

36、的指针”类型的指针类型的指针能够赋给一个能够赋给一个“类类A A的指针的指针”类型的变量时，那么该语言类型的变量时，那么该语言支持多态型。例如：支持多态型。例如：Class B Class B * *b=b=; ;Class A Class A * *a=b;a=b;则第二行被翻译成：则第二行被翻译成：class A class A * *a=a=convert_ptr_to_B_to_ptr_to_A(bconvert_ptr_to_B_to_ptr_to_A(b););现在，过程现在，过程convert_ptr_to_B_to_ptr_to_Aconvert_ptr_to_B_to_ptr

37、_to_A()()为一编译为一编译时类型的操作时类型的操作, ,它将指向子类它将指向子类B B的一个对象指针转换为指的一个对象指针转换为指向其父类向其父类A A对象的指针。因为类对象的指针。因为类B B的对象也是从类的对象也是从类A A的字的字段开始，因而指针的值并不需要改变，唯一影响的是改段开始，因而指针的值并不需要改变，唯一影响的是改变了指针的类型：变了指针的类型：mcy47a1a1a2a2b1b1指向指向B B的指针的指针指向指向B B中中A A的指针的指针但要注意，现在同一指针指向了不同类的对象但要注意，现在同一指针指向了不同类的对象mcy48动态绑定：动态绑定：因为类型因为类型cla

38、ss Aclass A* *的指针的指针p p可能实际上引用了类可能实际上引用了类B B的一的一个对象，动态绑定认为如果实际上为类个对象，动态绑定认为如果实际上为类B B的对象，那就的对象，那就应该调用应该调用m2_A_B,m2_A_B,如果实际为如果实际为A A的对象，那么就应该调的对象，那么就应该调用用m2_A_A.m2_A_A.对于方法调用对于方法调用P-m2(3),pP-m2(3),p是一指向类是一指向类A A对象对象指针，可以被翻译成如下形式：指针，可以被翻译成如下形式：switch(dynamic_type_of(p)switch(dynamic_type_of(p) case D

39、ynamic_class_A:m2_A_A(p,3);break; case Dynamic_class_A:m2_A_A(p,3);break; case Dynamic_class_B: case Dynamic_class_B: m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break; m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break; 当当p p为一指向类为一指向类B B对象指针时，可以立即将对象指针时，可以立即将p-m2(3)p-m2(3)调用翻调用翻译为：译为：m2_A_B(p,3);m2_A_B

40、(p,3);mcy49动态绑定对于方法动态绑定对于方法P-m2(3)P-m2(3)的更好翻译方法为：的更好翻译方法为：如果如果p p是一指向类是一指向类A A对象指针，则进行如下处理有：对象指针，则进行如下处理有：1.1. ( (dynamic_type_of(p)= =Dynamic_Class_A ? m2_A_A:m2_A_B)(p,3);dynamic_type_of(p)= =Dynamic_Class_A ? m2_A_A:m2_A_B)(p,3);如果指针如果指针p p实际上引用了类实际上引用了类B B的一个对象，则执行步骤的一个对象，则执行步骤2 2中的方法。中的方法。2.2.

41、 void m2_A_B(Class_A void m2_A_B(Class_A * *this_A,intthis_A,int i) i)Class_B Class_B * *this=this=convert_ptr_to_A_to_ptr_to_B(this_Aconvert_ptr_to_A_to_ptr_to_B(this_A););方法方法m2_A_Bm2_A_B的程序体，通过的程序体，通过this-xthis-x访问任一对象字段访问任一对象字段x x 如果如果p p是一指向类是一指向类B B对象指针，则进行如下处理有：对象指针，则进行如下处理有：1.1. m2_A_B(conve

42、rt_ptr_to_B_to_ptr_to_A(p),3);m2_A_B(convert_ptr_to_B_to_ptr_to_A(p),3);2.2. 执行的方法同上述的步骤执行的方法同上述的步骤2 2；mcy50对于上述的翻译方法，每一个对象的类型信息实现为一个对于上述的翻译方法，每一个对象的类型信息实现为一个指向分派表的指针，如下图所示指向分派表的指针，如下图所示( (分派表是存储方法地址分派表是存储方法地址的记录，下图分派表存储的是方法的记录，下图分派表存储的是方法m1_A_Am1_A_A， m2_A_B m2_A_B和和 m1_B_Bm1_B_B的地址的地址) )a1a1a2a2b1

43、b1指向指向B B的指针的指针指向指向B B中中A A的指针的指针m1_A_Am1_A_Am2_A_Bm2_A_Bm3_B_Bm3_B_B类类B B对象的表示对象的表示分派表分派表B-objectB-objectB-classB-classmcy517.4.2 堆管理堆管理对于允许程序为变量在运行时动态申请和释对于允许程序为变量在运行时动态申请和释放存储空间的语言放存储空间的语言, ,采用堆式分配是最有效的解采用堆式分配是最有效的解决方案决方案. .堆式分配的基本思想是堆式分配的基本思想是, ,为运行的程序划出适为运行的程序划出适当大的空间当大的空间( (称为堆称为堆Heap),Heap),每

44、当程序申请空间时每当程序申请空间时, ,就从堆的空闲区找出一块空间分配给程序就从堆的空闲区找出一块空间分配给程序, ,每当每当释放时则回收之释放时则回收之. .mcy52在在C C中处理链表等结构时中处理链表等结构时, ,常常随机地插入或删除一些结点常常随机地插入或删除一些结点, ,利用利用指针变量和结构类型指针变量和结构类型, ,可动态地生成新结点可动态地生成新结点( (使用使用mallocmalloc()()函数函数), ), 或删除之或删除之( (使用使用free()free()函数函数).).例如例如 structstruct node char data; node char dat

45、a; structstruct node node * *next;next;定义了定义了链表的结点链表的结点, ,下面函数可在表的尾部添加新结点下面函数可在表的尾部添加新结点: : void void Append(structAppend(struct node node * *head,char head,char chch) ) structstruct node node * *p=head;p=head; while( while(* *p) p=p-next; p-next=p) p=p-next; p-next=malloc(sizeof(structmalloc(sizeof

46、(struct node);node); p-next-data= p-next-data=chch; p-next-next=NULL; p-next-next=NULL;还可用下面的函数在表头删除一结点还可用下面的函数在表头删除一结点: :void void Delete(structDelete(struct node node * *head) head) structstruct node node * *p=head; p=head; if( if(* *p) head =head-next; free(p); p) head =head-next; free(p); 堆分配的必要

47、性堆分配的必要性mcy53将存储空间划分为若干存储块将存储空间划分为若干存储块; ;用户可随机地申请或用户可随机地申请或释放一个或多个块释放一个或多个块; ;在存储空间中建立两个队列在存储空间中建立两个队列: :空闲队列和忙队列空闲队列和忙队列, ,空闲空闲队列拉成链队列拉成链, ,链首用链首用FREEFREE指针指明指针指明, ,忙队列用一忙队列用一( (已占已占块块) )记录表记录各占用块的首址及大小信息记录表记录各占用块的首址及大小信息( (也可用链也可用链进行记录进行记录).).申请时可按需要找到合适的块分配之申请时可按需要找到合适的块分配之( (分配策略有最分配策略有最佳分配或随机分

48、配等佳分配或随机分配等););释放时将该块插入到空闲队列释放时将该块插入到空闲队列( (能合并时可合并能合并时可合并),),并并从占用记录表中删除相应的项从占用记录表中删除相应的项. .堆存储管理的实现堆存储管理的实现mcy54第第7 7章章 运行时环境运行时环境7.1 7.1 程序执行时的存储器组织程序执行时的存储器组织7.2 7.2 完全静态的运行时环境完全静态的运行时环境7.3 7.3 基于栈的运行时环境基于栈的运行时环境7.4 7.4 动态存储器动态存储器7.5 7.5 参数存储机制参数存储机制mcy557.5 7.5 参数传递机制参数传递机制值传递值传递值传递的处理方法是：进入过程时

49、值传递的处理方法是：进入过程时, ,送入形参对应的形式单元的是送入形参对应的形式单元的是相应实参的值相应实参的值; ;过程体中对形参的任何赋值都按对形式单元的直接过程体中对形参的任何赋值都按对形式单元的直接访问来产生代码。访问来产生代码。因此因此, ,一旦把实参之值送入对应形式单元之后一旦把实参之值送入对应形式单元之后, ,在执行过程体期间在执行过程体期间, ,除了以实参值作为形参的初值进行运算之外除了以实参值作为形参的初值进行运算之外, ,将将不再与实参发生任不再与实参发生任何联系。由此可见何联系。由此可见, ,过程执行的结果决不会改变实参之值。过程执行的结果决不会改变实参之值。void i

50、nc2( int x)/* incorrect! */ +x;+x; void inc2( int* x)/* now ok */ +(*x);+(*x); mcy56引用传递引用传递控制转入被调过程后控制转入被调过程后,由被调过程将实参的地址写入由被调过程将实参的地址写入相应的形式单元。过程体中对形式参数的任何引用相应的形式单元。过程体中对形式参数的任何引用或赋值或赋值,都按对相应形式单元间接访问的寻址方式为都按对相应形式单元间接访问的寻址方式为其产生代码其产生代码。显然。显然,执行过程时执行过程时,型参就变成了实参的型参就变成了实参的别名，别名，对形参的赋值将会影响相应实参之值。对形参的赋值将会影响相应实参之值。在在C+中中，是通过在参数说明中使用特殊字符是通过在参数说明中使用特殊字符& &来得来得到引用传递：到引用传递：void inc2( int &x)/* C+ reference parameter */ +x;+x; mcy57引用传递不要求复制被传递的值，这与值传递不同。引用传递不要求复制被传递的值，这与值传递不同。当要当要复制的值是一个较