当前课程知识点: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》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课我们来学习第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这样的结果
那么以上就是我们这节课所讲的内容
谢谢大家
-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