4.2.1 Bottom-Up Calculation of S-Attributed在线视频

各位同学大家好

我们继续第4章的学习

在上一讲中

我们着重介绍了

属性计算的顺序

在本讲中

我们将介绍如何具体进行属性计算

首先我们来回顾一下

第3章的内容

以递归下降预测分析为例

我们曾经讲过

每一个非终结符

可以对应一个分析过程

在进行递归下降预测分析的时候

每当遇到一个非终结符

我们就调用它的分析过程

来匹配当前的句子

当遇到一个终结符的时候

我们就调用match方法

来判断当前句子的首字母

和我们预期的首字母是否匹配

而当我们加入了属性以后

我们可以把这两种属性

附加到我们的分析过程中

具体的 针对综合属性

由于它是由产生式右部所有属性计算而来的

并且它是在完成整个产业式分析之后得到

因此很直观的

我们就可以联想到

综合属性可以对应到

我们过程的返回值

而另一种继承属性

在分析树中

它是依赖于

当前结点的父结点或者兄弟结点

因此它可以对应到

我们过程的参数

也就是

当我们希望分析某一个非终结符的时候

我们把对应的继承属性

传递给

当前记号的分析过程

以表示我们把对应的属性

传递给当前结点

这样一个语义

我们考虑之前提到过的

变量声明的例子

针对int id , id , id这样的句子

我们可以使用如下的产生式

以及对应的语义规则

来进行匹配

我们可以写出这样的伪代码

例如针对综合属性

例如T的type

它是由子结点来返回的

对应的我们就可以写出

左上这样的和左下这样的一个分析过程

在左下的分析过程中

T函数对应的就是

我们 T → int 或 T → real

这样一个分析过程

在分析过程中

我们T函数的返回值

就是当前结点的一个属性

这个属性会针对

我们当前句子的首字母

例如 lookahead 这个值

来判断它具体返回

应该是int类型还是real类型

在这个例子中

就可以很明显的看到

我们的综合属性

是以函数的返回值来表示的

对应的，针对继承属性

我们前面提到过

它是由参数来表示的

例如在L的分析过程

我们的L.in属性

就是通过参数

传递给当前的分析过程

下边也是类似

针对L→id这个产生式

我们构造这样一个分析过程

把L.in属性

传递给当前过程

这个属性会进一步的传递给addtype

来表示我们当前的id

给它添加一个属性类型信息

这个就是我们分析的一个方法

简而言之

综合属性对应我们的函数返回值

而继承属性

对应我们函数的参数

接着我们来介绍一个

更加实用的例子

也就是语法树的构造

我们知道在编译器中

分析树是一个非常重要的数据结构

在中间代码生成、代码优化等等阶段

都非常重要

而语法树是分析树的一个浓缩表示

它们的区别在于

在分析树中

我们的叶结点是终结符

而中间结点是非终结符

而在我们的语法树中

所有的结点都是终结符

在这种时候

它的空间要求

就比我们的分析树要更小

并且在很多场景下

分析起来也更加有用

然而值得注意的是

我们的语法制导的翻译方案

既可以针对分析树

也可以针对我们的语法树来实现

因为它们在语义上是等价的

例如考虑我们之前的

四则运算的例子

我们可以构造出如下的一些原语

这些原语都是用于

生成我们的分析树

例如我们可以使用如下三个方法

mknode和mkleaf

其中mkleaf 有两种

分别对应我们的树结点

和我们的标识符结点

而mknode的方法

是用来构造一个运算符结点

其中包括三个字段

分别是op, left, right

op代表我们的算符

例如加法和乘法

而两个字段

Left和right分别对应我们运算的两个子树

也就是我们两个运算数

给定如下原语以后

我们就可以把这些原语

用在我们的语义规则计算上

例如针对我们的产生式

每一个产生式

我们可以添加一个语义规则

在语义规则中

我们就可以使用刚才定义的

几种原语

例如从下往上看的话

在叶结点 F→digit 和 F→id

这两个产生式

我们分别使用 mkleaf() 的方法

来构造出这样一个叶结点

再向上的话

针对F→(E)的函数

我们可以直接把E的语法树结点

赋给F的结点

这个原因在于在语法树中

我们可以通过树的层次结构

来构造出一个优先级

而不需要括号来显示的标识

类似的针对T→F和E→T

我们也是直接把子结点的属性

赋给父结点

而针对第3个和第1个产生式

我们就使用mknode()的方法

前面提到过

它有三个域

分别是运算符、第1个运算数和第2个运算数

通过这种方法

我们就可以把两个子结点的

语法树结点

拼接到它的父结点上

构造出一个更高层的运算符

通过这种方式

我们就可以从叶结点

一直到根结点

构造出整个产生式它的语法树

需要值得注意的是

同样是产生附带语义规则

不同的语义规则

可能产生不同的作用

对于算符结点

一个域我们用来存放算符

