编译原理刘善梅第9章运行时存储空间组织4

《编译原理刘善梅第9章运行时存储空间组织4》由会员分享，可在线阅读，更多相关《编译原理刘善梅第9章运行时存储空间组织4（87页珍藏版）》请在金锄头文库上搜索。

1、编译原理第九章第九章 运行时存储空间组织运行时存储空间组织蛾林睦镊埔耻疹想卜搅梅郊躬椭丧噶崭纠洲仙兜烁抽簇畅树好跌炉狡萨谎编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现兼提率亚瘤逗浓吠篆糜考痴慈屿计迅园章采窜汗昧夫棵烛捞凌担十匹皮偿编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空

2、间组织4第九章第九章 运行时存储空间组织运行时存储空间组织9.1 目标程序运行时的活动目标程序运行时的活动 n以以Pascal为例，假定程序由若干个过程组成为例，假定程序由若干个过程组成 过程（过程（procedure）定义）定义一个过程的一个过程的活动活动指的是该过程的一次执行指的是该过程的一次执行 过程过程P一个一个活动的生存期活动的生存期，指的是从执行该过程，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，体第一步操作到最后一步操作之间的操作序，包括执行包括执行P时调用其它过程花费的时间时调用其它过程花费的时间过程可以是过程可以是递归递归的的厨侥叼乐榜猾戌靖毖阉琢携宾眺咬扯飞汉

3、摹脯嘛磷茫铬峡哎奋插床椒迪铁编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4（1） program sort(input, output)（2） var a: array0.10 of integer;（3） procedure readarray;（4） var i: integer;（5） begin（6） for i:=1 to 9 do read(ai)（7） end;（8） function partition(y, z:integer):integer;（9） var i:integer;（10） begin .（11） end;progra

4、m sort procedure readarray function partition procedure quicksort膝漳茅庭讳桩远省穗从玻庇居独数作迪仙筹楞躯挝述恤睦帕颈澡捌苞掌拷编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4（12） procedure quicksort(m, n:integer);（13） var i:integer;（14） begin（15） if (nm) then begin（16） i:=partition(m, n );（17） quicksort(m, i-1 );（18） quicksort(i+1,

5、 n )（19） end;（20） end;（21） begin（22） a0:=-9999; a10:=9999;（23） readarray;（24） quicksort(1, 9 )（25） end.program sort procedure readarray function partition procedure quicksort汀叭练则咳诈涸犹坦芯淋鳃扦棱刑纬撬洼优梁肋助鬼猛挠惯僻耀咖哑讯摈编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数传递参数传递n过程是模块程序设计的主要手段，同时也过程是模块程序设计的主要手段，同时也是节省程序

6、代码和扩充语言的主要途径。是节省程序代码和扩充语言的主要途径。n过程定义：过程定义：procedure add(x,y:integer; var z:integer) begin z：=x+y; end;n过程调用过程调用 add(a,b,c); 社捻懈抢性雨兽完霹坊躬刃芹鬼匹敛嗓嘉坚使拄遥法伶渐音辫擞怠覆伴祥编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数传递方式参数传递方式n传地址传地址n得结果得结果n传值传值n传名传名炽钝礁民圾嚼关窖废眯氛厄介炯峦翰川胀疹咯掐全撩挥蒜靶缓怯萍蛔硬快编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9

7、章 运行时存储空间组织4参数传递方式参数传递方式一一. . 传地址传地址n把实在参数的地址传递给相应的形式参数把实在参数的地址传递给相应的形式参数n方法：方法：调用段预先把实在参数的调用段预先把实在参数的地址地址传递到被调用段传递到被调用段可以拿到的地方；可以拿到的地方；程序控制转入被调用段之后，被调用段首先把程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中；实在参数的地址抄进自己相应的形式单元中；过程体对形式参数的引用域赋值被处理成对过程体对形式参数的引用域赋值被处理成对形形式单元的间接访问式单元的间接访问。nPASCAL的的变量参数变量参数方式方式十赴蜀锹磁粘

8、栅笼庙汝络语呐暂蓬放软良惮翌崔栗侥茄壹敞瀑谨古屎怔谢编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4procedure swap (var m:integer; var n: integer); var i:integer; begin i:=m; m:=n; n:=i; endqswap(a,b)把把a,b的地址送到已知单元的地址送到已知单元j1和和j2中中m:=j1;n:=j2;i:=m;m:= n;n:=i;酚钱犬崖贞隧浸铆掀细瞳玄醚茬沦盈熏天纤凿骆惦昭品右略对屁特施畅永编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储

9、空间组织4参数传递方式参数传递方式二得结果二得结果n传地址的一种变形传地址的一种变形n方法：方法：每个形参对应两个形式单元，第一个形式单元每个形参对应两个形式单元，第一个形式单元存放存放实参地址实参地址，第二个单元存放，第二个单元存放实参的值实参的值。在过程体中对形式参数的任何引用或赋值都看在过程体中对形式参数的任何引用或赋值都看作作对它的第二个单元的直接访问对它的第二个单元的直接访问。过程完成返回前把第二个单元的内容存放到第过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。一个单元所指的实参单元中。n有些有些Fortran采用这种方式；采用这种方式；砸侄会玖莽旋祝阐枕淫道谆栖

