4.3.2 Translation Schemes在线视频

各位同学大家好

我们继续第4章的学习

在本讲中

我们开始讲解翻译方案

即除了产生式对应的语义规则之外

还要同时标出计算顺序

这样就可以把实现细节表现出来

在翻译方案中

和文法符号相关的语义动作

用花括号括起来

插入到产生式右部的合适位置

这是一种动作和分析交替的方法

我们的表示方式就是这样

在产生式中

它的指定位置

加入我们的语义动作

以表示我们当前语义动作执行的时机

是在分析过B之后

并且分析C之前来完成

接下来我们考虑这样的例子

也就是将中缀表达式

转换为后缀表达式

例如一个中缀表达式8+5-2

则输出的是85+2-

它的翻译方案

可以如下所示

E→TR

R→ addop T R1 | ε

T→num

这是我们的产生式

除了产生式之外

我们还在产生式的指定位置

加入了我们的语义动作

例如在分析过T之后

并且分析R1之前

我们要打印addop的字面值

也就是加号和减号

对应的在T的产生式中

我们要在产生式的末尾

加上打印num.value它的意思

这个时候也就是说

打印它的字面值

假设我们考虑

自上而下进行推导

从我们的开始记号 E 开始

经过若干步的推导

我们可以得到最终的句子

在句子中

我们不但有我们的终结符

也包括在指定位置它的打印动作

这时候我们就可以完成

从中缀表达式转化为

后缀表达式的操作

我们考虑一个实际的例子

例如8+5-2

我们的翻译方案如图所示

和上一页是一样的

针对8+5-2

我们从根结点开始

E→TR

接着T再进行推导，得到8

在完成T→num的时候

我们执行打印动作

也就是打印出8的字面值

再接下来

我们树的右部R进行推导

可以得到 + T R 的操作

再接下来我们展开T

T是第2个操作数，也就是5

在使用T→ R 进行分析的时候

我们要打印出 num.value

也就是说我们在这个时机

打印出 5 这个值

到此为止

我们就完成了对T的分析

在 R → addop T R 的时候

我们在完成 T 的分析之后

我们要执行一个打印 addop 的操作

也就是说

我们要把加号输出来

这个时候事实上 8 + 5

已经被我们转换成了 8 5 +

后面操作是类似的

我们后边是减2的操作

也就是R→ -TR的操作

对应的T被我们展开成2

在使用T→num时候

我们要执行一个打印操作

也就是说打印2的字面值

再接下来

既然我们完成了T的推导

我们就要在T之后R之前

执行一个 print addop 操作

也就是打印出“减号”的字面值

而右边的 R 我们会推出 ε

也就是一个空串

到此为止

我们的8+5-2 这样一个中缀表达式

就转换成了一个

8 5 + 2 - 这样一个后缀表达式

我们就完成了对应的翻译操作

接下来我们来学习

如何建立翻译模式

我们将分情况来考虑

首先是比较简单的综合属性

由前面的学习我们知道

综合属性可以在完成产生式分析之后来进行

所以我们只需要

将每一个语义规则

放在产生式的末尾

即可完成

在分析当前产生式之后，执行对应的语义规则

如果我们既有综合属性又有继承属性

那么在建立翻译模式的时候

我们就要要保证如下前提被满足：

首先第1点

产生式右部的符号继承属性

必须在先于当前符号的动作之前计算出来

第2点

一个动作不能引用当前动作右边符号的综合属性

第3点

产生式左边非终结符的综合属性

只有在它所引用的

所有属性值都计算出来

才能完成

计算这种属性的动作

通常放在产生式右部末尾

这些其实也比较好理解

我们分别来看一下

第1点

一个属性值必须在动作之前来计算

在我们前面讲定义的时候就已经提过

第2点 一个动作不能引用

产生式右部的记号的综合属性

因为我们的分析是自左向右完成的

产生式右部的记号

我们还没有完成计算

所以说也就不能进行引用它

第3点综合属性

因为它是当前结点的子树的属性

所以说我们只有在完成

当前属性计算之后

才执行对应的语义操作

所以说最简单的方式

就是把它放在产生式的末尾

我们来看如下的例子

在这个例子中

就是一个典型的反例

