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

《研究生课程程序语言设计原理教程第04章》由会员分享，可在线阅读，更多相关《研究生课程程序语言设计原理教程第04章（22页珍藏版）》请在装配图网上搜索。

1、第第4 4章章 存存 储储 存储对象是程序对象在计算机中的实现存储对象是程序对象在计算机中的实现 程序对象不一一对应为存储对象程序对象不一一对应为存储对象 x:=0; x,0是两程序对象是两程序对象 只有一个存储对象只有一个存储对象x加指令清零加指令清零 初值常量也不作为单独存储对象初值常量也不作为单独存储对象4.1 4.1 程序变量的时空特性程序变量的时空特性4.1.1 4.1.1 引用和指针引用和指针计算对象有地址非固定地址计算对象有地址非固定地址, 因时而变因时而变, 相对地址相对地址 虚存空间虚存空间P指针是地址变量指针是地址变量 *P是是P所指的内容所指的内容, 也有左值和右值也有左

2、值和右值 *P左值是左值是P所指地址值，即所指地址值，即P的值的值 *P右值是所指地址内的内容值右值是所指地址内的内容值136140144A AB BC C3 31 12 23 31 16 63 32 20 0136140144( (R RA A) )3 31 12 2( (R RB B) )3 31 16 6( (R RC C) )3 32 20 0136144( (p p1 1) )4 44 48 8( (p p2 2) )4 45 50 04274.543312.27607.01( (A A) )1 13 36 6( (B B) )1 14 40 0( (C C) )1 14 44 4引

3、用是常指针是变量的别名引用是常指针是变量的别名, 但实现是不一样的但实现是不一样的4.1.2 4.1.2 递引用递引用 dereferencedereference通过指针变量引用变量的值为递引用通过指针变量引用变量的值为递引用*P1右值即递引用右值即递引用有些语言显式递引用算符如有些语言显式递引用算符如FORTH的的1 13 1 13 VARIABLE VARIABLE xx xx ( (声明变量声明变量xxxx并赋初值并赋初值13)13)2 0 2 0 VARIABLE Y (VARIABLE Y (声明变量声明变量Y Y并赋初值并赋初值0) 0) 3 3 xxxx 2 2 * * Y !

4、 ( Y ! (相当于相当于Y=Y=xxxx* *2)2)如果只写如果只写xxxx 2 2 * * 则为将则为将xxxx的地址乘以的地址乘以2 2放在放在Y Y之中之中4.1.3 变量的时态变量的时态 分配分配/未分配未分配/除分配除分配 分配分配: 为程序对象创建为程序对象创建存储对象存储对象 编译时分配叫静态分配编译时分配叫静态分配 allocate 运行时分配叫动态分配如声明指针运行时分配叫动态分配如声明指针p, 执执new才分配才分配 未分配未分配: 声明了未分配运行时分配声明了未分配运行时分配 除分配除分配: 取消存储对象取消存储对象(程序对象程序对象) delete操作显式操作显式

5、 自动除配自动除配: 无用单元收集无用单元收集Garbage collection动态语言有，静态可有动态语言有，静态可有Ada可没有可没有C续续43? ? a b c d e f 声明和定义：定义必然声明；反之不然声明和定义：定义必然声明；反之不然 声明的两个作用声明的两个作用 ：给出对象：给出对象, 该对象的时间有效性该对象的时间有效性 出了声明的作用域该对象失去定义。在声明的作用出了声明的作用域该对象失去定义。在声明的作用 域内显式删除也失去定义域内显式删除也失去定义定义定义/ /未定义未定义/ /失去定义失去定义 只要分配存储对象必然有残值只要分配存储对象必然有残值, 无意义即未定义无

6、意义即未定义 赋值或初值变量得以定义赋值或初值变量得以定义a,b:分配且有定义分配且有定义c,d:分配未定义或失去定义分配未定义或失去定义e,f:未分配或除配未分配或除配4.2 存储模型 基元类型值基元类型值 仅除数组仅除数组 记录、构造、表记录、构造、表 不可更新其中一元素不可更新其中一元素 函数抽象函数抽象, ML重过程重过程 变量引用变量引用可存储值可存储值StorableStorable：指最小的可直接访问的可存储单元中的值指最小的可直接访问的可存储单元中的值Pascal可存储值可存储值:集合不选择更新某一元素是可存储值，集合不选择更新某一元素是可存储值，Pascal, C ，Ada数