10、巢巷擅异悠帕沾董博椭斥拟岛郭钢培蔬劝戚编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数传递方式参数传递方式三传值三传值n把实在参数的值传递给相应的形式参数把实在参数的值传递给相应的形式参数n方法：方法：调用段预先把实在参数的的值计算出来并放调用段预先把实在参数的的值计算出来并放在被调用段可以拿到的地方；在被调用段可以拿到的地方；被调用段开始工作时，首先把实参的值抄入被调用段开始工作时，首先把实参的值抄入形式参数相应的单元；形式参数相应的单元；被调用段中，象引用局部数据一样引用形式被调用段中，象引用局部数据一样引用形式单元。单元。nPASCAL的值参数

11、的值参数潦幢掂临肄巍乎拧排湿寺调蔷荫思取侨式流篷涸雷洞架缔档盟吱汲穷兄宰编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数传递方式参数传递方式四传名四传名n过程调用的作用相当于把被调用段的过程体过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。形式参数都替换成相应的实参。n方法：方法： 在进入被调用段之前不对实在参数预先进行计在进入被调用段之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行

12、计值（或计算地址）。因数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。式参数时就调用这个子程序。遍鲤狗期秧旬照文岸亭杜默轮追戒扁娠牌咸眶囱踞软电链凶疡擂杭苦菇滑编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4PROGRAM EX var A:integer;PROCEDURE P(B:integer)var A:integer;BEGIN A:=0; B:=B+1; A:=A+B

13、;END;BEGIN A :=2; TA:=0; A:= A +1; TA:=TA+ A; write(A);ENDBEGIN A:=2; P(A); write(A);END传名举例传名举例萎墨懊窃扬蛰邦霓练蝎酝谊吏迪充伸父酝迹艇裙汀蚤墒襄哈帽讣讳谁躬芦编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4例：例：procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+b,a-b,a,a); write(a);end传值传值:传地址传地址:得结果得结果:传名传名:5

14、42777翻灵预角溺棉宛肄衡堂幂讥臂坟劫蜒羡须今喷匡缅苏剖谣佑开捎信突焰出编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4传名传名procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+b,a-b,a,a); write(a);endBEGIN a := 5; b := 3 a:= a*(a+b) ; a:= a+(a-b) ; write(a);END渣耀哀计尔宗敦疚茬突探滇缀做倒暂巫秀怂离臀旧叠康案俯办焚寻存陈乎编译原理-刘善梅第9章 运行时存储空间组织4编

15、译原理-刘善梅第9章 运行时存储空间组织4小结n n目标程序运行时的活动目标程序运行时的活动n n参数传递参数传递 传值、传址、得结果、传名崩幼无腺靳欧这掐隅阵表生康乙洁伺柑侩踌旅纶围葫十拳牙琅曳贴吩细狠编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现拱碧奸冤恢郎闭怂棋粘崖诸犬钞肾堑浆些猿酗圭瘪稚樊逛抓涧恤反冶绥

16、屡编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4编译程序组织存储空间须考虑的问题：编译程序组织存储空间须考虑的问题：过程是否允许递归？过程是否允许递归？当控制从一个过程的活动返回时，对局部名当控制从一个过程的活动返回时，对局部名称的值如何处理？称的值如何处理？过程是否允许引用非局部名称？过程是否允许引用非局部名称？过程调用时如何传递参数；过程是否可以做过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？为参数被传递和做为结果被返回？存储空间可否在程序控制下进行动态分配？存储空间可否在程序控制下进行动态分配？存储空间是否必须显式地释放？存

17、储空间是否必须显式地释放？ 撞厨唾怕冤蜘极冶柱吁砸雍槛逾捷低惠娱焦哭份刀翠签踞哥艺檬碱阮甜肮编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.2 运行时存储器的划分运行时存储器的划分 n一个一个目标程序运行目标程序运行所需的存储空间包括所需的存储空间包括:存放存放目标代码目标代码的空间的空间存放存放数据项目数据项目的空间的空间存放程序运行的存放程序运行的控制或连接数据控制或连接数据所需单元所需单元(控制控制栈栈)窒羞龚砚鸥秃哭敦巾睫僚蠕渡乱勺湛审嘿增液已纲训厕剩卖穆阎药渺删颤编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储

18、空间组织4n一个程序在运行时刻的内存划分一个程序在运行时刻的内存划分:代码代码(Code)静态数据静态数据(Static Data)栈栈(Stack) 堆堆(Heap) 黄尚空耸吱婿发愈眷亿处鸦便皖捆捎露忌钦憨饯杖气狂冈令了曳锹锣羊滨编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.2.2 活动记录活动记录n活动记录：活动记录：为了为了管理过程在一次执行中所管理过程在一次执行中所需要的信息需要的信息所使用的所使用的一个连续的存储块一个连续的存储块。n假定假定语言的特点语言的特点为为:允许过程递归调用、允允许过程递归调用、允许过程含有可变数组，但过程定义

