4.1.1 Attribute Grammars在线视频

各位同学大家好

今天我们来学习第4章

语法制导的翻译

我是大连理工大学的任志磊

在前面的学习中我们知道

我们编译器的目标是将源程序

编译成我们的目标程序

并且它们的语义应该是等价的

这里语义等价的含义是指

我们用的文本编写的源程序和目标程序

虽然在结构上可能不同

但是它们表达的语义以及结果

应该是完全相同的

目前主流的语义分析

大多数是采用语法制导翻译来实现的

在语义分析阶段

我们输入是语法分析阶段得到的分析树

在这个阶段

我们的目标就是要完成分析

这个分析就包括我们的语义检查

典型的包括像类型分析、运算符匹配、

数组维数是否越界等等

在完成语义检查之后

我们开始真正的翻译阶段

这个翻译就包括像存储分配、表达式求值、

中间代码生成等等

结合我们在第3章的学习内容

我们知道我们的产生式在语义分析阶段

主要有两个用途

分别是语法制导定义和翻译方案

第1种称为语法制导的定义

其特点是针对每一个产生式

我们会编制一个语义子程序

每当产生式被匹配时

我们就调用这个语义子程序

来完成对应的语义检查和翻译动作

另一种被称为语法翻译方案

与语法制导定义不同的是

语法翻译方案它粒度更加细

也就是规定了我们插入的语义动作它的具体位置

在分析的过程中

完成对应的语义动作

在这里事实上就有一个问题

也就是为什么

我们有了语法分析之后

还要进行语义分析

这里是由于我们常用的上下文无关文法所导致的

我们考虑这样一个例子

在我们的C语言或Java程序中

我们经常要使用变量的时候

先定义再使用

这时候我们使用这样的文法

L=wcw

其中第1个w代表我们每个变量要先声明

然后经过若干代码执行之后

我们引用这个w

这个文法不是上下无关文法

也就无法在分析阶段来完成语义检查

在这个时候

我们需要借助更高级的技术

也都是我们需要使用一个新的技术

在我们之前的阶段中

我们曾经介绍过上下无关文法

它可以使用一些技术来进行分析

典型的包括像LR、LALR等等

然而在语义分析阶段

我们需要得到更多的一些信息

这个信息

我们就要进入一个新的技术

我们称为属性文法

属性文法又称为翻译文法

它是由图灵奖获得者高德纳先生于1968年提出

属性文法在上下文无关文法基础上

为每一个文法符号，包括终结符、非终结符

都匹配若干的值

这个值我们就称为属性

其中属性代表文法符号它所附带的信息

例如像类型信息、符号表、指针等等

在属性文法中

我们的属性可以进行计算和传递

例如从语法树的叶结点传递到根结点

或者在兄弟结点之间进行传递

在引入了属性概念之后

我们就可以为每个产生式

匹配一组属性计算规则

这些规则我们就称为语义规则

有了属性文法

我们就可以给出语法制导定义的概念

也就是带属性和规则的上下文无关文法

在定义中

我们的上下文无关文法

又称为基础文法

例如我们考虑之前学习过的混合运算的基础文法

为了计算表达式的值

我们首先为这个文法的非终结符

添加一个value属性

接着我们用语义规则的方式来描述

当匹配每一个产生式的时候

计算这个属性的动作

例如

我们从下向上看语法制导定义

最下面产生式 F→digit

我们可以使用

digit它对应的在词法分析阶段得到一个属性

把它传递给F结点

再向上

当我们匹配到

F→ ( E ) 这产生式的时候

我们将 E 的value值

赋给我们F值

类似的上面产生式

也是使用相同的方式

再向上

当我们匹配到一个乘法的时候

由 T→T*F 这个产生式的时候

我们T结点的value值

它是由它的两个子结点

也就是T1.value以及F.value它们的乘积

来得到我们的T的value

再向上两个

分别是我们的加法的时候

使用的属性计算规则

