编译原理课件

1、第六章 运行时存储空间的组织和管理 编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。 在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问题。1第六章 运行时存储空间的组织和管理 过程的活动过程的一次执行称为过程的一次活动活动记录过

2、程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容讨论一个活动记录中的数据安排程序执行过程中，所有活动记录的组织方式 2第六章 运行时存储空间的组织和管理过程P一次活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作时间，包括执行P时调用其它过程花费的时间。过程可以是递归的一个过程可对应多个活动3第六章 运行时存储空间的组织和管理影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释

3、放本章在逻辑地址空间讨论46.1 (过程内部)局部存储分配策略6.1.1 过程过程定义、过程调用、形式参数、实在参数、活动的生存期Procedure f(a:int, b:bool)int c;过程定义void main()f(3,true);过程调用56.1 局部存储分配策略6.1.2 名字的作用域和绑定名字的作用域一个声明起作用的程序部分称为该声明的作用域。int a;Function f(int b)int c;void main()a = 0;c = 0;f(3);正确，在a的作用域内错误，超出了c的作用域66.1 局部存储分配策略6.1.2 名字的作用域和绑定名字的作用域即使一个名字

4、在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象。int a;Function f(int b)int c;void main()a = 0;f(3);f(5);两次调用，函数f中变量c对应不同的数据对象保存值的存储单元76.1 局部存储分配策略名字到存储单元的绑定环境把名字映射到左值（存储单元），而状态把左值映射到右值（值）。赋值改变状态，但不改变环境。 如果环境将名字x映射到存储单元s，我们就说x被绑定到s。名字存储单元状态值环境6.1.2 名字（变量）的作用域和绑定A = b5A4bA586.1 局部存储分配策略静态概念和动态概念的对应静 态 概 念 动 态 对 应 过程的

5、定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期 96.1 局部存储分配策略6.1.3 活动记录编译之后的程序每次运行时，从操作系统（OS）获得一块存储区（内存）。其内容包括：编译后的目标代码 (可执行程序 .exe)数据对象 (各种静态变量和动态变量)用于管理过程活动的控制栈 (活动记录)过程的活动中用于存放所需信息的存储空间, 称为活动记录或帧106.1 局部存储分配策略6.1.3 活动记录目标程序每次运行时，编译器从操作系统（OS）获得一块存储区（内存）。其空间安排：代 码静 态 数 据堆栈目标代码（.exe）静态变量和外部变量活动记录活动记录及动态变量116.1 局

6、部存储分配策略6.1.3 活动记录例子void p() void main() ; p(); .; 代 码静 态 数 据main的活动记录堆p的活动记录栈126.1 局部存储分配策略6.1.3 活动记录一般的活动记录的布局返 回 值临 时 数 据实 在 参 数控 制 链访 问 链机 器 状 态局 部 数 据本过程返回给调用过程的值调用过程传递给本过程的参数指向调用过程的指针用于引用存于其他活动记录的非局部数据用于保存本过程调用前的机器状态本过程内部定义的局部变量临时变量，中间结果136.1 局部存储分配策略6.1.4 局部数据的安排字节是可编址内存的最小单位。一个过程所声明的局部变量，按这些变

7、量声明时出现的次序，在活动记录的局部数据区中依次分配空间。 局部数据的地址可以用相对于某个位置（本过程对应的活动记录的起始位置）的偏移来表示。数据对象的存储安排深受目标机器寻址方式的影响，存在对齐问题。例如，要求整数（int，long）的相对地址可以被4整除。由于对齐而引起的无用空间称为衬垫空白区。14例题在X86/Linux工作站上，以下两个结构的size分别是20和16，为什么不一样？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a;

8、b;第一部分 存储区（内存）的划分15例题解答：typedef struct _achar c1;long i;charc2; double f;a;04812c1ic2f20衬垫空白区衬垫空白区19第一部分 存储区（内存）的划分16例题解答：typedef struct _bchar c1;char c2;longi; double f;b;0c14816ic2f衬垫空白区12第一部分 存储区（内存）的划分176.1 局部存储分配策略6.1.5 程序块语法如声明 语句本身含有局部变量声明的语句，可以嵌套最接近的嵌套作用域规则程序块B中声明的作用域包括B如果名字x没有在B中声明，那么B中x的出

9、现是在外围程序块B的x声明的作用域中，且满足B有x的声明B比其他任何包含x声明的程序块更接近被嵌套的B并列程序块不会同时活跃并列程序块的变量可以重叠分配 int a; .int b; a = 3; .int a BB1B2可以把程序块看成是不带参数和返回值的函数186.1 局部存储分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end

10、 of B1 / end of B0 /196.1 局部存储分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end of B1 / end of B0 /声 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 206.

11、1 局部存储分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end of B1 / end of B0 /声 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重叠分配存储单元 216.2 全

