当前课程知识点:Compilers Techniques >  5 Organization and Management of Run-Time Storage Space >  5.3 Calling Sequences >  5.3 Calling Sequences

返回《Compilers Techniques》慕课在线视频课程列表

5.3 Calling Sequences在线视频

下一节:5.4 Non Local Names and dynamic scope

返回《Compilers Techniques》慕课在线视频列表

5.3 Calling Sequences课程教案、知识点、字幕

各位同学大家好

这节课我们继续学习第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,也就是它的父节点

这就是它们存放在不同位置的区别

以上就是本节课的内容

谢谢大家

Compilers Techniques课程列表:

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-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.2 Regular form

-2.3  Finite automata

--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 Syntax Analysis

-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.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--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.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--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 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--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

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

5.3 Calling Sequences笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。