运行时的存储组织和分配.ppt

第7章 目标程序运行时的存储组织 存储组织 运行时的分配策略 从逻辑上看，在代码生成前，编译 程序必须进行目标程序运行环境的设计和数 据空间的分配。一般来讲，假如编译程序从 操作系统中得到一块存储区以使目标程序在 其上运行，该存储区需容纳生成的目标代码 和目标代码运行时的数据空间。 概述 数据空间应包括：用户定义的各 种类型的数据对象（变量和常数）所需的 存储空间，作为保留中间结果和传递参数 的临时工作单元，调用过程时所需的连接 单元，以及组织输入输出所需的缓冲区 。目标代码所占用空间的大小，在编译时 能确定，有些数据对象所占用的空间也能 在编译时确定，其地址可以编译进目标代 码中。但有些数据对象具有可变体积和待 编译性质，而无法在编译时确定存储空间 的位置。 因此运行时的存储区常常划分成：目标区、 静态数据区、栈区和堆区。 1.存储组织 目标代码区code 静态数据区 Stack heap 如图就是一种典型划分 ，代码（code）区用以存放 目标代码，这是固定长度的 ，即编译时能确定的。静态 数据区（static data）用 以存放编译时能确定所占用 空间的数据，堆栈区（ stack and heap）用于可变 数据以及管理过程活动的控 制信息。 编译程序分配目标程序运行时的 数据空间的基本依据是程序语言设计时对 程序运行中存储空间的使用和管理办法的 规定。 所谓数据空间的分配，本质上看，是将程序 中的每个名字与一个存储位置关联起来，该存储 位置用以容纳名字的值。我们知道，即便有些名 字在程序中只声明了一次，但该名字可能对应运 行时不同的运行空间位置以容纳每次执行时的值 。 因此，源语言的结构特点、源语言 数据类型、源语言中决定名字作用域的规则 等因素影响存储空间的管理和组织的复杂程 序，决定数据空间分配的基本策略。 2.数据空间的使用和管理方法分成三种： 静态存储分配 栈式动态存储分配 堆式动态存储分配 存储分配方案策略 静态存储分配 动态存储分配栈式、堆式 术语 静态：如果一个名字的性质通过 说明语句或隐或显规则而定义，则称这种 性质是“静态”确定的。 动态：如果名字的性质只有在程 序运行时才能知道，则称这种性质为“动 态”确定的。 可变（动态）数组：若一个数组 所需的存储空间的大小在编译时就已知道 ，则称它为确定数组，否则称为可变（动 态）数组。 如果在编译时能确定目标程序运行中所需的 全部数据空间的大小，编译时安排好目标程序运 行时的全部数据空间，确定每个数据对象的存储 位置，那么则称这种分配策略为静态存储分配。 如像FORTRAN这样的语言， 其程序 是段结构的，即由主程序段和若干子程序段 组成。各程序段中定义的名字一般是彼此独 立的（除公共块和等价语句说明的名字以外 ），也即各段的数据对象名的作用域在各段 中，同一个名字在不同的程序段表示不同的 存储单元，不会在不同段间互相引用、赋值 。 主子1子2子n FORTRAN程序构成特点 另外它的每个数据名所需的存储空间大小都 是 常量（即不许含可变体积的数据，如可变数 组），且所有数据名的性质是完全确定的。这样 ，整个程序所需数据空间的总量在编译时完全确 定，从而每个数据名的地址就可静态进行分配。 栈式动态存储分配： 这种分配策略是将整个程序的数据空间设计 为一个栈。它适用于PASCAL，C，ALGOL之类语言 的实现，每当调用一个过程时，它所需的数据空 间就分配在栈顶，每当过程工作结束时就释放这 部分空间。 过程所需的数据空间包括两部分 ，一部分是生存期在本过程这次活动中的 数据对象，如局部变量、参数单元、临时 变量等等；另一部分则是用以管理过程活 动的记录信息，即当一次过程调用出现时 ，调用该过程的那个过程的活动即被中断 ，当前机器的状态信息，诸如程序计数器 （返地址）、寄存器的值等，也都必须保 留在栈中。 当控制从调用返回时，便根据栈中记录的信 息恢复机器状态，使该过程的活动重新开始。 堆式动态存储分配: 如果一个程序语言提供用户自由地申请数据 空间和退还数据空间的机制（如C+中的new， delete， PASCAL的new，便是这种机制）或者不 仅有过程而且有进程的程序结构，即空间的使用 未必服从“先申请后释放，后申请先释放”的原 则，那么栈式的状态分配方案就不适用了。 这种情况下通常使用一种称为堆式 的动态存储分配方案。假设程序运行时有一 个大的存储空间，每当需要时就从这片空间 中借用一块，不用时再退还。 栈式存储分配的实现 前面提到，使用栈式存储分析策略意味着， 运行时每当进入一个过程，就在栈顶为该过程分 配所需的数据空间，当一个过程工作完毕返回时 ，它的栈顶的数据空间也即释放。下面讨论栈式 存储分配的实现。 术语过程的活动记录AR（Activation Record） 过程的活动记录是一段连续的存储区，用以 存放过程的一次执行所需要的信息为说明方便， 假定程序是由过程组成，过程区分为源文本，运 行时称作过程的激活。 一个过程的一次执行所需要的信息使用一个 连续的存储区来管理，这个区（块）叫做一个活 动记录。 临时工作单元 局部变量 机器状态信息 存取链 控制链 实 参 返回地址 1、临时工作单元，比如计算表达式过程中需 存放中间结果用的临时值单元。 2、局部变量，一个过程的局部变量。 3、保存机器状态，容纳该过程执行前关于机 器状态的信息，诸如程序计数器 、寄存器的值， 这些值都需要在控制从该过程返回时给予恢复。 4、存取链，用以存取非局部变量，这些变量 存放于其它过程活动记录中。并不是所有 语言需 要该信息。 5、控制链，指向调用该过程的那个过程的活 动记录，这也不是所有语言都需要的。 6、实参，也称形式单元，由调用过程向该被 调过程提供实参的值（或地址）。当然在实际编 译程序中，也常常使用机器寄存器传递实参。 7、返回地址，保存该被调过程返回后的地址 。 如果一个程序设计语言允许递归过程，可变 数组或可变数据结构，那么，就需要采用动态存 储管理技术。 简单的栈式分配方案 一种最简单的程序设计语言结构：没有分程 序结构，过程定义不嵌套，但允许过程递归调用 。 Program main； 全局变量的说明； proc R； end R； proc Q； end Q； 主程序执行语句 end.（main） 采用栈式动态分配策略，即运行时，每当进 入一个过程，则为该过程分配一段存储区，当一 个过程工作完毕返回时，它所占用的存储区则可 释放。程序运行时的存储空间，（栈）中在某一 时刻可能会包含某个过程的几个活动记录（某个 过程递归调用的情况）；另外，同样一个存储位 置，可能不同运行时刻分配给不同的数据对象。 参数传递 当一个过程调用其它过程时，调用过程和被 调过程之间的通信经由非局部量或者经由参数传 递。 （1）procedure exchangel（i， j:integer）； （2）var x:int eger； （3）begin； （4）x:=ai；ai:=aj；a j:=x （5）end； 带有非局部变量和形参的PASCAL过程，非局变量 ai和aj的值进行交换，i，j为形参（在这里 是传值）。 语句exchangel（m，n）；表示了 对过程exchangel的一次调用，其中m，n为 实在参数，简称实参。我们所讨论的问题 是，为执行 exchangel（m，n），形参i ，j应按何种方式同实参m，n相联，换句话 说，如何把实在参数传递给相应的形式参 数呢？ 有几种形实参对应的方法，分别称作值调用 ，地址（引用）调用，名字调用以及宏扩展。也 就是说，参数传递的几种不同途径是传值，传地 址，传名及宏扩展等。 在一个赋值语句ai:=aj中，表 达式aj表示一个值，而ai表示一个存储 位置，用于存放aj的值。通常术语左值（ value）指 表达式代表的存储，右值（ value）指该 存储位置中含有的值。“ 左”和“右”来自赋值语句的“左”端和“ 右”端。参数传递方法的不同主要基于实在 参数是表达一个右值，一个左值，还是实在 参数本身的文本。 传值： 现在讨论传值的实现。传值，即call-by- value，也称值调用。这是最简单的参数传递方法 。即将实参计算出它的值，然后把它传给被调过 程。具体来讲是这样的： 1、形式参数当作过程的局部变量处理，即 在被调过程的活动记录中开辟了形参的存储空间 ，这些存储位置即是我们所说的实参或形式单元 。 2、调用过程计算实参的值，并将它们的右值 （r-value）放在形式单元开辟的空间中。 传值或值调用的重要特点是对形式参数 的任 何运算来不影响调用过程的活动记录中实参的值 。 3、被调用过程执行时，就像使用局部变量一 样使用这些形式单元。 传地址： 例如：过程swap（var x，y:integer）； swap（a，b）；（a，b为调用时的实参）调用结 果a，b的值被改变。 传值（值调用）：特点是对形式参数的任何 运算不影响实参的值。 例如：过程swap（x，y:integer）； swap（a，b）；其结果：a，b调用前的值不改变 。 传地址的实现 把实在参数的地址传递给相应的形参，即调 用过程把一个指向实参的存储地址的指针传递给 被调用过程相应的形参： 1、实在参数是一个名字，或具有左值的表达 式传递左值。 2、实在参数是无左值的表达式计算值， 放入一存储单元，传此存储单元地址。 3、目标代码中，被调用过程对形参的引用变 成对传递给被调用过程的指针的间接引用。 Pragram main（input，output）； Procedure p（x，y，z）； begin y:=y+1； z=z+1； end； begin a:=2；b:=3；p（a+b，a，a）； print a end. 问：a的输出分别为多少 传值2 传地址8 第第五五章章: : 编译程序的数据结构和符号表编译程序的数据结构和符号表 5.15.1 分配型数据结构分配型数据结构 5.2 5.2 查找型数据结构查找型数据结构 概述概述 在编译过程中需要建立并保持一批表格符在编译过程中需要建立并保持一批表格符 号表。号表。 从提高编译程序从提高编译程序 的工作效率上考虑，有关的的工作效率上考虑，有关的 数据结构的设计就显得非常重要。数据结构的设计就显得非常重要。 从使用角度上看可以分为：查找型数据结构从使用角度上看可以分为：查找型数据结构 和分配型数据结构。和分配型数据结构。 查找型数据结构在编译过程中用于构造不同查找型数据结构在编译过程中用于构造不同 的信息表，保存源程序中不同实体的属性信息。的信息表，保存源程序中不同实体的属性信息。 特点是每个实体的项只创建一次，但可以查询多特点是每个实体的项只创建一次，但可以查询多 次，所以查询效率很重要。次，所以查询效率很重要。 分配型数据结构主要用于处理嵌套结构的程分配型数据结构主要用于处理嵌套结构的程 序。序。其特点是分配给实体的内存地址对实体用户其特点是分配给实体的内存地址对实体用户 是可知的。因此不会对其进行查询操作，但分配是可知的。因此不会对其进行查询操作，但分配 和回收的速度和内存的使用效率却是十分重要的和回收的速度和内存的使用效率却是十分重要的 。 5.2.1 5.2.1 查找型数据结构查找型数据结构 (1)(1)什么什么是符号表是符号表? ? 在编译过程中，编译程序用于记录源在编译过程中，编译程序用于记录源 程序中各种名字的特性信息，程序中各种名字的特性信息， 所以也称所以也称 为为名字特性表名字特性表。 名字名字： 程序名、过程名、函数名、程序名、过程名、函数名、 用户定义类型、变量名、符号名字。用户定义类型、变量名、符号名字。 特性信息特性信息：名字种类、类型、维数、：名字种类、类型、维数、 参数个数及目标地址（存储单元地址）参数个数及目标地址（存储单元地址） 等。等。 (2) (2) 建表和查表的必要性建表和查表的必要性 ( (符号表在编译过程中的作用符号表在编译过程中的作用) ) 源程序中变量要先声明，然后才能引用源程序中变量要先声明，然后才能引用 。 用户通过用户通过声明语句声明语句，声明各种，声明各种名字名字，以及给，以及给 出它们的类型维数等出它们的类型维数等信息信息，编译程序在出来这些，编译程序在出来这些 声明语句时，因将声明中的名字以及信息声明语句时，因将声明中的名字以及信息登录登录到到 符号表中，同时编译还要给变量分配存储单元，符号表中，同时编译还要给变量分配存储单元， 而而存储单元地址存储单元地址也必须登录在符号表中。也必须登录在符号表中。 当编译程序编译到当编译程序编译到引用引用所声明的变量时所声明的变量时（赋赋 值或引用其值）要进行语法语义正确性检查值或引用其值）要进行语法语义正确性检查 类型类型 是否符合要求和生成相应的目标程序，这就需要是否符合要求和生成相应的目标程序，这就需要 查查符号表来取得相关信息符号表来取得相关信息。 1.1.语法分析和语义分析语法分析和语义分析 说明语句赋值语说明语句赋值语 句的语法规则句的语法规则 上下文有关分析上下文有关分析 ；是否声明；是否声明； 类型一致性检查类型一致性检查 2. 2. 生成目标代码生成目标代码 LOAD a LOAD a 的地址的地址 ADD b ADD b 的地址的地址 STO x STO x 的地址的地址 例例: : intint x,a,b;x,a,b; L: x:=a+b; L: x:=a+b; 建表建表 分配存贮分配存贮 符号表符号表数据区数据区 X X 简单变简单变简单变简单变 量量 整整 型型 A A 简单变简单变简单变简单变 量量 整整 型型 B B 简单变简单变简单变简单变 量量 整整 型型 L L 标标标标号号 (3) (3) 有关符号表的操作：填表和查表有关符号表的操作：填表和查表 填表填表: :当分析到程序中的当分析到程序中的说明说明或或定义定义语句语句 时应将说明或定义的名字以及与之有关的信息时应将说明或定义的名字以及与之有关的信息 填入符号表中填入符号表中 例：例：Procedure P()Procedure P() 查表查表: : (1) (1) 填表前查表检查在程序的同一作用域填表前查表检查在程序的同一作用域 内内名字名字是否重复定义是否重复定义 (2) (2) 检查名字的检查名字的种类种类是否与说明一致是否与说明一致 (3)(3)对于强类型语言要检查表达式中各变对于强类型语言要检查表达式中各变 量的量的类型类型是否一致是否一致 (4) (4) 生成目标指令时要取得所需要的地址生成目标指令时要取得所需要的地址 5.2.2 5.2.2 符号表的组织与内容符号表的组织与内容 (1)(1)符号表的结构与内容符号表的结构与内容 符号表的基本结构如下符号表的基本结构如下 名字名字 特性特性( (信息信息) ) “ “名字名字”域域: :存放名字。一般为标存放名字。一般为标 识符的符号串，也可为指向标识符字识符的符号串，也可为指向标识符字 符串串指针符串串指针 “特性特性”域：域：可包括多个子域，分别表示可包括多个子域，分别表示 标识符的有标识符的有 关信息。如：关信息。如： 名字（标识符）的种类：名字（标识符）的种类：变量、函数、过变量、函数、过 程、数组、标号、参数等程、数组、标号、参数等 类型：类型：如整型、浮点型、字符型、指针等如整型、浮点型、字符型、指针等 性质：性质：变量形参、值形参等变量形参、值形参等 名字：名字：常量名常量名