最新编译原理-第9章分析课件PPT.ppt 40页

'编译原理-第9章分析 第九章　运行时存储空间组织9.1目标程序运行时的活动（略）9.2运行时存储器的划分9.3静态存储分配（略）9.4简单的栈式存储分配9.5嵌套过程语言的栈式实现9.6堆式动态存储分配 9.2运行时存储器的划分一、运行时存储器的划分1.编译器需要在存储区保护的对象（1）目标代码编译时可确定，故可放在一个静态确定的区域（2）数据对象部分数据对象的大小在编译时可确定，故也可放在一个静态确定的区域（3）跟踪过程活动的控制栈目标代码静态数据栈↓↑堆 9.2运行时存储器的划分三、存储分配策略1.静态存储分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。2.栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。3.堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆. 9.4简单的栈式存储分配1.前提：假设程序语言无分程序结构，过程定义不允许嵌套，但允许过程的递归调用。例如：C语言2.过程：运行时每当进入一个过程——即一个新的活动开始，就把其它活动记录压入栈（置于栈顶），从而形成过程工作时的数据区.当活动结束——即过程退出时，再把其活动记录弹出栈，这样，它在栈顶上的数据区也随即不复存在. 3.举例（1）主程序调用过程Q，而Q又调用R，在R进入运行后的存储结构.9.4简单的栈式存储分配R的活动记录Q的活动记录Main的活动记录全局数据SPTOP静态分配 3.举例（2）主程序调用过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构.9.4简单的栈式存储分配Q2的活动记录Q1的活动记录Main的活动记录全局数据 9.4简单的栈式存储分配3.举例（3）主程序先调用过程Q，然后主程序调用R，且过程Q不调用Q和R.R的活动记录Main的活动记录全局数据 4.指示器SP——总是指向现行过程活动记录的起点，用于访问局部数据.指示器TOP——始终指向（已占用）栈顶单元.9.4简单的栈式存储分配 一、C的活动记录1.C的活动记录的项目（1）连接数据——A.老SP值:即前一活动记录的地址B.返回地址（2）参数个数（3）形式单元——存放实在参数的值或地址（4）过程的局部变量——数组内情向量——临时工作单元临时工作单元内情向量简单变量形式单元参数个数返回地址老SPTOPSP9.4简单的栈式存储分配 2.（1）不允许过程嵌套——非局部量仅能出现在源程序头，可采用静态存储分配，编译时可确定其地址（2）局部变量或形参在活动记录中的位置确定即对它们都分配了存储单元，其地址是相对于活动记录的基地址SP的绝对地址=活动记录基地址+相对地址变址访问X[SP]X——代表相对数，即相对于活动记录起点的地址，编译时可完全确定下来.9.4简单的栈式存储分配 二、C的过程调用,过程进入、数组空间分配和过程返回已知过程调用的四元式序列为：parT1…parTncallP,n9.4简单的栈式存储分配 C语言过程调用与返回ParTi(i+3)[TOP]:=Ti（传值）或(i+3)[TOP]:=addr(Ti)（传地址）CallP,n1[TOP]:=SP3[TOP]:=nJSRP(转P)SP:=TOP+11[SP]:=返回地址TOP:=TOP+活动单元数Return(E)TOP:=SP－1SP:=0[SP]X:=2[TOP]UJ0[x]/*UJ:无条件转移*/ 9.5嵌套过程语言的栈式实现前提：假定允许过程定义嵌套，如Pascal语言，但去掉Pascal中的“文件。程序举例：——课本P258图9.15 一、非局部名字的访问的实现9.5嵌套过程语言的栈式实现1.静态链和活动记录A.静态链——活动记录的一个域，从一个过程的当前活动记录指向其静态直接外层的最新活动记录。动态链——活动记录一个域，从一个过程的当前活动记录指向调用该过程前正在运行的过程的最新的活动记录的基地址。B.活动记录结构——P259图9.16C.程序运行时栈的变化过程——举例： ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址0ic0(形参个数)0返回地址0xa0返回地址0过程S中调用Q时161514131211109876543210SPTOPTOPSP109876543210过程P中调用S时 dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址0TOPSP1211109876543210242322212019181716151413过程Q中调用R时 dcvu211返回地址17dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP过程R中递归调用R 静态链:通过其值可以找到当前过程/活动可以引用的“非局部变量”的过程的活动记录的基址，从而找到要引用的“非局部变量”。9.5嵌套过程语言的栈式实现动态链:通过其值可以找到当前过程/活动结束后，需要返回的上一层活动记录的基址SP。D.含义： 2.嵌套层次显示表（display）和活动记录2R的现行活动记录地址（SP的现行值）1Q的最新活动记录的地址0P的活动记里的地址9.5嵌套过程语言的栈式实现A.嵌套层次显示表：每进入一个过程后，在建立它的活动区的同时建立该表。B.表的内容：举例：令过程R的外层为Q，Q的外层为P，则R运行时display表为： C.“非局部量”地址的确定：绝对地址=display[静态层数]+相对地址D.活动记录结构:P261图9.18E.程序运行时栈的变化过程—P262-263图9.19TOPa321SP0临时单元内情向量简单变量display形参单元参数个数全局Display返回地址老SP(动态链)9.5嵌套过程语言的栈式实现 9.5嵌套过程语言的栈式实现F.静态链方法与显示表方法的比较：通过显示表访问非局部量要比沿着静态链访问非局部量的速度快。原因：因为通过显示表的一个域，可以确定任意外层活动记录的指针，再沿着这个指针便可以找到处于外层活动记录的非局部量。 9.5嵌套过程语言的栈式实现1.parTT——为数组（1）或者传递数组T的首地址（2）或者传递数组T的内情向量地址2.ParTT——为过程假设：过程P把过程T作为在世在参数传递过程Q，随后，Q又通过引用相应的形式参数调用T。3.ParTT——为标号二.参数传递的实现 ⇒在进入T之后，为了建立T自己的display，T必须知道它直接外层的display。又P的display或者正好就是这个外层的display，或者包含了这个外层display而由于T的层数是已知的⇒只要知道P的display，T就可以用它来建立自己的display。即假定T的层数为1，则T的display乃是由P的display的前1个单元的内容和SP的现行值所组成。⇒为了使得过程T工作时能够知道过程P的display，必须在P把T作为实参传递给Q的时候把P自身的display地址也传过去。即：过程P中的parT的作用可刻画为建立如下所示的两个相继临时单元：第一个临时单元B1：过程T的入口地址；第二个临时单元B2：现行的display地址。；然后执行（i+1）[TOP]:=addr(B1)把第一临时单元B1的地址传给Q9.5嵌套过程语言的栈式实现2.ParTT——为过程 假定过程Q现在执行到调用语句callZ,mZ—形式参数，形式单元Z中已含有上述B1的地址⇒故B1的内容将用来作为转子指令的目的地址（即转进过程T）B2的内容将作为“全局display地址”（第三项连接数据）传送给T9.5嵌套过程语言的栈式实现2.ParTT——为过程 9.6堆式动态存储分配1.堆式动态存储分配使用的情况（1）允许用户自由地申请数据空间和退还空间（2）不仅有过程而且有进程的程序结构即空间的使用未必服从“先请后还，后请先还”的原则例如：Pascal语言中的标准过程new-dispose2.该种分配方法必须考虑的几个主要问题（1）当运行程序要求一块体积为N的空间时，应该分配哪一块给它？（2）如果运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N，那该怎么办？ 一、堆式动态存储分配的实现1.定长块管理（1）实现方法：（2）优点：占用占用占用空闲空闲空闲占用空闲占用空闲空闲空闲availableavailable9.6堆式动态存储分配 2.变长块管理（1）实现方法（2）实现的非配策略A.首次满足法B.最有满足法C.最差满足法（3）3种分配策略的比较A.适用情况B.时间比较9.6堆式动态存储分配 二、隐式存储回收1.隐式存储回收的要求：用户程序和支持运行的回收子程序并行工作.原因:回收子程序需要知道分配给用户程序的存储块何时不再使用.2.存储块格式：块长度访问计数标记指针用户使用空间9.6堆式动态存储分配 3.回收过程（1）标记阶段：对已分配的块跟踪程序中各指针的访问路径，若某个块被访问过，则给该块加一个标记。（2）回收阶段：所有未加标记的存储块回收到一起，并插入空闲块链表中，然后消除在存储块中所加的全部标记。9.6堆式动态存储分配4.优缺点优点：防止死块产生。缺点：开销随空闲块的减少而增加。 第十八章信息服务贸易 18.1　信息资源、信息产业和信息调整公路18.1.1　信息资源的特点及其在新技术环境下的变化信息资源的特征和性质：它的存在具有普遍性；信息资源在时空中是可以转移和变换的；信息资源具有动态性和时效性；信息资源可以转化；信息资源具有主导性。 18.1.2　信息产业的经济特征、地位及其发展趋势信息产业的经济特征服务贸易性；外部经济性；统一兼容性；社会公益性；自然垄断性；强时效性；共享性；边际成本递减性；边际效用递增；交易不可逆性；价值不确定性；价格不敏感性。 信息产业在国民经济中的地位与作用信息作为商品越来越成为经济中重要的基础性资源；信息产业推进了国民经济信息化的进程；世界上依赖信息产业从事生产、贸易以及其他活动的人数已达空前的规模；信息产业是未来经济中具有潜在贸易利益的产业。 18.2　信息服务贸易及其对经济竞争力的影响18.2.1　信息服务贸易的定义范畴在A类信息服务交易中，信息服务提供者与消费者都不移动。包含两类具体的贸易形式：借助互联网络或电讯网络等进行的远距离信息服务贸易；信息服务消费者与服务提供者物理分离而借助物质载体参与国际贸易；ACBD信息服务消费者不移动　　　移动不移动移动信息服务提供者 在B类信息服务贸易中，信息服务提供者不移动而依靠消费者移动完成服务交易。在C类信息服务贸易中，信息服务提供者移动而消费者不移动。在D类信息服务贸易中，信息服务提供者和消费者双方都移动。18.2.2　信息服务贸易对经济竞争力的影响信息技术（和高技术）要素信息服务贸易促使厂商及时采取各种最新信息技术，以获得成本优势和产品差异而提高竞争力。 信息资源要素与自身开发信息资源相比，信息服务贸易使厂商获得相对低成本的信息资源而取得竞争优势。信息管理要素服务要素给外向型厂商提供了低成本参与国际竞争的外部信息条件，提高了本国厂商的国际竞争力。信息资本（投资）要素信息产品要素'