4.2.2 Stack Code在线视频

各位同学大家好

今天我们继续第4章的学习

在本节中

我们将介绍

如何实现综合属性的自下而上计算

特别的我们称一个

只包含综合属性的文法为S属性文法

在S属性文法的分析中

我们的综合属性

可以在分析输入串的同时

完成自下而上的分析和计算

在我们的分析器中

除了我们的状态栈

我们可以另外设置一个符号栈

这个符号栈描述的就是

每一个文法记号对应的属性

每当我们进行归约的时候

新的属性值

就可以从栈中

正在被归约的产生式中取出并且计算

计算之后

把它存储在我们的栈的指定位置

即可完成对应的语义规则

例如我们可以考虑一个LR分析器

在我们第3章讲解的时候

我们曾经讲过LR分析

在分析中

我们当时只使用了状态栈

为了进行属性计算

我们除了状态栈之外

增加了一个属性栈

用于保存每一个文法记号的属性

例如我们有一个产生式A→XYZ

假设它的语义规则是

A的A属性是由 X.x Y.y Z.c 经过一个f计算得到

很显然

A.a就是一个综合属性

这个属性如何计算呢？

我们可以这样考虑

假设当前我们

应该对当前产生式进行归约

那就意味着

在我们的状态栈中

就应该有X、Y、Z分别在栈顶

对应的X.x Y.y和Z.c

它们三个属性

也分别在栈的指定位置

我们就可以从栈的这三个位置

分别取出三个属性值

经过 f 计算以后

把它压入栈中

由于经过归约后

我们的X、Y、Z分别要进行弹栈

并且压入归约后的A

因此我们的A.a就会保存在a的指定位置

到这个地方为止

我们的属性计算就可以完成

例如我们考虑之前介绍过的

混合运算的例子

在这个例子中

我们有产生式对应的语义规则

以及我们的状态栈和属性栈

我们以之前曾经介绍过的

混合运算的例子

来介绍如何进行属性计算

具体的我们关注的是

如何将语义规则

翻译成对应的栈代码

在图中我们可以看到

我们有计算用的产生式、语义规则

以及对应的我们的状态栈和属性栈

我们就针对每一个产生式

来分别考虑

如何将语义规则转化成对栈的操作

针对第1条产生式L→En

我们的目标是打印出E的value属性

当我们使用这条产生式进行归约的时候

我们的栈顶应该是n

栈顶下一位应该是E的属性

这个时候我们就很容易看出

我们可以取出栈顶减1的位置

它的值就是E.value

我们就可以把它打印出来

这就是我们的代码栈

我们考虑第2条产生式

我们的产生式是E→E1+T

它的语义规则是E.value=E1.value+T.value

在当前的栈顶我们应该是有T

栈顶减1是加号

栈顶减2是E1

因此我们可以从

栈顶和栈顶减2的位置

取出E1和T的属性值

把它们做加法

接下来我们要做移进归约

也就是我们弹出栈领的三个元素

并且把E压入

因此我们计算后的值

应该存储在当前的 top减2位置

这就是我们的代码段的含义

从top和top减2

取出T和E1的value值做加法

并且把它保存在top减2的位置

好 第3条产生式E→T

它的语义规则是E.value=T.value

由于当前我们的栈顶元素

就是T.value

经过弹栈和压栈操作以后

我们的value值是保持不变的

因此我们的栈代码

应该是不需要做任何操作

再接下来

T→T1×F

这条产生式和第2条非常像

只不过我们把加法换成了乘法

它的操作也是类似的

从栈顶和栈顶减2的位置

取出F和T1的属性值

把它们做乘积

并且存储在栈顶减2的位置

好 接下来我们来看

T→F这个产生式

这个产生式和第3条产生式非常类似

我们的语义规则是T.value=F.value

因此我们并不需要

对属性栈做任何操作

再接下来F→(E)

这个产生式对应的语义规则

是F.value=E.value

当我们使用这条产生式进行归约的时候

我们的栈顶应该是 (E）

因此E.value

应该从栈顶的 top-1取得

并且因为我们需要弹栈三次 压栈一次

所以说计算后的属性值

应该保存在 top-2位置

因此我们的栈代码

就是value[ top-2 ]=value[ top-1 ]

最后一条 F→digit

这是一个叶结点

它的语义规则是

将词法分析得到的值赋给F.value

因此我们也不需要对栈做任何操作

到此为止

我们的所有语义规则

就已经翻译成了我们对应的栈代码

在移进归约的时候

每当需要进行归约的时候

我们就执行对应的栈操作

就可以完成对应的S属性计算

我们以一个具体的例子来看

我们考虑3×5+4

这样一个表达式

我们考虑它的移进归约分析

并且分别考虑它的

状态栈和属性栈的取值

最开始我们的输入是3×5+4n

我们的两个栈都是空的

首先我们需要移进

把3移入我们的状态栈和属性栈

这个时候我们就要使用

F→digit来进行归约

归约的时候

我们的属性栈保存的

就是它的3的值

因此不需要做任何操作

再接下来

我们使用T→F来归约

这个操作只需要对状态栈

做一个弹栈压栈操作

我们的value值

也不需要进行变化

接着我们进行移进

把乘号移进来

再接下来我们再移进，移进5

移进5以后

我们需要使用F→digit来进行归约

归约的时候

我们的栈依然不需要操作

再接下来

我们T×F需要使用 T进行归约

同时我们需要对栈顶的

top和top减2的位置

把5和3取出来做乘法

并且把它保存在top减2的位置

对应的我们得到最上面的值

我们的 value栈对应的栈顶是15

并且我们的状态栈是T

再接下来

和前面就比较类似

我们继续的移进加号

然后移进4

我们4使用F来进行归约

然后F使用T来进行替换

在这个时候

我们的栈顶就是E+T

我们需要使用E→E+T来进行归约

归约的时候

我们的栈操作就是

从栈顶和栈顶减2的位置

取出4和15

把它们做加法

并且压入在top-2的位置

经过归约的弹栈压栈以后

我们的栈顶就是19

并且我们的state栈

它的栈顶就是E

在这个时候

我们再移进n

表示我们的句子已经读完

并且我们的栈顶是19

最后我们执行打印动作

就可以把栈顶的19

这个值打印出来

到此为止

我们的3×5+4

这样一个表达式

就完成了移进归约分析

并且在移进归约分析的同时

我们完成了属性计算

得到了最终的表达式求值是19

好

我们做一个简单的小结

在本节中

我们主要关注的是自下而上分析

我们是以LR分析为例

也就是移进归约分析

首先给出了 S属性定义

也就是只包含综合属性的

这样的文法属性

然后我们给出了

如何把每一个语义规则

翻译成代码栈的操作

因此我们就构造出了

一个完整的翻译程序

针对这个过程

我们可以做一个类比

就像一个建筑

我们的语法分析就是一个框架

而在归约处

每一个归约处

我们设置一个挂钩

或者在编程的时候

我们可以把它类比成一个回调函数

每一次进行归约的时候

我们就调用我们挂钩处的一个动作

也就是调用一个回调函数

通过这种操作

我们就可以完成

在归约的同时

进行语义子程序的调用

进而完成我们的翻译任务

本节的内容处于本章的这个位置

我们在前面曾经介绍过属性

包括综合属性和继承属性

我们说基础文法加上综合属性

就是我们的S属性定义

我们是以自下而上分析为例

通过在归约的时候

执行对应的操作

来完成属性计算

在后续的过程中

我们将介绍其它的属性定义

以及对应的分析操作

好 这就是本讲的内容

谢谢大家