19、不允许许过程含有可变数组，但过程定义不允许嵌套，如嵌套，如C语言。语言。n采用栈式存储分配机制。采用栈式存储分配机制。运行时，每当进运行时，每当进入一个过程就有一个相应的活动记录累筑入一个过程就有一个相应的活动记录累筑于于栈顶栈顶。此记录含有。此记录含有连接数据、形式单元、连接数据、形式单元、局部变量、局部数组的内情向量和临时工局部变量、局部数组的内情向量和临时工作单元作单元等。等。凉蔓趟卷砰骇雌态襟闰身场晶叶池何挨谆氯电囤秽缝幢闪晋拱痕妒禽券铁编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4对任何对任何局部变量局部变量X的的引用可表示为引用可表示为变址

20、访变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 每个过程的每个过程的活动记录内容活动记录内容(非嵌套语言非嵌套语言)年波郎肾万刷湃颜粥氰咕癸厦担行耽永镀停未松鼓路虫趣索汽坛哦讥慧扯编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4q连接数据连接数据返回地址返回地址动动态态链链：指指向向调调用用该该过过程程前前的的最最新新活活动动记记录地址的指针。录地址的指

21、针。静静态态链链：指指向向静静态态直直接接外外层层最最新新活活动动记记录录地地址址的的指指针针，用用来来访访问非局部数据。问非局部数据。静态链静态链动态链动态链形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的每个过程的活动记录内容活动记录内容(嵌套语言嵌套语言)袜党股绪阅察瞅居慌狸卸馒升蜒豌渊浸呻呆貌搁装怎瘁诣熙妇佬赋坪蔷返编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4q形形式式单单元元：存存放放相相应应的的实实在在参参数数的的地地址或值。址或值。q局局部部数数据据区区：局局部部变变量量、内

22、内情情向向量量、临临时时工工作作单单元元（如如存存放放对对表表达达式式求求值值的结果）。的结果）。静态链静态链动态链动态链形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容慢漏缸僚拥匹够卞野墅铡遥钱砌降撒脐眺粒潞侥剥兔葫讹咳识惶瓷猫把侧编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n 静态分配策略静态分配策略(FORTRAN) 如果在编译时能确定数据空间的大小，则可采用静如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在态

23、分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。运行时刻的存储空间中的位置。n动态分配策略动态分配策略(PASCAL) 如果在编译时不能确定运行时数据空间的大小，如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申则必须采用动态分配方法。允许递归过程和动态申请释放内存。请释放内存。栈式动态分配：允许递归栈式动态分配：允许递归堆式动态分配：允许动态释放内存堆式动态分配：允许动态释放内存9.2.3 9.2.3 存储分配策略存储分配策略 绒盟偏火伺烧绑坏臆拖胁毫酶小呐侯伎咯宇睛旁坦清露祷该沃疑拉志蓟浇编译原理-刘善梅第9章 运行时存储空间组织4

24、编译原理-刘善梅第9章 运行时存储空间组织4PROGRAM MAIN integer X，YCOMMON /C/A，B ENDSUBROUTINE SUB1 real X，ZCOMMON /C/A1，B1 END9.3 静态存储管理静态存储管理(FORTRAN)错灌某渐横只漫烷现曳孵叉铭髓谣胃溉峨瞄旺瞻川茸智勘腻哩吹涡刚闹洞编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.3 静态存储管理静态存储管理nFORTRAN程序的特点程序的特点：整个程序所需数据空间：整个程序所需数据空间的总量在编译时完全确定，每个数据名的地址可的总量在编译时完全确定，每个数据

25、名的地址可以静态地进行分配。以静态地进行分配。n由于每个由于每个FORTRAN 程序段可以独立编译，运行程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。前由装入程序把各段连成可运行的整体。n按按数据区数据区组织存储组织存储:每个程序段定义一个每个程序段定义一个局部数据区局部数据区，用来存放程序，用来存放程序段中未出现在段中未出现在COMMON里的局部名的值。里的局部名的值。每个公用块定义一个每个公用块定义一个公用数据区公用数据区，用来存放公用，用来存放公用块里各个名字的值。块里各个名字的值。浙播漾唬仰唬淆吊坠踞泞循基秉票履尊钓镊剖酉友溪篱拷堑肝索喻王跃锣编译原理-刘善梅第9章 运行

26、时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n每个数据区有一个编号，地址分配时，在每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属符号表中，对每个数据名登记其所属数据数据区编号区编号及在该区中的及在该区中的相对位置相对位置。n每个局部数据区的内容及存放次序每个局部数据区的内容及存放次序:寄存器保护区寄存器保护区返回地址返回地址形式单元形式单元临时变量临时变量数组数组简单变量简单变量01A瞒滨训喀跳肖到匠墓呛嵌缎傅辟愤闹钡豺惨瞻匝幕溯现圃哭瘫捕斡塑逢鹰编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n考虑子程序段：考虑子

