4.4.1 Bottom-Up Parsing of L-Attributed Translation在线视频

各位同学大家好

我们继续第4章的学习

在上一讲中

我们讲解的是

基于递归下降方法进行属性计算

我们可以实现

翻译动作的边分析边计算

然而由于我们的自上而下分析

仅能够处理LL(1)文法

LL(1) 文法相对于其它的

像 LR 文法

它有一定局限性

因此为了为更一般的文法计算L属性

我们需要研究如何实现

自下而上的属性计算方法

并且它应该是基于比LL(1)更复杂的LR文法

在本讲中

我们将系统介绍

L属性的自下而上计算

以及它的语法分析过程

我们说L属性的自下而上计算

和自上而下的语法分析是一致的

但是它的难点在于

我们如何分析栈上的继承属性

栈上的综合属性

我们在之前的讲解中已经介绍过

我们只需要在状态栈之外

增加一个属性栈

然而这个属性描述的是

每一个文法记号的综合属性

它并不能直接的描述继承属性

因此为了描述继承属性

我们需要使用模拟的方式

来完成我们对继承属性的计算

因此我们在本讲的后续内容中将详细讲解

如何在栈上实现 L属性计算

在自下而上的语法分析框架中

我们实现L属性方法

可以做到对任何一个

基于LL(1)文法它的L属性的定义

它的计算

以及可以实现许多基于LR文法的

L属性计算

当然要注意

这里并不是所有的LR文法

都可以使用这种方法

在最后我们会给一个反例

我们回顾一下

在我们之前的讲解中

我们曾经提到过

在自下而上分析的时候

我们可以通过加入一个属性栈的方式

来为每一个文法记号分配一个属性

但是这个属性对应的是综合属性

而不是继承属性

考虑这样一个翻译方案

A→XYZ

并且Z有一个继承属性 i

i 的值是由 X 的 x 属性来赋值

x 属性是X的一个综合属性

因此它可以出现在我们的属性栈上

但是在这个时候

我们分析 Z 之前

我们需要准备好 Z 的 i 属性

因为它是一个继承属性

然而在我们的栈上

并没有位置

可以存放我们的 i 属性

因此在我们的自下而上分析的时候

我们要解决的一个重点问题就是

如何在我们栈上消除继承属性

在这里

我们把我们的问题来描述一下

在自下而上分析中

我们的语义动作执行

是在产生式对句柄进行归约的时候来进行的

但是L属性定义的继承属性

它的计算需要嵌入在产生式右部不同的位置

这对我们的自下而上分析

或者移进归约分析的时候

无法在属性栈中加入我们的属性

因此是一个需要解决的问题

而我们解决的方法就是通过改写文法

使得所有嵌入在产生式中间的动作

变换成只在产生式最右端出现

也就是说

把它变成一个综合属性

因为所有的综合属性

可以在我们的属性栈中分配位置

这样一来，就可以消除

我们必须为继承属性

分配额外空间的这样一个问题

例如我们可以首先考虑一些特殊情况

然后我们把它推广到一个一般的情况

第1个例子中

我们考虑之前曾经介绍过的

中缀表达式转化成后缀表达式

它的文法以及对应的翻译方案

它的文法是这样的

E → TR

R → +TR1 | -TR1 | ε

T → num

我们的动作分别包括

针对T→num的一个打印字面值的一个动作

以及在分析完T以后

我们打印对应的操作

包括加号和减号两种类型

在这种情况下

我们说一个带副作用的操作

可以看成是一个虚拟综合属性

然而在 T之后的虚拟综合属性

它并不能在T的属性栈中

指定位置出现

因为T的属性栈位置

应该保存的是num.value

这时候就带来一个问题

我们如何在打印动作的时候

获得相应的操作值

这个时候

我们可以在文法中

加入一个产生 ε 的这样一个标记非终结符

它是一个非终结符

并且它是一个特殊的类型

它只能推出一个空串

我们把推出空串的这样一个非终结符

加入到

我们需要打印的一个位置

并且我们把打印动作

作为当前新加入的非终结符的

一个虚拟综合属性

例如我们文法变成这样

E → TR 不变

R → +TR1 | -TR1

我们在R1之前加入M和N两个非终结符

并且这两个非终结符

都只能推出 ε

这样它对整个文法所描述的语言

并没有影响

并且我们的加号和减号的打印操作

可以作为M和N的虚拟综合属性

也就是说在 ε 归约成 M

或者 ε 归成 N 的时候

我们分别执行

打印加号和减号两个操作

在这种时候

我们就可以在我们的栈中保存我们需要的值

这就是我们的第1个类型

我们通过引入推出 ε 的非终结符

来保证我们可以在

正确的位置打印正确的值

接下来我们来看第2个特殊例子

我们考虑之前的变量声明的例子

例如给定一个int p, q, r

我们使用如下的文法来进行描述

D→TL

