编译原理第6章.ppt

第六章属性文法和语法制导翻译;介绍有关语义分析及翻译的问题。

语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。

本章中，将首先介绍属性文法的根本概念，然后介绍基于属性文法的处理方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。;本章内容概要;L属性文法和自顶向下翻译

翻译模式

自顶向下翻译

递归下降翻译器的设计

自下而上计算继承属性

从翻译模式中去掉嵌入在产生式中间的动作

分析栈中的继承属性

模拟继承属性的计算

用综合属性代替继承属性;属性文法;属性通常分为两类：

综合属性和继承属性。

综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。

在一个属性文法中，对应于每个产生式A→α都有一套与之相关联的语义规那么，每条规那么的形式为

b:＝f(c1，c2，…，ck)这里，f是一个函数，而且或者

〔1〕b是A的一个综合属性并且c1，c2，…，ck是产生式右边文法符号的属性；或者

(2)b是产生式右边某个文法符号的一个继承属性并且c1，c2，…，ck是A或产生式右边任何文法符号的属性。

在两种情况下，我们都说属性b依赖于属性c1，c2，…，ck;(1)终结符只有综合属性，它们由词法分析器提供；

(2〕非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规那么。

属性计算规那么中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规那么进行计算，它们由其它产生式的属性规那么计算或者由属性计算器的参数提供。;语义规那么所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。;;综合属性;继承属性;句子realid1，id2，id3的带注释的语法树。;基于属性文法的处理方法;依赖图;在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规那么引入一个虚综合属性b，这样把每一个语义规那么都写成

b：＝f(c1，c2，…，ck)

的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，那么附属性c的结点有一条有向边连到属性b的结点。更详细地说，对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：;for语法树中每一结点ndo

for结点n的文法符号的每一个属性ado

为a在依赖图中建立一个结点；

for语法树中每一个结点ndo

for结点n所用产生式对应的每一个语义规那么

b:＝f(c1，c2，…，ck)do

fori:=1tokdo

从ci结点到b结点构造一条有向边；;属性的计算次序;一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规那么计算的有效顺序。

在拓扑排序中，在一个结点上，语义规那么b:=f(c1，c2，…，ck〕

中的属性cl，c2…,ck

在计算b以前都是可用的。

属性文法说明的翻译是很精确的。根底文法用于建立输入符号串的语法分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规那么的顺序。用这个顺序来计算语义规那么就得到输入符号串的翻译。;在上图的依赖图中，每一条边都是从序号较低的结点指向序号较高的结点。因此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到以下程序，用an来代表依赖图中与序号n的结点有关的属性.这些语法规那么的计算将把real类型填入到每个标识符对应的符号表项中。

a4:=real

a5:=a4

addtype(id3.entry,a5)

a7:=a5

addtype(id2.entry,a7)

a9:=a7

addtype(id1.entry,a9);树遍历的属性计算方法;下面算法可对任何无循环的属性文法进行计算;只要文法的属性是非循环定义的，那么每一次扫描至少有一个属性值被计算出来。

如果语法树有n个结点〔因此最多有O(n)个属性〕，最坏的情况整个遍历需O(n2)时间。;例：S有继承属性a，综合属性b；X有继承属性c,综合属性d；Y有继承属性e、综合属性f；z有继承属性h、综合属性g。;一遍扫描的处理方法;因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：

〔1)所采用的语法分析方法；