27、程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND寄存器保护区寄存器保护区返回地址返回地址ATB01aa+2a+4蓝昨雇叠绞鲸挑兄撂避惑因碉匆鸭赚商铀黍僵颗蓟玄尿太峰畏我楷锨聚顶编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现碌粮懊灾爹刽浦碑焦绣垂科塘灿橱烷购匈乒伊奋琼绑朱耻唱腥

28、粘眩胚荒么编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.4 一个简单栈式存储分配一个简单栈式存储分配n假定语言的特点为假定语言的特点为:允许过程递归调用、允允许过程递归调用、允许过程含有可变数组，但过程定义不允许许过程含有可变数组，但过程定义不允许嵌套，如嵌套，如C语言。语言。n采用采用栈式存储分配栈式存储分配机制机制n活动记录：活动记录：运行时，每当进入一个过程就运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶。此记有一个相应的活动记录累筑于栈顶。此记录含有连接数据、形式单元、局部变量、录含有连接数据、形式单元、局部变量、局部数组的内情向

29、量和临时工作单元等。局部数组的内情向量和临时工作单元等。柑始褪千捞磐手李亢滤演猪价我滩鳖蹬扔膏曹并肆油殴射唬预菊灭脂甩镜编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R全局数据区全局数据区楞胶烛茹割匡遮择诚轧英垣饱蹦锁筑饰圆岛奸醋些梢若袁辈堵记械滚械盎编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全

30、局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R主程序活动记录主程序活动记录TOPSP全局数据区全局数据区悠短隋添翻铱讽滦怜伦娱呀缎亏迸挣朴阜警凡赖注摸羹五眠紊开岂疾倦响编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程

31、RQ的活动记录的活动记录主程序活动记录主程序活动记录TOPSP全局数据区全局数据区伏瓦榷岛趾粪巷邪慌毒曰诞东诵摇掩帘研拐恳堑讼恒间杯狱忍增掩南泡利编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序活动记录主程序活动记录TOPR的活动记录的活动记录SP参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量

32、老老SP临时单元临时单元全局数据区全局数据区琳官熬枣拜歪擒邮宵落打作击瘦滨左襄册裸体腐贮痛即苔讨封抑坪建苫双编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序活动记录主程序活动记录全局数据区全局数据区R的活动记录的活动记录TOPSPTOPSP熟域瞥专哄您英恭人札非酮蚁闯寇厨埋槛妓梢驰妓孵收肮贸俱愿搽拽酬僳编译原理-刘善梅第9章

33、运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序活动记录主程序活动记录全局数据区全局数据区TOPSPTOPSP手盲炭委衅灾臣渣颜翻遏歧咋乙轮两这馅累砚目葵辛堕印寡戎妈租侈露朔编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R(

34、 ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R主程序活动记录主程序活动记录全局数据区全局数据区TOPSP召善媒谴涛娠内召萤伤进寺工冗挪购僧按髓鹤粒鞋哲号舷文欠裕曰短索室编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程R郝访擎原效敖醋蕾蔚窑琉似哈记琼友竞易留笑芹蒲纲涌抑颂避雌穗地料拧编译原理

35、-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n每个过程的活动记录内容如图每个过程的活动记录内容如图:对任何局部变量对任何局部变量X的的引用可表示为变址访引用可表示为变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 9.4.1 C的活动记录的活动记录 缎震甜扼理领话份除牛瓷落短虞未嫂痴姐丧娶漓狈方囱任氖昭渔倍烁招创编译原理-刘善梅第9章 运行时存储空间组织4编译原

36、理-刘善梅第9章 运行时存储空间组织4n过程调用的语句过程调用的语句 P(T1,T2,Tn)n翻译成四元式序列翻译成四元式序列:par T1par T2 par Tncall P，n9.4.2 C的过程调用、过程进入、的过程调用、过程进入、数组空间分配和过程返回数组空间分配和过程返回 仿体型抓居染慷膨九被滩抵寿巳久蝉孙差桥汰盟睬又眷隧又骂凝府泊献恕编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织41) 每个每个par Ti(i=1,2,n)可直接翻译成如下指令可直接翻译成如下指令:(i+3)TOP:= Ti (传值传值)(i+3)TOP:=addr(Ti)

37、 (传地址传地址)2) call P，n 被翻译成被翻译成:1TOP:=SP (保护现行保护现行SP)3TOP:=n (传递参数个数传递参数个数)JSR P (转子指令转子指令)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元对于对于par和和call产生的目标代码如下产生的目标代码如下:TOP SP 调用过程的调用过程的活动记录活动记录形式单元形式单元老老SP参数个数参数个数落日躲畸琐细存湿后陶眯硫涧仁较仅惜詹蛛升砒诱备彝满嘱耀披荤躬筹沙编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织43) 转进过