T→int | real

L是一个列表

可以推出L , id 或者 id

在这个文法中

我们加入动作以及动作执行的时机

把它变成一个翻译方案

在这个例子中

我们很明显知道

in 属性是一个继承属性

在分析 L 之前

我们需要使用T的 type 属性来进行赋值

并且把它传递给L

在L产生式中

我们要使用这个 in 属性

来为我们的 id 添加符号表项类型

来作为一个参数

在自下而上分析的时候

我们说继承属性

没有办法给它分配位置

在这个例子中

我们可以通过复写规则来

在指定的位置找到我们需要的值

也就是我们通过

重用属性栈中的数值

来为我们的继承属性赋值

我们可以考虑如下的例子

例如我们的状态栈、输入栈

和我们使用产生式如左图所示

我们的分析树在上边

D→TL

T是int类型

而L列表，我们有 p, q, r 三个值

我们的问题在于

我们需要在每一个参数列表

知道每一个类型

它如何赋值给 p, q, r 三个变量

也就是说

在使用 L → id 进行归约的时候

我们要为 addtype 准备一个参数

这个参数是一个继承属性

按理来说

这个属性

在我们的属性栈中是不存在的

然而由于文法的特殊性

我们总是能够从指定位置

取到这个值

例如我们可以考虑

这样的产生式和代码段

在出现 L.in 属性位置时候

我们其实总是能够从 L的上一个位置

取到它的类型

而L的上一个位置就是T

而T对应的属性栈的值

就是我们的 type 类型

在这个例子中就是int

也就是说属性 T.type

在我们的栈中的位置

相对于栈顶是事先知道的

因此我们可以使用栈中的属性值

T.type 来代替 L.in

也就是说每一次我们需要使用 L.in 的时候

我们总是可以从栈的指定位置

例如在L→ L1 , id 的时候

我们这个参数应该是L.in

而 L.in 总是能够从Top减3

当前我们的栈顶是 id

前面是逗号 L1

再往前一个就是T的类型

因此我们可以从Top减3的位置

取到我们的L.in

最后一个产生式类似的

L→ id 的时候

我们的栈顶是 id

而栈顶前一个位置事实上就是T

而 T 的 value

其实就是我们的替代 type 这个值

在这个例子中

不管哪种情况

我们的 L.in 的值

都可以从指定的位置来获得

并且这个位置

我们是能够事先知道的

因此我们在这种情况下

就不需要为继承属性

额外分配空间

只需要在指定的位置找到它

进行赋值即可

这就是我们的第2个例子

再接下来我们就来看

并不是所有的情况下

我们都是能够事先知道

我们需要的继承属性的位置

例如考虑如下的产生式

S→aAC

或者S→bABC

C→c

针对产生式

我们有如下的语义规则

在第1个产生式中 C.i 使用 A.s 来赋值

C.i 在第2个产生式中使用 A.s 来赋值

在第3个产生式中

C.s 这是一个综合属性

它是使用它的继承属性

使用 g 函数来计算,来进行获得

在前两个产生式中

C.i 是很典型的继承属性

它需要依赖产生式右部在它左侧出现的记号

因此它是可以进行分析的

然而在两个产生式中

A.s 的位置

相对于C来说是不固定的

在第1个产生式中

A和C是连接出现在栈中

而在第2个产生式中

ABC，A和C中间隔了一个B

因此当我们使用 C → c 这个产生式归约的时候

我们的 C.i 无法从指定的位置得到

考虑如下两个例子

第1个是 S → aAC

第2个例子是 S → bABC

我们 C.i 属性

在两个分析树上

是从不同的位置获得的

例如在前面一个例子

我们的栈可以是 aAC

我们可以从栈顶减1的位置

获得 A.i 属性

如果我们的栈顶是bABC的时候

我们的 C.i 应该从栈顶减2的位置获得

在我们使用 C → c 进行归约的时候

我们无法知道

到底应该是从第1种情况

还是第2种情况

获得我们的属性

因此在这种情况下

我们就无法预先知道

我们的继承属性从何而来

这就造成一个问题

而这个问题解决

需要我们考虑一般的情况

为了解决这个问题

我们就需要引入一个额外的记号

和前面特殊情况类似

我们可以在

第2个产生式C之前

引入一个特殊的非终结符

非终结符M它只能推出空串

因此它不会影响整个语义

并且可以看到

通过引入M以后

我们的M可以保存一个综合属性

这个综合属性可以是由A复制而来

在这种情况下

无论是第一个产生

还是第二个产生式

我们的 C.i 属性

都可以从栈顶减1 的位置得到

只不过在第1种产生式中

C.i 栈顶减1 是A

而在第2个产生式中

C.i 栈顶减1是M

并且M的属性

我们是可以从前面的A获得

而且M的属性和A它的位置是相对固定的

我们可以预先知道

M属性赋值方式