7、组可选择更新数组可选择更新, 不是可存储值。不是可存储值。引用非可存储引用非可存储(C+可存储可存储), 过程和函数名也非可存储过程和函数名也非可存储ML几乎都是可存储值几乎都是可存储值, 也带来毛病：每次更新结构数据都要重也带来毛病：每次更新结构数据都要重来。它们是：来。它们是：( if exp then sin else cos ) (x) 得得sin(x)cos(x)可存储值可存储值 4.2.1存储对象的生存期存储对象的生存期 全局变量全局变量 和引用程序寿命一样长和引用程序寿命一样长 局部变量局部变量 和程序中的一个模块寿命一样长和程序中的一个模块寿命一样长 持久变量持久变量 比程序寿

8、命长除非显式撤销比程序寿命长除非显式撤销 文件变量文件变量 瞬间变量（瞬间变量（transient)持久变量的逆持久变量的逆每个存储对象都有创建每个存储对象都有创建(生生), 可用可用(活着活着)，撤销，撤销(死死)的的生命期。按生命期长短分：生命期。按生命期长短分：4.2.2 4.2.2 静态存储对象静态存储对象 编译时分配存储对象编译时分配存储对象, 近代语言类属对象直到装入后近代语言类属对象直到装入后确立确立(elaboration)之时才定下存储对象叫静态分配之时才定下存储对象叫静态分配 一旦执行不再改动其存储，直至所在存储单元无效一旦执行不再改动其存储，直至所在存储单元无效叫静态叫静

9、态(Static)存储对象存储对象 全局变量均为隐式的静态对象全局变量均为隐式的静态对象, COBOL,BASIC全全静态，静态，ALGOL，C是显示声明静态，是显示声明静态，Pascal除全局，除全局，Ada 不能。不能。 C语言的静态变量是既私有又不随所在声明块中消逝语言的静态变量是既私有又不随所在声明块中消逝, 全局于所在文件。全局于所在文件。auto是静态分配动态装入不叫静态对是静态分配动态装入不叫静态对象。象。Extern是静态对象。是静态对象。externstaticauto4.2.3动态存储对象动态存储对象 把寿命特长的（如文件，全局量）排出来归到栈底的某一组，把寿命特短的（如循

10、环控制变量）另立嵌套组，这个问题也就解决。块5块66块1块2块3块45466546寿寿命命4.2.4 4.2.4 动态存储对象动态存储对象XX 二叉树其大小由输入值定在运行中确立。内存开二叉树其大小由输入值定在运行中确立。内存开辟堆（辟堆（heap)随生成随堆放动态存储对象。指针（即随生成随堆放动态存储对象。指针（即堆变量）所指程序对象用堆存放堆变量）所指程序对象用堆存放 问题：多次重分，内存成了小洞问题：多次重分，内存成了小洞 解决办法：按寿命分组寿命最长的放在较低（按解决办法：按寿命分组寿命最长的放在较低（按其所在块生命期）。其所在块生命期）。重复使用重复使用无法再分无法再分4.2.5 4

11、.2.5 堆栈帧管理堆栈帧管理 由动态堆栈联想到一般嵌套式语言可按动态堆栈式管由动态堆栈联想到一般嵌套式语言可按动态堆栈式管理理, 多数变量和所在块寿命一样长多数变量和所在块寿命一样长(语言称之为自动变量语言称之为自动变量) 动态堆栈式存储动态堆栈式存储 按程序动态执行按程序动态执行, 以动态堆栈管理局部数据和动态生以动态堆栈管理局部数据和动态生成数据成数据 运行时堆栈运行时堆栈Run-time stack其底压入程序代码和全局，其底压入程序代码和全局，静态量。每执行到调用时生成一个堆栈帧静态量。每执行到调用时生成一个堆栈帧(frame)记录该记录该块数据信息块数据信息, 每当返回则局部量自动

12、撤销对于递归块的每当返回则局部量自动撤销对于递归块的局部量可多次生成多次消除。局部量可多次生成多次消除。 动态链描述调用父辈地址动态链描述调用父辈地址, 返回地址是继续执行的下返回地址是继续执行的下一地址。一地址。 静态链描述词法父辈静态链描述词法父辈lexical parent块地址块地址, 按该块复制按该块复制局部变量。局部变量。参数参数 返回地址返回地址动态链动态链静态链静态链返回值返回值局部变量局部变量程序代码程序代码全局静态存储全局静态存储首先调用块首先调用块堆栈帧堆栈帧第二调用块第二调用块堆栈帧堆栈帧最新最新调用块调用块堆栈帧堆栈帧临时变量空间临时变量空间栈顶栈顶堆栈帧堆栈帧组织组

13、织运行时堆栈运行时堆栈续续调调用用块块首首地地址址本本帧帧词词法法父父辈辈 举例举例 求整数连乘积之递归程序求整数连乘积之递归程序: 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:2return :?kk:25jj:1return :?kk:7jj:0return :?kk:?临时存储临时存储DLS

14、L:SL:静态链静态链DL:DL:静态链静态链最初调用时堆栈帧最初调用时堆栈帧第一次调用时堆栈帧第一次调用时堆栈帧第一次调用时堆栈帧第一次调用时堆栈帧 栈顶栈顶SL4.2.6 动态堆存储动态堆存储 忽略死对象忽略死对象 不超过一页浪费不超过一页浪费, 若寿命差不多浪费不大若寿命差不多浪费不大 保持一个自由表保持一个自由表(链表链表)8个字节头说明数据个字节头说明数据 按类型长度保持多个表减少识别域开销按类型长度保持多个表减少识别域开销(Ada) 动态堆栈缺点：开始帧不知有多大动态堆栈缺点：开始帧不知有多大,要求存储对象要求存储对象比创建它的块寿命长。比创建它的块寿命长。 指针和显式动态分配依然