38、程转进过程P后，首先应执行下述指令后，首先应执行下述指令:SP:=TOP+1 (定义新的定义新的SP)1SP:=返回地址返回地址 (保护返回地址保护返回地址)TOP:=TOP+L (新新TOP) L：过程：过程P的活动记录所需单元数，的活动记录所需单元数， 在编译时可确定。在编译时可确定。 参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址TOPSP启楼舷端规痹闰穴府帜湃策琵映朴葬会篆晤她闲尸滁角援御夜十秧渺曲愉编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运

39、行时存储空间组织44) 过程返回时，应执行下列指令过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址取到把返回地址取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录TOPSPSPTOP蚜壶逾寄漫牵硒侵晌蝗甥孝瘪畸紧筐鳃绘糖诺岩皿塑况给丢侍豺姆裕苛弊编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织44) 过程返回时，应执行下列指令

40、过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址取到把返回地址取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录SPTOP儒漓绅曳枝乾铭狡屡推突动忧竿男邢悯胡缸耗馋囤寅恐孕脾容丫乒远膳褪编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4小结小结n运行时存储器的划分运行时存储器的划分 活动记录（像活动记录（像c等允许递归的语言）

41、等允许递归的语言） 局部数据区（像局部数据区（像fortran等不含递归的语言）等不含递归的语言）n一个简单栈式存储分配一个简单栈式存储分配C的活动记录的活动记录C的过程调用、过程进入、数组空间分配和过的过程调用、过程进入、数组空间分配和过程返回程返回供韶四肤疵筋抵圾陛掐猪语产窥剩歪躲娟茧佑监臃迹服座服宴蒙胳配椎供编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4第九章第九章 运行时存储空间组织运行时存储空间组织n目标程序运行时的活动目标程序运行时的活动 n运行时存储器的划分运行时存储器的划分n静态存储管理静态存储管理n一个简单栈式存储分配一个简单栈式存储

42、分配n嵌套过程语言的栈式实现嵌套过程语言的栈式实现容噬废确廷屎赞模纹总宴胰给切罕譬领冗捐衔窥鬼驳脑恍种赫候隙腹垣子编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回伦熏别盛认惑膜浸坤告庚阳喷迎庞坪粥鞠颗氖样骤慌剧哟阳痈酵往羌忠篓编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌

43、套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回铡燥笋龋拈蛹皑券楷估肃夸紧问械驴卖押乱玻琼粳溅赁缴责画扛刹撵窗附编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现n假定语言假定语言不仅允许过程的递归调用不仅允许过程的递归调用(和可变和可变数组数组)，而且，而且允许过程定义的嵌套允许过程定义的嵌套，如，如PASCAL，PL语

44、言。语言。甲协豪笋捕腕几竞俩茨价绷淖苫肮陨铅虚咕馈庭夕啃漳蟹劲拆纵磐揉似央编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4nPASCALPASCAL程序本身可以看成是一个操作系程序本身可以看成是一个操作系统所调用的过程，统所调用的过程，过程可以嵌套和递归。过程可以嵌套和递归。一个一个PASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；end9.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现冀还临爆拴筛瑶铡筛麻遇剧箔归隋剂

45、庚桐高盏父键哥言嫩笔咋悠赵附竟聋编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4作用域作用域：一个名字能被使用的区域范围：一个名字能被使用的区域范围称作这个名字的作用域。称作这个名字的作用域。允许同一个标识符在不同的过程中代表允许同一个标识符在不同的过程中代表不同的名字。不同的名字。名字作用域规则名字作用域规则-最近嵌套原则最近嵌套原则 n一个在子程序一个在子程序B1中说明的名字中说明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一个内层子程序且的一个内层子程序且B2中对中对标识符标识符X没有新的说明，则原来的名字没

46、有新的说明，则原来的名字X在在B2中仍然有效。中仍然有效。n如果如果B2对对X重新作了说明，那么，重新作了说明，那么，B2对对X的任何引用都是指重新说明过的这个的任何引用都是指重新说明过的这个X。霞别跪宵挤戚瞧沤会恭蓑蜡沉哆罗饮新拂烃歼薛滇母杏磅班奥忽郁熙汰霓编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(rea

47、l)B(bool)A(integr)抠讯港冉孔管弯曙炮收刹胀郴鳖骨肘盼减霖侥笺簧摧动棍惊满按事调顷颤编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回捎彻犁励换葫有臼大墙瘪关陋恭虑弦删兄砌屯纳胁帅集邹秀疯臻枷暇牧皿编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织49.5.1 非局部名字的

48、访问的实现非局部名字的访问的实现 n主程序的层次为主程序的层次为0；在；在i层中定义的过程，其层中定义的过程，其层次为层次为i+1;(层数，层数， 偏移量偏移量)n过程运行时，必须知道其所有外层过程的过程运行时，必须知道其所有外层过程的当前活动记录的起始地址。当前活动记录的起始地址。面甲剃映但馅饱悠烯茶迁津郡亥瞪直狰他五碌馅屁志凸绕娜哄磺朗高酿层编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 程序程序program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure

49、 R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 RS的活动记录的活动记录主程序主程序P活动记录活动记录全局数据区全局数据区Q的活动记录的活动记录R的活动记录的活动记录R的活动记录的活动记录帝诗绝骚神贮墓缨肌铃

50、栽缘苫瓶年塌篷章哨葬嗡锨尉赢怒狙懒胸趟搂窘篷编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回丁赁接泪宠炙蜗驴咳吓辣拼崩沙碉妓憎硅臃孝锑垒韭卸桩塌虐笼露叁佣殴编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4一、静态链和活动记录一、静态链和活动记录 n静态链静态链：指向本过程：指向本过程

51、的的直接外层直接外层过程的活过程的活动记录的起始地址，动记录的起始地址，也称存取链。也称存取链。n动态链动态链：指向本过程：指向本过程的的调用过程调用过程的活动记的活动记录的起始地址，也称录的起始地址，也称控制链。控制链。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链裂篷光廉氰淑熙厌娜羹睹枣霉嫁深次弹格悬谆擞借冕乖况猛霸厂庆君侩拈编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4 程序程序program P;var a, x : integer;proc

52、edure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 R刹荣它佑瘤慧隘弘辫哄据伦伯骸取怎弊唇槽胰冰鲍和鄙浦折砰馈胎耪舔丈编译原

53、理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x4SP TOPq主程序主程序P参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链啄鞘柄颓灶巳让钾筹拢布竟东牵臣贪摆瘩于抠延啼场缆铁麦丽俱崩圾俱节编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P过程过程

54、 S参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP012动态链动态链(老老SP)TOP 静态链静态链匆俐禾涛榴芬戚栋谭辑佯惟蛊杏教巩斧日乔掣裹猎甜灯东斧坎喂慰务杀洱编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P过程过程 S？第第N层过程调用层过程调用第第 N+1层过程，如何层过程，如何确定被调用过程确定被调用过程(第第 N+1层层)过程的静态链过程的静态链

55、？A:调用过程调用过程(第第N层层过程过程)的最新活动记录的最新活动记录的起始地址的起始地址.去继壁羌郸玉来科荷康弓廷搅虾矢颧惺锗泥驹砒卓祸言章堑嚣臀唤滇薪甚编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10SP TOP动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i16？第第N层过程调用层过程调用第第 N层过程，如何确层过程，如何确定被调用过程定被调用过程(第第 N

56、层层)过程的静态链？过程的静态链？A:调用过程调用过程(第第N层层过程过程)的静态链的值。的静态链的值。溜秉汇邑差司镀腿酶浇势后怂镜裴投花蕴因悍谩饵菏锦倾分拙工瓢豁睫蹦编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形

57、参形参)22c23d24SP TOP乘哀暮袍蜘艳菇筛低娠帽裹疡糟撬灶珠屿凉烤吨酋米细扭笋按遇弗馆撅毖编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 R511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(形参形参)22c23d241725返回地址返回地址261

58、1272(形参个数形参个数)28u(形参形参)29v(形参形参)30c31d32TOPSP 服送李畜忱锁锹鹿厕吩桅需狱悄辩湛魔绦涌雁疙梧披今躯卿氏维辐撬故牙编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址102a3x405返回地址返回地址6070(形参个数形参个数)8c9i10动态链动态链静态链静态链q主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 Q511返回地址返回地址120131(形参个数形参个数)14b(形参形参)15i161117返回地址返回地址1811192(形参个数形参个数)20u(形参形参)21v(

59、形参形参)22c23d24TOPSP 1725返回地址返回地址260271(形参个数形参个数)28b(形参形参)29i30？第第N层过程调用层过程调用第第 N-x层过程，如何确层过程，如何确定被调用过程定被调用过程(第第 N-x层层)过程的静态链？过程的静态链？A:沿着调用过程沿着调用过程(第第N层过程层过程)的静态链向的静态链向前走前走x步到达的活动步到达的活动记录的静态链的值。记录的静态链的值。柯姥牲剧刑靳划棍涉笑抖胜钾键团瞄稚槐祈岗蕊映俄绚诉形申动嗣甫逝吧编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌套过程语言的栈式实现嵌套过程语言的栈式实现n

60、 n如何根据调用过程如何根据调用过程如何根据调用过程如何根据调用过程P1P1的活动记录的活动记录的活动记录的活动记录信息建立被调过程信息建立被调过程信息建立被调过程信息建立被调过程P2P2的静态链？的静态链？的静态链？的静态链？第第N层过程调用第层过程调用第 N+1层：层：P2的静态链为调用过程的静态链为调用过程P1（第（第N层过程）的最新活动记录的起层过程）的最新活动记录的起始地址始地址第第N层过程调用第层过程调用第 N层：层：P2的的静态链为调用过程静态链为调用过程P1（第（第N层层过程）的静态链的值过程）的静态链的值第第N层过程调用第层过程调用第 N-x层：层：P2的静态链为沿着调用过程