并为该结点做一个标记

其余的两个域

用来指向运算对象的指针

基本运算对象结点

一个域存放我们的对象类型

定义域用来存放值

也可以用于存放其它的一些属性值

下面我们就针对我们的混合运算

来作为一个例子

我们来看这是刚才的产生式

以及对应的语义规则

下面我们针对一个表达式

来具体来看

如何构造我们的语法树

针对我们的表达式

A+5×B这样一个算式

我们来看如何的

同我们的分析树

构造出语法树

我们采用一个自下而上的方式

来进行表达

首先是我们的叶结点

我们考虑我们的叶结点a变量

在 F→id的时候

我们可以构造出id的符号表项

并且可以把它传递给F结点

接着在T→F产生式中

我们可以把 F结点的

它的指针传递给它的父结点F

这个过程还会继续向上

一直传递给E的nptr结点

在这个时候

我们的E的nptr属性

就保存了一个符号表项

它指向我们的id

同样的，在我们的右边子树

也是类似的

针对F→num这样一个产生式

我们可以构造出

num的一个符号表项

并且在T→F这样一个尝试中

我们可以把F的nptr向上

传递给它的父结点

同理针对最右边的子树

我们F→id构造出id的表项

并且把它赋给F

再向上一层的话

我们就可以构造出T×F它的一个符号表项

针对我们的右边这棵子树

在完成了两个运算数 T和F的属性计算以后

我们就可以再向上一层计算

T×F它的语法树结点

具体做法就是我们可以

构造出一个结点

它包含三个域

分别是乘号、第一个运算数

以及第二个运算数

我们把前面两个子结点

T和F的结点

分别添加到我们指定的域

就可以构造出我们的 T的nptr属性

它会指向左边这个子树

也就是T×F

对应的就是5×B

再继续向上

就可以构造出我们的根结点

也就是我们的加法

它的方式和乘法是类似的

只不过我们的第1个域

是一个加号

而它对应的两个运算数

分别是整个树的最左边一棵子树

也都是我们的a

而右边这个域

对应的就是5×B这个子树

把它添加到

我们加法三个域中的最后一个域

到这个地方为止

我们的E结点

它的nptr属性

就会指向我们整个语法树的根结点

到此为止

我们的整个语法树

也就各自完成了

再接下来

我们看一个相似的例子

同样还是一个运算

在这个例子中

我们考虑的是加减混合运算

使用的原语

依然是mknode()和mkleaf()

例如我们考虑如下的产生式

以及每个产生式对应的语义规则

我们可以看到

针对我们的叶结点

我们使用的是mkleaf()原语

来构造一个叶结点

针对括号

同样的是

直接把E结点的属性

传递给它的父结点

而在加法和减法

我们分别使用mknode()

并且把第一个域

分别设为加号或减号

来构造出一个结点

我们给出一个

自下而上的语法树的构造过程

首先从叶结点开始

我们首先构造第1个运算数

它的一个符号表项

并且把它向上传递给它的父结点

也就是T

T在接下来一步

把它传递给它的父结点

也就是E

再接下来是第2个算数

也就是我们的4

它会把4的符号表项

传递给它的父结点

也就是T.nptr会指向4的一个符号表项

再接下来又是第1个运算

也就是a-4这个部分

我们会构造出一个E.nptr

它会指向一个结点

这个结点三个元素

分别是减号、

第1个算术指向a、

第2个算术指向4

再接下来右边这棵子树

依然是自底向上的

首先我们构造出

c的符号表项

把它向上传递给它的父结点

也就是T

再接下来

我们就可以构造出加法的结点

这个方式和前面减法是类似的

首先是算符加号

第1个运算数

指向我们刚才的a+4这个结点

第2个算数

指向我们刚才的c结点

到这个地方为止

我们的根结点

也就是E结点

就可以有一个属性nptr

指向我们当前构造出的

语法树的根结点

至此我们这个句子

它对应的语法树就构造完成

在刚才的例子中

如果我们抛开分析树

只是看按照顺序执行的原语的话

其实它就是一个

构造语法树的步骤

它总共有5步

分别是mkleaf、mkleaf、mknode、mkleaf

和最后一个mknode

如果按顺序来看的话

它其实就是我们构造

整棵语法树的一个方式

例如第1个原语

我们构造出p1

它是a结点的语法树

第2步

我们构造另一个结点

也就是第2个算符

p3 构造出减法的语法树

它分别是减号

第1个算符和第2个算

第4个原语

就是构造出c的语法树

最后第5步

我们构造出根结点

也就是加法的结点

它分别有三个域：

加法

第1个算符

就是我们的a-4这样一个语法树

第3个域是我们第3个算符

也就是c对应的一个语法树

到这地方为止

我们的p5指向的

就是整棵语法树的结构

这个时候

我们就可以构造出

一个完整的语法树

这就是本讲的主要内容

谢谢大家