当前课程知识点:Compilers Techniques >  5 Organization and Management of Run-Time Storage Space >  5.2 Global Stack Storage >  5.2 Global Stack Storage

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

5.2 Global Stack Storage在线视频

下一节:5.3 Calling Sequences

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

5.2 Global Stack Storage课程教案、知识点、字幕

各位同学大家好

这节课我们继续学习第6章的内容

运行时存储空间的组织和管理

那么在这一节当中

我们重点学习

其中的存储分配的内容

对于局部数据的存储

在上一节当中我们介绍过

它会受到目标机器寻址方式的影响

那么还有一点需要大家注意的是

在存储的过程当中

为了考虑效率等相关方面的因素

我们会在其中空余一些空间

具体来说

我们以这个例子来看

我们看

左右两个都是结构体

左侧的结构体称其为_a

定义了一个char,一个long

接下来又是一个char

接着是一个double

那么右侧的这个(结构体)

同样的是两个char

一个long,一个double

也就是说

它们定义的数据类型都是一样的

个数也相同

只不过是顺序有所区别

不同的是

如果我们看两个结构体的大小

会发现

左侧的大小是20

右侧的是16

也就是说定义同样的数据内容

只是变了顺序

两个结构体的大小就不同了

为什么会这样呢?

这就是由衬垫空白区来引起的

下面我们就通过这个例子

来了解一下两个结构体

分别是怎么样来对齐的

通常对齐有这样的要求

要考虑两方面的因素

第一方面就是变量本身所占的字节的大小

另一方面就是当前程序所要求的对齐方式

两者取一个较小者

我们以 _a 这个结构为例

我们看第一个变量是 char 的 c1

那么这个变量它是 char

所占的字节就是一个字节

通常程序要求 4 字节对齐

4 和 1 会取一个较小者

那也就是 1

这意味着什么呢?

这就意味着

当前的 c1

要存放在是 1 的整数倍的地址上

我们知道所有的地址都能被 1 整除

因此 c1 就可以存放在任意的位置

我们假设整块内存

是从地址零开始的

我们就可以从这开始来放 c1

c1 放好之后

接下来我们看 long 的 i

long 占 4 个字节

然后整个程序要求 4 字节对齐

4 和4 取较小者,仍然是4

所以我们要求 i 的变量所存放的位置

也就是它的门牌号

需要能被 4 整除

那么很显然 c1 存放完之后

接下来的门牌号是 1

它不能被 4 整除

怎么办呢?

我们可以空出一定空间

我们看就可以空出 3 个空间

这样就到了 4

这样的一个门牌号

这样的一个地址

这样来存放 i 这4个字节

接下来 c2 它的情况和 c1 相同

任意存放

所以可以连续的来放

接下来遇到的是double型的 f

它占8个字节

程序要求 4 字节对齐

4 和 8 取较小者是4

所以在这里我们很显然

不能从9这个位置来存放double

我们需要再空出 3 个字节来到达 12

12能被4整除

所以从12开始来放 double型的 f

我们就到了20

这就是为什么 _a 这个结构体占20个字节

我们接下来看一下 _b 这个结构体

又是如何存放的呢?

我们看它和 _a 的区别在于

两个 char 的变量被放到了一起

放到了前面

进而是 long 型的变量和 double 型的变量

根据刚才所学两个 char 的c1、c2 会先存放,挨着存放

因为它们没有对齐的要求

接下来要存放 long 的时候

我们只需要空出两个字节就可以了

而恰好在 long 型的 i 结束之后

我们想存放 double型的 f

它是从可以被 4 整除的、

编号为 8 的这样的地址空间开始的

所以我们看整个的

这样写完之后的结构体

它的大小就是16个字节

那么从这个例子当中

我们可以看出

大家在写程序的时候

也尽量写成 _b 这样结构体的这样的形式

可以为大家节省一些内存的空间

好, 那么接下来

我们再来学习一部分内容

就是程序块的相关内容

对于程序块来说

大家可以给它看成是一个

没有函数头的函数体

也就是说用大括号括起来的一部分函数块

这样的程序块

比如说

通常

我们可以把从这儿一直到这儿

这样的一个程序段

看成是一个完整的程序块

它有变量

还有相应的执可执行语句来构成

那么对于其中的变量的使用

我们通常采用

最临近的作用域的规则

也就是说

我们看整个的B程序块里面

又包含了两个小块

分别是B1,还有B2

那么在B1当中,用到 a=3

我整个的在B1的这个块里

没有我去哪去找呢?

去它的直接外层去找

这就是程序块

它的对应的变量寻找的方式

那么并列的程序块不会同时活跃

也就是说B1执行完才会执行B2

那么我们通过一个例子来看一下

这里面的变量

它的使用顺序执行过程

左侧是一个例子

我们来看整个的程序块是 B0

这是 B0 的开始位置

它的结束位置

在 B0 里面定义了 int a 和 int b

因此 int a=0 它的作用范围

我们看,就是在 B0 这个范围内

因为到 B1 的时候

我们就把 b 这个值改成 1 了

所以我们看 a=0 的范围就是

B0 除去 B2 的范围

因为在 B2 里,我们把 a 改成了 2

其余的过程,a 的值都是0

那么 b 等于 0 的作用范围

一进到 B1 里 b=0 就被改变了

所以 b 等于0的作用域范围

是 B0 除掉 B1 这部分

那么 b 等于 1 的作用范围呢?

大家看一下

红色的部分就是 B1 的程序块

它初始的 b 是等于 1 的

然后到 B3 的位置

我们看 b 就改成 3 了

所以在这里面 b=1 的作用范围

就是 B1 的程序块除去 B3 的作用范围

同理 a=2 和 b=3

那就分别是 B2 和 B3 所在的位置

接下来我们来学习

在存储过程当中

三个最基本的存储策略

分别是全局、栈式、

还有堆式的存储分配策略

这三种存储分配策略

对应的内存在不同的位置

比如说栈式分配策略就在栈里

堆式在堆里

静态数据区就是对应的

静态存储策略的分配

首先我们先来了解第一部分的内容

也就是静态分配

对于静态分配来说

名字通常在编译阶段

就会被绑定到存储单元里面去

那么绑定的生存期

就是程序的整个运行时间

控制再一次进入这个过程的时候

原有的变量里面的内容是不变的

如果用它来存放活动记录的话

那么每个活动记录的大小也是固定的

采用静态分配

早期的fortran语言是采用这种方式来分配

但是它有一定的局限性

它是不允许递归的

那么 C语言的外部变量

和程序当中出现的常量

也可以采用静态分配的方式

我们常见的就是一些全局变量

我们知道每个程序都可以去使用

这样的量就是采用静态分配的

此外在程序内部

有一些局部静态变量

大家可以回忆一下

在学习语言的时候

那些加 static 关键字的这样的变量

也是存放在静态数据区

采用静态分配的策略

那么这是刚才列举的两个例子

静态分配

会对早期的语言带来一定的限制

比如说递归是不被允许的

原因是过程每次过来之后

这个变量都是不变的

都是上一次执行的值

那么递归过程不可以

而且数据对象它的长度、在内存当中的位置

必须得编译期间就能够知道

不能够动态的建立数据结构

这都是它的局限

接下来我们来了解

栈式存储分配策略

这也是用的最多的一种存储分配方式

栈式主要是用来管理活动记录

也就是上一节当中

我们学习的活动记录

就存放到栈里面

那么局部变量是和栈绑定到一起的

因为它是活动记录的一部分

可以说它和栈的内容

是同时出现、同时消亡的

控制进入这个过程的时候

局部变量就会入栈

绑定到相应的存储单元里面

那么过程结束之后

局部变量对应的空间被释放

对应的那块活动记录

也会被弹栈也消失

那么接下来我们来了解一下

为了能够控制

这个过程之间的调用和转移

我们可以把过程调用的先后顺序

用活动树来表示

也就是可以用活动树

这样的树形结构来描绘

控制进入和离开活动的方式

以左侧这个图为例

就是过程先调用 m 函数

进而调用 r 函数

r 调用结束之后,调用 q 函数

实参是2和3

在 q 函数执行的过程当中

分别调用了 p(2, 3) q(2, 1) 和 q(3, 3)

处在整个树形结构同一层级的过程

它们是有调用的先后顺序

那么父子关系的这样的节点

表示的是调用和被调用的关系

我们看活动树的特点就是

每个节点来代表过程的一个活动

根节点代表主程序

节点 a 是节点 b 的父节点

比如说 m 是 q 的父节点

那就表示 m 来调用 q

那么如果 a 处在 b 的左边

比如说这里面 p 处在 q 的左边

它的意思就是先调用 p 后调用 q

接下来我们来看

对于一个活跃的过程来说

比如说我们这里红色标识的

当前执行到 p(2, 3)

在栈里

都会有哪些过程的活动记录呢?

根据刚才活动树的描述

我们知道

如果执行到 p(2, 3)

那么它的父亲以及父亲的父亲 m

都仍然存在在内存当中

那也就是整个过程执行的顺序从 m 开始

到它q(2,3),到它p(2,3),这样一次过来

那么控制栈里的内容

那就是 m,q(2, 3) 和 p(2, 3)

那么整个过程

如果想把整个过程执行的顺序

给它展示出来

实际上你用深度优先搜索的方法

得到的节点

依次出现的节点

就是执行的顺序

那么最后我们通过运行栈

来把活动树

和在栈里的活动记录的整个出现的过程

结合到一起

我们看从 main 函数开始

main 函数最先调用

它的活动记录会先入栈

进而调用到 q(1, 9) 这个函数的时候

那么 q(1, 9) 的活动记录

我们看两个红线之间的内容会入栈

接下来调用到 q(1, 3)

最后调用到 q(1,0)

那么整个这些都是在栈里会出现的

我们来动态的演示一下这个过程

main 函数最先出现

那么在栈里它的活动记录也会出现

进而调用到 r 这个函数

r 的活动记录入栈

r 调用完之后调用 q

那么 r 这块空间就会被释放掉

进而 q 的活动记录入栈

再接下来

调用到 p 这个函数

p 调用完之后调用 q

这块空间也会被释放掉

进而 q 的活动记录进来

那么最后就是再调用p,p弹出去

然后调用q,q的活动记录进来

以上就是我们这节课讲的内容

谢谢大家

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.2 Global Stack Storage笔记与讨论

也许你还感兴趣的课程:

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