3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间

Slides:



Advertisements
Similar presentations
1/67 美和科技大學 美和科技大學 社會工作系 社會工作系. 2/67 社工系基礎學程規劃 ( 四技 ) 一上一下二上二下三上 校訂必修校訂必修 英文 I 中文閱讀與寫作 I 計算機概論 I 體育 服務與學習教育 I 英文 II 中文閱讀與寫作 II 計算機概論 II 體育 服務與學習教育 II.
Advertisements

2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
§ 3 格林公式 · 曲线积分 与路线的无关性 在计算定积分时, 牛顿 - 莱布尼茨公式反映 了区间上的定积分与其端点上的原函数值之 间的联系 ; 本节中的格林公式则反映了平面 区域上的二重积分与其边界上的第二型曲线 积分之间的联系. 一、格林公式 二、曲线积分与路线的无关性.
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
聖若翰天主教小學 聖若翰天主教小學歡迎各位家長蒞臨 自行分配中一學位家長會 自行分配中一學位家長會.
地方自治團體之意義與組織 范文清 SS 2011.
「健康飲食在校園」運動 2008小學校長高峰會 講題:健康飲食政策個案分享 講者:啟基學校-莫鳳儀校長 日期:二零零八年五月六日(星期二)
清代章回小說----儒林外史 製作群:侑桂、品希、萱容、怡靜、佩涓、凸凸.
☆ 104學年度第1學期 活動藏寶圖 ☆ II III IV V 找到心方向-談壓力調適 陳佩雯諮商心理師
脊柱损伤固定搬运术 无锡市急救中心 林长春.
第一章 C语言概述 计算机公共教学部.
陶板屋 組員:陳婷 劉峻愷 趙崇佑 陳鵬如.
務要火熱服事主.
作业现场违章分析.
蒙福夫妻相处之道 经文:弗5:21-33.
Oracle数据库 Oracle 子程序.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
第9章 运行时的存储组织 重点:符号表的内容、组织,过程调用实现, 难点:参数传递,过程说明语句代码结构,
Using C++ The Weird Way Something about c++11 & OOP tricks
6.5滑坡 一、概述 1.什么是滑坡? 是斜坡的土体或岩体在重力作用下失去原有的稳定状态,沿着斜坡内某些滑动面(滑动带)作整体向下滑动的现象。
行政處分6 – 行政執行 范文清 SS 2011.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
编译原理与技术 运行环境 2018/11/24 《编译原理与技术》-运行环境.
第六章 运行时存储空间的组织和管理 术语 本章内容 讨论一个活动记录中的数据布局 程序执行过程中,所有活动记录的组织方式 过程的活动
6 下标变量的中间代码生成 下标:数组;变量: 下标变量:即数组分量: 简单变量:id,其地址可查到;
管理信息结构SMI.
辅导课程六.
第9章 符号表.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
本节内容 模拟线程切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
逆向工程-汇编语言
动态规划(Dynamic Programming)
3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间
第八章 运行时存储空间的组织与管理 目标程序运行时的存储结构 过程活动记录和运行时栈 变量访问环境 是CPU能直接寻址的存储空间.
语义分析概述 符号表 第六章 语义分析.
聖本篤堂 主日三分鐘 天主教教理重温 (94) (此簡報由聖本篤堂培育組製作).
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
$9 泛型基础.
运行时刻环境 (Runtime Environment)
习题课 编译原理与技术 计算机科学与技术学院 李诚.
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第九章 运行时存储空间组织 网上教学系统: : 编译原理
本节内容 结构体 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
College of Computer Science & Technology
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
第7章 模板 陈哲 副教授 南京航空航天大学 计算机科学与技术学院.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 Windows线程切换_时钟中断切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
基督是更美的祭物 希伯來書 9:1-10:18.
明愛屯門馬登基金中學 中國語文及文化科 下一頁.
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
陳維魁 博士 儒林圖書公司 第六章 領域與範圍 陳維魁 博士 儒林圖書公司.
圣经概論 09.
编译原理实践 6.程序设计语言PL/0.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

3 变量访问环境 临时变量区 变量访问环境 机器状态 返回值 Size InitOff 过程层数 top 堆区空间 栈区空间 静态区空间 3 变量访问环境 局部变量区 临时变量区 形参变量区 变量访问环境 过程层数 动态链指针 sp 返回地址 top 机器状态 返回值 Size 库代码空间 目标代码空间 静态区空间 堆区空间 栈区空间 高地址 低地址 InitOff

