4.3.3 Design of Predictive Translator在线视频

各位同学大家好

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

在本讲中

我们关注预测分析的设计

以及在一些场景下

如何使用综合属性来替代继承属性

首先我们来关注

如何设计自上而下的分析

如果我们的文法是满足LL(1)文法的话

我们就可以比较容易的实现边分析边计算

在这个时候

我们的函数返回值

可以作为A的综合属性

如果说我们的属性有多个的话

可以考虑使用记录或者使用某一个记录的指针

来封装若干个域

为了简单起见

在本讲中

我们假设

每一个非终结符只有一个综合属性

对于每一个函数过程中

未出现在A的产生式中的每一个文法记号

设计一个局部变量

局部变量就可以用来记录

出现的每一个记号的它的属性

再接下来

针对非终结符A对应的函数过程中

根据当前的输入符号

我们可以确定使用

哪一个产生式作为候选

这个过程就和我们在第3章讲解过的

match函数是一致的

因为LL(1)文法

它没有左递归

没有公共左因子

所以我们总是能够根据当前的

第1个记号来判断

应该使用哪一个产生式

在每个产生式对应的代码中

我们按照自左向右的顺序

对于简单的终结符、

非终结符和语义动作

做以下的工作：

第1点

对于带有综合属性 x 的终结符 X

我们可以把 x 的值

存入 X.x 这样一个局部变量中

然后产生一个匹配 X 调用

并且继续读入一个符号

第2点

针对每一个非终结符 B

产生赋值语句

c=B ( b1, b2, ..., bk )

其中 b1 到 bk 是输入参数

而 B 是非终结符 B 对应的分析过程

这样一来

我们就可以把B的综合属性保存在 c 中

这个 c 就是为了B的综合属性

所设置的一个局部变量

第3点

对于语义动作

我们把语义动作对应的代码

抄入分析器中

用代表属性的变量来代替

属性中的每一次引用

我们来看

我们的预测分析器的设计

我们的设计目标是为文法计算

其中的一个L属性值

相比前面综合属性

L属性就相对复杂一些

我们的方法是

把预测分析的构造方法

推广到翻译方案的实现

例如考虑这样一个产生式

R → +TR | ε

它的分析过程

如前所述

针对这样的产生式

我们要构造一个分析函数

我们把它命名为 R

并且针对它的一个产生式右部(进行讨论)

第1个记号是一个加号

所以说我们要首先判断

当前的第1个位置是不是加号

如果是的话，我们则匹配加号

然后分别调用 T 和 R 的分析过程

如果首字母不是加号的话

我们就应该使用

第2个产生式 R → ε 来进行匹配

在这个情况下

我们什么都不需要做

只要有一个空的else 分支即可

当我们考虑属性以后

我们就可以把当前的分析过程

进行扩展

在当前的 R 过程中

我们的参数

表示的就是我们当前 R 的继承属性

也就是从其它结点中

传入当前分析结点的属性

对应的它的返回值syntaxTreeNode

表示的就是当前属性

计算完了一个综合属性

针对我们产生式右部可能出现的所有记号

我们设置一个局部变量

并且我们针对当前输入的首字母

来进行判断

如果是加法的话

我们就匹配当前加号

调用T和R

并且使用对应的变量

来保存它们的返回值

和 R 的过程类似

T的返回值就是

T结点对应的分析过程它的综合属性

而R的返回值就是

R 这个结点它的综合属性

R的参数就是

它的一个继承属性

对于 R → +TR 这样一个过程

我们后面这个R 它的输入属性

也就是我们分析到 R 之前所构造的一个语法结点

它的构造方式是通过调用

mknode 的这样一个原语

它的参数就是：

我们在前面分析得到的一个运算符、

输入进来的一个参数、

以及我们前一个结点对应的一个属性

到此为止

我们的S就是我们的返回值

表示的就是分析完当前 R 以后

得到的一个语法树结点

对应的，如果说

我们的输入首字母不是加号的话

我们则使用第2个产生式

也就是 R → ε 来进行匹配

在这种情况下

我们需要对它的返回值做一个赋值

在 R → ε 的时候

我们知道

