当前课程知识点:Compilers Techniques > 5 Organization and Management of Run-Time Storage Space > 5.3 Calling Sequences > 5.3 Calling Sequences
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课我们继续学习第6章
运行时存储空间的组织与管理
在整个程序执行的过程当中
我们通过以往的学习了解到
它应该有代码区、有数据区
还有用来管理整个过程之间调用的栈区
栈区存放的
就是我们这一章重点学习的
活动记录的相应内容
除此之外,实际上
过程想要被调用
调用结束之后想返回
我们还需要其它的辅助
这个辅助
就是我们这节课所要讲的重点内容
也就是过程调用及返回
所需要的一些代码
这些代码的主要作用
就是来管理活动记录来入栈
然后保存和恢复相应的信息状态
也就是说
我们前几节
一直在讲的活动记录的内容
是如何进入到栈里面去的
以及程序运行结束之后
它又是如何被释放掉的
那么我们看它是通过过程调用序列
和过程返回序列来完成的
这个过程调用序列和返回序列
操作系统维护的
好像两支队伍一样
它也是两段程序
当一个程序被调用的时候
过程调用序列就会被激活
它来执行
把活动记录入栈的这样的一个工作
当程序结束之后
对应的活动记录要弹出栈
那么这样的工作
就由过程返回序列来完成
那么也就是这两部分
分处于调用过程和被调用过程当中
过程的调用和返回
即使对同一种语言来说
调用序列和返回序列
对应的次序也会有一些区别
那么对于这些活动记录入栈的原则
和出栈的方式
一般有一些基本的规定
比如说
会以活动记录当中某个位置
比如说控制链的地方
作为基地址
那么长度能够比较早确定的
放到活动记录的中间
比如说返回值
我们通常知道有几个它的类型
然后通常把临时数据
放到局部数据的后面
因为临时数据它一直在变化
放到栈顶的好处是
不用给它预留空间
你预留的空间有可能又不够用
这样就比较麻烦
把参数和有可能的返回值
放到紧邻调用活动记录的地方
这样的好处是
当你退栈的过程当中
程序执行结束
最后要拿到的就是相应的返回值
对同样的代码来执行
各个活动记录的保存和恢复
接下来我们就以一个过程调用另一个过程为例
我们来看一下
过程调用序列和过程返回序列
都执行着什么样的功能
假设过程 p 调用过程 q
我们当前在栈里存在的
就是 p 对应的活动记录
它调用 q, 它会先在栈里出现
接下来 p 要做的事
我要计算相应的实参
因为它得调用q 会把实参传递给q
依次放入到栈顶
并在栈顶预留返回值的空间
那么压栈的过程top_sp
就是栈顶的指针会往上走
对于栈来说,我们知道
堆是往高地址增加
而栈是往低地址增加
所以说
当我的栈顶的指针往上挪的时候
实际上这个地址的指针
指针的值是减小的
也就是说在这个过程当中
栈顶指针往上移
top_sp 的值在这个过程当中会被改变
接下来 p会把返回地址
压到 q 的活动记录当中
那么把控制转移到 q
我们看 top_sp 的值接着增长
接下来控制转移到 q 之后
所有的操作就由 q 起到主导作用了
那么 q 就把保存寄存器
相应的值和相应的状态
这里面就要把控制链压栈
控制链是什么
根据我们讲的活动记录的内容
它里面存放的调用它的这块记录
也就是P的记录中控制链所在的位置
它就好像是整个记录的一个基地址
插了一面小旗一样
那么整个没调用到 q 的时候
这面小旗的位置在这儿了
我们用 base_sp 指针来指向它
当我控制转移到 q
我需要把指针保存到这里
同时 base_sp 的指针也挪到这个位置
我们看就是这样
接下来 q就会根据局部数据
和临时数据的大小
来增加 top_sp 的这样的值往上走
那么这就是整个调用序列的过程
我们看对于活动记录的划分来说
从中间黑色的实线来划分
分别是 p 的记录以及 q 的记录
但是从它们执行的功能和责任来说
p 是把控制链和机器状态栈之后
这个责任才转移到 q
q 来负责其余的压栈的部分
那么第二点我们来看一下
整个过程调用结束之后
想返回到 p这个调用者
那是如何退栈的呢?
我们看
首先现在控制权在 q 这里
它会把返回值放到活动记录里
也就是说它调用结束计算出来一些值
先放到这里面
然后参数的个数可变的场合
我们通常要确定返回值的位置
(如果)不好确定,用寄存器来存放
这是常用的办法
然后接下来
q 对应调用序列的步骤4
来增加 top_sp 的值
增加 top_sp 实际上是退栈的过程
因为栈往下是越来越大
地址越来越大
那么退到这儿的时候
base_sp里面指向的是控制链的地址
这样就可以把里面的内容取出来
把base_sp 指向原有的控制链所在的地方
这样 top_sp 就可以一直往下降
降到最后,就可以根据类型和返回值
调整 top_sp
取出返回值
整个调用结束
那么在这里面
我们接下来了解几个个例
也就是说,整个调用和返回
基本是刚才讲的这样的一个过程
但是不同的语言
会有一些特殊的情况出现
比如说参数
过程的参数有可能会出现
可变参数的这样的情况
第一种方式
我们可以改用寄存器来传递参数
这样也就是说参数这部分
我们就不放在活动记录里了
另外还有一种办法是什么呢?
我把参数计算完之后
实参来逆序的进栈
意思是说逆序进栈,先出现的后进栈、
后出现的先进栈
这样在退栈的过程当中
我就会先拿到第一个参数
通过第一个参数
我就可以找到
接下来会出现几个参数
这些参数的值分别是什么
这就是整个逆序进栈参数的
另一个解决办法
有的同学可能觉得
这种方式不常用
实际上并不是这样
我们在学习语言学到的第一个编程语言当中
用到的一句话
printf 实际上就是一个可变参数的实例
我们看这里面printf 的第一元
是一个双引号引出的一个字符串
在这里面我们可以给出
后面将会出现多少个参数
比如说三个 %d
我们知道 printf 后面还会出现三个参数
那如果我写错了的话
这里面只有一个双引号引出的字符串的话
后面并没有给出三个整数
那会出现什么样的效果呢
我们联系我们这节课讲的内容
我们会考虑到
它会产生对于它的一个逆序进栈的代码
也就是说我退栈的时候
我会先拿到这个字符串
通过字符串的分析
我分析下面会接着有三个整数出现
因此
我就会从这个字符串所在的位置往下
4个字节当成是1个整数
把它翻译成整数打印出来
所以说这就是为什么
尽管后面的参数缺省
我仍然能够通过这句话
打印出三个整数的原因
那么接下来我们看还有一个特例
就是栈上可变长的数据
比如说 Java 语言
是把一些可变长的数据放到堆上
那么对于其它的语言
还有另一种方式是什么呢
也就是说
当我程序调用的过程当中
如果某一个变量
我当前并不能确定它的大小
比如说可变数组
需要用户给我敲定一个整数
我才知道我这个数组有多大
这种方式我可以
在这个记录里面
先保留对应数组的指针
然后当确定它的大小之后
把相应的空间放到栈顶
这样它的灵活性就比较高
这个指针就指向
它所分配的这样的位置
这样就保证了
我不用在活动记录里事先预留空间
这样灵活性
可以有效的来提高
那么对应的我们看
这就是 这是 p 的活动记录
在这里面对应的局部数据只放指针
然后对应的数据放到栈顶
这是 p 的活动记录、p 的数组
同理可以放 q 的活动记录
以及 q 的数组
最后大家在写程序的过程当中
学习了我们这一章的内容
要注意
不要引起悬空引用的情况
比如说这里面
定义了一个 main 函数
它这里面调用 dangle 这个函数
调用这个函数它的返回是一个地址
是谁的地址呢?
这个局部数据大家看
这个 j 的这样的地址
我们知道
根据刚才所学
dangle 调用结束之后
这块空间就会被释放掉
那么你再返回它的地址
能够返回回来
但是没有任何意义
你再对它操作
实际上这已经是一块被释放的无效的内存了
那么这种操作往往是不允许的
如果写到程序里
往往会引起漏洞
和程序执行结果的不稳定
最后我们来介绍一下
堆式分配
对于堆的了解
大家应该是还停留在
学习 C语言的时候
我们可以自由申请一块空间
这块空间用完之后可以释放掉
实际上堆的这种分配
往往也可以用到记录活动记录的
这样的一个方式上
那么过程停止之后
局部数据的名字还必须要维持
你想要不用这块内容了
需要手动的来释放
那么它内存的释放
可以按照任意的次序来进行
我可以任意时间来分配
任意时间想释放的时候可以释放
那么它可能包含交错的、正在使用的
和已经释放的这样的区域
不像栈里的内容那样连续
就好像栈好比是一个柜子
你往里面放衣服
一定是都是挨着的
但是堆里有可能
它们之间
存在着很多这样的空白的地方
我们接下来就用一个活动树
来对比一下
活动记录在栈里和堆里的区别
我们看左侧的活动树
就是过程s 调用r
然后调用q 这样的一个过程
对于栈来说
在栈里会先出现s 的活动记录
调用完 r 之后会被释放
现在调用到 q 里面
就没有 r 的活动记录了
而对于堆来存放活动记录这种情况来说
我们看会出现 s 的记录、r的记录、q的记录
如果r 不被显示的释放的话
那么它会一直存在
那么这两块记录的指针
都会指向s,也就是它的父节点
这就是它们存放在不同位置的区别
以上就是本节课的内容
谢谢大家
-1.1 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
-2.2 Regular form
--2.2 Regular form
-2.3 Finite automata
--2.3 Finite automata
-2.4 DFA construction, Subset construction, Simpleset DFA
--2.4 DFA construction, Subset construction, Simpleset DFA
-2.5 Lex
--2.5 Lex
-3.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes
--Syntax-Directed Definitions
-4.2 Bottom-Up Calculation of S Attribute
--4.2.1 Bottom-Up Calculation of S-Attributed
-4.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--4.3.3 Design of Predictive Translator
--L-Attributed Definitions
-4.4 Bottom-Up Parsing of L-Attributed Translation
--4.4.1 Bottom-Up Parsing of L-Attributed Translation
--4.4.2 Simulate the Parsing of Inherited Properties
--Bottom-Up Parsing of L-Attributed Translation
-5.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-7.2 Target Machine
--Target Machine
-7.3 Basic Blocks and Flow Graphs
--7.3 Basic Blocks and Flow Graphs
-7.4 A Simple Code Generator
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava