当前课程知识点:Compilers Techniques >  5 Organization and Management of Run-Time Storage Space >  5.4 Non Local Names >  5.4 Non Local Names and dynamic scope

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

5.4 Non Local Names and dynamic scope在线视频

下一节:6.1 Overview of Intermediate Code Generation

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

5.4 Non Local Names and dynamic scope课程教案、知识点、字幕

各位同学大家好

这节课我们来学习第6章

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

最后一部分内容

这节课我们来学习变量的访问

也就是说

我们了解了程序之间的调用之后

那么这些变量是如何来获取的呢?

我如何能够访问到

非局部的这样的变量呢?

我们来看

在这节课我们会介绍到过程内部

是如何访问过程外部声明的名字的

主要的来说

我们会介绍两方面的内容

第一个是静态作用域

另一方面是动态作用域

在静态作用域里

包含两点

第一点是无过程嵌套的静态作用域

另一点是有过程嵌套的静态作用域

好,那么首先我们看第一点

无过程嵌套的静态作用域

这一方面

实际上

我们现有的很多高级语言

都是采用这种方式

大家可以以 C语言为例

了解它的特点

我们知道

在写 C语言的程序的时候

我们是在定义的过程的当中

是不需要过程嵌套过程的

这就是没有过程嵌套的这样的含义

那么当要使用一个变量

在局部的函数里面没有的时候怎么办呢

所用的办法

就是去全局区域去找

这就是没有过程嵌套的

想访问非局部的(变量)

唯一的解决办法

那么在这里它的好处是

不用深入到栈里面去取数据

过程可以作为参数来传递

也可以作为结果来返回

这一点在编程的过程当中

大家应该有所了解

那么接下来我们重点来看一下

有过程嵌套的这样的作用域

它是怎么来访问非局部数据的

我们以Pascal为例

我们看

以 sort这个函数为主体的

这样的一个定义

里面包含了

readarray、exchange 还有quicksort

这样三个过程

也就是说

sort 是最外层的这样的一个过程

里面还包含了三个

除此之外

quicksort 这个过程里面

又包含了一个过程叫 partition

从这里我可以看出

sort 如果看成是最外层、第1层的话

那么readarray、exchange 还有 quicksort

可以看成第2层

那么在 quicksort 里面的 parttion

就可以看成是第3层

那么我们可以把过程的嵌套深度

看成是当前变量所在的深度

也就是说如果在 partition 里面定义的变量

那么我们认为它的层数就是三层

在sort 里面、readarray 外面定义的就是第1层

同理在这三个里面

分别定义的就是第2层

接下来我们来以一个实际的例子

来看一下

如果我想访问的变量

我本身不存在

我基本的想法是根据刚才我们讲的

上一节讲的过程体为例的话

我们应该上我的直接外层去找

我怎么知道

我的直接外层在哪里呢?

实际上就是通过我们活动记录

当中的一项

也就是访问链来找到的

我们看 s这个过程调用 q这个过程

s是第1层

q这个过程quicksort是第2层

那么 s就是 q的直接外层

因此访问链的指针

指向的就是 s的活动记录

同理

我们看这个例子

s调用q(1, 9)

q(1, 9) 调用q(1, 3)

按照调用过程来说

它们之间是s调用q(1, 9),q(1, 9)调用q(1, 3)

它们应指的控制链

应该是在指向这儿,再指向这

但是访问链

指向的永远是在静态正文里面

它的直接外层

因此

q(1, 3)和q(1, 9)

指向的都是s的这块记录

同理

我们可以得到

其它的这样的例子

也就是说访问链的建立

和调用无关

只和静态正文的

包含与被包含有关系

接下来我们以一个实际的例子为例

来看一下

对于非局部的变量

我们是如何通过访问链来得到的

我们看这个例子当中

sort是第1层

readarray、exchange还有quicksort是第2层

partition是第3层

那么假设过程p的嵌套深度是np

它引用嵌套深度为na的

这样的一个变量a

na的深度小于np的这样的深度

我们应该如何去找到它呢?

举个例子来说

就是这里面

q的深度

我们看它是2层

它想引用深度为1层的sort这样的变量

要如何找到呢?

这样就可以通过访问链

它根据它们之间的深度的差别

来追踪这个访问链

也就是说

我们可以从栈顶的活动记录开始

追踪访问链np-na次

达到 a声明所在的活动记录

就可以完成了

也就是说

比如说在partition当中

我们要访问变量a

而这个变量a

它所在的层是1层

partition所在的层是3层

它们之间差了2层

这2层之间

就是我们要追踪访问链的次数

那么追踪两次就可以到达

它要的变量所在的位置

那么我们以这个为例

我们看假设

p这个过程里面

想访问s这个过程里的变量

s是1层,p是3层

3和1作差2层

因此我们就可以追踪两次

我们看就可以达到

它想要的变量所在的位置

那么这里

同理黑色的是差1层的

这样的一个结构

那么接下来我们看

达到了你所要的活动记录以后

我还要在活动记录当中

定位到变量所在的位置

通常的办法就是

定位到位置之后

通过活动记录的基本的偏移

来找到这个变量在哪里

那么这个基地址我们说过

通常是以控制链所在的位置作为基地址

那么这个偏移就可以

它在活动记录当中

差了多少个字节

这样来表示

我们就可以得到

对应的位置了

那么了解了

活动记录当中的访问链怎么用

接下来我们来学习

如何建立它

也就是说

我们是怎么样把访问链给它建成的呢?

这种指针的指向是如何完成的呢?

我们以两种情况分别来分析

假设嵌套深度为np的过程p

来调用嵌套深度为nx的过程x

有可能深的来调用浅的

也可能浅的来调用深的

我们分两种情况来讨论

第一种就是np小于nx的情况

也就是说

p的过程

它的层数是比较浅的

我要调用深度为nx的这样的过程

要调动比较深的这样的过程

那么我们看通常这种调用

我们在Pascal里面是不允许跨层的

也就是第1层

我只能调用第2层

第2层只能调用第3层

因此我们看x肯定就声明在p里

比如说

sort调用readarray

那么readarray的活动记录

对应的访问链的指针

它的直接外层就是它的调用者

直接指向sort就可以了

我们来看几个例子

比如说这里面的s调用q

1层调用2层

指针直接从2层指向1层

同理,q调用p,

2层的调用3层的

3层的直接指过的2层

就可以了

这种情况比较简单

接下来我们来看

建立访问链的过程当中

另外一种情况

同样是np来调用nx

不同的是 np>=nx

也就是说

层数深的来访问层数浅的这样的情况

举例来说

比如说 partition来调用readarray这个过程

如果是这样的话

那么很显然

readarray它是第2层

它要指向第1层

而调用者是第3层

很显然不能直接指向它

我们应该怎么样来做

我们来看

在这种情况下

是深的来调用浅的

那么我们就可以根据

调用者已经建立的访问链

来找到被调用者nx的直接外层

那也就是说

它们的外围过程都相同

以刚才为例

第3层我来调用第2层的过程

第2层应该直接指向第1层

第1层怎么找呢?

我就可以从调用者第3层的过程开始

追踪访问链一次到第2层

再追踪一次就到第1层了

因此我们可以追踪np-nx+1次

就可以达到相应的nx要指向的

活动记录所在的位置

我们举例来说就是这里面

比如说q(1, 9)用q(1, 3)

它们的层数相同

那么我们要追踪几次呢?

q(1, 9)在第2层

q(1, 3)也在第2层

它要指向的是q(1, 3)所在的这样的位置

2-1=1

需要追踪的就是2-1,就一次

通过它追踪一次到s

因此它的访问链就可以指过来了

同理,在这里面我们看

partition调用exchange

partition是第3层

exchange是第2层

2-1=1

3-1=2

因此在p这里追踪2次到达s

我们就可以把 e的访问链

给它建立起来

这就是在另一种情况下

访问链的建立

接下来我们来学习

本章的最后一项内容

也就是动态作用域

它的访问方法

通常我们了解的

都是静态的作用域

这个意思是说

我要访问什么

我在编译期间

就能够确定下来

要访问的值

我也了解也清楚

动态作用域

它和程序的执行过程是相关的

也就是说

我要访问的变量

我局部没有的时候

我去哪找呢

和静态正文无关

和调用有关

谁调用我就去谁那儿找

如果找不到怎么办

再去找它调用它的父节点

所对应的内容

这就是和静态作用域的

一个本质上的区别

我们看实现动态作用域的方法有两种

一种就是深访问

另一种叫做浅访问

所谓深访问

就是深入栈中取数据

也就是说

我既然要的变量和调用有关

我就可以通过控制链

找到调用我的父过程

进而再调用

再找到调用我的服务过程

依次找下去

就可以找到我想使用的变量

那么缺点就是

需要深入到栈里面取数据

常用的方法是第二种,叫做浅访问

什么意思呢?

就好像在寄存器里

开辟了一块公共的空间

每一次

当我要给一个变量重新赋值的时候

那么我把当前的变量

存到我的活动记录里

然后把我当前的新的更新的值

放到那块公共的空间去

这样就保证了

如果一个程序被调用的时候

用到这个变量

它去那块公共的空间

就能找到当前它最新的值

而当它的父节点结束调用之后

就需要把这个值再恢复回去

这就是浅访问的整个过程

我们可以通过一个实际的例子

来看一下

我们看这个程序

这个程序叫dynamic

这个程序里面

定义了一个全局的变量r

然后定义了两个过程

分别叫做show和small

在show里面什么也没有做

做了一个print

write在Pascal里面相当于C语言的print

这样的打印r的这样的一个值

在small这里面

给r重新赋值成了0.125

那么这里面我们来看一下

调用完 Small

在r赋值结束之后

又调用了show

调用完show之后再表示end

我们来看begin和end

从begin和end的结束

这相当于我们C语言当中的main函数的位置

从r开始r=0.125

我们看在这里面

并没有对r进行定义

这里面用的r

就是全局变量r的值

这个时候我们看,接着往下来

先给r赋值0.25

那么在全局的静态数据区

r里面写入的值就是0.25了

接下来调用到show

调用到show的作用

就是把这个r打印出来

因此在全局的数据区里面是0.25

打印出来的也是0.25

再接下来我们看会调用到small

调用到small的时候

这里面

对r进行了重新的赋值

而且这里r有重新的定义

那么这个办法就是

我们要用浅访问的话

small的这块区域

就需要把全局静态区的0.25

给它保存起来

然后把自己重新更新的0.125

写入到静态数据区

这样在small调用show的时候

show永远都上全局静态那去看

看到的是0.125

因此打印的就是0.125

再接下来打印回车

那么对应的退栈

接下来和上面的过程是相同的

先调用show,再调用small,再打印回车

那么最后我们得到的

还是0.25和0.125这样的结果

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

谢谢大家

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.4 Non Local Names and dynamic scope笔记与讨论

也许你还感兴趣的课程:

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