它和乘法基本上是一样

除了我们在计算的时候

使用的是加号，而不是乘号

最后一个

当我们匹配到根结点的时候

我们根结点L的属性

也就是我们的整个分析树

它这个表达式它对应的求值

这种方式

我们就可以实现我们的属性计算

在接下来

就是我们的基础文法

基础文法

它就是在我们的文法基础之上

添加了一组属性

针对每一个形如A→α这样一个产生式

我们可以有一组属性

这组属性它形如b=f(c1, c2, ..., ck)

其中c1一直到ck

是我们文法产生式的一系列属性

它们经过一个函数F计算

得到我们最终的一个属性

这个时候我们的属性

就要做一个分类

它主要有两种形式

第1种称为综合属性

如果我们的b是产生式左部文法记号的属性的时候

并且c1一直到ck 是我们产生式右部的属性

或者 A 除了b 属性之外的其它属性的时候

我们就称属性是一个综合属性

相对的

如果说我们的 b是产生式右部某一个文法记号X属性

并且c1一直到ck是产生式右部的属性

或者A的其它属性的时候

我们就称当前的属性是一个继承属性

在介绍了继承属性和综合属性之后

我们就来看

我们的属性值它的一个特点

在综合属性中

我们的属性值

是由分析树上它的子结点的属性来计算

而我们的继承属性

它的值是由当前结点的兄弟结点或者它父结点传递而来的

对于文法记号的属性

我们给出如下一些性质

第1点

终结符只有综合属性

并且这些属性的计算，一般来自词法分析

第2点

非终结符既可以有综合属性，也可以有继承属性

其中一个特例是文法的开始记号

一般来说

文法的开始记号没有继承属性

除非我们加以特殊的说明

这个时候我们的属性值要注意

因为我们的属性值

是由结点的兄弟结点或它的父结点来计算

而我们的开始记号是没有兄弟或父结点

所以说它就不会有继承属性

第3点

我们的文法符号的综合属性和继承属性

它的交集应该为空

对于出现在产生式右部的继承属性

和出现在产生式左部的综合属性

必须我们要提供一个计算规则

属性计算规则中

只能使用产生式中的文法符号的属性

这是由于在分析的过程中

我们的可见范围

只有在当前产生式涉及的终结符和非终结符

因此计算

也只能使用当前产生式的属性

出现在产生式左边的继承属性

和出现在产生式右部的综合属性

它不是由当前的产生式计算规则来计算

而是由它们对应的产生式来进行计算

这个也很好理解

例如我们的产生式左部的继承属性

应该是由当前的记号

它出现在某一个产生式的右部的时候

由它的兄弟结点或父结点来实现

同理，我们产生式

右部某一个记号的综合属性

应该是由它对应的出现在产生式左部的某一个产生式来计算

在接下来我们就来看语义规则

语义规则它描述的工作

可以包括像属性计算、静态语义检查、符号表操作、以及代码生成等等

例如我们考虑一个非终结符A、B和C

其中A有一个继承属性a和一个综合属性b

B有一个综合属性c

而C有一个继承属性d

假设我们有一个产生式

A→BC

我们可以有如下的规则

第1条规则

C的d属性是由B的c属性加1来实现

而A的b属性

是由A的a属性和B的c属性相加得到的

在计算规则中我们要注意

结点A的a属性和结点B的c属性

它不是由当前语义规则计算的

原因在于我们A的a属性是一个继承属性

它是由 A结点出现在某一个产生式的右部的时候

由它的兄弟结点或父结点计算而来

同理，B的c属性是一个综合属性

它是由B出现在某一个产生式左部的时候

由它的子结点计算而来

这两个属性

就是在其它地方计算

而不是在当前产生式计算

再接下来我们来看语义规则

给定一个语义规则

B=f(c1, c2, ..., ck)

这样一个规则中

我们的函数f通常是一个表达式

例如像T.value=F.value

这样一个赋值操作