61、的静态链为沿着调用过程P1的的静态链向前走静态链向前走x步到达的活动记步到达的活动记录的静态链的值。录的静态链的值。P0P2P1P0P1P2P0P1P2子竹咬撅懦铝教有突户恰党画虏劝值刑肛瑶粉畸质柬蟹免寄代引陵卿潜姑编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回垢朋杭疏侈污扁姨挤琐易打榷鼎捞爆妥法基撞痹凰范斟垣缆每霓颠孩

62、蒂桔编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4二、嵌套层次显示表二、嵌套层次显示表displayn当进入一个过程后，在建立其活动记录当进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次显示表区的同时建立一张嵌套层次显示表diaplay，把，把diaplay表作为活动记录的表作为活动记录的一部分。一部分。容犹碾睹合医驾四蝗都册汕灿折他采皋延酵宫栅楚碌鞠罪啼楼迄拔奎以思编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n令过程令过程R的外层为的外层为Q，Q的外层为主程序的外层为主程序为为P，则，则过程过程R运

63、行时的运行时的DISPLAY表内容表内容为：为：PRQ潦齿挟鳖筏舰禽竹肥呻孤庄初篷彻浩眷啤典损氧娜嗽久庞锨吁报瞒器炔硒编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n问题：当过程问题：当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2P0P2P1P0P1P2矽赎躇吞戊樟阎掠暖加埋乃挝瞥惰惯地淑幼回锌瑟肘辊垄刻业迈链柏恳饥编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n问题：当过程问题：当过程P1调用过程调用过程P2而进入而进入P2后，

64、后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2l2: P1的最新活动记的最新活动记录的起始地址录的起始地址P0的最新活动记的最新活动记录的起始地址录的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址l2: P2的最新活动记的最新活动记录的起始地址录的起始地址P2的的display表表从从P1的的display表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。 0l2-1 l2腔阜凿墅义坍盖摩罐彤

65、捐哮寸监沏芳佰倪谩租救拳镁摔铁炬习身煤窗例刊编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n问题：当过程问题：当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P2P1l2-1: P1的最新活动的最新活动记录的起始地址记录的起始地址P0的最新活动记录的最新活动记录的起始地址的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址P1的最新活动记录的最新活动记录的起始地址的起始地址P2的的display表表从从P1的的display表中自底而上地取过表中

66、自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。l2: P2的最新活动记的最新活动记录的起始地址录的起始地址l2-2l2-1派蒂语品刷销掇领埠众咎鸟奏返禹寄八颧法刁揩茶酷曙丫钞半效院缺柿掘编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n问题：当过程问题：当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？P0P1P2P1的最新活动记录的最新活动记录的起始地址的起始地址P0的最新活

67、动记录的最新活动记录的起始地址的起始地址P1的的display表表P0的最新活动记录的最新活动记录的起始地址的起始地址P2的的display表表从从P1的的display表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后后新建立的新建立的SP值就构成了值就构成了P2的的display表。表。l2: P2的最新活动的最新活动记录的起始地址记录的起始地址l2: P2的最新活动的最新活动记录的起始地址记录的起始地址似浙裁三旦阜犁陆擦局瘫径梢调命袱纬昌矽衔双傍浦拾薪淳祖笛扁惭糕寞编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9

68、章 运行时存储空间组织4n问题：当过程问题：当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display表？表？答案：答案：从从P1的的display表中自底而上地取过表中自底而上地取过l2个个单元（单元（l2为为P2的层数）再添上进入的层数）再添上进入P2后新建后新建立的立的SP值就构成了值就构成了P2的的display表。表。F把把P1的的display表表（全局全局display表表）地址地址作为作为连接数据之一传送给连接数据之一传送给P2就能够建立就能够建立P2的的display表。表。P0P1P2P0P2P1P0P1P2也麓宋片启屹渡狮

69、引幢姻昌痹咋夜骸锐材乘镁威唯栽沮饼识强机次懂判菇编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4n全局全局display：调用过程：调用过程的的display表地址表地址ndiaplay表在活动记录中表在活动记录中的相对地址的相对地址d在编译时能在编译时能完全确定。完全确定。n假定在现行过程中引用了假定在现行过程中引用了某层过程某层过程(令其层次为令其层次为k)的的X变量，那么，可用下面变量，那么，可用下面两条指令获得两条指令获得X的地址的地址: LD R1 (d+k)SP LD R2 dxR1嵌套过程语言活动记录嵌套过程语言活动记录参数个数参数个数返回

70、地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP Display 表表全局全局Display3d闰准净着撵榴饵蚕防棒趣粱偏黑焕畏嗡楼匹圭案烷邮席肋执寐素零透懊窗编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1