当前给定产生式

S→A1 A2

A→α

其中S→A1 A2这个产生式它对应的语义规则

是A1.in=1 A2.in=2

A→ α 产生式对应的语义规则

是打印A的 in 属性

在这样一个翻译方案中

我们可以看到

它的语义规则是在产生式末尾

然而我们可以很容易看出

in 属性应该是一个继承属性

因为在A→ α 的时候

我们就要打印属性

但是当我们使用A→α进行展开的时候

我们的语义动作还没有执行

所以说

它就不符合我们当前的条件

我们需要把它放在正确的位置

既然它是继承属性

我们就要把它的动作执行

放在分析当前非终结符的之前

在这种情况下

我们就可以在A1A2之前

对 A1.in 和A2.in 赋值

在后续A1和A2的分析的时候

我们就可以把它打印出来

这种时候才能保证

我们的分析是正确的

在这图中我们就可以看到

S→A1 A2

如果当前的语义规则放在最后的话

我们的打印操作就不会实现

如果把这个结点推在A1之前

我们就可以把它传递给兄弟结点

再传递给子结点

这种情况

我们就可以正确的

打印出它的值

这就是为什么

我们需要把语义规则

插入在正确的位置

它的重要性

再接下来我们来看一个

比较实际的例子

这是一个简单的数学排版语言EQN

在这个语言中

我们支持一种下标操作

我们使用sub关键字来描述一个下标

例如 E sub 1 .val

在这个句子中

由于我们使用了 sub

这个 1 就作为一个下标出现

这个语言的语法是这样来写的

S→B

B→B1 B2

表示是一个字符串拼接操作

B→B1 sub B2

表示B2这个字符串是作为B1的下标出现

B也可以推出text

这是我们的终结符

也就是我们可以推出一段文本

在这种情况下

我们就既包含了字符串的拼接

也包含了字符串的下标操作

在给出产生式之后

我们给出对应的语义规则

在产生式中的记号里

我们引入了两个属性

一个是综合属性ht

用于表示一个文本的高度

另外还有一个继承属性

叫做pointsize ps

指的是当前字符串输入的字大小

我们可以使用如下公式

来计算正文的实际高度

也就是它等于

正文的正常高度乘以点的大小

ps值越大

我们当前的高度就会越高

越小的话反之亦然

而ht 的话就是我们计算之后得到的属性值

给定产生式以及我们的属性

我们就可以给出对应的语义规则

例如在开始的时候

我们对ps做一个赋初值

也就是它等于10

而ht由于是综合属性

它是从B的ht来进行赋值

针对第2条产生式

B→B1 B2

这是一个字符串拼接操作

所以说

B1和B2的ps属性

都是它的父结点B的ps属性

而 B的ht它的高度就是 B1和B2的高度取大

因为在B1和B2中可能存在下标操作

而一个下标可能会引起它得偏移

所以整个高度会发生变化

所以说整个字符串B的ht

就应该是B1和B2两个子串

它们的高度取一个大

再接下来B→B1 sub B2

我们的输入属性

B1 它的继承属性ps是从B复制而来的

而B2

由于 sub 关键字的出现

我们需要对B的ps做一个shrink操作

也就是做一个压缩操作

这样的话就可以使得

B的高度发生一个变化

它会变小

并且 B的ht我们需要

通过B1的ht和B2的ht做一个偏移操作

也就是，因为我们的下标

使得我们的高度发生了变化

disp就是一个偏移的函数

最后B →text

这是我们的叶结点

针对终结符text

我们的高度就使用这个公式

B.ht=text.h

它本身的高度

乘以它的输入的继承属性参数 B.ps

得到当前text的一个属性

有了产生式、有了语义规则

并且我们知道

其中既包含综合属性也包含继承属性

那么下面我们关注的重点就是

如何把我们的语义规则

插入到产生式中正确的位置

来完成对应计算

好 我们来看这个语义规则

如何插入到我们的产生式中

我们的插入

需要满足以下的规则

也就是产生式右部的继承属性

必须在当前动作之前计算出来

第2点

不能引用产生右部的记号的综合属性

第3点，综合属性要在产生式分析完后才进行

按照三条原则

我们就可以把我们语义规则