3.1 变量访问环境概述 声明链:声明链是过程名的序列,序列的头是主程序名M。具体定义如下: (M)是过程声明链; 3.1 变量访问环境概述 声明链:声明链是过程名的序列,序列的头是主程序名M。具体定义如下: (M)是过程声明链; 若(M,…,P)是声明链,且P中有过程Q的声明,则(M,…,P,Q)也是过程声明链。 用DeclareChain(Q)= (M,…,P,Q)表示声明链。 若Q的层数为N,则其声明链的长度为N+1; 对于任一过程Q,它的声明链是唯一的,并且在Q中出现的变量,其声明一定在DeclareChain(Q)中的过程内。

活跃活动记录 一个过程S在动态链中可有多个AR,但其中只有最新AR(S )是可访问的,称此AR(S)为S的活跃活动记录,并记为LiveAR(S),简写为LAR(S)。 例:假设有当前调用链是(M, P1, P2, Q1, R1, R2, R3 ) 则当前动态链为: [AR(M),AR(P1),AR(P2),AR(Q1),AR(R1),AR(R2),AR(R3)] 活跃活动记录LAR为: LAR( M ) = AR(M) LAR( P ) = AR(P2) LAR( Q ) = AR(Q1) LAR( R ) = AR(R3)

声明链和变量访问环境 (当前)变量访问环境:Q的声明链中的每个过程的活跃活动记录构成的链称为Q的变量访问环境,记为: VarVisitEnv(LAR(Q)) = [LAR(M), … , LAR(P), LAR(Q)] 例:(M,P,Q,R)为R的声明链,假设有当前调用链是(M,P1,P2,Q1,R1,R2,R3 ) 则当前动态链为: [AR(M),AR(P1),AR(P2),AR(Q1),AR(R1),AR(R2),AR(R3)] R3的当前变量访问环境: VarVisitEnv(LAR(R) =[AR(M), AR(P2),AR(Q1),AR(R3)]

非局部变量访问的实现 假设Q的变量访问环境: VarVisitEnv(LAR(Q)) = [LAR(M),…,LAR(P),LAR(Q)] 在Q中有变量XQ,YM,ZP,它们分别定义在过程Q、M和P中,则它们的存储单元地址可表示如下(其中<LAR(Q)>表示LAR(Q)的始地址,其它类似): addr( XQ )= <LAR(Q)> + OffsetX addr( YM )= <LAR(M)> + OffsetY addr ( ZP )= <LAR(P)> + Offsez 结论: 对于每个AR,只要知道了它的变量访问环境VarVisitEnv(AR),即可实现包括非局部变量在内的所有变量的访问。

如何计算当前过程的变量访问环境 PROC P; PROC Q; DeclaChain(P)= (M,P1, P2,…,PN-2,PN-1) 情况2 PROC Q; Begin … end … … PROC P; Q End 情况1 情况3 情况4 PROC P; … … Begin P End PROC P; … … PROC Q Begin End Begin Q End PROC Q; … … PROC P; Begin Q End Begin End 情况1: P调用P : P层数等于P层数N. 情况3: P调用Q ,P层数(N-1)小于Q层数(N). DeclaChain(P)= (M,P1, P2,…,PN-2,PN-1) DeclaChain(Q)=(M,P1, P2,…,PN-2, PN-1 , Q) 情况4:P调用Q,P层数大于Q层数(N). DeclaChain(P)= (M,P1, P2,…,PN-1,Q,…,P) DeclaChain(Q)=(M,P1, P2,…,PN-1, Q) 情况2: P调用Q,P层数等于Q层数N. DeclaChain(P)= (M,P1, P2,…,PN-1,P) DeclaChain(Q)=( M,P1, P2,…,PN-1,Q)

如何计算当前过程的变量访问环境 定理: 设[AR(M),…,AR(P),AR(Q)]DynamicChain(Q),且Q 的层数为N,则有: VarVisitEnv(AR(Q)) =VarVisitEnv(AR(P))N AR(Q) 结论:变量访问环境可由先行过程的变量访问环境求得。

变量访问环境的实现方法 Display表方法 局部表法 全局表法 静态链方法

3.2 局部Display表方法 Display表:如果层数为N的过程P, 其AR(P)的变量访问环境为: VarVisitEnv(AR(P))=[AR0,…,ARN], ari表示ARi的始地址,则称: [ar0,…,arN] 为AR(P)的Display表,其长度为N+1。 局部化Display表方法:对于每个AR求出其变量访问环境,并把它以地址表的形式(Display表)保存在AR中。因为每个AR都自带Display表,称这种方法为局部化Display表方法。

Display表的求法 NewAR.Display= CurrentAR.Display的前Nnewsp; … … [ar0,ar1,…,arN-1,newsp] Display表 … … newsp 动态链指针 sp … … Display表 [ar0,ar1,…,arN-1,…] … … sp 动态链指针

局部Display表时变量的访问 绝对地址=CurrentAR.Display[静态层数]+ 相对地址 对一个变量X(L, off),地址为: addr(X)=CurrentAR.Display[L]+ off 可用下面两条变址指令获得X的值: LOAD R1,(InitOff+L)[sp] LOAD R2, Off[R1]

例1:有过程M,Q,R,S,其中level(M)=0;level(Q)=1;level(R)=1;level(S)= 2, 并且CallChain(S)= (M,Q,R,S)。 假设当前过程S有变量XS、YR和ZM,其中下标名表示变量被定义的过程名 则上述三个变量的地址分别如下: addr( XS ) = sp + offsetx= (sp + InitOff)[2] + offsetx addr( YR ) = (sp + InitOff)[1] + offsety addr( ZM ) = (sp + InitOff)[ 0 ] + offsetz (2, offsetx) (1, offsety) (0, offsetz) AR(S) AR(Q) ..... ar1 AR(R) AR(M) ar0 ..... X单元 Z单元 Y单元 ar0 ar1 ar0 ar2 ar0 ..... sp ar0 ar2 Display表 nil ar2 ..... InitOff sp

3.3 全局Display表 当层数为j的过程Q被调用时: 当退出Q时:恢复原来D[j]的内容: 将旧的D[j]的内容保存到NewAR(Q)中: NewAR(Q).ResumeAddr = D[j]; 改写D[j]的内容:D[j]=NewAR(Q)的地址; 当退出Q时:恢复原来D[j]的内容: D[j] = CurrentAR.ResumeAddr 局部变量X(L,off,indir/dir)的访问 X的地址: addr(X)= D[L]+off

    过程P1 过程 Q2 过程 R2 过程 S3 过程 T3 …… Z(3,offz) ars arT 全局Display proc P;(设P层数为1) proc Q; (Q层数为2) begin R end proc R; (R层数为2) proc S;(S层数为3) begin T end proc T; (T层数为3) begin X(1,offx) … Y(2,offy) … Z(3,offz)… end begin S end begin Q end Z(3,offz) ………………………… ars AR(T) 动态链(控制链)指针 arT ←sp ………………………… 全局Display AR(S) …… 动态链(控制链)指针 arS Y(2,offy) ………………………… arQ AR(R) 动态链(控制链)指针 arR ………………………… arT arS D(3) AR(Q) 动态链(控制链)指针 arR arQ arQ D(2) X(1,offx) ………………………… AR(P) arP D(1) 动态链(控制链)指针 arp D(0)

    主程序P 过程 Q 过程 R 过程 S 过程 T …… proc P;(设P层数为1) proc Q; Q层数为2 begin R end proc R; R层数为2 proc S; S层数为3 begin T end proc T; T层数为3 begin … end begin S end begin Q end ………………………… ars AR(T) 动态链(控制链)指针 arT ………………………… 全局Display表 AR(S) …… 动态链(控制链)指针 arS ………………………… arQ AR(R) 动态链(控制链)指针 arR ………………………… arT arS D(3) AR(Q) 动态链(控制链)指针 arQ arR arQ D(2) ………………………… AR(P) arP D(1) arp D(0)

3.3 静态链的方法 原Display表部分变成一个单元,称为静态链单元,存放静态链指针,指向直接外层的最新活动记录的始地址。这就使得运行时栈上的活动记录之间又拉出一条链,称为静态链。

Level(M)=0, Level(G)=1, Level(H)=2,Level(R)=3,Level(S)=3 AR0(M) AR1(G) AR2(H) AR3(R) AR4(S) nil sp nil ar0 ar1 ar2 ar3 ar4 AR0(M).Display =[ ar0 ] AR1(G).Display =[ ar0, ar1 ] AR2(H).Display =[ ar0, ar1 , ar2 ] AR3(R).Display =[ ar0, ar1, ar2, ar3] AR4(S).Display =[ ar0, ar1, ar2, ar4] 虚线为静态链指针 实线为动态链指针

其中Indir(sp,k)表示sp的k次间接内容。 静态链指针的确定 Level(M)=0, Level(G)=1, Level(H)=2,Level(R)=3,Level(S)=3 CurrentAR NewAR AR0(M) AR1(G) AR2(H) AR3(R) AR4(S) nil sp nil ar0 ar1 ar2 ar4 ar3 若 k= CurrentAR.level+1-NewAR.level ,则 NewAR.StaticChainPointer=Indir(sp,k) 其中Indir(sp,k)表示sp的k次间接内容。

K= CurrentAR.level-LX addr(X)= Indir(sp,k)+OffSetx 使用静态链时变量的访问 CurrentAR(P) ……. sp Indir(sp,k) 局部变量X(LX, OffSetx)的访问 X的地址: K= CurrentAR.level-LX addr(X)= Indir(sp,k)+OffSetx

总结 Display表方法是用表结构表示变量访问环境。 局部Display表的产生需要花时间,但返回时不需要为恢复变量访问环境做任何事情。

总结 静态链方法是用链表表示变量访问环境 静态链方法实际上是一种共享化的局部Display表方法。其主要优点同全局Display表方法是能节省存储单元。产生需要花时间,但返回时不需要为恢复变量访问环境做任何事情。 具体采用哪种方法,取决于机器条件:如果寄存器较少,则使用Display表方法可能合适些;如果机器能提供较好的间接操作,则可选用静态链方法。

4 地址分配原则回顾 值引用的形参按照类型大小分配 地址引用的形参分配1 局部变量按照类型长度分配 临时变量分配1 函数和过程作为形参分2,其中1个是实参的入口地址,另一个是先行的display表地址 分配原则,对于值引用的形参,我们还是按照类型的长度分,~~ 地址引用的给她分配1个 都是要存实参的地址,不管实参是什么(都解释) 局部变量的分配就是按照类型的长度来分,临时变量我们一般分1个,特别说明以函数或者过程作为形参,我们一般分配两个单元,一个是实参的入口地址,另外一个是先行的display表的地址,后面我们要讲嵌套型语言进行地址计算的时候要用。 看一个例子()这些我们前面都讲过,现在看看例子来回忆一遍。复习

抽象地址的变化规律 I.处理声明部分: 处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址 处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址 (ℓ,off)  LabelDec  (ℓ,off) (ℓ,off)  ConstDec  (ℓ,off) (ℓ,off)  TypeDec  (ℓ,off) (ℓ,off)  Var id:T  (ℓ,off+nT) (ℓ,off)  ProcDec  (ℓ,off) (ℓ,off)  FuncDec  (ℓ,off)

(ℓ,off)  Proc p()  (ℓ+1,off1) (ℓ,off)  Func f():T  (ℓ+1,off1) II.处理完函数首部: 处理前可用的 处理内容 处理后可用的 抽象地址 抽象地址 (ℓ,off)  Proc p()  (ℓ+1,off1) (ℓ,off)  Func f():T  (ℓ+1,off1) (ℓ,off)  Proc P()  (ℓ,off+2)(形式过程) (ℓ,off)  Func F():T  (ℓ,off+2)(形式函数) 注:小写字母的标识符表示实在标识符,大写字母的标识符则表示形参标识符。nT 表示类型T的长度,off1表示处理完形参部分(实在过程首部)时的偏移值。

(ℓ,off) Var ID:T (ℓ,off+1)C语言:T *ID III. 处理形式参数: (ℓ,off) Var ID:T (ℓ,off+1)C语言:T *ID (ℓ,off) ID:T (ℓ, off+ nT ) C语言:T ID IV.处理过程名及左括号之后: (ℓ,off) Proc p( (ℓ+1,d) (ℓ,off) Func f( (ℓ+1,d) (ℓ,off) Proc P( (ℓ+1,d) (ℓ,off) Fucn F( (ℓ+1,d) 注:小写字母的标识符表示实在标识符,大写字母的标识符则表示形参标识符。nT 表示类型T的长度,off1表示处理完形参部分(实在过程首部)时的偏移值, d为第一个形参的可用区距。

抽象地址分配的实例: (ℓ,10)Label 100,200; (ℓ,10) Const pai=3.14; Type arr=array[1..10]of integer; Var x:integer; (ℓ,11) a:array[1..5]of integer; (ℓ,16) Function f( (ℓ+1,d) Var x:real; (ℓ+1,d+1) a:arr; (ℓ+1,d+11) Var c:arr; (ℓ+1,d+12) Procedure G(); (ℓ+1,d+14 ) Function F():real (ℓ+1, d+16 ) ):real; (ℓ+1, d+16 =off1) Begin ……end;

习题:假设当前层数为L,可用偏移为off0,试写出各个程序点的层数和偏移的变化情况。(d为第一个形参的可用区距) ①typedef at = int a[10][10]; typedef bt = struct {int number; at score;}; ②at x,y; ③int f (at a, ④at* b, ⑤float x) { ⑥bt m; ⑦int n; ………… }⑧ void g() {⑨ int l; ………… } (ℓ,off0 ) (ℓ,off0 ) (ℓ,off0+200 ) (ℓ+1,d+100 ) (ℓ+1,d+101 ) (ℓ+1,d+103 ) (ℓ+1,d+204) (ℓ,off0+200 ) (ℓ+1,d) (ℓ,off0+200 )

例子 内存 fac A R 临时变量 #define n 5 int sum = 0; int fac(int i) { if i=0 return 1; if i<0 return -1; return (i*fac(i-1)); } void main () { sum = fac(n); i: 4 gp sp …… fac A R 临时变 量 i: 5 gp …… main A R 临时变 量 gp …… sum : 0 gp Code area (代码区) pc 内存