它总是从 M的位置向前减两个值

就可以得到A的属性值

因此我们通过引入一个中间记号

来保存 C.i 的属性值

并且 M的位置相对于C和前面的是一样的

在这种情况下

我们的C.i 的值

总是能够从栈顶减一的位置得到

无论是产生式 1 还是产生式 2

在这种情况下

我们就可以预先知道

C.i 属性是如何来计算的

例如在针对C→c 这个产生式

我们栈代码的话

就总是能够从栈顶减1 的位置取得

虽然说在第1个产生式和第2个产生式中

M的计算方式和A它是有区别的

但是我们总是能从这个位置

找到我们需要的值

这个就是我们解决的一个思路

通过标记非终结符M复写值的属性

我们就可以预先知道

值在栈中所处的位置

在这种情况下

我们总是能够通过

引入一个非终结符

并且保证通过引入非终结符

我们可以从栈指定位置

得到我们需要的信息

进而可以写出

我们需要的栈代码

好

我们把前几种情况做一个总结

我们的思路都是

希望能够从栈的指定位置

获得我们需要的信息

这个获得方式

都是通过引入

一个推出 ε 的这样一个非终结符

并且把属性计算

移动到当前新增标记的

归约时间来进行

这样在我们的产生式中

就可以能够从指定位置来得到这个信息

例如我们可以考虑

这样的一个一般的例子

继承属性可以由一个

综合属性的函数来获得

例如我们产生式

S→aAC C→c

在这个例子中

我们的 C.i 它不再是由一个属性

直接赋值而来

而是由 A.s 属性

通过一个函数计算来得到

在这种时候

我们也是可以考虑

使用类似的思路

例如如果我们不改写文法的话

我们的栈上是保存的是aAC

同时我们的属性栈分别表示

A.s 属性和 C.s 属性

我们无法同时保存 g(C.i) 和 f(A.s)

在这种情况下

我们的解决思路也是一样的

在需要继承属性的位置

我们可以引入一个

推出 ε 空串的一个非终结符

在我们的例子中

我们的非终结符是N

也就是说

原来的 S → aAC

变成了现在的 S → aANC

而N→ ε

在这种情况下

我们的属性计算

因为是一个函数

而不是直接赋值

我们就可以把这个函数计算

它的值保存在N的位置

也就是说，我们新增的虚拟非终结符

它对应的综合属性

保存的就是我们的对 N.i 做一个 f 计算

并且保存

而 N.i 是如何来的呢

N.i 是它的继承属性

可以从前一个产生式获得

在这种情况下

我们需要计算 C.i 属性的时候

我们就可以使用 N.s 属性

而 N.s 属性

总是能够从栈顶减 1 的位置

因为 N 总是出现在 C 前一个位置

它的传递方式就是

从A.s 属性先传到 N.i

然后 N.i 到 s 的时候

我们使用了一个函数计算

再接下来

N.s 可以传递给 C.i

我们的方式就是

栈点减 1 的位置得到 N.s

这就是一个一般的处理思路

我们都是通过引入一个

推出 ε 空串的一个非终结符

并且保证从我们的引入非终结符

到我们的指定位置

它是一个固定的值

我们就可以从预先知道的位置

取出我们需要的属性

在我们引入虚拟非终结符的时候

我们就可以避免了

必须在栈中出现

继承属性的这样一个问题

好，我们来做一个小结

针对LL(1)文法和我们的LR文法

我们的这种方式是有区别的

如果说我们的基础文法是LL(1)文法的话

我们所有的LL(1)文法

都是可以使用这种方式的

也就是它并不会产生影响

然而如果说我们的产生式是一个LR文法的话

我们就并不能保证

总是能够使用这种方式

例如我们可以考虑

如下的一个文法

L → Lb | a 这样一个文法

它本身是LR(1)文法

为了解决我们继承属性的问题

我们尝试在L前面加一个M属性

M是一个推出空串的一个虚拟非终结符

但是在这种情况下

并不能保证我们引入了虚拟非终结符以后

文法依然是LR(1)文法

这就是一个典型的例子

它并不是一个LR(1)文法

在这种情况下

我们虽然语义是一致的

但是它不能够使用我们的方法

来进行边分析并计算

所以说我们在使用这种方式

来解决的时候

需要考虑特殊情况

好，最后我们做一个小结

在本节中我们介绍的是

L属性定义

以及对应它的翻译方案

针对自上而下分析和自下而上分析

我们都可以实现通过基于推导

和基于归约的方式

来实现边分析边计算

特别的我们强调了

在移进归约分析中

如果我们需要做边分析边计算的话

我们可以通过引入一个

虚拟非终结符的方式

来消除继承属性

虚拟非终结符

是推出空串的这样一个非终结符

通过这种方式

我们就可以消除

必须在栈中使用继承属性

这样一个问题

好，这就是本讲的内容

谢谢大家

的