插入到指定位置

例如针对 S→B 我们的开始记号的产生式

我们要把 ps等于10

作为输入参数

以继承属性的方式传递给B

所以说B.ps=10

就作为B的继承属性

放在它之前执行

而ht由于它是一个综合属性

我们只需把当前的综合属性

放在整个产生式的末尾

标识我们分析完整个产生式

它来执行S.ht的赋值

第2个产生式 B→B1 B2

也是类似的

既然ps是继承属性

我门就把继承属性的赋值

放在当前记号的之前来进行

例如B1.ps在B1分析之前

而B2.ps是在B2分析之前

而ht操作和前面类似

也是放在整个产生式的末位

区别只在于它的计算

需要综合考虑B1和B2两个值的ht属性

第3个产生式B→B1 sub B2

下标操作的时候，也是类似

B1和B2的ps属性

分别在它们之前来赋值

只不过B2的属性

因为有 sub 的存在

我们需要对ps值做一个缩小操作

而 ht 属性

既然它是一个综合属性

也是把它放在产生式末尾的计算

对于 B → text 这样一个产生式

它只有一个综合属性

也就是ht

ht是由text.h 是它的词法记号的属性

乘以我们的输入参数，也就是继承属性ps

得到它的综合属性

这个综合属性将会向上传递给它的父结点

来完成我们的属性计算

在接下来的例子中

我们来看一个特殊的场景

也就是由消除左递归引入的继承属性

文法就是我们之前考虑的

加法和乘法的混合运算

在我们原始的文法中

我们可以看到

nptr 是一个典型的综合属性

表示的是当前的非终结符

对应的语法树的指针

我们在之前课程中还介绍过

如何使用mknode、mkleaf原语

来构造我们的语法树

在文法中我们只有综合属性

因此它是一个S属性定义

但是这个文法有一个问题

它不是LL(1)文法

因为它存在左递归

我们说，为了消除所递归

我们需要对文法进行重写

重写操作就是

提取公共左因子

来构造出一个

没有左递归的这样一个语法

这就是左边的文法

会转化成右边的文法

例如我们考虑加法操作

我们把它变成 E → TR

R →+ TR1

R → ε 这样的串

我们可以使用这样的文法

来描述连加的操作

例如针对上面的T+T+T这样的连加操作

我们的第1个T会被 E → TR 的 T 来匹配

而 R 会匹配 +T+T+T 等等

在后面的 R 我们展开的时候

是 +TR1 的方式来展开

当我们遇到最后的位置的时候

我们使用 R → ε 来进行展开

在这个例子中

我们改变后的文法

是没有公共左因子的

因此它是一个LL(1) 文法

但是这个修改导致了

我们无法直接使用综合属性

来描述它的语法树

原因在于我们

提取公共左因子的操作

把第1个T和第2个T

在我们的产生式中强行的分在两个产生式中

也就是第1个产生式

E → TR 的 T 可以匹配第1个 T

而 T+T 的操作中的第2个运算数

被分在了我们第2个产生式

在这种时候

我们的两个产生式中的属性

它就要以一种机制来进行传递

这种传递

我们就不能再使用综合属性

而必须使用继承属性

把 T 的一个属性传递给 R

这也就是我们之前所说的

我们的消除公共左因子

或者消除左递归的操作

会导致我们的语法

从一个S属性的定义

变成了一个包含继承属性定义

在这种时候

我们的分析方法和属性计算

就要发生变化

当我们考虑乘法操作的时候

也是类似的

乘法的

消除左递归的方式

和加法是一样的

也就是说我们的操作

会把 F 同一个计算中的F分在不同的产生式中

因此我们也需要以继承属性的方式

把前面F的属性传递给后边的F

共同的完成一个语法树的构造

因此

这个例子就是非常典型的

消除左递归引入继承属性的问题

后续的F→ ε

由于它比较简单，我们就不再给出

我们来看如何使用继承属性

来完成我们的语法树构造

在这个语法中

我们是引入了一个新的属性

W.i 来表示我们的继承属性

同时我们还要使用一个 W.s 来表示

分析完当前 W 记号以后

得到的语法树

它是一个综合属性

而 W.i 是一个继承属性

用于传递我们之前

