编译原理(4)存储空间

正文索引 [隐藏]

编译原理:存储空间

啊~肝 TM 最后一部分,波波李赐我力量

经过词法、语法、语义分析,如果忽略代码优化,编译程序就能跑通了,但是在语义分析的介绍中没有仔细介绍数据在运行的时候是如何存储的,这部分就要学习这个问题

一、符号表

存放程序中名字的信息(内情向量表、标识符信息)

编译程序必须收集和利用出现在源程序种的名字的信息:

  • 表示名字的字符串
  • 种属(简单变量、数组、过程)
  • 名字的类型(int, char, str 等)
  • 与分配存储单元相关的信息

符号表就是管理这些信息的数据结构,当然语法分析、语义分析的时候同样在完善符号表

  • 扫描源程序时,遇到一个名字就检索表,若它是一个新的名字,就填表

  • 词法语法分析时,还要把有关的信息填入(如标号的链,定义等)

  • 语义分析时,用它来检查名字的使用是否与它们原先的说明一致,如GOTO L , L为标号

  • 代码生成时,需要了解必须给名字分配多少,以及哪一种存储

一般的符号表长这个样子:
符号表
可以单独构造常数表、变量表、过程表、标号表;不过也可以把这些全部扔到一张表里。这是两种不同的设计思路。

符号表的功能

  1. 确定一个给定的名字是否在表中
  2. 填入新的名字
  3. 访问所给名字的有关信息
  4. 对给定的名字,填写和更新它的有关息
  5. 删除一个或者一组名字

信息栏都填些什么?

  1. 表示名字的字符串+编号,如果多个程序块或过程中可以使用同一标识符,则必须指出这个名字属于哪一个程序块或过程
  2. 名字的属性(包括类型和种类)以及识别名字用途的信息(标号、形参、数组)
  3. 参数(维数、下标的上下界)
  4. 描述分配给名字存储单元的位置的偏移量

内情向量表(又称数组信息表)

还记得在语法分析中提到的,数组仅有名字存在符号表中,其他信息会专门开辟一个内情向量表进行存储,然后将内情向量表的地址存在符号表的信息栏中去,如下图所示:
内情向量表

其他至于表的结构如何设计、如何快速查找、删节、排序,都是数据结构的知识,不再讨论

二、运行时存储空间

这一部分主要是要搞清楚代码在运行的时候,各种变量、常量等用户定义的量是如何存放的,如何去访问它们,生成四元式的过程相当于构建汇编程序的代码段,而存储空间分配就相当于构建数据段、堆栈段。

1. 常见的存储分配策略

静态、动态存储的概念

  • 静态:编译时完全确定所有数据项存储空间的位置,针对:常量、全局变量、静态变量
  • 动态:不能完全确定
    • 栈式:自动完成,在内存中先申请后先释放,地址由高到低,针对:参数、返回值局部变量
    • 堆式:编程者手动申请,何时释放一般可有编程者手动设置,有时候需要手动释放(比如 C 中的 malloc),地址由低向高,针对:程序员申请的动态内存

存储空间典型划分

存储空间典型划分
PS:下端地址比上端地址小

  • 代码区:存放目标代码
    • 过程名、过程代码关联
    • 区域大小静态可确定
  • 静态区:存放数据对象
    • 尺寸可静态确定的数据
    • 全局变量、静态变量等
  • 栈:保存过程调用所用数据对象,地址由高到低
  • 堆:动态申请的空间,地址由低到高

2. 过程的活动

定义:过程的一次执行称为过程的活动。比如:过程 p 的活动是从调用 p 时开始,p 返回时结束,这个时间段被称为该过程活动的生命期

表示方法——活动树

用一颗树来表示整个程序运行时所有过程的活动
过程的活动树

  • 过程调用的序列和先根序遍历活动树一致
  • 过程返回的序列与后根序遍历活动树一致

活动记录:过程的存储空间

活动记录是非常重要的,是栈区的一段数据,内部构造如下:
活动记录

  • 实在参数区:按形参-实参结合原则,保存调用该过程时的实参值
    可约定前几个放在寄存器中,但默认全放栈上
  • 访问链:非局部变量访问链指针
    注意,这个还可以构造一个 Display 表进行算法查找优化,不细说啦
  • 控制链:指向调用过程活动记录的指针
  • 机器状态区:调用该过程是的机器状态(返回地址、返回时需要恢复的寄存器状态)
  • 局部数据区:过程声明的数据对象
  • 临时变量区:代码生成过程中产生的临时变量
  • 返回值:单独一个区域或者预定存放在指定寄存器中,默认后者