当然也有一些特殊情况

有一些规则

可以写成一个过程调用或者程序段

例如当我们要执行一个打印动作

或者我们需要输出一个中间代码的时候

这个时候这种规则

我们就称为副作用

例如像打印一个动作

它就是一个有副作用的操作

我们可以把这样有副作用的操作

看成是产生式左部非终结符的一个虚拟综合属性

也就意味着

它的执行是在我们分析完整个产生式之后才得到

属性文法

就是指我们的语义规则函数

没有任何副作用

这样的语法制导定义

也就是在基础文法中

有一类特殊的（文法）

我们称为属性文法

在这类文法中它的语义规则

没有任何一个包含副作用的过程调用

接下来我们结合例子来看

我们属性的分类

首先是综合属性定义

我们看刚才介绍过的

这样一个计算器的例子

在这个产生式中

我们可以实现加法和乘法的混合运算

在这个例子中

我们每一个非终结符

都有一个value属性

value属性我们刚才介绍过

它只是依赖于产生式右部的记号的value属性

因此它是一个典型的只包含综合属性的

这样一个语法制导定义

我们称这样的语法制导定义

是综合属性定义

针对8+5×2

我们给出其分析树

这是由于语法分析阶段我们得到的

如果我们把语义规则

其中的属性标注在我们的分析树上

我们得到的就是一棵注释分析树

很明显

这棵树上的属性是可以自下而上来计算得到的

例如我们的叶结点

包含的是我们词法分析得到的这样的属性

它可以向上的传递给它的父结点

这样依次的向上传递

当遇到加法或乘法的时候

它的父结点属性

是由它的子结点

来实现加号和乘号的操作

来计算出父结点的属性

这个属性向上

一直传递到它的根结点

得到整个分析树它的一个属性值

我们将我们的产生式语义规则

和我们的分析树放在一起

可以更清晰的看到这个过程

例如我们考虑T点value这个值

它是由它的子结点T×F它的两个属性值得到的

对应到我们的产生式

它就是有这个规则

在我们使用T→T×F进行匹配的时候

它的属性值就是由它的两个子结点计算得到的

介绍完了我们的注释分析树之后

我们来看继承属性

在继承属性中

我们的语法树上

一个结点的继承属性

是由它的父结点或者兄弟结点的某个属性来计算得到的

使用继承属性

可以很方便地描述出

我们程序设计语言中的一些结构上下文的依赖

例如我们考虑这样一个例子

在我们的像C和CPP这样的程序中的

我们可以使用函数定义

形如像int id , id , id这样

我们可以声明一系列变量

这样的语句

我们可以使用这样一系列产生式来描述

例如D→TL

T→int | real

分别表示整型和浮点型

而L是我们的标识符列表

它可以由一系列的id由逗号分割来得到

在这个产生式中

我们可以看到

像in属性它是一个典型的继承属性

例如我们看产生式L→L1 , id

我们L1.in属性就是由L.in属性来得到

它依赖于它的父结点

而在这产生式中除了继承属性

我们其实也有综合属性

例如我们的T结点

它的type属性

就是一个典型的综合属性

它是由叶结点integer和real传递给T结点

结合我们的注释分析树

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

在我们的分析树上

我们的type属性是由int叶结点传递上来的

这个属性

它会进一步地传递给它的兄弟结点

再由兄弟结点传递给它的子结点

我们将注释分析树

和我们的产生式以及语义规则放在一起

可以更清晰的看到它们之间的联系

例如我们考虑产生式

L→L1 ，id

以及对应的语义规则

可以看到

in属性是一个继承属性

L1的in是由它的父结点L传递而来

对应到我们的树上

也就是这个位置

我们的 L的in属性是由它的父结点传递而来

也就是由父结点

把它的类型信息传递给它子结点

这个时候就可以很清晰的看到

我们的继承属性传递方式

是可以由父结点传递给它的子节点的

就是我们本讲的内容

谢谢大家