12、局存储分配策略介绍程序运行时所需的各个活动记录在存储空间的分配策略描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略堆式分配策略栈式分配策略代 码静 态 数 据堆栈226.2 全局存储分配策略6.2.1 运行时内存的划分代 码静 态 数 据堆栈236.2 全局存储分配策略6.2.2 静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的。246.2 全局存储分配策略静态分配的应用：Fortra

13、n语言被设计成允许静态存储分配C语言程序的外部变量和程序中出现的常量都可以静态分配。声明在函数外面外部变量声明在函数里面静态局部变量常量25 像FORTRAN这样的语言，其程序是段结构的，即由主程序段和若干子程序段组成。 各程序段中定义的名字一般是彼此独立的，也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。 另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组），且所有数据名的性质是完全确定的。 这样，整个程序所需数据空间的总量在编译时完全确定，换句话说，一旦存储空间的某个位置分配给了某个数据名（关联起

14、来）之后，在目标程序的整个运行过程中，此位置（地址）就属于该数据名了。 266.2 全局存储分配策略静态分配给语言带来限制递归过程不被允许数据对象的长度和它在内存中位置，必须是在编译时可以知道的数据结构不能动态建立276.2 全局存储分配策略6.2.3 栈式分配栈式分配主要用于管理过程的活动记录。局部变量的生存期是过程活动的时间。控制进入该过程时，局部变量绑定到存储单元，过程活动结束后，局部变量的空间释放。286.2 全局存储分配策略6.2.3 栈式分配活动树:用树来描绘控制进入和离开活动的方式srq(2,3)q(2,1)q(3,3)p(2,3) 活动树的特点每个结点代表某过程的一个活动根结点

15、代表主程序的活动结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动结点a 处于结点b 的左边，当且仅当a的生存期先于b的生存期活动执行的顺序？深度优先搜索296.2 全局存储分配策略当前活跃着的过程活动可以保存在一个栈中控制栈的内容：s, q (2, 3), p(2, 3) srq(2,3)q(2,1)q(3,3)p(2,3)306.2 全局存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） sa : arrays316.2 全局存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） si: integerra :

16、arraysr326.2 全局存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） sk: integerq (2, 3)a : arraysq(2,3)r336.2 全局存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） sk: integerq (2, 3)a : arrayp(2, 3)k: integersq(2,3)rp(2,3)34/48346.2 全局存储分配策略运行栈的管理:过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中的

17、代码过程返回序列过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码调用序列和返回序列都分常常分成两部分，分处于调用过程和被调用过程中356.2 全局存储分配策略即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则是把参数域和可能有的返回值域放在紧靠调用者活动记录的地方以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间一般把临时数据域放在局部数据域的后面用同样的代码来执行各个活动的保存和恢复366.2 全局存储分配策略调用者和被调用者之间的任务划分被调用者的责任调用者的责任调用者的活动记录被调

18、用者的活动记录过程p调用过程q局部数据临时数据控制链访问链和机器状态返回值和参数局部数据临时数据返回值和参数 控制链访问链和机器状态top_sp base_sp 栈qP376.2 全局存储分配策略过程p调用过程q的调用序列p在栈上留出放返回值的空间，并计算实参，依次放入栈顶，同时改变top_sp的值。p把返回地址存入q的活动记录中，建立q的访问链q保存寄存器的值和其它机器状态信息，将base_sp的值压栈,并将当前的top_sp作为自己的base_sp 。q根据局部数据域和临时数据域的大小减小top_sp的值，初始化它的局部数据，并开始执行过程体。局部数据临时数据控制链访问链和机器状态返回值和

19、参数局部数据临时数据返回值和参数 控制链访问链和机器状态top_sp base_sp 栈qP386.2 全局存储分配策略过程p调用过程q的返回序列q把返回值置入邻近p的活动记录的地方q增加top_sp的值 q恢复寄存器（包括base_sp）和机器状态，返回pp根据参数个数与类型和返回值类型调整top_sp，然后取出返回值39/48局部数据临时数据控制链访问链和机器状态返回值和参数局部数据临时数据返回值和参数 控制链访问链和机器状态top_sp base_sp 栈qP396.2 全局存储分配策略过程的参数个数可变的情况函数返回值改成用寄存器传递编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数根据第一个参数到栈中取第二、第三个参数等等局部数据临时数据控制链访问链和机器状态返回值和参数局部数据临时数据返回值和参数 控制链访问链和机器状态top_sp base_sp 栈qP406.2 全局存储分配策略活动记录的长度在编译时不能确定的情况局部数组的大小要等到过程激活时才能确定在活动记录中为这样的数组分别存放数组指针的单元运行时，这些指针指向分配在栈顶的存储空间访问动态分配的数组q的数组q的活动记录p的数组