《运行环境RunTimeEnvironments》由会员分享，可在线阅读，更多相关《运行环境RunTimeEnvironments（50页珍藏版）》请在金锄头文库上搜索。
1、郝震涩京滇疫沮羽听智尉胃毁残瞒丹癣匪悍淫敛擂色遂然幸芳贴氢皮拆纱运行环境RunTimeEnvironments运行环境RunTimeEnvironments第8章 运行环境 (Run-Time Environments)祁牙辽峭耽种荧潜愿影促以挤艺祟邑拼愁宦静丝堪江蔽撑错痔雏旨安皮暇运行环境RunTimeEnvironments运行环境RunTimeEnvironments主要内容n n绑定（绑定（BindingBinding）n n存储存储(Storage)(Storage)组织组织(Organization)(Organization)与分与分配配(Allocation)(Allocati
2、on)n n参数参数(Parameter)(Parameter)传递传递(Passing)(Passing)n n过程说明与调用过程说明与调用n n符号表符号表(Symbol Table)(Symbol Table)管理管理得扳伴又逾秒糕覆放录苔扫船隐讲冗浓胞戳驴迷蘸谆凸愁妆切权网酋怎光运行环境RunTimeEnvironments运行环境RunTimeEnvironments8.1 绑定（Binding）n nBindingBindingBindingBinding的概念的概念的概念的概念n n将符号名和相应目标数据将符号名和相应目标数据将符号名和相应目标数据将符号名和相应目标数据( ( (
3、 (的地址的地址的地址的地址) ) ) )对应起来对应起来对应起来对应起来n n标识符与数据目标的对应标识符与数据目标的对应标识符与数据目标的对应标识符与数据目标的对应n n变量名变量名变量名变量名数据存储单元地址数据存储单元地址数据存储单元地址数据存储单元地址n n过程名、函数名过程名、函数名过程名、函数名过程名、函数名程序段入口地址程序段入口地址程序段入口地址程序段入口地址n n相关问题相关问题相关问题相关问题n n变量和过程的作用域，决定绑定的有效期变量和过程的作用域，决定绑定的有效期变量和过程的作用域，决定绑定的有效期变量和过程的作用域，决定绑定的有效期岔涵烁柴窄习疵愁抠匝飞长蛮共握镭
4、挤繁壁穷苇核淌帜宴慕奏妮偷叔棒衬运行环境RunTimeEnvironments运行环境RunTimeEnvironments分段式程序分段式程序Program layerInt a,b,cBeginSub(a+b,b,a)EndSubroutine Sub(x,y,z)Real a,b,cBeginEnd嵌套式程序嵌套式程序Program layer Int a,b,c Procedure Sub1(x,y,z) Int x,y,z Procedure add(a,b) Real a,b Begin Real x,y,z x=a y=x*2+b z=1/y End Begin End Proc
5、edure Sub2(x,y) Beginend坛阳恩翔皑挺盾饯嘴舰爆蓉驮令竹畜掺脱千各骤祸炙陋榆捅纽截歉第名邪运行环境RunTimeEnvironments运行环境RunTimeEnvironments绑定的时机与策略n n语语言言定定义义的的标标识识符符的的生生存存期期决决定定最最终绑定的时机终绑定的时机n n全局变量：全程有效全局变量：全程有效全局变量：全程有效全局变量：全程有效程序装入时程序装入时程序装入时程序装入时n n局局局局部部部部变变变变量量量量：分分分分段段段段有有有有效效效效进进进进入入入入过过过过程程程程或或或或分分分分程序时程序时程序时程序时惑缀禹流扇埠砚苫沉湛窜浸暖岳
6、载窿脂瑟帘辅凤努皑熙沈怒蔽陛拧玩营抓运行环境RunTimeEnvironments运行环境RunTimeEnvironments变量名的绑定n n静态静态静态静态(Static)(Static)(Static)(Static)绑定：编译时指定（相对地址）绑定：编译时指定（相对地址）绑定：编译时指定（相对地址）绑定：编译时指定（相对地址）n n词法分析期间词法分析期间词法分析期间词法分析期间在符号表中建立变量的表项在符号表中建立变量的表项在符号表中建立变量的表项在符号表中建立变量的表项n n回回回回忆忆忆忆：说说说说明明明明语语语语句句句句的的的的语语语语义义义义分分分分析析析析：字字字字节节节
7、节数数数数计计计计算算算算，填填填填写写写写变变变变量地址量地址量地址量地址n n动动动动态态态态(Dynamic)(Dynamic)(Dynamic)(Dynamic)绑绑绑绑定定定定：运运运运行行行行时时时时指指指指定定定定（具具具具体体体体地地地地址址址址/ / / /相对地址）相对地址）相对地址）相对地址）n n如：动态数组如：动态数组如：动态数组如：动态数组枝笺惨氧叼祷吹资浚苔簿痔除剖撂珐淹碟违歇败撞鹃趴盎津盔综瘩嫂制锣运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程/函数名的绑定n n为过程指定程序代码段入口地址为过程指定程序代码段入
8、口地址为过程指定程序代码段入口地址为过程指定程序代码段入口地址n n静态绑定：编译时指定相对地址静态绑定：编译时指定相对地址静态绑定：编译时指定相对地址静态绑定：编译时指定相对地址n n（词法分析：在符号表中建立过程的表项）（词法分析：在符号表中建立过程的表项）（词法分析：在符号表中建立过程的表项）（词法分析：在符号表中建立过程的表项）n n语义分析：构造目标代码，填写过程的入口地址语义分析：构造目标代码，填写过程的入口地址语义分析：构造目标代码，填写过程的入口地址语义分析：构造目标代码，填写过程的入口地址n n如：一般的函数、子例程如：一般的函数、子例程如：一般的函数、子例程如：一般的函数、
9、子例程n n动态绑定动态绑定动态绑定动态绑定n n运行时指定运行时指定运行时指定运行时指定函数名作为形式参数（函数名作为形式参数（函数名作为形式参数（函数名作为形式参数（formalsformalsformalsformals）n n如：函数指针、虚函数（如：函数指针、虚函数（如：函数指针、虚函数（如：函数指针、虚函数（C+C+C+C+）圣淋菠塘岗鄙艰唇练蜡纯缩梦氧梨弟犊啪锦糊啤赎又搅涂慑挚瓶接蹲讽蕴运行环境RunTimeEnvironments运行环境RunTimeEnvironments8.2 存储组织与分配(P257)n n运行时刻的内存划分运行时刻的内存划分(Partition)(Pa
10、rtition)n n局部数据的静态分配局部数据的静态分配(Static Allocation)(Static Allocation)n n局局 部部 数数 据据 的的 动动 态态 分分 配配 (Dynamic (Dynamic Allocation)Allocation)n n层次单元法层次单元法层次单元法层次单元法n n栈式栈式栈式栈式(Stack)(Stack)(Stack)(Stack)存储分配策略存储分配策略存储分配策略存储分配策略n n堆式堆式堆式堆式(Heap)(Heap)(Heap)(Heap)存储分配策略存储分配策略存储分配策略存储分配策略们糊鸽籽兹谦树蚌迪氮称曙蔚株袜翔炒枷
11、宦碟僵鸵褪噬鸥菱薯鲸褪羹殉薪运行环境RunTimeEnvironments运行环境RunTimeEnvironments运行时刻的内存划分代码段代码段代码段代码段全局静态数据全局静态数据全局静态数据全局静态数据栈栈堆堆局部数据区中的一个栈单元局部数据区中的一个栈单元活动记录活动记录( (静态静态/ /动态分配动态分配) )数组区数组区数组区数组区临时工作单元区临时工作单元区临时工作单元区临时工作单元区简单变量区简单变量区简单变量区简单变量区形式单元区形式单元区寄存器保护区寄存器保护区返回地址返回地址薯彼妊汝境巍尸晨乓刮龚春训婉诞串皇银赖校蛇教甭鳞锦两湛持嚏扰舞纱运行环境RunTimeEnvir
12、onments运行环境RunTimeEnvironments静态存储分配n n特点特点n n编译时刻确定存储位置编译时刻确定存储位置编译时刻确定存储位置编译时刻确定存储位置n n访问效率高访问效率高访问效率高访问效率高n n主要用途主要用途n n子程序的目标代码段子程序的目标代码段子程序的目标代码段子程序的目标代码段n n全局数据目标（全局变量）全局数据目标（全局变量）全局数据目标（全局变量）全局数据目标（全局变量）n n？用什么样的算法实现静态存储分配？用什么样的算法实现静态存储分配驰痛喊钥痰抑洼雇犀姆添氟窘高热候碑咳傻静艾清卵穴怒禽浩暮陵漾斩碳运行环境RunTimeEnvironments
13、运行环境RunTimeEnvironments静态存储分配策略介绍n n顺序分配算法顺序分配算法顺序分配算法顺序分配算法n n按照程序段出现的先后顺序逐段分配按照程序段出现的先后顺序逐段分配按照程序段出现的先后顺序逐段分配按照程序段出现的先后顺序逐段分配1/222/153/184/176/105/23程序段程序段 区域区域1 1 021 0212 2 2236 22363 3 3754 37544 4 5571 55715 5 7294 72946 6 95104 95104共需要共需要105105个存储单元个存储单元程序段之间的调用关系程序段之间的调用关系程序段号程序段号/ /所需数据空间所
14、需数据空间能用更少的空间么？能用更少的空间么？筑刨红炎慰棺固民庐低掩溶色嘴救归兰瓮锥袖虎峪而丙箕渺掣铝旷之玄噶运行环境RunTimeEnvironments运行环境RunTimeEnvironments分层分配算法n n允许程序段之间的覆盖（覆盖可能性分析）允许程序段之间的覆盖（覆盖可能性分析）允许程序段之间的覆盖（覆盖可能性分析）允许程序段之间的覆盖（覆盖可能性分析）程序段程序段 区域区域6095022 4016323402173114162共需要共需要6363个存储单元个存储单元1/222/153/184/176/105/23思考：如何设计分配算法？思考：如何设计分配算法？7/807/80
15、惩辐獭叶既讽歪裸并泼丈石亚厂秽曰显厌潍杭垂绵厕肉粮察榴擂校醇造蛰运行环境RunTimeEnvironments运行环境RunTimeEnvironments静态存储分配无法克服的问题1n n动态数组问题动态数组问题n n层次单元法层次单元法层次单元法层次单元法n n层次单元层次单元层次单元层次单元n n标准单元的使用标准单元的使用标准单元的使用标准单元的使用孽安央蛀喂惯政潮掀桑泉样当渝包靠硷侗缮逸猾北孺天狰醚恩鼻波策远蛛运行环境RunTimeEnvironments运行环境RunTimeEnvironmentsP4嵌套式程序嵌套式程序嵌套式程序嵌套式程序program layerprogram
16、 layerprogram layerprogram layer int a,b,c int a,b,c int a,b,c int a,b,c procedure Sub1(x,y,z) procedure Sub1(x,y,z) procedure Sub1(x,y,z) procedure Sub1(x,y,z) int x,y,z int x,y,z int x,y,z int x,y,z procedure add(a,b) procedure add(a,b) procedure add(a,b) procedure add(a,b) real a,b real a,b real
17、a,b real a,b begin begin begin begin Real x,y,z Real x,y,z Real x,y,z Real x,y,z x=a x=a x=a x=a y=x*2+b y=x*2+b y=x*2+b y=x*2+b z=1/y z=1/y z=1/y z=1/y end end end end begin begin begin begin end end end end procedure Sub2(x,y) procedure Sub2(x,y) procedure Sub2(x,y) procedure Sub2(x,y) beginbeginb
18、eginbeginsub1(a1,a2,a3)sub1(a1,a2,a3)sub1(a1,a2,a3)sub1(a1,a2,a3)endendendendPP3P2P1begin real x,y,z x=a y=x*2+b z=1/y begin int a,b,c beginchar name,from,a end end Sub2(x,y)endS1S2P喻精仰怕拧臀策脚篓惜埋镀乡丛坎挺陡会口证慨之氛脚芜奉留迹嘻绩淆桌运行环境RunTimeEnvironments运行环境RunTimeEnvironments静态存储分配无法克服的问题2n n递归调用问题递归调用问题n n栈式存储分配栈式
19、存储分配栈式存储分配栈式存储分配横巾据榜寸死英阜厘袖昨然展丈霍骨囤酉挂矮世题羹靛通甩饭韭播荧套频运行环境RunTimeEnvironments运行环境RunTimeEnvironments栈（Stack）式存储分配n n用途用途n n过程的局部环境过程的局部环境过程的局部环境过程的局部环境n n活动记录活动记录活动记录活动记录n n特点特点n n嵌套调用次序嵌套调用次序嵌套调用次序嵌套调用次序n n先进后出先进后出先进后出先进后出n n生存期限于本次调用生存期限于本次调用生存期限于本次调用生存期限于本次调用n n自动释放自动释放自动释放自动释放运行栈运行栈暮逗靛绑提草个缠创说覆铬挂啦肾括蜗幅序
20、恰畴鞠稿栋做滋勇翱埠壁柬闺运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程数据区结构SPSPn nSPSPn-1n-1SPSP1 1SPSP0 0数组存储区数组存储区本本过过程程 所所辖辖分分 第第 临时工作单元临时工作单元程程 一一序序 层层 局部数组说明局部数组说明存存 分分储储 程程 局部变量局部变量区区 序序 分程序分程序TOP本过程本过程Display形式单元（形式单元（m+1个）个）连连 主调分程序主调分程序TOP接接 全局全局Display地址地址数数 返回地址返回地址据据 主调过程主调过程SP本过程本过程TOPSPSPSPn n为
21、第为第n n层过程数层过程数据区首址据区首址稽毅汰锤柔等唁诵抗膏憎溉抿釉妖坦耪付沂琉宴映肛每埔攻戎用嗡格怪儡运行环境RunTimeEnvironments运行环境RunTimeEnvironments静态存储分配无法克服的问题3n n被调用者的生存期超过调用者被调用者的生存期超过调用者/ /局部数据需局部数据需要保留（要保留（ save save ）n n堆式存储分配堆式存储分配堆式存储分配堆式存储分配最液耐束新驯薄铬菊谆娃升笋虑缸群挤噶潭歇咏父豌介箍冕乾涌刽寝案谭运行环境RunTimeEnvironments运行环境RunTimeEnvironments堆（Heap）式存储分配n n用于动态
22、数据结构用于动态数据结构n n存储空间的动态分配和释放存储空间的动态分配和释放存储空间的动态分配和释放存储空间的动态分配和释放n n实现方法：实现方法： n n将内存空间分为若干块，根据用户要求分配将内存空间分为若干块，根据用户要求分配将内存空间分为若干块，根据用户要求分配将内存空间分为若干块，根据用户要求分配n n无无无无法法法法满满满满足足足足时时时时，调调调调用用用用无无无无用用用用单单单单元元元元收收收收集集集集程程程程序序序序将将将将被被被被释释释释放的块收集起来重新分配放的块收集起来重新分配放的块收集起来重新分配放的块收集起来重新分配沃央向懂腕朗疗狐尼鄂橱顺觉达砂驰驱冒矣酌读浙怂语
23、哨悼稠碉愚留屠弥运行环境RunTimeEnvironments运行环境RunTimeEnvironments8.3 参数传递n n传值调用传值调用传值调用传值调用 call-by-value call-by-value call-by-value call-by-valuen n过程调用时计算实参过程调用时计算实参过程调用时计算实参过程调用时计算实参(Actual)(Actual)(Actual)(Actual)，将值存到活动记录，将值存到活动记录，将值存到活动记录，将值存到活动记录n n形参形参形参形参(Formal)(Formal)(Formal)(Formal)绑定于活动记录的实参域绑定
24、于活动记录的实参域绑定于活动记录的实参域绑定于活动记录的实参域调用者调用者被调用者被调用者直接使用直接使用A A实际参数实际参数A A形式参数形式参数X XA A的值的值单向传值单向传值想阉萤待涕顽贮悯盎袱辫抨堰淮唱身遗怎仁赵卯删财姻队犹邓扭骇榷婿淤运行环境RunTimeEnvironments运行环境RunTimeEnvironmentsn n引用调用引用调用 Call-by-Reference/Address Call-by-Reference/Addressn n如如如如果果果果实实实实在在在在参参参参数数数数具具具具有有有有左左左左值值值值，则则则则存存存存放放放放其其其其左左左左值值
25、值值到到到到活活活活动动动动记记记记录录录录中中中中；否否否否则则则则计计计计算算算算出出出出表表表表达达达达式式式式的的的的值值值值，将将将将此此此此值值值值存存存存入入入入一一一一个个个个单元，并将该单元的地址传给被调用者。单元，并将该单元的地址传给被调用者。单元，并将该单元的地址传给被调用者。单元，并将该单元的地址传给被调用者。调用者调用者被调用者间址访问实参被调用者间址访问实参A AA A实参实参A A形参形参X XA A的地址的地址传地址传地址跌幼藏徽睫捧档淌厦苍副似殷捎雁拓梗樊募艺箍次攒预景辽蚜葵瓜捅骤誊运行环境RunTimeEnvironments运行环境RunTimeEnvir
26、onments复制恢复 Copy-Restoren n将参数的左、右值同时传给被调用者，将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计算结果被调用者直接使用右值，并将计算结果按照左值返回给调用者按照左值返回给调用者调用者调用者被调用者被调用者A A实际参数实际参数A A形式参数形式参数X XA A的值的值传值传值/ /传地址传地址A A的地址的地址扎湿敝招男剪渤枚众愤壕王傻印漆认任躯阻祖郭粤毕豫靶妨匹矩哥骂束疹运行环境RunTimeEnvironments运行环境RunTimeEnvironments传名调用Call-by-Namen n将被调过程的过程体复制到调用处，并将被调
27、过程的过程体复制到调用处，并将每一个形参将每一个形参“文字地文字地”替换成实参替换成实参n n用换名子程序实现用换名子程序实现ThunkThunkn n是一种早期的语言是一种早期的语言ALGOLALGOL用的一种参数传用的一种参数传递方式递方式禹恢妊拱绕量科耶捡爪霉栽待味桨醇蔼炼咐老海瘫去讽涌念阵杰渔萝微阉运行环境RunTimeEnvironments运行环境RunTimeEnvironments上次课主要内容n n回填技术回填技术回填技术回填技术n nS S S S if C then if C then if C then if C then S S S S1 1 1 1 的翻译的翻译的翻
28、译的翻译C.true := newlabel;C.true := newlabel;C.true := newlabel;C.true := newlabel;S S S S1 1 1 1.next := S.next; .next := S.next; .next := S.next; .next := S.next; C.false:= S.next; C.false:= S.next; C.false:= S.next; C.false:= S.next; S.code := C.code S.code := C.code S.code := C.code S.code := C.cod
29、e |gen( C.true: ) |gen( C.true: ) |gen( C.true: ) |gen( C.true: ) |S|S|S|S1 1 1 1.code.code.code.codeC.codeS1.beginC.trueS.nextS1.codeC.false化技周拯料刑喷咋嚣舰始粳雾酵谊头富犹王夜坑克瞅钞锨秧薯稀铣女凰侈运行环境RunTimeEnvironments运行环境RunTimeEnvironments上次课主要内容n nS S S S if C then S if C then S if C then S if C then S1 1 1 1 else els
30、e else else S S S S2 2 2 2 的翻译的翻译的翻译的翻译C.true := newlabel; C.true := newlabel; C.false := newlabel; C.false := newlabel; S S1 1.next := S.next := S2 2.next := S.next;.next := S.next;S.code := C.code | gen( S.code := C.code | gen( C.true: )|C.true: )|S S1 1.code | gen( goto S.next ) .code | gen( goto
31、 S.next ) | |gen( C.false: ) | Sgen( C.false: ) | S2 2.code.codeC.codeS1.beginC.trueS.nextS1.codeC.falsegoto goto S.nextS.nextS S2 2.code.code握汗椅减畅全吁宾坛送征婆敏视句柱伶搜秋痪锄妥粪歹钝廓诬甜最宵须拿运行环境RunTimeEnvironments运行环境RunTimeEnvironments上次课主要内容n nS S S S while C do S while C do S while C do S while C do S1 1 1 1翻译翻译
32、翻译翻译S.begin := SS.begin := SS.begin := SS.begin := S1 1 1 1. . . .next next next next := := := := newlabel;newlabel;newlabel;newlabel;C.true := SC.true := SC.true := SC.true := S1 1 1 1.begin := .begin := .begin := .begin := newlabel;newlabel;newlabel;newlabel; C.false := S.next; C.false := S.next;
33、C.false := S.next; C.false := S.next; S.code := gen( S.begin: ) S.code := gen( S.begin: ) S.code := gen( S.begin: ) S.code := gen( S.begin: ) | C.code | C.code | C.code | C.code |gen( C.true: ) | gen( C.true: ) | gen( C.true: ) | gen( C.true: ) | S S S S1 1 1 1.code |.code |.code |.code | gen( gotoS
34、.begin )gen( gotoS.begin )gen( gotoS.begin )gen( gotoS.begin )C.codeS1.codegoto S.beginC.trueS1.beginC.falseS.nextS.begin脆税秆俭悦傀俘疙翔剧获俄别配步眉谅滦佐溯加非逛伞墅乏篱彻尿得渍匈运行环境RunTimeEnvironments运行环境RunTimeEnvironments上次课主要内容n运行环境运行环境n n绑定：静态、动态绑定：静态、动态n n静态分配静态分配n n动态分配动态分配n n层次单元法层次单元法层次单元法层次单元法n n栈式栈式栈式栈式(Stack)(St
35、ack)(Stack)(Stack)存储分配策略存储分配策略存储分配策略存储分配策略n n堆式堆式堆式堆式(Heap)(Heap)(Heap)(Heap)存储分配策略存储分配策略存储分配策略存储分配策略药骑赔叙虫羚书平芬博词愚怀碍芯输特暖俄命读粥伎孺硷端佩蒙个评酸遍运行环境RunTimeEnvironments运行环境RunTimeEnvironments上次课主要内容n n参数传递参数传递n n传值调用传值调用传值调用传值调用 call-by-value call-by-value call-by-value call-by-valuen n引用调用引用调用引用调用引用调用 Call-by-
36、Reference/Address Call-by-Reference/Address Call-by-Reference/Address Call-by-Reference/Addressn n复制恢复复制恢复复制恢复复制恢复 Copy-Restore Copy-Restore Copy-Restore Copy-Restoren n传名调用传名调用传名调用传名调用Call-by-NameCall-by-NameCall-by-NameCall-by-Name充报骨蹬波砧鲁晋枪宣党服唱崭寒煌即琴灰孽岁浪襄帧期蜕咬婶钮赚卖钓运行环境RunTimeEnvironments运行环境RunTimeE
37、nvironments子程序子程序P(X,Y,Z);Y:=Y+1; Z:=Z+X传值调用：传值调用：2传地址：传地址：X=T=5,Y=Z=A=2A:=A+1=2+1A:=A+T=3+58复制恢复：复制恢复：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=2+5=7Y A=3Z A=77换名换名A:=A+1=3A:=A+A+B=3+3+39主程序主程序A:=2; B:=3;P(A+B, A, A);Print A临时单元临时单元: T:A+B=5型鹿儒失硒宦襄该跌溯里榷倾哺拍领氏删讳鲤锗锁虾踌眼紫肝柠业琐嗜哪运行环境RunTimeEnvironments运行环境RunTimeEnviro
38、nments8.4 过程调用n n过程过程(procedure)(procedure)n n子程序子程序子程序子程序(subroutine)(subroutine)(subroutine)(subroutine)、函数、函数、函数、函数(function)(function)(function)(function)n n过程的定义与调用过程的定义与调用n n形参和实参的结合：参数计算与传递形参和实参的结合：参数计算与传递形参和实参的结合：参数计算与传递形参和实参的结合：参数计算与传递n n调用与返回调用与返回调用与返回调用与返回猛探臭橙硼体多辆群励况前纵搂毕芬稻辆齐帖抛琢祥斜厦黄百自佑计愧郡运
39、行环境RunTimeEnvironments运行环境RunTimeEnvironments工作方式n n调用方：当前环境的保存与恢复调用方：当前环境的保存与恢复n n被调方：构造环境，参数绑定被调方：构造环境，参数绑定Main( ) Sub1( 10 )Sub1( x ) Sub2( x + 1 )Sub2( y ) Sub3( )时丘宫晚攀快缘看一秽逢脑捡沥戮乓符腾符者认阎覆蔬但女豌洋胜拍虽蕉运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程调用实现n n简单过程调用简单过程调用n n实在参数的计算和保存实在参数的计算和保存实在参数的计算和保存实
40、在参数的计算和保存n n控制转移、返回地址的保存控制转移、返回地址的保存控制转移、返回地址的保存控制转移、返回地址的保存n n实在参数和形式参数的结合实在参数和形式参数的结合实在参数和形式参数的结合实在参数和形式参数的结合( ( ( (多种结合方式多种结合方式多种结合方式多种结合方式) ) ) )n n局部变量的处理局部变量的处理局部变量的处理局部变量的处理n n返回值的处理返回值的处理返回值的处理返回值的处理n n递归过程调用与过程参数递归过程调用与过程参数n n每层过程调用信息的保存与相应信息的查找每层过程调用信息的保存与相应信息的查找每层过程调用信息的保存与相应信息的查找每层过程调用信息
41、的保存与相应信息的查找则鳃拈蚌桔层争江疯勇吓舷搭织琳瞩囤柿卿睹篡汐森浙似辐腰裂铂厌旭秒运行环境RunTimeEnvironments运行环境RunTimeEnvironments活动记录中过程所用信息n n用于表达式的计算用于表达式的计算用于表达式的计算用于表达式的计算n n局部数据局部数据局部数据局部数据n n寄存器、程序计数器（返回地址）寄存器、程序计数器（返回地址）寄存器、程序计数器（返回地址）寄存器、程序计数器（返回地址）n n保存实在参数的值或地址保存实在参数的值或地址保存实在参数的值或地址保存实在参数的值或地址n n存放返回值存放返回值存放返回值存放返回值n n保存调用者活动记录地
42、址等保存调用者活动记录地址等保存调用者活动记录地址等保存调用者活动记录地址等(SP)(SP)(SP)(SP)n n用于存取嵌套外层过程中的非局部名用于存取嵌套外层过程中的非局部名用于存取嵌套外层过程中的非局部名用于存取嵌套外层过程中的非局部名(Display)(Display)(Display)(Display)访问链访问链控制链控制链返回值返回值实在参数实在参数机器状态机器状态局部变量局部变量临时变量临时变量石瓶弧仆妊喊轻妖痈拢茎潮懂禾犹品怠孪芹泪毅冀袒耘火凶克磊衬懂桐钳运行环境RunTimeEnvironments运行环境RunTimeEnvironments例子函数的活动记录int su
43、b( i, p )int sub( i, p )int i;int i;char *p;char *p; char buf32; char buf32; bufi = *(p + i); bufi = *(p + i); return i + 1; return i + 1; 临时变量临时变量: t1,t2,t3局部变量局部变量：buf32机器状态机器状态：R0, , R9, SP, PC, PS参数参数：i, p返回值返回值控制链控制链Display症必孤拦嘘忿烷卖隔罚庶厌丘来禄骤窗姐估恩猎乌鸿泳院震灾摸读酌沾显运行环境RunTimeEnvironments运行环境RunTimeEnviro
44、nments过程说明语句的翻译n n分析参数的类型、分配地址分析参数的类型、分配地址n n统计参数和返回值的空间需求统计参数和返回值的空间需求统计参数和返回值的空间需求统计参数和返回值的空间需求n n与调用语句配合完成形与调用语句配合完成形与调用语句配合完成形与调用语句配合完成形/ / / /实参数的结合实参数的结合实参数的结合实参数的结合n n符号表处理符号表处理n n完成过程名的属性登记完成过程名的属性登记完成过程名的属性登记完成过程名的属性登记说明语句说明语句： Procedure id(X1,X2,Xn)腥胖羚婶凸谦付李知徊将以柿捧借椎痛像妇盈丧崔酌硒瞻琉在枫啤渊告披运行环境RunTi
45、meEnvironments运行环境RunTimeEnvironments过程说明语句代码结构过程说明语句代码结构说明语句说明语句： Procedure id(X1,X2,Xn)代码结构代码结构X1.code 按参数传递要求实现参数按参数传递要求实现参数X X1 1的传递，或者完成传递准备的传递，或者完成传递准备；X2.code 按参数传递要求实现参数按参数传递要求实现参数X2X2的传递，或者完成传递准备的传递，或者完成传递准备；Xn.code 按参数传递要求实现参数按参数传递要求实现参数XnXn的传递，或者完成传递准备的传递，或者完成传递准备；完成动态存储分配相关的工作；完成动态存储分配相关
46、的工作；进入过程体进入过程体宦劲琳绒腑平撞坪琴职江江癌坏漓挣寞聚辩媚崎乳掺堂淋泌文犬钡傲号谷运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程调用语句的代码结构过程调用语句的代码结构过程调用语句过程调用语句id(Eid(E1 1,E,E2 2, , ,E ,En n) )E1.codea1:=E1.placeEn.codean:=En.place动态存储分配相关工作动态存储分配相关工作goto pc+n+1param a1param ancall id.place，n需要一个队列存放需要一个队列存放a a1 1, , a a2 2, , , a,
47、an n，以生成，以生成忿酗喧诡簇戎恼超诀祥祭惮欧琼萎幢糯瞧丑盼苦冒桅韧刁卓韧瘩泥钾旧阐运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程调用的实现n n1) 1) 1) 1) 在过程在过程在过程在过程 f f f f 中调用过程中调用过程中调用过程中调用过程 p p p p 时时时时n na. a. a. a. f f f f 对对对对实实实实在在在在参参参参数数数数求求求求值值值值，将将将将结结结结果果果果存存存存入入入入 p p p p 的活动记录参数域的活动记录参数域的活动记录参数域的活动记录参数域n nb. b. b. b. 在在在在 p
48、 p p p 的的的的活活活活动动动动记记记记录录录录中中中中存存存存放放放放返返返返回回回回地地地地址址址址和和和和当前栈顶指针当前栈顶指针当前栈顶指针当前栈顶指针n nc. c. c. c. 按按按按照照照照活活活活动动动动记记记记录录录录的的的的大大大大小小小小，上上上上移移移移栈栈栈栈顶顶顶顶指指指指针针针针n nd. d. d. d. 控制转到控制转到控制转到控制转到 p p p p 的入口（过程体）的入口（过程体）的入口（过程体）的入口（过程体）临时变量临时变量局部变量局部变量机器状态机器状态参数参数返回值返回值控制链控制链Display蒙苯纵毕拷拒邀就全黍惰痞充忧曲迭怯死翱盟严纸
49、赐痹硷锥未袖引腹宪匀运行环境RunTimeEnvironments运行环境RunTimeEnvironmentsn ne. p e. p e. p e. p 存放寄存器值和其它状态存放寄存器值和其它状态存放寄存器值和其它状态存放寄存器值和其它状态信息信息信息信息n nf. f. f. f. 执行过程体执行过程体执行过程体执行过程体n n2. 2. 从过程从过程 p p 返回：对应返回：对应returnreturn语句语句n na. p a. p a. p a. p 在返回值域中保存返回值在返回值域中保存返回值在返回值域中保存返回值在返回值域中保存返回值n nb. b. b. b. 恢恢恢恢复复
50、复复原原原原栈栈栈栈顶顶顶顶指指指指针针针针和和和和其其其其它它它它寄寄寄寄存存存存器器器器n nc. c. c. c. 按返回地址返回调用者按返回地址返回调用者按返回地址返回调用者按返回地址返回调用者临时变量临时变量局部变量局部变量机器状态机器状态参数参数返回值返回值控制链控制链Display镀苯虎录鹊编瞎折死崇尊钙望楼捶实窃点铃航酷扔番召必铺虐粱份瓶徘纺运行环境RunTimeEnvironments运行环境RunTimeEnvironments过程调用语句的制导翻译定义产生式产生式语义规则语义规则S call id ( Elist ) S.code := Elist.code |gen(g
51、oto pc+Elist.num+1)|for 队列队列q中的每一项中的每一项 t do gen(param t ) |gen(call id.place,Elist.num) Elist E Elist.num := 1; Elist.code := E.code | t:=newtemp; gen(t:= E.place)；建立队列建立队列q，并将并将t 放入放入qElist Elist1,E Elist.num := Elist 1.num+1; Elist.code := Elist 1.code | E.code | t:=newtemp; gen(t:= E.place);将将t
52、放入放入队列队列q祈撤捣符碴炯亨纲斌耙什是瘩澎儿吸姆琢扁蚂蕾块携跋利秽哭堂碘岛棠鞋运行环境RunTimeEnvironments运行环境RunTimeEnvironments生成的目标代码生成的目标代码生成的目标代码生成的目标代码t1 := 3 + at1 := 3 + agoto pc+3goto pc+3param t1param t1param 6param 6call f, 2call f, 2函数调用函数调用 f(3+a,6) f(3+a,6)的翻译的翻译芭希恬抢来处硝塞绚砍狮岂刨咐瞥长虾颓君现窥翰呸欠嘲吝鬃蛮续莫筛未运行环境RunTimeEnvironments运行环境RunTim
53、eEnvironments函数调用 f(b*c-1,x+y,x,y)的翻译t1:=b*ct1:=b*ct1:=b*ct1:=b*ct2:=t1-1t2:=t1-1t2:=t1-1t2:=t1-1t3:=x+yt3:=x+yt3:=x+yt3:=x+ygoto pc+5goto pc+5goto pc+5goto pc+5param t2param t2param t2param t2param t3param t3param t3param t3param xparam xparam xparam xparam yparam yparam yparam ycall f, 4call f, 4c
54、all f, 4call f, 4川阂恫球轨秀信俭饼蛊紊北徐鞘免债乏菜骏初浦敛虚瞪溶厕澳玲暴塘钳吭运行环境RunTimeEnvironments运行环境RunTimeEnvironments赋值语句x:=a+b+ f(b*c-1,x+y,x,y)的翻译t1:=a+bt1:=a+bt2:=b*ct2:=b*ct3:=t1-1t3:=t1-1t4:=x+yt4:=x+ygoto pc+5goto pc+5param t3param t3param t3param t3param t4param t4param t4param t4param xparam xparam xparam xparam
55、yparam yparam yparam ycall fcall fcall fcall f.place.place.place.place, 4 , 4 , 4 , 4 t5:=t1+f.valt5:=t1+f.valt5:=t1+f.valt5:=t1+f.valx:=t5x:=t5x:=t5x:=t5疫溺简谬恿写梆兢拾佯杉奠扰澜界记敷籍鼓寸旦芜品顺提嗜接宰配调虏十运行环境RunTimeEnvironments运行环境RunTimeEnvironments8.4 符号表管理n n种类种类n n关关键键字字表表、层层次次表表、符符号号表表（过过程程表表、变量表、标号表）、常数表变量表、标号表
56、）、常数表名字名字名字名字信息信息信息信息1 1 1 1信息信息信息信息n n n nsum1sum1sum1sum1Real Real Real Real 定义定义定义定义鼻艾亩霞波淘磐耗檀禽掺齿宙纫共机鳞僧刚讼幽靖衙播妈父娶伯侥蛾群柴运行环境RunTimeEnvironments运行环境RunTimeEnvironments关键字表n n表项结构表项结构n n关键字标识关键字标识关键字标识关键字标识 ( ( ( (整数整数整数整数) ) ) ) n n关键字名字关键字名字关键字名字关键字名字 ( ( ( (字符串，如字符串，如字符串，如字符串，如whilewhilewhilewhile，i
57、f)if)if)if)n n常用的操作：常用的操作：n nint IsKeyword( char Name )int IsKeyword( char Name )int IsKeyword( char Name )int IsKeyword( char Name )关键字名字关键字名字关键字名字关键字名字 关键字标识关键字标识关键字标识关键字标识beginbeginbeginbegin112112112112endendendend113113113113whilewhilewhilewhile114114114114乡歹勋懂农外念匈酥餐证救葡酗栗盂叫篓函嘎颧绦好尚圃长钢隅库铰豢蛙运行环境Ru
58、nTimeEnvironments运行环境RunTimeEnvironments层次表n n保保存存各各级级分分程程序序、循循环环语语句句、条条件件语句的有关信息语句的有关信息n n如：局部名字、转移标号等如：局部名字、转移标号等如：局部名字、转移标号等如：局部名字、转移标号等n n辅助实现标识符的管理辅助实现标识符的管理n n标识符的作用域标识符的作用域标识符的作用域标识符的作用域所在层所在层所在层所在层性质性质性质性质起点起点起点起点终点终点终点终点直接外层直接外层直接外层直接外层本层计数本层计数本层计数本层计数脯尽炬接锯姻拣挡医厚叙犁茹苏叙不僵化棕碉刚恃她猎暖摸搀忻疼哭碴脱运行环境Run
59、TimeEnvironments运行环境RunTimeEnvironments符号表n n保存名字及其属性保存名字及其属性保存名字及其属性保存名字及其属性n n名字：变量名，过程名，标号名和常数名名字：变量名，过程名，标号名和常数名名字：变量名，过程名，标号名和常数名名字：变量名，过程名，标号名和常数名n n属性：种类（属性：种类（属性：种类（属性：种类（KindKindKindKind），类型（），类型（），类型（），类型（TypeTypeTypeType），长度，作用），长度，作用），长度，作用），长度，作用域，标志（引用域，标志（引用域，标志（引用域，标志（引用/ / / /定义），地址
60、等定义），地址等定义），地址等定义），地址等n n种种种种类类类类：简简简简单单单单变变变变量量量量、数数数数组组组组、记记记记录录录录、结结结结构构构构、函函函函数数数数、常数、常量常数、常量常数、常量常数、常量n n类型：整、实、复、布尔、字符、指针、标号类型：整、实、复、布尔、字符、指针、标号类型：整、实、复、布尔、字符、指针、标号类型：整、实、复、布尔、字符、指针、标号名字名字名字名字种类种类种类种类类型类型类型类型长度长度长度长度地址地址地址地址标志标志标志标志韶贫掐犯渡筛遏草滑稗晶杆壶聊雇紊询营莱滓指雄怪讽奇绝围吨粳舟旗扳运行环境RunTimeEnvironments运行环境Run
61、TimeEnvironments符号表的作用n n作用作用n n记录源程序中出现的各种符号的相关属性，为记录源程序中出现的各种符号的相关属性，为记录源程序中出现的各种符号的相关属性，为记录源程序中出现的各种符号的相关属性，为编译提供相应的信息：地址、类型编译提供相应的信息：地址、类型编译提供相应的信息：地址、类型编译提供相应的信息：地址、类型n n建立表项建立表项n n以标识符为关键字以标识符为关键字以标识符为关键字以标识符为关键字实愧谤供堤霜官糕哇邢达疏准图鼓隘宫症侗雄幕芯睛奸雍喻孜穷妻扁根溢运行环境RunTimeEnvironments运行环境RunTimeEnvironments符号表的
62、实现n n实现方法：实现方法：n n线性表、散列表（线性表、散列表（线性表、散列表（线性表、散列表（HashHashHashHash）、二叉树）、二叉树）、二叉树）、二叉树n n特殊问题特殊问题n n结构成员、函数参数、分程序结构结构成员、函数参数、分程序结构结构成员、函数参数、分程序结构结构成员、函数参数、分程序结构n n性能性能n n优先考虑查找的效率优先考虑查找的效率优先考虑查找的效率优先考虑查找的效率掠椰纱耪谐钻甭亏作奎猫跺努孪惮乐力绎烦瘁屠挫蔫写韩朔鹏好慨茄韦棱运行环境RunTimeEnvironments运行环境RunTimeEnvironments思考题n n1 1 试分别给出下
63、列语句的三地址码，并希试分别给出下列语句的三地址码，并希望你能讲清楚是如何转换出来的。望你能讲清楚是如何转换出来的。n ncall sub(a+5,b*a,c)call sub(a+5,b*a,c)call sub(a+5,b*a,c)call sub(a+5,b*a,c)n na+fun(a+5,b*a,c)a+fun(a+5,b*a,c)a+fun(a+5,b*a,c)a+fun(a+5,b*a,c)n n2 2 什么叫静态绑定？什么叫动态绑定？变什么叫静态绑定？什么叫动态绑定？变量的绑定和过程的绑定有什么区别？量的绑定和过程的绑定有什么区别？n n3 3 程序的执行过程中如何进行存储分配？程序的执行过程中如何进行存储分配？何时为哪些数据目标分配存储空间？何时为哪些数据目标分配存储空间？先奎谜挽雁巩置戈几梗腊霸衔娄荣蔗郧蔼撅蹄旷筐涩竣枕沸衅悔礼贰脆犯运行环境RunTimeEnvironments运行环境RunTimeEnvironments
