第九章 程序运行时存储空间的组织
第一部分：符号表
1 符号表的作用
登记各类名字的信息；
编译各阶段都需要使用符号表（一致性检查和作用域分析、辅助代码生成）
2 符号表的组织
符号表的每一项(入口)包含两大栏：名字栏，也称主栏，关键字栏；信息栏，记录相应的不同属性，分为若干子栏。
按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表…
对符号表的操作：
填入名称；
查找名字；
访问信息；
填写修改信息；
删除。
对符号表进行操作的时机：
定义性出现，int index；
使用性出现，if index < 100。
栏目的长度：
方法一：安排各项各栏的存储单元为固定长度；
方法二：用间接方式安排各栏存储单元（存放指针等，会影响效率）。
符号表的存放：
方法一：把每一项置于连续K存储单元中，构成一张K*N的表(N为符号表的项数)；
方法二：把整个符号表分成M个子表，如T1、T2、…、Tm，每个子表含N项。
3 符号表的整理和查找
线性查找：按关键字出现的顺序填写各项。
结构简单，节省空间，填表快，
查找慢，时间复杂度O(n)。
改进：自适应线性表。
二分查找：表格中的项按名字的“大小”顺序整理排列。
填表慢，查找快，时间复杂度:O(Log2n)。
改进：组织成二叉树。
杂凑查找(HASH技术)：
杂凑函数H(SYM)：0~n-1，n：符号表的项数。
填表快，查找快。
要求：
计算简单高效，
函数值分布均匀。
4 符号表的内容
符号表的信息栏中登记了每个名字的有关性质：
类型：整、实或布尔等；
种属：简单变量、数组、过程、函数等；
大小：长度，即所需的存储单元字数；
相对数：指分配给该名字的存储单元的相对地址。
表格的定义：
名字表(nametab)、
程序体表(btab)、
层次显示表(display)、
数组信息表(atab)、
中间代码表(code)。
名字表(nametab)，登记程序中出现的各种名字及其属性：
name，名字标识符；
kind，名字种类，可以是常量(constant)、变量(variable)、类型(type)、过程(procedure)；
lev，名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依此类推；
typ，名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype；
normal，一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填；
ref，当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表中的位置；其他情况ref为0；
adr/val/size，adr，当名字为变量名时(包括形参)，存入该变量(或形参)在相应活动记录中分配的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址，val，当名字为常量名时，填入他们的相应值，size，当名字为类型名时，填入该类型数据所需存贮单元数目；
link，指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0，通过link可以方便的进行遍历。
程序体表(btab)，记录各程序体的总信息，用于对源程序中定义的名字的作用域进行分析，对名字表进行管理：
lastpar，指向本程序体中最后一个形式参数在nametab中的位置；
last，指向本程序体中最后一个名字在nametab中的位置；
psize，本程序体所有形参所需体积、包括连接数据所占空间；
vsize，本程序体所有局部数据所需空间大小。
层次显示表(display)，描述正在处理的各嵌套层，对程序体表进行管理。
数组信息表(atab)，用于记录每个数组的详细信息：
inxtyp，数组的下标类型；
eltyp，数组元素类型；
elref，当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0；
low，数组下限；
high，数组上限；
elsize，数组元素的体积；
size，数组本身的体积。
中间代码表(code)，用于存放编译程序所产生的每条中间代码：
opcode，操作码；
l，第一操作数，程序体层数；
a，第二操作数，相对地址。
5 名字的作用范围
在许多程序语言中，允许同一个标识符在不同过程中代表不同的名字，名字都有一个确定的作用范围。
作用域：一个名字能被使用的区域范围称作这个名字的作用域。
两种程序体结构：
并列结构，如FORTRAN；
嵌套结构，如PASCAL，PL。
并列结构：
一个程序由一个主程序段和若干辅程序段组成，每个程序段由一系列的说明语句和执行语句组成，各段可以独立编译，各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。
嵌套结构：
最近嵌套原则（作用域链）。
第二部分：运行时存储空间的组织
6 参数传递概念
过程或函数是模块程序设计的主要手段，也是节省程序代码和扩充语言的主要途径。
过程定义：
1
2
3
4procedure add(x, y : integer; var z : integer)
begin
z := x + y;
end;
过程调用：
add(a, b, c);
7 参数传递方式
传地址，把实在参数的地址传递给相应的形式参数。
方法：调用程序把实在参数(实参)的地址传递到被调用过程相应的形式单元中。被调用过程中，对形式参数(形参)的引用或赋值被处理成对形式单元的间接访问。
示例：PASCAL的变量参数，C/C++传引用。
得结果，传地址的一种变形。
方法：每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值，在过程体中对形参的任何引用或赋值都看作对它的第二个单元的直接访问，过程完成返回前，把第二个单元的内容存放到第一个单元所指的实参单元中。
示例：有些Fortran采用这种方式。
传值，把实在参数的值传递给相应的形式参数。
方法：调用程序预先把实在参数的值计算出来，并传递到被调用过程相应的形式单元中，被调用过程中，象引用局部数据一样引用形式参数，直接访问对应的形式单元。
示例：PASCAL的值参数，C/C++的省缺参数传递。
传名（不常用），过程调用的作用相当于把被调用过程的过程体抄到调用出现的地方，但把其中出现的形式参数都替换成相应的实参。
方法：在进入被调用过程的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址），通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。
8 过程的活动与生存期
过程或函数是模块化程序设计的主要手段，也是节省程序代码和扩充语言的主要途径。
一个过程的活动指的是该过程的一次执行。
过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间。
编译程序必须知道目标程序的运行时存储空间组织。
9 运行时的存储组织
一个目标程序运行所需的存储空间包括：
存放目标代码的空间；
存放数据项目的空间；
存放程序运行的控制或连接数据所需单元。
编译程序组织存储空间须考虑的问题：
过程是否允许递归？
当控制从一个过程的活动返回时，对局部名称的值如何处理？
过程是否允许引用非局部名称？
过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返回？
存储空间可否在程序控制下进行动态分配？
存储空间是否必须显式地释放？
存储分配策略：静态分配策略和动态分配策略。
10 静态分配策略
静态分配策略：在编译时能确定数据空间的大小，并为每个数据项目确定出在运行时刻的存储空间中的位置。
示例：FORTRAN等。
FORTRAN程序的特点：
整个程序所需数据空间的总量在编译时完全确定；
每个数据名的地址可以静态地进行分配；
各程序段可以独立编译，由链接装配程序把各段连成可运行的整体。
按数据区组织存储：
每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值；
每个公用块定义一个公用数据区，用来存放公用块里各个名字的值。
局部数据区：
每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属数据区编号及在该区中的相对位置。
局部数据区的内容如下图：
11 动态分配策略
动态分配策略：在编译时不能确定运行时数据空间的大小，允许递归过程和动态申请释放内存。
分为栈式动态分配、堆式动态分配。
示例：PASCAL，C/C++等。
活动记录：运行时，每当进入一个过程就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。
非嵌套过程语言（如C语言）：
特点：允许过程递归调用、也可以允许过程含有可变数组；过程定义不允许嵌套。
采用栈式存储分配机制。
嵌套过程语言（如PASCAL语言）：
特点：允许过程递归调用、也可以允许可变数组，过程定义允许嵌套。局部可以访问非局部名字。
非局部名字的访问的实现方法：静态链和活动记录；嵌套层次显示表Display。
嵌套过程语言的静态链方法（在活动记录中增加静态链单元）：
过程运行时，必须能知道它的所有外层过程的当前活动记录的起始地址。
静态链：指向本过程的直接外层过程的活动记录的起始地址，也称存取链。
嵌套过程语言的Display表方法（在活动记录中增加Display表方法）：
进入一个过程时，在建立其活动记录的同时建立一张嵌套层次显示表Display，自顶向下依次存放着当前过程、直接外层、…、直至最外层(主程序,0层)过程的最新活动记录的起始地址。