分在不同产生式中的语法结点

我们可以看到

针对我们的T+T+T等等

这样一个操作

我们前面的 T分析完了以后

我们可以得到T.nptr 表示

当前 T 结点的语法树结点

在这个时候

我们就要把它赋给 R 的 i 属性

R 的 i 属性和 W 的 i 属性是一样的

它都是继承属性

表示我们前面分析到

T以后得到一个语法树结点

考虑我们之前的 T 连加的操作

我们的 R.i 就用 T.nptr

也就是T的结点赋值

这个时候

我们就可以把它传递给后续的表达式

和后边的T共同的拼接成一个语法树结点

在R的产生式中

我们可以更清晰的看到这一点

R → +TR1 这样一个产生式中

我们就可以对 R.i 进行赋值

也就是说

后边的R.i

我们使用前边分析完 +T 以后

并且加上我们前面 R.i 产生式左部的继承属性

共同的构造出一个结点

并且把当前结点

赋值给我们的 R1

并且在分析完R1之后

我们把 R 的 s 属性

使用 R1.s 进行赋值

也就是分析完 s 以后

我们得到产生式它的语法树结点

来进行赋值

对于乘法

也是类似的

我们把 W.i 属性用来表示

分析W之前我们得到语法树结点

而 W.s 表示的是

分析完语法树之后

我们得到的语法树结点

它的赋值和下面也是类似的

我们可以把

前一个产生式中的语法树结点

赋给后一个产生式

以方便在 W→ *FW1

这样一个产生式中

来构造我们的语法树结点

后面的

F产生式由于比较简单

我们也照例不再给出

刚才的介绍可能比较抽象

接下来我们就来用一个例子来看

在树上如何来反应我们刚才的操作

例如我们可以考虑

这样一个连乘操作

a*b*5它的操作

前面 E → TR 推出 T 这一部分

由于比较直观

我们就不再列出

我们从T开始列出当前子树

当前我们认为

T是我们的根结点

T→FW

在完成F→ id 这样一个产生式的时候

我们就可以构造出

id 对应的一个符号表项

并且它作为当前的语法树结点

传递给F的 nptr 属性

再接下来

我们就要以继承属性的方式

把 F 的 nptr 属性传递给 W

这个操作就是我们使用

W.i=F.nptr 来进行赋值

赋值以后

我们就可以把刚才树左边的一个语法树结点

传递给树的右边

在右边我们得到了这个属性以后

结合后边 *F 的子树以后

我们就可以构造出

一个乘法的一个语法树结点

它的左子树

是我们刚才传递进来的继承属性

右子树是当前的F的nptr

也就是第2个值5的表项

到这个地方为止

我们就构造出了a*5

它的语法树结点

并且我们可以把这个结点

作为继承属性

传递给它的子结点W

而在W中，我们分析完 *、分析完F以后

我们可以再构造它的一个

语法树结点

也就是构造出了星号

左边是a*5，右边是B

到此为止

我们语法树

事实上已经构造完了

但是我们最后还有一个结点

W→ ε

它的 i 属性

还是需要使用W的综合属性来进行赋值

也就是我们刚才构造出的

语法树结点

要赋给最后一个W.i

到此为止

我们的输入事实上已经结束了

因此我们使用W → ε

来进行匹配

在这个匹配过程中

我们就要把W的继承属性

赋值给W综合属性

我们说

W的综合属性 s 表示的是

分析完W以后

得到的语法树结点

在最右下的W结点它的 s 属性

事实上就保存了

我们整个的语法树

因为它是综合属性

所以这个属性

会被向上的传递给它的父结点

直到传递给我们的根结点

到最后我们的 T.nptr 得到的

就是我们的语法树

这个过程

我们就可以这样来看一下

我们由左向右依次进行计算

在计算到最后的时候

我们可以得到

我们的语法树

也就是分析完W→ ε 以后

在树的最右下结点

得到我们的语法树根结点

并且由于我们的语法树中

有一个W.s综合属性

它是由W.i赋值的

因此我们可以把

W.s 反向的逆推给它的根结点

到最后我们的根结点

就可以保存了

整个语法树的一个结点

好，这就是本讲的主要内容

谢谢大家