4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes在线视频

各位同学大家好

我们继续第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种称为忽略规则的方法

在进行词法分析的同时

我们来完成翻译

也就说我们

边分析边计算属性

计算次序由我们的分析方法确定

而语义规则是无关的

这种方法是有利有弊的

它的缺点在于这样计算的次序

它限制能够实现的

语法制导定义的类型

而优点也很明显

我们不需要构造依赖图

不需要对依赖图

进行拓扑排序

因此它提高了时空效率

这三种类型的方法

要根据实际的场景

来进行选择

没有哪一种是在所有情况下

优于其它的方法

谢谢大家

这就是本讲的内容