举几个栗子:
活动记录2
活动记录5

活动记录的访问

由于活动记录存储在栈区里,数据结构属于栈,那么访问它就需要两个指针,一个 sp 指针标出过程活动记录区的栈顶,一个 fp 指针指向当前活动记录的控制链,通过 fp + 变址 的方式访问所有单元:
活动记录3

  • fp + 2 = 首个实参
  • fp + 1 = 访问链
  • fp = 控制链
  • fp - 1 = 返回地址
  • fp - 2 = 局部数据区
  • fp - 3 = 临时变量区

ps:不考虑机器字长,简化模型

还有一种分配方案是,用 TOP 指针指向最高位(栈底),用 SP 指针指向最低位(栈顶),不细说了。

活动记录的创建

比如说 A 过程 CALL 了 B 过程,此时 fp、sp 还都在 A 的活动记录相应位置,B 的活动记录就会如下创建

  1. 实参求值并保存在形参单元
  2. 修改 fp:
    • push fp
    • fp := sp
  3. 保存返回地址
  4. 分配局部变量和临时变量的单位
  5. 将控制流跳转到被掉过程代码入口

参数传递

左值右值

  • 左值:既有单元又有值,如变量、下标变量、临时变量等
  • 右值:只有值,如常数、表达式的值等。

参数传递过程

  1. 调用者计算实参值
  2. 被调用者的形参与实参建立对应

参数传递的方式

int f(b){
    A[1] = 3;
    i = 2;
    write(b[i]);
    b[i] = 5;
    return b[i]
}
  • 传地址:实参作为左值其地址放到形参单元中;被调过程中凡是引用形参 p 均解释为引用 *p

    int a[3] = {6,7,8};
    f(&a[0]);
  • 传值:实参值放到形参单元中

    int a[3] = {6,7,8};
    f(a[0]);
  • 得结果:调用时按照传值方式传递实参值到形参单元中,返回时要将形参单元内容拷贝到对应实参单元中

    int a[3] = {6,7,8};
    a = f(a[0]);
  • 传名:类似于宏扩展,将实参看做字符串,替换掉被调过程中对应形参的每一次出现;执行被调过程时是执行替换后的代码。

    int a[3] = {6,7,8};
    f(a)

    ps:传名这个例子不是很恰当,因为 C++ 中不允许这么做,大概意思是可以把 a[i] 当成参数传进去,i 会随着 子过程中 i 的变化而变化

过程作为参数的处理

program closureEx(output);
procedure p(procedure a);
    begin
        a;
    end;

procedure q;
    var x:integer;

    procedure r;
        begin
            writeln(x); 
        end;

    begin
        x:=2;
        p(r);
    end;

begin
    q;
end;

调用过程:q -> p(r) -> r

  • q 建立 p 活动记录:q 访问链走过 i-k+1 作为 p 的访问链,i、k为q、p层数

  • p(r)建立r活动记录

    • r 的调用者为 p 但可认为是 q,比如 p 中调用 s(r)…
    • 沿着 q 访问链走过 i-k+1 步作为r的访问链,k 为 r层数
    • 所以在 p(r) 体执行时必须知道 q 活动记录,这就决定了 r 实参内容

超长实参的处理

  • 超长的实参放在临时变量区

    • 过程闭包
    • 数组A作为实参
  • 实参是指向该存储位置的指针

简单栈式存储分配

简单栈式存储

这种存储分配方式是 C 系列语言常用的,具体约束如下:

  • 没有分程序结构

  • 过程定义不允许嵌套

  • 允许过程递归调用

  • 允许过程含有可变数组(但不允许全局可变数组)

这样过程调用时生成的四元式序列就是:

par T1, _, _
par T2, _, _
...
par Tn, _, _
call P, n, _

执行时对活动记录的操作:

  • par 执行参数压栈

  • call 执行:

    fp 修改

    保存返回地址

    分配局部变量和临时变量的单位

    将控制流跳转到被掉过程代码入口

总结

​ 这篇文章只是非常浅显、囫囵吞枣式的概述了下程序运行时存储空间,Display 表、堆式存储分配都没有涉及,但是 TMD 我是真的肝不动了,并且真实生产环境中的编译器的运行存储空间肯定不长这个样子(比如 VS 系列妖孽级的异常处理系统,怎么可能靠这些简单的结构实现啊啊啊)。

​ 好了好了,狗不动了,期末保命要紧,刷题去了 T_T