当前课程知识点:Compilers Techniques > 4 Syntax-Directed Translation > 4.1 Syntax-Directed Definitions > 4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
我们继续第4章的学习
在介绍过语法制导的定义之后
我们来学习语义规则的计算顺序
参考我们在第3章的学习
我们经过词法分析、语法分析之后
得到分析树
在上一讲中
我们介绍过了注释分析树
也就是在分析树的结点加上属性
之后我们通过构造依赖图
来确定语义规则计算次序
这也是我们本讲的主要内容
首先我们来介绍属性依赖图
结合上一讲中的注释分析树
我们在一棵分析树中的节点上
把它的属性标注在我们的分析树上
可以得到一个有向图
具体的针对每一个包含过程调用的语义规则
我们添加一个虚拟综合属性B
这个属性是在分析当前节点之后来完成
在依赖图中
我们为每一个属性设置一个节点
如果说属性b依赖于属性c
我们就从属性c的结点画一条有向边
指向属性B的节点
意味着在计算属性b之前
我们首先要完成属性c的计算
例如针对加法计算的分析树
由于我们是一个综合属性
意味着父节点的属性
是由子节点属性计算而来的
因此从每一个参数
也就是子节点的属性
有一条有向边指向它的父节点
如图所示
在我们的产生式E→E+E中
我们父节点的属性E.value
它是由两个子节点的属性计算而来的
因此我们两个子节点的属性
要优先于父节点属性的计算
在这种情况下
我们就有两条有向边
分别从两个子节点
指向它的父节点
来表示它们计算的先后顺序
我们再来看一个更复杂的例子
这是我们上一讲曾经介绍过的
属性声明的一个例子
有D→TL
T是它的属性
而L是一个标识符的列表
在产生式中
我们首先要获得三个标识符的属性
也就是它的符号表位置
在之后
我们可以计算出T的属性
它是一个综合属性
它是由它的子节点 int和real
得到整个句子的类型
再接下来
T的type属性会传递给L的in属性
意味着我们L整个变量列表
它的属性都是int类型
再接下来
因为我们要执行一个动作addtype
也就是为我们的符号表
添加一个类型信息
我们把这种规则
称为一个虚拟综合属性
它的阶段依赖于两个参数
一个是id.entry,一个是L.in
这个动作是要在(结点)5和3之后来完成
因此我们也有一条有向边
来标示出这样一个顺序
再接下来 L→L , id
我们子节点中的L的in属性
是由父结点传递而来的
因此有一条有向边从父节点指向子节点
再接下来是类似的
就是我们从id.entry和L.in
来调用我们的addtype
所以说也会有一个有向边
从两个依赖的参数
指向它的调用参数
这个过程一直继续
直到我们整个
分析树中的所有属性都完成计算
意味着我们整个的依赖图构造完成
这个就是我们的分析树
它的依赖图构造的顺序
再接下来
我们结合一个特定产生式来观察一下
结合我们的产生式D→TL来看
D→TL在我们的产生式的上部
在这个产生式中
我们的L的in 属性是由T的type属性得到的
因此它的有向边从4到5
意味着我们首先要计算
4对应的一个属性
然后把它传递给5
类似的 我们刚才提过
虚拟综合属性
它可以看成一个特殊的综合属性
它在完成L的分析之后来进行
并且在我们的函数调用中
addtype分别是3和5之后
也就只有在执行完3和5之后
我们才能够调用addtype
这个顺序计算
我们就要回顾一下
我们过去学过的知识
在数据结构这门课程中
大家应该学习过
拓扑排序这样一个概念
也就是给定一个有向图
我们要能够得到它的一个合理的遍历顺序
这个遍历顺序就称为拓扑排序
按照拓扑排序得到一个序列
我们就能够保证
每一次它的有向边
都是从它的尾节点指向它的头节点
例如根据这个依赖图
我们就可以得到一个可行的遍历顺序
例如像1、2、3、4一直到10
这个遍历顺序
它的特点就是
每一次我们出发
都是一个入度为0的结点
当我们执行完它以后
把当前结点删除掉
后续再从剩下的图中
得到一个入度为零的结点
迭代的进行
直到整个的所有结点
都完成遍历
我们得到就是一个可行的拓扑排序
当然值得注意的是
我们的拓扑排序
只是一个可行并且合理的排序
但是它并不是唯一的
例如我们考虑这样一个有向图
它有从1~7的7个节点
下面列出的三个
都是可行的拓扑排序
例如
7 6 5 4 3 2 1、7 5 6 4 3 2 1
这些都是可行的拓扑排序
我们选择任何一个
都是可以来完成属性计算的
但是要注意
如果说
我们的有向图中它存在环路
例如我们的A.s和B.i两个节点
它们如果存在循环依赖的话
就会在有向图中存在一个环路
例如考虑我们的产生式A→B
假设我们的A.s=B.i
但是B.i=A.s+1
这种时候
我们第1条规则要求
A.s 在 B.i 之后计算
而第2条规则要求
B.i 在 A.s 之后计算
这个时候 我们就无法确定
一个合理的拓扑排序
这就不是一个良好定义的依赖图
我们称
如果说一个属性文法
不存在属性之间的循环依赖
我们的这个文法
就是一个良好定义的属性文法
我们来做一个简单小结
一个依赖图的任何拓扑排序
给出的都是一个分析树中
语义规则计算的正确顺序
具体做法为
首先我们的基础文法
用于建立符号串的语法分析树
接着根据语义规则
我们建立依赖图
从依赖图的拓扑排序中
我们就可以得到一个
计算语义顺序的规则
到这个地方为止
我们就可以得到
一个合理的计算规则
也就是从我们的输入串
经过词法分析
语法分析得到分析树
然后构建依赖图
再之后我们遍历依赖图
经过拓扑排序
得到一个计算顺序
按照顺序
执行我们的语义规则
就可以完成对应的翻译动作
结合我们刚才的例子
在我们的依赖图中
我们可以通过拓扑排序
得到当前有向图的一个遍历顺序
把图中的编号顺序
从1~10就是一个合理的拓扑排序顺序
前三条规则由于比较简单
我们就简单略过
从第4点开始
在第4点中
我们进行了一个类型的赋值
接着在第5点
我们把赋值传递给我们的兄弟结点
再接下来第6步
我们调用过程addtype
给标识符赋一个属性信息
再之后我们再将属性信息
传递给它的子节点
后续addtype传递子节点
以及最后一个addtype
我们就可以完成整个分析树
它的一个语义计算
这个就是我们的语义计算的一个顺序
首先我们构造输入的分析树
第2步构造属性依赖图
(第3步) 对结点进行拓扑排序
最后按照拓扑排序
执行我们的语义规则
我们就可以完成整个的属性计算
然而值得注意的是
我们只是介绍一种可行方法
除了我们介绍的这种方法之外
还有其它的一些方法
例如可以有基于规则的方法
以及忽略规则的方法
第1种分析树方法
就是我们前面介绍过的方法
下面我们分别来看
其它的两种方法
在基于语义规则的方法中
我们的语法分析和属性计算是分离的
首先我们构造分析树
然后按照预先定义好的遍历顺序
来计算属性
语义规则的定义和计算顺序
是在编译器构造之前完成的
也就是它是一个静态的规则
分析树遍历策略的确定
要考虑语义规则的定义顺序
因此它是一个基于规则的方法
第3种称为忽略规则的方法
在进行词法分析的同时
我们来完成翻译
也就说我们
边分析边计算属性
计算次序由我们的分析方法确定
而语义规则是无关的
这种方法是有利有弊的
它的缺点在于这样计算的次序
它限制能够实现的
语法制导定义的类型
而优点也很明显
我们不需要构造依赖图
不需要对依赖图
进行拓扑排序
因此它提高了时空效率
这三种类型的方法
要根据实际的场景
来进行选择
没有哪一种是在所有情况下
优于其它的方法
谢谢大家
这就是本讲的内容
-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