7.2节要点：
1,属性文法(语法制导的定义)（Syntax-Directed Definition）。
形式：每个产生式A((对应与之相关联的一个语义规则（semantic rules）集合，每条规则形如b:=f(c1,c2,…,ck)，其中f是一个函数，b,c1,c2,…,ck是该产生式中文法符号的属性（attributes），b有两个可能：（1）是A的综合属性（synthesized attribute），（2）是(中文法符号的继承属性（inherited attribute）。
函数f通常以表达式的形式出现。
有时，某些语义规则的目的只是为了表达副作用，这类语义规则可以表达为过程调用或代码段。这可以理解为是定义相关产生式左部非终结符A的综合属性值，只是没有把此虚设的属性和:=号显现出来而已。
2,综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。
3,基于属性文法的处理，或语法制导的翻译（Syntax-Directed Translation）。
两类处理方法：（1）通过遍历分析树进行属性计算（树遍历方法）；（2）语法分析遍的同时进行属性计算（On-the-fly方法，即一遍扫描方法）。
树遍历方法步骤：（1）构造对应输入串的语法分析数；（2）构造依赖图；（3）若该依赖图是无圈的，则按造此无圈图的一种拓扑排序（topological sort）对分析树进行遍历，则可以计算所有的属性。依赖图的概念和构造方法见教材172页。
一遍扫描方法只适合于特定的语法制导定义。本课程只讨论S-属性定义（对应讲稿中的S-属性文法）和L-属性定义（对应讲稿中的L-属性文法）的情形。
4,S-属性定义中只包含综合属性。L-属性定义中可以有继承属性，但产生式右端某文法符号的继承属性的计算只取决于该符号左边文法符号（包括产生式左边的文法符号）的属性，可参见教材174页。S-属性定义是L-属性定义的一个特例。
5．S-属性定义的翻译通常采用自下而上的方式进行。若采用LR分析技术，可以通过扩充分析栈中的域，形成语义栈来存放综合属性的值，计算相应产生式左部文法符号的综合属性值刚好发生在每一步归约之前的时刻。
例如，假设有相应于产生式A(XYZ的语义规则A.a,= f（X.x,Y.y,Z.z）。在XYZ归约到A之前，X.x,Y.y,和 Z.z分别存放于语义栈的top，top-1和top-2的相应域中，因此A.a可以顺利求出。归约后，X.x,Y.y,Z.z被弹出，而在栈顶top的位置上存放A.a。
6．L-属性定义的翻译可以采用深度优先后序遍历的方式进行，参考如下算法（见影印板龙书297页）：
procedure dfvisit(n,node);
begin
for n的每一孩子m,从左到右 do
begin
计算m的继承属性值;
dfvisit(m)
end;
计算n的综合属性值
end
该算法可以和自上而下预测分析的过程对应。因此，基于LL(1)文法的L-属性定义可以采用这种方法进行翻译。
7,翻译模式（Translation Scheme）形式上类似于属性文法，但允许由{}括起来的语义规则集合（即语义动作）出现在产生式右端的任何位置。这样做的好处是可以显式地表达动作和属性计算的次序，而在前述的语法制导定义不体现计算次序。
在设计翻译模式时，必须作某些限制，以确保每个属性值在被访问到的时候已经存在。我们仅讨论两类受限的翻译模式：
一是受S-属性定义的启示，对于仅需要综合属性的情形，只要创建一个语义规则集合，放在相应产生式右端的末尾，把属性的赋值规则加入其中即可。
二是受L-属性定义的启示，对于即包含继承属性又包含综合属性的情形，必须注意：（1）产生式右端某个符号的继承属性的计算必须位于该符号之前；（2）每个计算规则不访问位于它右边符号的综合属性；（3）产生式左部非终结符的综合属性的计算只能在所用到的属性都已计算出来之后进行，通常放在相应产生式右端的末尾。
8,为借助于自上而下的预测分析技术进行语法制导翻译，可以采用如教材第175页的方法将含有左递归的翻译模式转换成不含左递归的翻译模式。
9,对基于适合于自上而下预测技术的翻译模式，语法制导翻译程序可以如下构造：
对每个非终结符A，构造一个函数，以A的每个继承属性为形参（call by reference），以A的综合属性为返回值。如同预测分析程序的构造，该函数代码的流程是根据当前的输入符号来决定调用哪个产生式。与每个产生式相关的代码根据产生式右端的终结符，非终结符，和语义规则集（语义动作），依从左右的次序完成下列工作：
（1）对终结符X，保存其综合属性x的值至专为X.x而声明的变量；然后调用匹配终结符（match_token）和取下一输入符号（next_token）的函数。
（2） 对非终结符B，利用相应的函数调用产生赋值语句c:=B(b1,b2,…,bk)，其中变量b1,b2,…,bk对应B的个继承属性，变量c对应B的综合属性。
（3）对语义规则集，直接copy其中每一语义规则（动作）来产生代码，只是将对属性的访问替换为属性对应的变量。
10．继承属性的自下而上计算。本课程主要涉及到三种技术：（1）从翻译模式中去掉嵌入在产生式中间的动作；（2）分析栈中的继承属性处理；（3）用综合属性代替继承属性。对于（1）、（3），通过教材176页8.2.4中的例子理解即可。对于（2），课堂上没来及讲，要点是复写规则（copy rules）的处理及其应用，这里对其进行一些简述：
自下而上翻译程序根据产生式A(XY的归约过程中，假设X的综合属性X.s已经出现在语义栈上。因为在Y以下子树的任何归约之前，X.s的值一直存在，因此它可以被Y继承。如果用复写规则Y.i:=X.s来定义Y的继承属性Y.i，则在需要Y.i时，可以使用X.s。这一点可以通过阅读课堂讲稿中的例子加以理解。
下面补充两个这种复写规则处理的应用例子，以加深理解。
考虑如下翻译模式：
S ( a A {C.i,= A.s} C
S ( b A B {C.i,= A.s} C
C ( c {C.s,= g(C.i)}
若直接应用上述复写规则的处理方法，则在使用C ( c进行归约时，C.i的值或存在于次栈顶（top-1），或存在于次次栈顶（top-2），不能确定用哪一个。一种可行的做法是引入新的非终结符M，将以上翻译模式改造为：
S ( a A {C.i,= A.s} C
S ( b A B {M.i,= A.s} M {C.i,= M.s} C
C ( c {C.s,= g(C.i)}
M ( ε {M.s,= M.i }
yacc这样处理
S ( a A M C
S ( b A B M C
C ( c {C.s,= g(C.i)}
M ( ε {C.i,= A.s}
这样，在使用C ( c进行归约时，C.i的值就一定可以通过访问次栈顶（top-1）得到。想一想，为什么？
另一个例子，考虑如下翻译模式：
S ( a A {C.i,= f(A.s)} C
这里，继承属性C.i不是通过复写规则来求值，而是通过普通函数f(A.s) 调用来计算。在计算C.i时，A.s在语义栈上，但f(A.s)并未不存在于语义栈。同样，一种做法是引入新的非终结符M，将以上翻译模式改造为：
S ( a A {M.i,= A.s} M {C.i,= M.s} C
M ( ε {M.s,= f(M.i)}
yacc这样处理
S ( a A M C
M ( ε {C.i,= f(A.s)}
这样就解决了上述问题。想一想，为什么？
11．课堂讲稿中倒数第2页中的Yacc程序片断。
输入串为bbabb时的输出结果为：
B1
B1
B1
B1
S3 NUM2
若将 A,B {$$ = num * 2;} A B {num = $2; $$ = $3+1; } 用如下两条产生式替换：
A,B M A B {num = $2; $$ = $3+1; }
M,{$$ = num * 2;}
请给出新的程序片断在输入串为bbabb时的输出结果，与前面的结果进行比较。
此外，请大家通过阅读Yacc文档，理解一下 $$ 出现在不同位置时的含义。如出现在产生式的末尾、中间的语义规则集（语义动作）中，出现在:=的左边和右边。
注：本材料中所提到的龙书是指：
ALFRED V.AHO，RAVI SETHI,JEFFREY D.ULLMAN
Compilers Principles,Techniques,and Tools
1,属性文法(语法制导的定义)（Syntax-Directed Definition）。
形式：每个产生式A((对应与之相关联的一个语义规则（semantic rules）集合，每条规则形如b:=f(c1,c2,…,ck)，其中f是一个函数，b,c1,c2,…,ck是该产生式中文法符号的属性（attributes），b有两个可能：（1）是A的综合属性（synthesized attribute），（2）是(中文法符号的继承属性（inherited attribute）。
函数f通常以表达式的形式出现。
有时，某些语义规则的目的只是为了表达副作用，这类语义规则可以表达为过程调用或代码段。这可以理解为是定义相关产生式左部非终结符A的综合属性值，只是没有把此虚设的属性和:=号显现出来而已。
2,综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。
3,基于属性文法的处理，或语法制导的翻译（Syntax-Directed Translation）。
两类处理方法：（1）通过遍历分析树进行属性计算（树遍历方法）；（2）语法分析遍的同时进行属性计算（On-the-fly方法，即一遍扫描方法）。
树遍历方法步骤：（1）构造对应输入串的语法分析数；（2）构造依赖图；（3）若该依赖图是无圈的，则按造此无圈图的一种拓扑排序（topological sort）对分析树进行遍历，则可以计算所有的属性。依赖图的概念和构造方法见教材172页。
一遍扫描方法只适合于特定的语法制导定义。本课程只讨论S-属性定义（对应讲稿中的S-属性文法）和L-属性定义（对应讲稿中的L-属性文法）的情形。
4,S-属性定义中只包含综合属性。L-属性定义中可以有继承属性，但产生式右端某文法符号的继承属性的计算只取决于该符号左边文法符号（包括产生式左边的文法符号）的属性，可参见教材174页。S-属性定义是L-属性定义的一个特例。
5．S-属性定义的翻译通常采用自下而上的方式进行。若采用LR分析技术，可以通过扩充分析栈中的域，形成语义栈来存放综合属性的值，计算相应产生式左部文法符号的综合属性值刚好发生在每一步归约之前的时刻。
例如，假设有相应于产生式A(XYZ的语义规则A.a,= f（X.x,Y.y,Z.z）。在XYZ归约到A之前，X.x,Y.y,和 Z.z分别存放于语义栈的top，top-1和top-2的相应域中，因此A.a可以顺利求出。归约后，X.x,Y.y,Z.z被弹出，而在栈顶top的位置上存放A.a。
6．L-属性定义的翻译可以采用深度优先后序遍历的方式进行，参考如下算法（见影印板龙书297页）：
procedure dfvisit(n,node);
begin
for n的每一孩子m,从左到右 do
begin
计算m的继承属性值;
dfvisit(m)
end;
计算n的综合属性值
end
该算法可以和自上而下预测分析的过程对应。因此，基于LL(1)文法的L-属性定义可以采用这种方法进行翻译。
7,翻译模式（Translation Scheme）形式上类似于属性文法，但允许由{}括起来的语义规则集合（即语义动作）出现在产生式右端的任何位置。这样做的好处是可以显式地表达动作和属性计算的次序，而在前述的语法制导定义不体现计算次序。
在设计翻译模式时，必须作某些限制，以确保每个属性值在被访问到的时候已经存在。我们仅讨论两类受限的翻译模式：
一是受S-属性定义的启示，对于仅需要综合属性的情形，只要创建一个语义规则集合，放在相应产生式右端的末尾，把属性的赋值规则加入其中即可。
二是受L-属性定义的启示，对于即包含继承属性又包含综合属性的情形，必须注意：（1）产生式右端某个符号的继承属性的计算必须位于该符号之前；（2）每个计算规则不访问位于它右边符号的综合属性；（3）产生式左部非终结符的综合属性的计算只能在所用到的属性都已计算出来之后进行，通常放在相应产生式右端的末尾。
8,为借助于自上而下的预测分析技术进行语法制导翻译，可以采用如教材第175页的方法将含有左递归的翻译模式转换成不含左递归的翻译模式。
9,对基于适合于自上而下预测技术的翻译模式，语法制导翻译程序可以如下构造：
对每个非终结符A，构造一个函数，以A的每个继承属性为形参（call by reference），以A的综合属性为返回值。如同预测分析程序的构造，该函数代码的流程是根据当前的输入符号来决定调用哪个产生式。与每个产生式相关的代码根据产生式右端的终结符，非终结符，和语义规则集（语义动作），依从左右的次序完成下列工作：
（1）对终结符X，保存其综合属性x的值至专为X.x而声明的变量；然后调用匹配终结符（match_token）和取下一输入符号（next_token）的函数。
（2） 对非终结符B，利用相应的函数调用产生赋值语句c:=B(b1,b2,…,bk)，其中变量b1,b2,…,bk对应B的个继承属性，变量c对应B的综合属性。
（3）对语义规则集，直接copy其中每一语义规则（动作）来产生代码，只是将对属性的访问替换为属性对应的变量。
10．继承属性的自下而上计算。本课程主要涉及到三种技术：（1）从翻译模式中去掉嵌入在产生式中间的动作；（2）分析栈中的继承属性处理；（3）用综合属性代替继承属性。对于（1）、（3），通过教材176页8.2.4中的例子理解即可。对于（2），课堂上没来及讲，要点是复写规则（copy rules）的处理及其应用，这里对其进行一些简述：
自下而上翻译程序根据产生式A(XY的归约过程中，假设X的综合属性X.s已经出现在语义栈上。因为在Y以下子树的任何归约之前，X.s的值一直存在，因此它可以被Y继承。如果用复写规则Y.i:=X.s来定义Y的继承属性Y.i，则在需要Y.i时，可以使用X.s。这一点可以通过阅读课堂讲稿中的例子加以理解。
下面补充两个这种复写规则处理的应用例子，以加深理解。
考虑如下翻译模式：
S ( a A {C.i,= A.s} C
S ( b A B {C.i,= A.s} C
C ( c {C.s,= g(C.i)}
若直接应用上述复写规则的处理方法，则在使用C ( c进行归约时，C.i的值或存在于次栈顶（top-1），或存在于次次栈顶（top-2），不能确定用哪一个。一种可行的做法是引入新的非终结符M，将以上翻译模式改造为：
S ( a A {C.i,= A.s} C
S ( b A B {M.i,= A.s} M {C.i,= M.s} C
C ( c {C.s,= g(C.i)}
M ( ε {M.s,= M.i }
yacc这样处理
S ( a A M C
S ( b A B M C
C ( c {C.s,= g(C.i)}
M ( ε {C.i,= A.s}
这样，在使用C ( c进行归约时，C.i的值就一定可以通过访问次栈顶（top-1）得到。想一想，为什么？
另一个例子，考虑如下翻译模式：
S ( a A {C.i,= f(A.s)} C
这里，继承属性C.i不是通过复写规则来求值，而是通过普通函数f(A.s) 调用来计算。在计算C.i时，A.s在语义栈上，但f(A.s)并未不存在于语义栈。同样，一种做法是引入新的非终结符M，将以上翻译模式改造为：
S ( a A {M.i,= A.s} M {C.i,= M.s} C
M ( ε {M.s,= f(M.i)}
yacc这样处理
S ( a A M C
M ( ε {C.i,= f(A.s)}
这样就解决了上述问题。想一想，为什么？
11．课堂讲稿中倒数第2页中的Yacc程序片断。
输入串为bbabb时的输出结果为：
B1
B1
B1
B1
S3 NUM2
若将 A,B {$$ = num * 2;} A B {num = $2; $$ = $3+1; } 用如下两条产生式替换：
A,B M A B {num = $2; $$ = $3+1; }
M,{$$ = num * 2;}
请给出新的程序片断在输入串为bbabb时的输出结果，与前面的结果进行比较。
此外，请大家通过阅读Yacc文档，理解一下 $$ 出现在不同位置时的含义。如出现在产生式的末尾、中间的语义规则集（语义动作）中，出现在:=的左边和右边。
注：本材料中所提到的龙书是指：
ALFRED V.AHO，RAVI SETHI,JEFFREY D.ULLMAN
Compilers Principles,Techniques,and Tools