它已经进入到分析树的右下结点

这种时候

我们只需要把它的输入参数

作为返回值返回即可

无论哪一种情况

我们的S都表示分析完当前过程以后

得到的一个语法树的结点

最后我们只要把语法树结点

作为当前过程的返回值

也就是分析完当前产生式左部以后

得到的综合属性

那就完成了当前函数的匹配

好，接下来我们来看一个特殊的案例

也就是在一定场景下

我们可以使用综合属性

来替代继承属性

我们说综合属性分析起来

总是比继承属性要更容易一些

在一定场景下

我们可以在两个属性之间进行转换

例如我们考虑这样的例子

这是PASCAL语言它的变量声明的一个语法

和C语言、Java等等不同的是

PASCAL语言它的变量声明

我们的标志符是写在前面

然后通过冒号

来分割我们的变量声明以及类型

这个语句 m, n: integer 表示的是

我们上面有两个变量：m 和 n

它们的类型是整型

我们可以使用这样的文法来描述

D→ L : T

L代表我们的变量列表

而T代表我们的类型

T→ integer | char

表示两种类型

而L是一个列表

它是L1, id 或者 id

给定这样的语法以后

我们就可以

针对每个句子来构造它的分析树

例如从根结点D开始

D→ L : T

L是我们的参数列表

也就是 L → L , id

L→ id

T是我们的类型，是integer

在这种文法情况下

我们的分析树是长这个样子

我们需要对每一个 id

赋值它的类型

但是我们的类型是出现在分析树的右下

所以它需要

首先传递给它的父结点

并且由父结点传递给它的左边的兄弟结点

然后传递给子结点

具体传递到我们的两个 id

在这个时候

我们可以对 id 的类型进行赋值

赋值方式类似于我们前面的addtype

但是这个时候我们看到

它的赋值方式是从右向左的

和我们的分析方式是有个区别

因此不适合我们边分析边计算

在这种情况下

我们可以通过改写文法的方式

来进行变换

把我们的继承属性

变成可以使用综合属性来描述

针对上面的文法

我们可以做这样一个变换

D→id L

L→ , id L | : T

而T是我们的 integer 或者 char 两种类型

这两种文法描述的语言是一致的

都是可以推出形如 m, n : integer 这样的句子

但是它的好处在于我们可以

构造出不同的分析树

例如还是 id , id : integer 这样的一个句子

我们构造的分析树是这样的

D (作为根结点)

左边是 id 右边是 L 逗号 id

然后我们的列表结束

后边是我们的类型

类型是 : integer

在这种情况下

我们的类型是在最下边

它可以以综合属性的方式向上传递

并且传递给包含 id 的每一个 L 以后

我们可以使用

虚拟综合属性的方式

来执行我们的 addtype 操作

当完成 L 分析以后

它已经知道了它的类型是integer

并且知道了它的 id 表项

所以我们可以完成 L 分析以后

调用 addtype 操作

来给 id 赋一个类型信息

左边的 id 也是类似的

可以通过分析完 D 以后

执行 addtype 操作

在这种时候

我们既知道了 id 的信息

也知道类型信息

所以调用 addtype 是没有问题的

通过这种方式

我们就可以把原来很难分析的

一个包含继承属性的这样一个例子

变成一个只使用综合属性

就可以完成的分析

当然我们要注意

这是一个只有在特殊场景下可以使用的

因为这种文法改写

并不是总能成立的

把我们刚才描述的属性传递的过程

使用我们的翻译方案来描述的话

只需要把我们的语义规则对应的动作

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

就可以完成

我们刚才的类型传递以及 addtype 操作

这时候我们可以看到

在我们的翻译方案中只有综合属性

因为我们所有的动作

都是在产生式最右部以后来执行的

像 addtype 我们刚才也提过

因为它是一个有副作用的动作

它需要在完成当前结点分析以后来执行

所以它也是一个综合属性

在这个例子中

就是一个非常典型的

使用综合属性来描述

原来必须使用继承属性的例子

当然我们需要在合适的场景

考虑使用合适的方式来进行改写

这个需要在大家今后的工作中

进行自我摸索

好，谢谢大家

这就是本讲的内容