研究生课程_程序语言设计原理教程_第04章.ppt

第4章 存 储,存储对象是程序对象在计算机中的实现 程序对象不一一对应为存储对象 x:=0; x,0是两程序对象 只有一个存储对象x加指令清零 初值常量也不作为单独存储对象,4.1 程序变量的时空特性,4.1.1 引用和指针,计算对象有地址非固定地址, 因时而变, 相对地址 虚存空间,P指针是地址变量 *P是P所指的内容, 也有左值和右值 *P左值是P所指地址值，即P的值 *P右值是所指地址内的内容值,引用是常指针是变量的别名, 但实现是不一样的,4.1.2 递引用 dereference,通过指针变量引用变量的值为递引用 *P1右值即递引用 有些语言显式递引用算符如FORTH的,1 13 VARIABLE xx (声明变量xx并赋初值13) 2 0 VARIABLE Y (声明变量Y并赋初值0) 3 xx 2 * Y ! (相当于Y=xx*2) 如果只写xx 2 * 则为将xx的地址乘以2放在Y之中,4.1.3 变量的时态,分配/未分配/除分配 分配: 为程序对象创建存储对象 编译时分配叫静态分配 allocate 运行时分配叫动态分配如声明指针p, 执new才分配 未分配: 声明了未分配运行时分配 除分配: 取消存储对象(程序对象) delete操作显式 自动除配: 无用单元收集Garbage collection 动态语言有，静态可有Ada可没有C,续,4,3,?,?,a b c d e f,声明和定义：定义必然声明；反之不然 声明的两个作用 ：给出对象, 该对象的时间有效性 出了声明的作用域该对象失去定义。在声明的作用 域内显式删除也失去定义,定义/未定义/失去定义 只要分配存储对象必然有残值, 无意义即未定义 赋值或初值变量得以定义,a,b:分配且有定义 c,d:分配未定义或失去定义 e,f:未分配或除配,4.2 存储模型,基元类型值 仅除数组 记录、构造、表 不可更新其中一元素 函数抽象, ML重过程 变量引用,可存储值Storable：指最小的可直接访问的可存储单元中的值 Pascal可存储值:集合不选择更新某一元素是可存储值，Pascal, C ，Ada数组可选择更新, 不是可存储值。 引用非可存储(C+可存储), 过程和函数名也非可存储 ML几乎都是可存储值, 也带来毛病：每次更新结构数据都要重来。它们是：,( if exp then sin else cos ) (x) 得sin(x)cos(x),可存储值,4.2.1存储对象的生存期,全局变量 和引用程序寿命一样长 局部变量 和程序中的一个模块寿命一样长 持久变量 比程序寿命长除非显式撤销 文件变量 瞬间变量（transient)持久变量的逆,每个存储对象都有创建(生), 可用(活着)，撤销(死)的生命期。按生命期长短分：,4.2.2 静态存储对象,编译时分配存储对象, 近代语言类属对象直到装入后确立(elaboration)之时才定下存储对象叫静态分配 一旦执行不再改动其存储，直至所在存储单元无效叫静态(Static)存储对象 全局变量均为隐式的静态对象, COBOL,BASIC全 静态，ALGOL，C是显示声明静态，Pascal除全局，Ada 不能。 C语言的静态变量是既私有又不随所在声明块中消逝, 全局于所在文件。auto是静态分配动态装入不叫静态对象。Extern是静态对象。,extern,static,auto,4.2.3动态存储对象,把寿命特长的（如文件，全局量）排出来归到栈底的某一组，把寿命特 短的（如循环控制变量）另立嵌套组，这个问题也就解决。,块5,块66,块1,块2,块3,块4,5,4,6,6,5,4,6,寿 命,4.2.4 动态存储对象,二叉树其大小由输入值定在运行中确立。内存开辟堆（heap)随生成随堆放动态存储对象。指针（即堆变量）所指程序对象用堆存放,问题：多次重分，内存成了小洞 解决办法：按寿命分组寿命最长的放在较低（按其所在块生命期）。,重复使用,无法再分,4.2.5 堆栈帧管理,由动态堆栈联想到一般嵌套式语言可按动态堆栈式管理, 多数变量和所在块寿命一样长(语言称之为自动变量),动态堆栈式存储 按程序动态执行, 以动态堆栈管理局部数据和动态生成数据 运行时堆栈Run-time stack其底压入程序代码和全局，静态量。每执行到调用时生成一个堆栈帧(frame)记录该块数据信息, 每当返回则局部量自动撤销对于递归块的局部量可多次生成多次消除。 动态链描述调用父辈地址, 返回地址是继续执行的下一地址。 静态链描述词法父辈lexical parent块地址, 按该块复制局部变量。,参数,返回地址,动态链,静态链,返回值,局部变量,程序代码 全局静态存储,首先调用块 堆栈帧,第二调用块 堆栈帧,最新调用块 堆栈帧,临时变量空间,栈顶,堆栈帧组织,运行时堆栈,续,调 用 块 首 地 址,本 帧 词 法 父 辈,举例 求整数连乘积之递归程序: function product (jj： Integer)： Integer； var kk： Integer; begin if jj = 0 then product:=1 else begin readln (kk)； product:=kk * product(jj-1) end end；,Product函数 目标代码,jj:2 return :? kk:25,jj:1 return :? kk:7,jj:0 return :? kk:?,临时存储,DL,SL:静态链,DL:静态链,最初调用时堆栈帧,第一次调用时堆栈帧,第一次调用时堆栈帧,栈顶,SL,4.2.6 动态堆存储,忽略死对象 不超过一页浪费, 若寿命差不多浪费不大 保持一个自由表(链表)8个字节头说明数据 按类型长度保持多个表减少识别域开销(Ada),动态堆栈缺点：开始帧不知有多大,要求存储对象比创建它的块寿命长。 指针和显式动态分配依然不少了堆。按帧也设heap 各种语言堆分配 FORTH LISP C Pascal Ada 分配 Here cons malloc new new 除配 无回收 有回收 显式除 显式除 有回收 死堆对象处理 死堆对象也叫无用单元garbage。(垃圾）,4.3 悬挂引用Dangling Reference,当堆式管理同时提供显式除配命令KILL时；堆栈式管理外块指针指向内块对象时; 函数抽象作为第一类值时,都会产生悬挂引用 解决办法 Pascal把指针限制为堆对象且不用dispose，不提供地址运算。操作数组不能按指针寻址, 快速索引 C语言比较自由，悬挂引用留给程序员 局部函数作为返回值产生的悬挂指针。 ML, Mirada完全作为堆变量且无KILL。Algol 68是引用（常指针）, 不赋比局部量寿命更长的值,例 悬挂引用(C) int * dangle (int * ppp) /参数是指针的指针 int p=5； int m=21； *ppp=&p； /传回的指向p的指针 return & m； /返回m的地址 main( ) int k =17； int * pm， *pk=&k； /pk指向k pm = dangle (&pk)； /返回时pm，Pk均指向已 /失去定义的指针函数的 /局部量，即p和m,4.4 变量更新,更新途径：赋值 动态赋值 初始化 静态赋值 4.4.1 变量初始化 分配了自动赋初值, 有多种不便 显式赋初值 FORTRAN和C的例子,static char end_of_file_flag = “no ”； int isum=0； static float a8 = 8.2，2.6，3.1，17.0；,CHARACTER * 3 EOFLAG DIMENSION A(8) DATA EOFLAG，ISUM/'NO '，0/(A(I)，I=1， 8)/8.2， 2.6，3.1，17.0，4* 0.0/,简单赋值与聚集 近代语言扩充动态聚集值强行赋值或RAED调用 typedef struct int age，weight；char sex；person； person a，b = 10，70，'M；/b有初值，a没有。 a = b； /动态聚集赋值，a也有了。 函数赋值 没有简单赋值采用统一的函数返回值。LISP, C, APL 函数赋值是表达式计算后有一中间值, 被赋给变量。故赋值命令可作为表达式, 且支持多重赋值。 #define MAXLENGTH 100 float arMAXLENGTH； int high_sub， num_elements； high_sub=(num_elements=MAXLENGTH)-1；,4.4.2 动态更新,续,常见语言赋值实现,语言 赋值号 聚集赋值 多重赋值 实现机制 COBOL MOVE 可 可 =（在COMPUTE语句中） 否 可 语 ADD,SUBTRACT,MULTIPLY 否 可 句 DIVIDE FORTRAN = 否 否 ALGOL := 否 否 PL/1 = 可 可 FORTH ! 否 否 Pascal := 可 否 Ada := 可 否 返回结果 LISP replace,replaced 某些版本可 引用 函 APL 可 值 数 C(1973) = 否 值 ANSI C = 可 值,4.5 有副作用表达式,表达式求值中不会改变操作数的值, 如果表达式中有函数, 其中的局部变量在求值中改变了, 如果有全局变量则会引起副作用。 4.5.1 块表达式 带变量声明的表达式合成一封闭块（声明在块内有效）称块表达式： let D in E end let val s = (a+b+c)*0.5 in sqrt (s*s(s-a)*(s-b)*(s-c) end,4.5.2 命令表达式,没有声明, 块中只有命令叫命令表达式： (c = getchar ( ) ) ! =EOF 此处赋值命令是子表达式返回值是字符 命令的一般有副作用是：两次执行不是同一结果值 副作用在此增强表达能力,