第六章: 属性文法和语法制导翻译
一.属性文法
1.属性文法
是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。
属性:代表与文法符号相关的信息，和变量一样，可以进行计算和传递。
例:类型、值、代码序列、符号表内容等
2.属性的分类：综合属性，继承属性
(1)综合属性
1）用于“自下而上”传递信息
2）在语法树中，一个结点的综合属性的值，由其子结点的属性值确定
3）S—属性文法：仅仅使用综合属性的属性文法
(2)继承属性
1）用于“自上而下”传递信息。
2）在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定
3.语义规则
属性计算的过程即是语义处理的过程
对于文法的每一个产生式配备一组属性的计算规则，则称为语义规则
b:=f(c1,c2,…,ck)
这里f是一个函数，而且或者
(1)b是A的一个综合属性并且c1,c2,…ck是产生式右边文法符号的属性；或者
(2)b是产生式右边某个文法符号的一个继承属性并且c1,c2,…ck是A或产生式右边任何文法符号的属性
在这两种情况下，我们都说属性b依赖于属性c1,c2,…,ck.
A->β1β2...βn
b:=f(c1,c2,…,ck)
(1)b是A的一个综合属性
(2)b是βi的一个继承属性
注意：
(1)终结符只有综合属性，它由词法分析器提供
(2)非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。
(3) 产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则
(4) 产生式左边符号的继承属性和产生式右边符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算
二.基于属性文法的处理方法
1.基于属性文法的处理过程
输入串->语法树->依赖图->语义规则计算次序->计算结果
这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。
2.依赖图
1).一些说明
如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的属性规则必须在确定c的语义规则之后使用
在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。
在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成
b:= f(c1,c2, …ck)
依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。
2).2.依赖图的构造算法
for分析树中每一个结点n
for 结点的文法符号的每一个属性a
为a在依赖图中建立一个结点；
for分析树中每一个结点n
for结点n所用产生式对应的每一个语义规则
b:=f(c1,c2,…ck)
for i :=1 to k
从ci结点到b结点构造一条有向边
3) 属性的计算次序
一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, …mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。
一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则b:=f（c1,c2,…ck)中的属性c1,c2…ck在计算b以前都是可用的。
3.树遍历的属性计算方法
假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有的属性。
最常用的遍历方法是深度优先，从左到右的遍历方法
如果需要，可使用多次遍历
1)属性计算算法
While 还有未被计算的属性
VisitNode(S) /*S是开始符号*/
void VisitNode(Node N);
{ if N是一个非终结符
/* 假设它的产生式为 N X1…Xm */
for i:=1 to m
if Xi∈VN then /*即Xi是非终结符*/
{
计算Xi的所有能够计算的继承属性；
VisitNode(Xi)
}
}
计算N的所有能够计算的综合属性
4.一遍扫描的处理方法
与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。
因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：
所采用的语法分析方法
属性的计算次序
5.抽象语法树
从语法树中去掉对翻译不必要的信息，而获得更有效的源程序中间表示。
这种经变换后的语法树称之为抽象语法树（Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。
三.S-属性文法的自下而上计算
S—属性文法，它只含有综合属性。
综合属性可以在分析符号串的同时由自上而下的分析器来构造
分析器可以保存与栈中文法符号有关的综合属性值
每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算
可以通过扩充分析器中的栈来存放这些综合属性值
S-属性文法的翻译器通常可借助于LR分析器实现
1. S属性的自下而上计算
将LR分析器增加一个域来保存综合属性值
val[top] = Z.z val[top-1] = Y.y val[top-2] = X.x
四.L-属性文法的自顶向下翻译
问题：边分析边翻译的方式能否用于继承属性？
属性的计算次序受分析方法所限定的分析树结点建立次序的限制
分析树的结点是自左向右生成
如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算
1.L属性文法的定义
如果每个产生式A X1 X2 … Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性， 1 j n, 但它仅依赖：
该产生式中Xj左边符号X1, X2, …, Xj-1的属性；
A的继承属性
S属性文法包含于L属性文法
2. 翻译模式
1） 定义
翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛ ｝括起来，可被插入到产生式右部的任何合适的位置上。
这是一种语法分析和语义动作交错的表示法，他表达在按深度优先遍历分析树的过程中何时执行语义动作。
翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。
2）3. 设计翻译模式（根据语法制导定义）
条件：语法制导定义是L-属性定义
保证语义动作不会引用还没有计算的属性值。
(1)只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
(2)既有综合属性又有继承属性：
①产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。
②一个动作不能引用这个动作右边符号的综合属性。
③产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。
3.自顶向下的翻译
1.从翻译模式中消除左递归对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。
2.关于左递归翻译模式更一般化的讨论
左递归翻译模式
A→A1Y｛A.a:=g(A1.a,Y.y)}
A→X ｛A.a:=f(X.x)} (1式)
每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。
消除左递归，文法转换成
A→X R
R→Y R|ε
再考虑语义动作，翻译模式变为：
A→X ｛R·i:=f(X · x)}
R ｛A.·a:=R. ·s}
R→Y ｛R1 · i:=g（R ·i,Y·y）}
R1 ｛R · s:=R1 · s}
R→ε｛R · s:=R · i} (2式)
经过转换的翻译模式与图5.14中一样,使用R的继承属性i和综合属性s。
五.知识应用