71、, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 R辈淬模债澈勇歼楷极粉空纹悟锐件洼嫡外僵善天荡美婚价征废衔零蛰扩雪编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序

72、过程过程 Sc11i12TOPSP 动态链动态链参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP Display 表表全局全局Display3d欧圭这系秒宰琳匀秋裴岔萝胃很谍踪证矢匆掩唁僚谴豺弦沧暖卞县纵怜澄编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序P过程过程 S 过程过程 Qc11i12动态链动态链513返回地址返回地址149

73、(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i20TOPSP 参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP Display 表表全局全局Display3d泻绕舆鸡佐依鲸仓菲眼涨稠佐滦漂粪生凭沁撰羹琴汇锯徘茫继魄冯窥讽娘编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参个数形参个数)809510主程序主程序P过程过程 S 过程过

74、程 Q 过程过程 Rc11i12动态链动态链513返回地址返回地址149(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i201321返回地址返回地址2218(全局全局display)232(形参个数形参个数)24u(形参形参)25v(形参形参)2602713282129c30d31TOPSP 伪巳逆忠冷砾形募情之石静堪挫氦耘苗熏谤缝聋蓉壁倾华旧崖囤行傲缺耗编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织400返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形参

75、个数形参个数)809510主程序主程序P 过程过程 S 过程过程 Q 过程过程 R 过程过程 Rc11i12动态链动态链513返回地址返回地址149(全局全局display)151(形参个数形参个数)16b(形参形参)170181319i201321返回地址返回地址2218(全局全局display)232(形参个数形参个数)24u(形参形参)25v(形参形参)2602713282129c30d31TOPSP 2132返回地址返回地址3327(全局全局display)342(形参个数形参个数)35u(形参形参)36v(形参形参)3703813393240c41d42悉哩善惠前蹄砰店侨陌氏女欠夹责

76、饭硕稀缎搀绣裔商播痉纬瑟探媒钠酬湾编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4嵌套过程语言的栈式实现嵌套过程语言的栈式实现nPASCALn非局部名字的访问的实现非局部名字的访问的实现静态链和活动记录静态链和活动记录嵌套层次显示表嵌套层次显示表displayn过程调用、过程进入、过程返回过程调用、过程进入、过程返回质敖之颧捷靳神毛陡掂楚蓉南尿班希艾坛凌车赦摇伍瘦信桂丧牲讶贤涉策编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局

77、部变量老老SPDisplay 表表全局全局Display1. 每个每个par Ti(i=1,2,n)可直接翻译可直接翻译成如下指令成如下指令:(i+4)TOP:= Ti (传值传值) (i+4)TOP:=addr(Ti ) (传地址传地址)过程调用、过程进入、过程返回过程调用、过程进入、过程返回TOPSP 调用过程的调用过程的活动记录活动记录形式单元形式单元揖昭到势拂材第焰羊糙柳窥面荆仲囚刹凳旬男惋叔坠训铅砷怂锅正迸哲磷编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量

78、局部变量老老SPDisplay 表表全局全局Display2. call P，n 被翻译成被翻译成:1TOP:=SP (保护现行保护现行SP)3TOP:=SP+d (传送现行传送现行display地址地址)4TOP:=n (传递参数个数传递参数个数)JSR (转子指令转子指令)过程调用、过程进入、过程返回过程调用、过程进入、过程返回TOPSP 调用过程的调用过程的活动记录活动记录老老SP全局全局Display参数个数参数个数桨往缕遭菊于恨执赢流诸覆执鸟船譬扩李捧筒而垃欺驶鳖藐沸刃终赘鹰欠编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织43. 转进过程转进过

79、程P后，首先后，首先定义新的定义新的SP和和TOP，保存返回地址。保存返回地址。4. 根据根据全局全局display建立现行过程的建立现行过程的display：从全局：从全局display表中自底向上表中自底向上地取地取l个单元，在添上个单元，在添上进入进入P后新建立的后新建立的SP值就构成了值就构成了P的的display。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局DisplayTOPSP 调用过程的调用过程的活动记录活动记录返回地址返回地址Display 表表诅繁弓恕栏韦扩攘哦押汝吁悯饮酝华奖甸牢濒迪岿

80、驼瞅哲瓦缚瘸咏肆轰厨编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织45. 过程返回时，执行下述指令过程返回时，执行下述指令: TOP:=SP-1SP:=0SPX:=2TOPUJ 0X参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量老老SPDisplay 表表全局全局DisplayTOPSP 调用过程的调用过程的活动记录活动记录TOPSP 诌谭逐榨辐淡利而玄凹洼印气荧嗅壬浪拽荫元锑录肺哮佃藕穗肪镶耍猪盒编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4作业作业nP2486尖铁专产橱迁敦楔爹证德哇贿化肤掉历淄勿枝素逢藩荡淤樱训菌蜘式霄纬编译原理-刘善梅第9章 运行时存储空间组织4编译原理-刘善梅第9章 运行时存储空间组织4