15、不少了堆。按帧也设指针和显式动态分配依然不少了堆。按帧也设heap 各种语言堆分配各种语言堆分配 FORTH LISP C Pascal FORTH LISP C Pascal AdaAda分配分配 Here cons Here cons malloc malloc new new new new除配除配 无回收无回收 有回收有回收 显式除显式除 显式除显式除 有回收有回收 死堆对象处理死堆对象处理 死堆对象也叫无用单元死堆对象也叫无用单元garbage。(垃圾）垃圾）4.3 4.3 悬挂引用悬挂引用Dangling ReferenceDangling Reference 当堆式管理同时提供显

16、式除配命令当堆式管理同时提供显式除配命令KILL时；堆栈式时；堆栈式管理外块指针指向内块对象时管理外块指针指向内块对象时; 函数抽象作为第一类值函数抽象作为第一类值时时,都会产生都会产生悬挂引用悬挂引用 解决办法解决办法 Pascal把指针限制为堆对象且不用把指针限制为堆对象且不用dispose，不提供地不提供地址运算。操作数组不能按指针寻址址运算。操作数组不能按指针寻址, 快速索引快速索引 C语言比较自由，悬挂引用留给程序员语言比较自由，悬挂引用留给程序员 局部函数作为返回值产生的悬挂指针。局部函数作为返回值产生的悬挂指针。 ML, Mirada完全作为堆变量且无完全作为堆变量且无KILL。

17、Algol 68是引用（常指针是引用（常指针）, 不赋比局部量寿命更长的值不赋比局部量寿命更长的值例例 悬挂引用悬挂引用( (C)C)intint * * dangle ( dangle (int int * * * ppp ppp) /) /参数是指针的指针参数是指针的指针 intint p=5 p=5； intint m=21 m=21； * *pppppp=&p=&p； /传回的指向传回的指向p p的指针的指针 return & mreturn & m； / /返回返回m m的地址的地址main( ) main( ) int int k =17 k =17； intint * * pm

18、pm， * *pkpk=&k=&k； /pkpk指向指向k k pm pm = dangle (& = dangle (&pkpk) )； /返回时返回时pmpm，PkPk均指向已均指向已 /失去定义的指针函数的失去定义的指针函数的 / /局部量，即局部量，即p p和和m m4.4 4.4 变量更新变量更新更新途径：赋值更新途径：赋值 动态赋值动态赋值 初始化初始化 静态赋值静态赋值4.4.1 4.4.1 变量初始化变量初始化 分配了自动赋初值分配了自动赋初值, 有多种不便有多种不便 显式赋初值显式赋初值 FORTRAN和和C的例子的例子static char end_of_file_flag

19、 = “no ”static char end_of_file_flag = “no ”； int isumint isum=0=0； static float a8 = 8.2static float a8 = 8.2，2.62.6，3.13.1，17.017.0；CHARACTER CHARACTER * * 3 EOFLAG 3 EOFLAGDIMENSION A(8)DIMENSION A(8)DATA EOFLAGDATA EOFLAG，ISUM/NO ISUM/NO ，0/(A(I)0/(A(I)，I=1I=1， 8)/8.28)/8.2， 2.62.6，3.13.1，17.017

20、.0，4 4* * 0.0/ 0.0/简单赋值与聚集简单赋值与聚集 近代语言扩充动态聚集值强行赋值或近代语言扩充动态聚集值强行赋值或RAED调用调用 typedef struct typedef struct intint age age，weightweight；char sexchar sex；personperson； person aperson a，b = 10b = 10，7070，MM；/b/b有初值，有初值，a a没有。没有。 a = ba = b； /动态聚集赋值，动态聚集赋值，a a也有了。也有了。 函数赋值函数赋值 没有简单赋值采用统一的函数返回值。没有简单赋值采用统一的

21、函数返回值。LISP, C, APL 函数赋值是表达式计算后有一中间值函数赋值是表达式计算后有一中间值, 被赋给变量。被赋给变量。故赋值命令可作为表达式故赋值命令可作为表达式, 且支持多重赋值。且支持多重赋值。 # #define MAXLENGTH 100define MAXLENGTH 100 float float ararMAXLENGTHMAXLENGTH； intint high_sub high_sub， numnum_elements_elements； high_sub=(high_sub=(numnum_elements=MAXLENGTH)-1_elements=MAXL

22、ENGTH)-1；4.4.2 4.4.2 动态更新动态更新续续常见语言赋值实现常见语言赋值实现语言语言 赋值号赋值号 聚集赋值聚集赋值 多重赋值多重赋值 实现机制实现机制 COBOL MOVE COBOL MOVE 可可 可可 = =（在（在COMPUTECOMPUTE语句中）语句中） 否否 可可 语语 ADD,SUBTRACT,MULTIPLY ADD,SUBTRACT,MULTIPLY 否否 可可 句句 DIVIDE DIVIDE FORTRAN = FORTRAN = 否否 否否 ALGOL := ALGOL := 否否 否否 PL/1 = PL/1 = 可可 可可 FORTH ! FO

23、RTH ! 否否 否否 Pascal := Pascal := 可可 否否 AdaAda := := 可可 否否 返回结果返回结果 LISP replace,replaced LISP replace,replaced 某些版本可某些版本可 引用引用 函函 APL APL 可可 值值 数数 C(1973) = C(1973) = 否否 值值 ANSI C = ANSI C = 可可 值值4.5 4.5 有副作用表达式有副作用表达式 表达式求值中不会改变操作数的值表达式求值中不会改变操作数的值, 如果表达式如果表达式中有函数中有函数, 其中的局部变量在求值中改变了其中的局部变量在求值中改变了,

24、如果有如果有全局变量则会引起副作用。全局变量则会引起副作用。4.5.1 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 4.5.2 命令表达式命令表达式 没有声明没有声明, 块中只有命令叫命令表达式：块中只有命令叫命令表达式： (c = getchar ( ) ) ! =EOF 此处赋值命令是子表达式返回值是字符此处赋值命令是子表达式返回值是字符 命令的一般有副作用是：两次执行不是同一结果值命令的一般有副作用是：两次执行不是同一结果值 副作用在此增强表达能力副作用在此增强表达能力