属性文法本节要点
语义
属性文法
属性等式
合成属性和继承属性
依赖图
属性计算顺序
S-属性文法和 L-属性文法属性文法本节要点
属性文法的应用
值的计算
类型计算
抽象语法树生成
翻译模式语义分析、属性文法主要参考资料
1.程序设计语言 —— 实践之路
Michael L,Scott,Programming Languages Pragmatics,Morgan
Kaufmann,2000,2005）
中文版由裘宗燕译,电子工业出版社出版,2005
2.编译原理及实践,Kenneth C.Louden.机械工业出版社,1997
3.程序设计语言编译原理 (第 3版）,陈火旺,国防工业出版社,2000
4.编译原理,李建中等译,机械工业出版社,2005
(Compilers Principles,Techniques,and Tools)
语义语法分析关注程序的结构，而语义关注的是程序的意义。
语义,一组规则,用它可以定义一个程序的意义 。
语义规则可分为静态语义和动态语义
编译器在编译期间推行静态语义规则，生成的代码在执行时实施动态语义规则
有些错误不可能在编译时捕获，必须推迟到程序执行时，如：被 0除，数组下标越界等。
语义的描述方法描述方法：
自然语言描述
隐藏错误、二义性和不完整性
形式描述：
操作语义
指称语义
代数语义
属性文法 (目前流行的方法）
语义分析和中间代码生成都可以通过在分析树或者语法树上加标注的方法实现，这些标注称为 属性 。
语义分析器的角色不同的语言语义分析器扮演不同的角色
强制不同
FORTRAN和 C允许在表达式中混合使用各种类型；
Ada一类的语言根本不允许。
执行动态检查多少不同
C语言几乎不做，除了硬件顺便做的（除 0，数组越界等）
Java尽可能地检查许多规则，以便保证无法信任的程序不会对其运行所在的机器的存储或文件造成任何破坏。
通常语义分析器创建一棵带标注的语法树，随后由中间代码生成器将它线性化为某种理想机器的汇编语言。
语义分析和中间代码生成可以与语法分析交错进行，
也可单独作为一遍。
2.6.1 属性文法属性文法 （ 属性翻译文法 ）
Knuth在 1968年提出
在上下文无关文法的基础上,为每个文法符号
（ 终结符或非终结符 ） 配备若干相关的,值,（ 称为属性 ） 。
属性描述文法符号对应程序结构的特性,如：
变量的数据类型 。
符号表
表达式的值 。
存储器中变量的位置
程序的目标代码
数的有效位数 。
2.6.1 属性文法属性的表示：
属性直接与语言的文法符号 (终结符号或非终结符号 )
相联系 。 如果 X是一个文法符号,a 是 X的一个属性,
那么我们把与 X关联的 a的值记作 X.a。
属性可以进行计算和传递语义规则,对于文法的每个产生式都配备了一组属性的计算规则 （ 属性等式 ）
属性文法可看成是上下文无关文法＋语义规则 。
若有一个属性的集合 a1,.,,,ak,语法制导语义的原理应用于每个文法规则
X0→X 1 X2,,,Xn ( X0∈V N,Xi∈(V N∪V T) )，每个文法符号 Xi的属性 Xi,aj的值与规则中其他符号的属性值有关。如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来。每个关系用属性等式或语义规则表示，形式如下：
Xi.aj=fij(X0.a1,...,X0.ak，
X1.a1,...,X1.ak,...,Xn.a1,...,Xn.ak )
属性等式思考为什么在属性等式中说,如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来,？
思考解答为什么说在属性等式中,如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来,？
答：这类似于张三是人的一个实例，李四也是人的一个实例，但是他们的特征是不同的，是两个不同的对象。
属性文法举例例 考虑下列简单的整数算术表达式文法：
exp → exp + term | exp - term | term
term → term * factor | factor
factor →(exp)| number
文法规则 语义规则
exp1→exp 2+term exp1.val=exp2.val+term.val
exp1→exp 2-term exp1.val=exp2.val-term.val
exp→term exp.val=term.val
term1→term 2*factor term1.val=term2.val*factor.val
term→factor term.val=factor.val
factor→(exp) factor.val=exp.val
factor→number factor.val=number.val
( 34 - 3 )*4 2 的语法树，显示例 2中属性文法的 val属性计算：
属性文法举例例 带进制数可以是八进制或十进制的，分别通过一个字符后缀 o
(八进制 )或 d (十进制 )来表示。文法如下所示：
based-num → num basechar
basechar → o | d
num → num digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
属性文法举例分析：
在带进制文法中，有值和进制两个属性，分别用 val和
base表示。
只有看到一个数末尾的 o或者 d时，才能确定该数是十进制还是八进制，故有下列属性等式关系：
文法规则 语义规则
based-num→ num basechar based -num.val=num.val
num.base=basechar.base
basechar→o basechar.base=8
basechar→d basechar.base=10
属性文法举例
num1→num 2 digit num1.val=
if digit.val=error or num2.val=error
then error
else num2.val*num1.base+digit.val
num2.base=num1.base
digit.base=num1.base
属性文法举例
num→digit num.val=digit.val
digit.base=num.base
digit→0 digit.val=0
digit→1 digit.val=1
.,,,,,
digit→7 digit.val=7
digit→8 digit.val=if digit.base=8
then error else 8
digit→9 digit.val=if digit.base=8
then error else 9
属性和属性文法
345o属性计算的语法树属性
合成属性：,自下而上,传递信息
继承属性：,自上而下,传递信息一个属性 a 是合成的，如果以其对应结构为左部的文法规则 A →X 1 X2,,,Xn,左边仅有一个 a 的相关属性等式有以下形式：
A.a = f (X1.a1,.,,,X1,ak,.,,,Xn,a1,.,,,
Xn,ak )
在语法树中，一个结点的合成属性的值由其子结点的属性值确定。
使用自底向上的方法在每一个结点处使用语义规则计算合成属性的值不是合成属性的属性都是继承属性。
一个属性文法中所有的属性都是合成的，就称作 S属性文法 (S-attributed grammar)。
S属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算。
procedure PostEval(T,treenode);
beginfor each child C of T do PostEval(C);
compute all synthesized attributes of T;end;
说明
终结符只有合成属性,由词法分析器提供
非终结符既可有合成属性也可有继承属性
文法开始符号的所有继承属性作为属性计算前的初始值
对出现在产生式右边的继承属性和出现在产生式左边的合成属性都必须提供一个计算规则 。 属性计算规则中只能使用相应产生式中的文法符号的属性
出现在产生式左边的继承属性和出现在产生式右边的合成属性不由所给的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供语义规则所描述的工作可以包括属性计算,静态语义检查,符号表操作,代码生成等等 。
例,考虑非终结符 A,B和 C,其中,A有一个继承属性 a和一个合成属性 b,B有合成属性 c,C有继承属性 d。 产生式
A→BC可能有规则
C.d:=B.c+1
A.b:=A.a+B.c
而属性 A.a和 B.c在其它地方计算继承属性
在语法树中，一个结点的继承属性由此结点的父结点和 /或兄弟结点的某些属性确定
用继承属性来表示程序设计语言结构中的上下文依赖关系很方便产 生 式 语 义 规 则
D→TL L.in,= T.type
T→int T.type,= integer
T→real T.type,= real
L→L1,id L1.in,=L.in
addtype(id.entry,L.in)
L→id addtype(id.entry,L.in)
句子 real id1,id2,id3的带注释的语法树
id1
L,id2
L,id3
L
real
T
D
.type=real,in=real
.in=real
.in=real
2.6.2 基于属性文法的的处理方法由源程序的语法结构所驱动的处理办法就是语法制导翻译法语义规则的计算可能产生代码,在符号表中存放信息,给出错误信息或执行任何其它动作 。 对输入符号串的翻译也就是根据语义规则进行计算的结果 。
输入串 语法树 依赖图 语义规则计算次序
2.6.2.1 依赖图在一棵语法树中的结点的继承属性和合成属性之间的相互依赖关系可以由称作 依赖图 的一个有向图来描述为每一个包含过程调用的语义规则引入一个虚合成属性 b,这样把每一个语义规则都写成
b:=f(c1,c2,…,ck)
的形式依赖图中为每一个属性设置一个结点,如果属性
b依赖于属性 c,则从属性 c的结点有一条有向边连到属性 b的结点 。
for 语法树中每一结点 n do
for 结点 n的文法符号的每一个属性 a do
为 a在依赖图中建立一个结点；
for语法树中每一个结点 n do
for 结点 n所用产生式对应的每一个语义规则
b:=f(c1,c2,…,ck ) do
for i:=1 to k do
从 ci结点到 b结点构造一条有向边；
E→E1＋ E2 E.val:=E1.val+E2.val
E1 + E2
E val
val val
句子 real id1,id2,id3的带注释的语法树的依赖图
id1
L,id
2
L,id3
L
real
T
D
4
type
5
in
6
7
in
8
9
in
10
1
entry
2
entry
3
entry
如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为 良定义的属性的计算次序一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序属性文法说明的翻译是很精确的
基础文法用于建立输入符号串的语法分析树
根据计算语义规则建立依赖图
从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序输入串 语法树 依赖图 语义规则计算次序句子 real id1,id2,id3的带注释的语法树的依赖图
id1
L,id
2
L,id3
L
real
T
D
4
type
5
in
6
7
in
8
9
in
10
1
entry
2
entry
3
entry
a4:=real;
a5:=a4
addtype (id3.entry,a5);
a7:=a5;
addtype (id2.entry,a7);
a9:=a7
addtype (id1.entry,a9);
2.6.2.2 树遍历的属性计算方法通过树遍历的方法计算属性的值
假设语法树已经建立起了,并且树中已带有开始符号的继承属性和终结符的合成属性
以某种次序遍历语法树,直至计算出所有属性
深度优先,从左到右的遍历
While 还有未被计算的属性 do
VisitNode(S) /*S是开始符号 */
procedure VisitNode (N:Node) ;
begin
if N是一个非终结符 then
/*假设它的产生式为 N→X1…Xm*/
for i,=1 to m do
if not Xi?VT then /*即 Xi是非终结符 */
begin
计算 Xi的所有能够计算的继承属性；
VisitNode (Xi)
end;
计算 N的所有能够计算的合成属性
end
产 生 式 语 义 规 则
S→XYZ Z.h,= S.a
X.c,= Z.g
S.b,= X.d -2
Y.e,= S.b
X→x X.d,=2*X.c
Y→y Y.f,= Y.e*3
Z→z Z.g,=Z.h+1
例 考虑属性的文法 G。其中,S有继承属性 a，
合成属性 b； X有继承属性 c、合成属性 d； Y有继承属性 e、合成属性 f； Z有继承属性 h、合成属性 g
假设 S.a的初始值为 0，输入串为 xyz
S:a=0
X Y Z
x y z
:h=0
g=1
:c=1
d=2
,b=0
:e=0
f=0
2.6.2.3 一遍扫描的处理方法一遍扫描的处理方法是在语法分析的同时计算属性值，与下列两个因素密切相关：
所采用的语法分析方法
属性的计算次序
L－属性文法适合于一遍扫描的自上而下分析
S－属性文法适合于一遍扫描的自下而上分析按一遍扫描编译的模式，所谓 语法制导翻译法,直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则语义规则被计算的时机
在自上而下语法分析中，一个产生式匹配输入串成功时
在自下而上分析中，当一个产生式被用于进行归约时
2.6.2.4 抽象语法树在语法树中去掉那些对翻译不必要的信息，
从而获得更有效的源程序中间表示。这种经变换后的语法树称之为 抽象语法树
(Abstract Syntax Tree)
B S1 S2
if_then_else
S→if B then S 1 else S2?3*5+4
*
5
4
+
3
建立表达式的抽象语法树
mknode (op,left,right) 建立一个运算符号结点,标号是 op,两个域 left和 right分别指向左子树和右子树 。
mkleaf (id,entry) 建立一个标识符结点,
标号为 id,一个域 eutry指向标识符在符号表中的入口 。
mkleaf (num,val) 建立一个数结点,标号为 num,一个域 val用于存放数的值 。
建立抽象语法树的语义规则产 生 式 语 义 规 则
E→E1+T E.nptr,= mknode( ‘+’,E1.nptr,T.nptr )
E→E1-T E.nptr,= mknode( ‘-’,E1.nptr,T.nptr )
E→T E.nptr,= T.nptr
T→ (E) T.nptr,= E.nptr
T→id T.nptr,= mkleaf( id,id.entry )
T→num T.nptr,= mkleaf( num,num.val )
a－ 4＋ c的抽象语法树
E nptr T nptr
E nptr
To entry for a
E
T nptr
id
- T nptr id
id-
id num 4
+
To entry for c
2.6.3 S-属性文法的自下而上计算一般的属性文法的翻译器可能比较难建立，但
S-属性文法的翻译器很容易建立。
S-属性文法：只含有合成属性合成属性可以在分析输入符号串的同时由自下而上的分析器来计算。
分析器可以保存与栈中文法符号有关的合成属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。
在分析栈中使用一个附加的域来存放合成属性值 （加一个值栈）
假设语义规则 A.a:=f(X.x,Y.y,Z.z)是对应于产生式 A→XYZ的
S m Z,z Z
S m - 1 Y,y Y
S m - 2 X,x X
… … …
S 0 — #
TO P
S’ m - 2 A.a A
… … …
S 0 — #
T O P
用 LR分析器实现台式计算器产生式 代 码 段
L→En print(val[top])
E→E1+T val[ntop],= val[top-2]+val[top]
E→T
T→T1*F val[ntop],= val[top-2]*val[top]
T→F
F→ (E) val[ntop],=val[top-1]
F→digit ntop表示新的栈顶输入 state val 用到的产生式
3*5+4n — —
*5+4n 3 3
*5+4n F 3 F→digit
*5+4n T 3 T→F
5+4n T* 3 -
+4n T*5 3 - 5
+4n T*F 3 - 5 F→digit
+4n T 15 T→T*F
输入 state val 用到的产生式
+4n E 15 E→T
4n E+ 15-
n E+4 15- 4
n E+F 15- 4 F→digit
n E+T 15- 4 T→F
n E 19 E→E+T
En 19-
L 19 L→En
2.6.4 L-属性文法和自顶向下翻译通过深度优先的方法对语法树进行遍历，
计算属性文法的所有属性值
LL（ 1）：自上而下分析方法，深度优先建立语法树一个属性文法称为 L-属性文法,如果对于每个产生式 A→X1X2… Xn，其每个语义规则中的每个属性或者是合成属性，或者是 Xj(1?j?n)的一个继承属性且这个继承属性仅依赖于：
(1) 产生式 Xj的左边符号 X1,X2,…,Xj-1的属性；
(2) A的继承属性。
S-属性文法一定是 L-属性文法例：试判断下述文法是否 L-属性文法产 生 式 语 义 规 则
A→LM L.i,= l(A.i)
M.i,=m(l.s)
A→QR R.i,= r(A.i)
Q.i,=q(R.s)
A.s,=f(Q.s)
2.6.4.1 翻译模式属性文法是隐去实现细节的关于语言翻译的高级规范说明 。
翻译模式是另一种适合语法制导翻译的方式
给出了使用语义规则进行计算的次序,这样就可把某些实现细节表示出来
在翻译模式中,和文法符号相关的属性和语义规则 （ 这里我们也称 语义动作 ）,用花括号 { }括起来,插入到产生式右部的合适位置上,从而给出了计算顺序 。
翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式
E→TR
R→addop T {print(addop.lexeme)} R1 |?
T→num {print(num.val)}
-
E
T R
9 {print(‘9’)} T R
5 {print(‘5’)}
{print(‘-’)}
+ T
2 {print(‘2’)}
R{print(‘+’)}
9+5-2的语法树 (备注）
设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。
L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。
建立翻译模式当只需要合成属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾产生式 语义规则
T→T1*F T.val:=T1.val× F.val
建立产生式和语义动作：
T→T1*F {T.val:=T1.val× F.val}
建立翻译模式如果既有合成属性又有继承属性，在建立翻译模式时就必须保证：
1,产生式右边的符号的继承属性必须在这个符号前面的动作中计算出来。
2,一个动作不能引用这个动作右边的符号的合成属性。
3,产生式左边非终结符的合成属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。
翻译模式试判断下列是否正确的翻译模式：
S→A1A2 {A1.in:=1; A2.in:=2}
A→a {print(A.in)}
翻译模式
S→A1A2 {A1.in:=1; A2.in:=2}
A→a {print(A.in)}
不正确因为它不符号第一条规则当对 aa进行自顶向下分析时，当 A与 a匹配时，要打印
A.in,但此时 A.in还未定义。
可改为
S→ {A1.in:=1; ｝ A1｛ A2.in:=2}A2
A→a {print(A.in)}
通常给定一个 L-属性文法，可以建立满足前述三个条件的翻译模式。
翻译模式举例
—— 基于数学格式语言 EQN
给定输入
E sub 1,val
EQN把 E,1和,val分别按不同的大小放在相关位置上。
E 1,val
盒子的语法制导翻译识别输入并进行格式安放的 L-属性文法产 生 式 语 义 规 则
S→B B.ps,=10
S.ht,=B.ht
B→B1B2 B1.ps,=B.ps
B2.ps,=B.ps
B.ht,= max(B1.ht,B2.ht)
B→B1 sub B2 B1.ps,=B.ps
B2.ps,=shrink(B.ps)
B.ht,=disp(B1.ht,B2.ht)
B→text B.ht,=text.h× B.ps
非终结符 B（表示盒子）代表公式。
B→B1B2代表两个并列的盒子
B→B1 sub B2代表 B2比 B1小，放在其下脚标位置。
Ps是继承属性，影响了公式的高度。此文法是一个 L-属性文法。
Shrink将 B2.ps减少 30％。
Disp函数将 B2放在 B1的下标位置，并计算 B的高度。
翻译模式
S → {B.ps:=10}
B {S.ht:=B.ht}
B → {B1.ps:=B.ps}
B1 { B2.ps:=B.ps }
B2 {B.ht:=max(B1.ht,B2.ht)}
B → {B1.ps:=B.ps}
B1
sub {B2.ps:=shrink(B.ps)}
B2 {B.ht:=disp(B1.ht,B2.ht)}
B → text{B.ht:=text.h× B.ps}
2.6.4.2 自顶向下翻译动作是在处于相同位置上的符号被展开
（匹配成功）时执行的。
为了构造不带回溯的自顶向下语法分析，
必须消除文法中的左递归当消除一个翻译模式的基本文法的左递归时同时考虑属性 —— 适合带合成属性的翻译模式关于算术表达式的左递归文法相应的翻译模式
E→E1+T {E.val:=E1.val+T.val}
E→E1-T {E.val:=E1.val-T.val}
E→T {E.val:=T.val}
T→(E) {T.val:=E.val}
T→num {T.val:=num.val}
消除左递归，构造新的翻译模式
E → T {R.i:=T.val}
R {E.val:=R.s}
R → +
T {R1.i:=R.i+T.val}
R1 {R.s:=R1.s}
R → -
T {R1.i:=R.i-T.val}
R1 {R.s:=R1.s}
R →? {R.s:=R.i}
T → (
E
) {T.val:=E.val}
T → num {T.val:=num.val}
计算表达式 9－ 5＋ 2
E
T R
numnum.val=9
.val=9,i=9
- T R
numnum.val=5
.val=5,i=4
+ T R
numnum.val=2
.val=2,i=6
R.s=6
R.s=6
R.s=6
.s=6
一般方法假设有翻译模式：
A→A1Y {A.a:=g(A1.a,Y.y)}
A→X {A.a:=f(X.x)}
它的每个文法符号都有一个合成属性，用小写字母表示,g和 f是任意函数。
消除左递归：
A→XR
R→YR |?
翻译模式变为,
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}
XYY在旧文法的语法树
—— 自下而上的分析
X
A.a=f(X.x) Y1
A.a=g(f(X.x),Y1.y) Y2
A.a=g(g(f(X.x),Y1.y),Y2.y)
XYY在新文法的语法树
—— 自顶向下的语法分析
A
X R.i=f(X.x)
Y1 R.i= g(f(X.x),Y1.y)
Y2 R.i= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
.a= g(g(f(X.x),Y1.y),Y2.y)
两种方法得到相同的结果！
构造抽象语法树的属性文法定义转化成翻译模式属性文法如下：
E→E1+T {E.nptr:=mknode(‘+’,E1.nptr,T.nptr)}
E→E1-T {E.nptr:=mknode(‘-’,E1.nptr,T.nptr)}
E→T {E.nptr:=T.nptr}
问题：翻译模式与属性文法有什么区别？
翻译模式考虑了计算顺序等细节。
构造抽象语法树的属性文法定义转化成翻译模式E → T {R.i:=T.nptr}
R {E.nptr:=R.s}
R → +
T {R1.i:=mknode(‘+’,R.i,T.nptr)}
R1 {R.s:=R1.s}
R → －
T {R1.i:=mknode(‘－ ’,R.i,T.nptr)}
R1 {R.s:=R.s}
R →? {R.s:=R.i}
T → (
E
) {T.nptr:=E.nptr}
T → id {T.nptr:=mkleaf(id,id.entry)}
T → num {T.nptr:=mkleaf(num,num.val)}
使用继承属性构造 a－ 4＋ c的抽象语法树E
T R
id
To entry for a
id
T.nptr
- T
num
num 4
T.nptr R,i
-
R
+ T R
id
To entry for c
id
T.nptr R,i
+
R,i
R,s
R,s
R,s
E.nptr
2.6.4.3 递归下降翻译器的设计如何在递归下降分析中实现翻译模式，
构造 递归下降翻译器设计递归下降翻译器的方法
1,
对每个非终结符 A构造一个函数过程，对 A的每个继承属性设置一个形式参数
函数的返回值为 A的合成属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个合成属性
A对应的函数过程中，为出现在 A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。
设计递归下降翻译器的方法
2,非终结符 A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。
设计递归下降翻译器的方法
3,每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：
i) 对于带有合成属性 x的终结符 X，把 x的值存入为 X.x设置的变量中。然后产生一个匹配 X的调用，并继续读入一个输入符号。
ii) 对于每个非终结符 B，产生一个右边带有函数调用的赋值语句
c=B(b1,b2,…,bk)，其中,b1,b2,…,bk是为 B的继承属性设置的变量,c是为 B的合成属性设置的变量。
iii) 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。
设计递归下降翻译器
E → T {R.i:=T.nptr}
R {E.nptr:=R.s}
R → +
T {R1.i:=mknode(‘+’,R.i,T.nptr)}
R1 {R.s:=R1.s}
R → －
T {R1.i:=mknode(‘－ ’,R.i,T.nptr)}
R1 {R.s:=R.s}
R →? {R.s:=R.i}
T → (
E
) {T.nptr:=E.nptr}
T → id {T.nptr:=mkleaf(id,id.entry)}
T → num {T.nptr:=mkleaf(num,num.val)}
例：下述文法是 LL(1)的，因此可以用于自顶向下的分析。
非终结符 E,R,T的函数及其参数类型
function E:↑AST-node;
function R(in:↑AST-node),↑AST-node;
function T,↑AST-node;
用 oddop代表＋和－
R → oddop
T {R1.i:=mknode(addop,lexme,R.i,T.nptr)}
R1 {R.s:=R1.s}
R→? {R.s:=R.i}
产生式 R→addop TR|?的递归分析过程
procedare R;
begin
if sym=addop then begin
advance;T; R
end
else begin /*do nothing*/
end
end;
function R (in:↑AST-node),↑AST-node;
var nptr,i1,s1,s,↑AST-node;
addoplexeme,char;
begin
if sym=addop then begin
/*产生式 R→addop TR */
addoplexeme:=lexval;
advance;
nptr:=T;
i1:=mknode (addoplexeme,in,nptr);
s1:=R (i1)
s:=s1
end
else s:=in;
return s
end;
2.6.5 自下而上计算继承属性在自下而上的分析过程中实现 L-属性文法的方法可实现任何基于 LL（ 1）文法的 L-属性文法，还可以实现许多（不是所有）基于
LR（ 1）文法的 L-属性文法
2.6.5.1 从翻译模式中去掉嵌入在产生式中间的动作在自下而上的分析方法中，要求把所有的语义动作都放在产生式的末尾转换方法，它可以使所有嵌入的动作都出现在产生式的末尾
在基础文法中加入一些新的产生式，形如：
M→?
把嵌入在产生式中的每个语义动作用不同的标记非终结符 M代替，并把这个动作放在产生式 M→?的末尾转换举例翻译模式
E → TR
R → ＋ T {print (‘＋ ’ )} R | － T {print
(‘－ ’ )}R|?
T → num {print (num.val)}
转换为
E → TR
R → ＋ TMR | － TNR |?
T → num {print (num.val)}
M →? {print (‘＋ ’ )}
N →? {print (‘－ ’ )}
分析栈中的继承属性形如 Y.i＝ X.s的规则称为复制规则在自底向上的语法分析中，复制规则在继承属性的计算过程中起 着重要作用。
例：要实现的类型说明文法翻译模式如下：
D→T {L.in,= T.type }
L
T→int {T.type,= integer}
T→real {T.type,= real }
L→{ L1.in,=L.in}
L1,id{addtype(id.entry,L.in)}
L→id {addtype(id.entry,L.in) }
分析栈中的继承属性分析自底向上语法分析器在输入
real p,q,r上所做的移动。
用合成属性代替继承属性有时可通过改写基础文法来避免使用继承属性。
如,Pascal语言的类型声明文法如下：
D?L:T
T?integer|char
L?L,id | id
由于标识符由 L产生，但类型却不在 L的子树中，
因此仅用合成属性不能把标识符与类型联系在一起。
不是 L-属性用合成属性代替继承属性但可改写文法为：
D?id,L
L?,id L |,T
T?integer | real
将类型变为标识符表的最后一个元素，
化为子结点，类型变成合成属性。
当标识符由 L产生时，其类型可填入符号表中。
语义
属性文法
属性等式
合成属性和继承属性
依赖图
属性计算顺序
S-属性文法和 L-属性文法属性文法本节要点
属性文法的应用
值的计算
类型计算
抽象语法树生成
翻译模式语义分析、属性文法主要参考资料
1.程序设计语言 —— 实践之路
Michael L,Scott,Programming Languages Pragmatics,Morgan
Kaufmann,2000,2005）
中文版由裘宗燕译,电子工业出版社出版,2005
2.编译原理及实践,Kenneth C.Louden.机械工业出版社,1997
3.程序设计语言编译原理 (第 3版）,陈火旺,国防工业出版社,2000
4.编译原理,李建中等译,机械工业出版社,2005
(Compilers Principles,Techniques,and Tools)
语义语法分析关注程序的结构，而语义关注的是程序的意义。
语义,一组规则,用它可以定义一个程序的意义 。
语义规则可分为静态语义和动态语义
编译器在编译期间推行静态语义规则，生成的代码在执行时实施动态语义规则
有些错误不可能在编译时捕获，必须推迟到程序执行时，如：被 0除，数组下标越界等。
语义的描述方法描述方法：
自然语言描述
隐藏错误、二义性和不完整性
形式描述：
操作语义
指称语义
代数语义
属性文法 (目前流行的方法）
语义分析和中间代码生成都可以通过在分析树或者语法树上加标注的方法实现，这些标注称为 属性 。
语义分析器的角色不同的语言语义分析器扮演不同的角色
强制不同
FORTRAN和 C允许在表达式中混合使用各种类型；
Ada一类的语言根本不允许。
执行动态检查多少不同
C语言几乎不做，除了硬件顺便做的（除 0，数组越界等）
Java尽可能地检查许多规则，以便保证无法信任的程序不会对其运行所在的机器的存储或文件造成任何破坏。
通常语义分析器创建一棵带标注的语法树，随后由中间代码生成器将它线性化为某种理想机器的汇编语言。
语义分析和中间代码生成可以与语法分析交错进行，
也可单独作为一遍。
2.6.1 属性文法属性文法 （ 属性翻译文法 ）
Knuth在 1968年提出
在上下文无关文法的基础上,为每个文法符号
（ 终结符或非终结符 ） 配备若干相关的,值,（ 称为属性 ） 。
属性描述文法符号对应程序结构的特性,如：
变量的数据类型 。
符号表
表达式的值 。
存储器中变量的位置
程序的目标代码
数的有效位数 。
2.6.1 属性文法属性的表示：
属性直接与语言的文法符号 (终结符号或非终结符号 )
相联系 。 如果 X是一个文法符号,a 是 X的一个属性,
那么我们把与 X关联的 a的值记作 X.a。
属性可以进行计算和传递语义规则,对于文法的每个产生式都配备了一组属性的计算规则 （ 属性等式 ）
属性文法可看成是上下文无关文法＋语义规则 。
若有一个属性的集合 a1,.,,,ak,语法制导语义的原理应用于每个文法规则
X0→X 1 X2,,,Xn ( X0∈V N,Xi∈(V N∪V T) )，每个文法符号 Xi的属性 Xi,aj的值与规则中其他符号的属性值有关。如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来。每个关系用属性等式或语义规则表示，形式如下：
Xi.aj=fij(X0.a1,...,X0.ak，
X1.a1,...,X1.ak,...,Xn.a1,...,Xn.ak )
属性等式思考为什么在属性等式中说,如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来,？
思考解答为什么说在属性等式中,如果同一个符号 Xi在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来,？
答：这类似于张三是人的一个实例，李四也是人的一个实例，但是他们的特征是不同的，是两个不同的对象。
属性文法举例例 考虑下列简单的整数算术表达式文法：
exp → exp + term | exp - term | term
term → term * factor | factor
factor →(exp)| number
文法规则 语义规则
exp1→exp 2+term exp1.val=exp2.val+term.val
exp1→exp 2-term exp1.val=exp2.val-term.val
exp→term exp.val=term.val
term1→term 2*factor term1.val=term2.val*factor.val
term→factor term.val=factor.val
factor→(exp) factor.val=exp.val
factor→number factor.val=number.val
( 34 - 3 )*4 2 的语法树，显示例 2中属性文法的 val属性计算：
属性文法举例例 带进制数可以是八进制或十进制的，分别通过一个字符后缀 o
(八进制 )或 d (十进制 )来表示。文法如下所示：
based-num → num basechar
basechar → o | d
num → num digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
属性文法举例分析：
在带进制文法中，有值和进制两个属性，分别用 val和
base表示。
只有看到一个数末尾的 o或者 d时，才能确定该数是十进制还是八进制，故有下列属性等式关系：
文法规则 语义规则
based-num→ num basechar based -num.val=num.val
num.base=basechar.base
basechar→o basechar.base=8
basechar→d basechar.base=10
属性文法举例
num1→num 2 digit num1.val=
if digit.val=error or num2.val=error
then error
else num2.val*num1.base+digit.val
num2.base=num1.base
digit.base=num1.base
属性文法举例
num→digit num.val=digit.val
digit.base=num.base
digit→0 digit.val=0
digit→1 digit.val=1
.,,,,,
digit→7 digit.val=7
digit→8 digit.val=if digit.base=8
then error else 8
digit→9 digit.val=if digit.base=8
then error else 9
属性和属性文法
345o属性计算的语法树属性
合成属性：,自下而上,传递信息
继承属性：,自上而下,传递信息一个属性 a 是合成的，如果以其对应结构为左部的文法规则 A →X 1 X2,,,Xn,左边仅有一个 a 的相关属性等式有以下形式：
A.a = f (X1.a1,.,,,X1,ak,.,,,Xn,a1,.,,,
Xn,ak )
在语法树中，一个结点的合成属性的值由其子结点的属性值确定。
使用自底向上的方法在每一个结点处使用语义规则计算合成属性的值不是合成属性的属性都是继承属性。
一个属性文法中所有的属性都是合成的，就称作 S属性文法 (S-attributed grammar)。
S属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算。
procedure PostEval(T,treenode);
beginfor each child C of T do PostEval(C);
compute all synthesized attributes of T;end;
说明
终结符只有合成属性,由词法分析器提供
非终结符既可有合成属性也可有继承属性
文法开始符号的所有继承属性作为属性计算前的初始值
对出现在产生式右边的继承属性和出现在产生式左边的合成属性都必须提供一个计算规则 。 属性计算规则中只能使用相应产生式中的文法符号的属性
出现在产生式左边的继承属性和出现在产生式右边的合成属性不由所给的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供语义规则所描述的工作可以包括属性计算,静态语义检查,符号表操作,代码生成等等 。
例,考虑非终结符 A,B和 C,其中,A有一个继承属性 a和一个合成属性 b,B有合成属性 c,C有继承属性 d。 产生式
A→BC可能有规则
C.d:=B.c+1
A.b:=A.a+B.c
而属性 A.a和 B.c在其它地方计算继承属性
在语法树中，一个结点的继承属性由此结点的父结点和 /或兄弟结点的某些属性确定
用继承属性来表示程序设计语言结构中的上下文依赖关系很方便产 生 式 语 义 规 则
D→TL L.in,= T.type
T→int T.type,= integer
T→real T.type,= real
L→L1,id L1.in,=L.in
addtype(id.entry,L.in)
L→id addtype(id.entry,L.in)
句子 real id1,id2,id3的带注释的语法树
id1
L,id2
L,id3
L
real
T
D
.type=real,in=real
.in=real
.in=real
2.6.2 基于属性文法的的处理方法由源程序的语法结构所驱动的处理办法就是语法制导翻译法语义规则的计算可能产生代码,在符号表中存放信息,给出错误信息或执行任何其它动作 。 对输入符号串的翻译也就是根据语义规则进行计算的结果 。
输入串 语法树 依赖图 语义规则计算次序
2.6.2.1 依赖图在一棵语法树中的结点的继承属性和合成属性之间的相互依赖关系可以由称作 依赖图 的一个有向图来描述为每一个包含过程调用的语义规则引入一个虚合成属性 b,这样把每一个语义规则都写成
b:=f(c1,c2,…,ck)
的形式依赖图中为每一个属性设置一个结点,如果属性
b依赖于属性 c,则从属性 c的结点有一条有向边连到属性 b的结点 。
for 语法树中每一结点 n do
for 结点 n的文法符号的每一个属性 a do
为 a在依赖图中建立一个结点；
for语法树中每一个结点 n do
for 结点 n所用产生式对应的每一个语义规则
b:=f(c1,c2,…,ck ) do
for i:=1 to k do
从 ci结点到 b结点构造一条有向边；
E→E1＋ E2 E.val:=E1.val+E2.val
E1 + E2
E val
val val
句子 real id1,id2,id3的带注释的语法树的依赖图
id1
L,id
2
L,id3
L
real
T
D
4
type
5
in
6
7
in
8
9
in
10
1
entry
2
entry
3
entry
如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为 良定义的属性的计算次序一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序属性文法说明的翻译是很精确的
基础文法用于建立输入符号串的语法分析树
根据计算语义规则建立依赖图
从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序输入串 语法树 依赖图 语义规则计算次序句子 real id1,id2,id3的带注释的语法树的依赖图
id1
L,id
2
L,id3
L
real
T
D
4
type
5
in
6
7
in
8
9
in
10
1
entry
2
entry
3
entry
a4:=real;
a5:=a4
addtype (id3.entry,a5);
a7:=a5;
addtype (id2.entry,a7);
a9:=a7
addtype (id1.entry,a9);
2.6.2.2 树遍历的属性计算方法通过树遍历的方法计算属性的值
假设语法树已经建立起了,并且树中已带有开始符号的继承属性和终结符的合成属性
以某种次序遍历语法树,直至计算出所有属性
深度优先,从左到右的遍历
While 还有未被计算的属性 do
VisitNode(S) /*S是开始符号 */
procedure VisitNode (N:Node) ;
begin
if N是一个非终结符 then
/*假设它的产生式为 N→X1…Xm*/
for i,=1 to m do
if not Xi?VT then /*即 Xi是非终结符 */
begin
计算 Xi的所有能够计算的继承属性；
VisitNode (Xi)
end;
计算 N的所有能够计算的合成属性
end
产 生 式 语 义 规 则
S→XYZ Z.h,= S.a
X.c,= Z.g
S.b,= X.d -2
Y.e,= S.b
X→x X.d,=2*X.c
Y→y Y.f,= Y.e*3
Z→z Z.g,=Z.h+1
例 考虑属性的文法 G。其中,S有继承属性 a，
合成属性 b； X有继承属性 c、合成属性 d； Y有继承属性 e、合成属性 f； Z有继承属性 h、合成属性 g
假设 S.a的初始值为 0，输入串为 xyz
S:a=0
X Y Z
x y z
:h=0
g=1
:c=1
d=2
,b=0
:e=0
f=0
2.6.2.3 一遍扫描的处理方法一遍扫描的处理方法是在语法分析的同时计算属性值，与下列两个因素密切相关：
所采用的语法分析方法
属性的计算次序
L－属性文法适合于一遍扫描的自上而下分析
S－属性文法适合于一遍扫描的自下而上分析按一遍扫描编译的模式，所谓 语法制导翻译法,直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则语义规则被计算的时机
在自上而下语法分析中，一个产生式匹配输入串成功时
在自下而上分析中，当一个产生式被用于进行归约时
2.6.2.4 抽象语法树在语法树中去掉那些对翻译不必要的信息，
从而获得更有效的源程序中间表示。这种经变换后的语法树称之为 抽象语法树
(Abstract Syntax Tree)
B S1 S2
if_then_else
S→if B then S 1 else S2?3*5+4
*
5
4
+
3
建立表达式的抽象语法树
mknode (op,left,right) 建立一个运算符号结点,标号是 op,两个域 left和 right分别指向左子树和右子树 。
mkleaf (id,entry) 建立一个标识符结点,
标号为 id,一个域 eutry指向标识符在符号表中的入口 。
mkleaf (num,val) 建立一个数结点,标号为 num,一个域 val用于存放数的值 。
建立抽象语法树的语义规则产 生 式 语 义 规 则
E→E1+T E.nptr,= mknode( ‘+’,E1.nptr,T.nptr )
E→E1-T E.nptr,= mknode( ‘-’,E1.nptr,T.nptr )
E→T E.nptr,= T.nptr
T→ (E) T.nptr,= E.nptr
T→id T.nptr,= mkleaf( id,id.entry )
T→num T.nptr,= mkleaf( num,num.val )
a－ 4＋ c的抽象语法树
E nptr T nptr
E nptr
To entry for a
E
T nptr
id
- T nptr id
id-
id num 4
+
To entry for c
2.6.3 S-属性文法的自下而上计算一般的属性文法的翻译器可能比较难建立，但
S-属性文法的翻译器很容易建立。
S-属性文法：只含有合成属性合成属性可以在分析输入符号串的同时由自下而上的分析器来计算。
分析器可以保存与栈中文法符号有关的合成属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。
在分析栈中使用一个附加的域来存放合成属性值 （加一个值栈）
假设语义规则 A.a:=f(X.x,Y.y,Z.z)是对应于产生式 A→XYZ的
S m Z,z Z
S m - 1 Y,y Y
S m - 2 X,x X
… … …
S 0 — #
TO P
S’ m - 2 A.a A
… … …
S 0 — #
T O P
用 LR分析器实现台式计算器产生式 代 码 段
L→En print(val[top])
E→E1+T val[ntop],= val[top-2]+val[top]
E→T
T→T1*F val[ntop],= val[top-2]*val[top]
T→F
F→ (E) val[ntop],=val[top-1]
F→digit ntop表示新的栈顶输入 state val 用到的产生式
3*5+4n — —
*5+4n 3 3
*5+4n F 3 F→digit
*5+4n T 3 T→F
5+4n T* 3 -
+4n T*5 3 - 5
+4n T*F 3 - 5 F→digit
+4n T 15 T→T*F
输入 state val 用到的产生式
+4n E 15 E→T
4n E+ 15-
n E+4 15- 4
n E+F 15- 4 F→digit
n E+T 15- 4 T→F
n E 19 E→E+T
En 19-
L 19 L→En
2.6.4 L-属性文法和自顶向下翻译通过深度优先的方法对语法树进行遍历，
计算属性文法的所有属性值
LL（ 1）：自上而下分析方法，深度优先建立语法树一个属性文法称为 L-属性文法,如果对于每个产生式 A→X1X2… Xn，其每个语义规则中的每个属性或者是合成属性，或者是 Xj(1?j?n)的一个继承属性且这个继承属性仅依赖于：
(1) 产生式 Xj的左边符号 X1,X2,…,Xj-1的属性；
(2) A的继承属性。
S-属性文法一定是 L-属性文法例：试判断下述文法是否 L-属性文法产 生 式 语 义 规 则
A→LM L.i,= l(A.i)
M.i,=m(l.s)
A→QR R.i,= r(A.i)
Q.i,=q(R.s)
A.s,=f(Q.s)
2.6.4.1 翻译模式属性文法是隐去实现细节的关于语言翻译的高级规范说明 。
翻译模式是另一种适合语法制导翻译的方式
给出了使用语义规则进行计算的次序,这样就可把某些实现细节表示出来
在翻译模式中,和文法符号相关的属性和语义规则 （ 这里我们也称 语义动作 ）,用花括号 { }括起来,插入到产生式右部的合适位置上,从而给出了计算顺序 。
翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式
E→TR
R→addop T {print(addop.lexeme)} R1 |?
T→num {print(num.val)}
-
E
T R
9 {print(‘9’)} T R
5 {print(‘5’)}
{print(‘-’)}
+ T
2 {print(‘2’)}
R{print(‘+’)}
9+5-2的语法树 (备注）
设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。
L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。
建立翻译模式当只需要合成属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾产生式 语义规则
T→T1*F T.val:=T1.val× F.val
建立产生式和语义动作：
T→T1*F {T.val:=T1.val× F.val}
建立翻译模式如果既有合成属性又有继承属性，在建立翻译模式时就必须保证：
1,产生式右边的符号的继承属性必须在这个符号前面的动作中计算出来。
2,一个动作不能引用这个动作右边的符号的合成属性。
3,产生式左边非终结符的合成属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。
翻译模式试判断下列是否正确的翻译模式：
S→A1A2 {A1.in:=1; A2.in:=2}
A→a {print(A.in)}
翻译模式
S→A1A2 {A1.in:=1; A2.in:=2}
A→a {print(A.in)}
不正确因为它不符号第一条规则当对 aa进行自顶向下分析时，当 A与 a匹配时，要打印
A.in,但此时 A.in还未定义。
可改为
S→ {A1.in:=1; ｝ A1｛ A2.in:=2}A2
A→a {print(A.in)}
通常给定一个 L-属性文法，可以建立满足前述三个条件的翻译模式。
翻译模式举例
—— 基于数学格式语言 EQN
给定输入
E sub 1,val
EQN把 E,1和,val分别按不同的大小放在相关位置上。
E 1,val
盒子的语法制导翻译识别输入并进行格式安放的 L-属性文法产 生 式 语 义 规 则
S→B B.ps,=10
S.ht,=B.ht
B→B1B2 B1.ps,=B.ps
B2.ps,=B.ps
B.ht,= max(B1.ht,B2.ht)
B→B1 sub B2 B1.ps,=B.ps
B2.ps,=shrink(B.ps)
B.ht,=disp(B1.ht,B2.ht)
B→text B.ht,=text.h× B.ps
非终结符 B（表示盒子）代表公式。
B→B1B2代表两个并列的盒子
B→B1 sub B2代表 B2比 B1小，放在其下脚标位置。
Ps是继承属性，影响了公式的高度。此文法是一个 L-属性文法。
Shrink将 B2.ps减少 30％。
Disp函数将 B2放在 B1的下标位置，并计算 B的高度。
翻译模式
S → {B.ps:=10}
B {S.ht:=B.ht}
B → {B1.ps:=B.ps}
B1 { B2.ps:=B.ps }
B2 {B.ht:=max(B1.ht,B2.ht)}
B → {B1.ps:=B.ps}
B1
sub {B2.ps:=shrink(B.ps)}
B2 {B.ht:=disp(B1.ht,B2.ht)}
B → text{B.ht:=text.h× B.ps}
2.6.4.2 自顶向下翻译动作是在处于相同位置上的符号被展开
（匹配成功）时执行的。
为了构造不带回溯的自顶向下语法分析，
必须消除文法中的左递归当消除一个翻译模式的基本文法的左递归时同时考虑属性 —— 适合带合成属性的翻译模式关于算术表达式的左递归文法相应的翻译模式
E→E1+T {E.val:=E1.val+T.val}
E→E1-T {E.val:=E1.val-T.val}
E→T {E.val:=T.val}
T→(E) {T.val:=E.val}
T→num {T.val:=num.val}
消除左递归，构造新的翻译模式
E → T {R.i:=T.val}
R {E.val:=R.s}
R → +
T {R1.i:=R.i+T.val}
R1 {R.s:=R1.s}
R → -
T {R1.i:=R.i-T.val}
R1 {R.s:=R1.s}
R →? {R.s:=R.i}
T → (
E
) {T.val:=E.val}
T → num {T.val:=num.val}
计算表达式 9－ 5＋ 2
E
T R
numnum.val=9
.val=9,i=9
- T R
numnum.val=5
.val=5,i=4
+ T R
numnum.val=2
.val=2,i=6
R.s=6
R.s=6
R.s=6
.s=6
一般方法假设有翻译模式：
A→A1Y {A.a:=g(A1.a,Y.y)}
A→X {A.a:=f(X.x)}
它的每个文法符号都有一个合成属性，用小写字母表示,g和 f是任意函数。
消除左递归：
A→XR
R→YR |?
翻译模式变为,
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}
XYY在旧文法的语法树
—— 自下而上的分析
X
A.a=f(X.x) Y1
A.a=g(f(X.x),Y1.y) Y2
A.a=g(g(f(X.x),Y1.y),Y2.y)
XYY在新文法的语法树
—— 自顶向下的语法分析
A
X R.i=f(X.x)
Y1 R.i= g(f(X.x),Y1.y)
Y2 R.i= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
R.s= g(g(f(X.x),Y1.y),Y2.y)
.a= g(g(f(X.x),Y1.y),Y2.y)
两种方法得到相同的结果！
构造抽象语法树的属性文法定义转化成翻译模式属性文法如下：
E→E1+T {E.nptr:=mknode(‘+’,E1.nptr,T.nptr)}
E→E1-T {E.nptr:=mknode(‘-’,E1.nptr,T.nptr)}
E→T {E.nptr:=T.nptr}
问题：翻译模式与属性文法有什么区别？
翻译模式考虑了计算顺序等细节。
构造抽象语法树的属性文法定义转化成翻译模式E → T {R.i:=T.nptr}
R {E.nptr:=R.s}
R → +
T {R1.i:=mknode(‘+’,R.i,T.nptr)}
R1 {R.s:=R1.s}
R → －
T {R1.i:=mknode(‘－ ’,R.i,T.nptr)}
R1 {R.s:=R.s}
R →? {R.s:=R.i}
T → (
E
) {T.nptr:=E.nptr}
T → id {T.nptr:=mkleaf(id,id.entry)}
T → num {T.nptr:=mkleaf(num,num.val)}
使用继承属性构造 a－ 4＋ c的抽象语法树E
T R
id
To entry for a
id
T.nptr
- T
num
num 4
T.nptr R,i
-
R
+ T R
id
To entry for c
id
T.nptr R,i
+
R,i
R,s
R,s
R,s
E.nptr
2.6.4.3 递归下降翻译器的设计如何在递归下降分析中实现翻译模式，
构造 递归下降翻译器设计递归下降翻译器的方法
1,
对每个非终结符 A构造一个函数过程，对 A的每个继承属性设置一个形式参数
函数的返回值为 A的合成属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个合成属性
A对应的函数过程中，为出现在 A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。
设计递归下降翻译器的方法
2,非终结符 A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。
设计递归下降翻译器的方法
3,每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：
i) 对于带有合成属性 x的终结符 X，把 x的值存入为 X.x设置的变量中。然后产生一个匹配 X的调用，并继续读入一个输入符号。
ii) 对于每个非终结符 B，产生一个右边带有函数调用的赋值语句
c=B(b1,b2,…,bk)，其中,b1,b2,…,bk是为 B的继承属性设置的变量,c是为 B的合成属性设置的变量。
iii) 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。
设计递归下降翻译器
E → T {R.i:=T.nptr}
R {E.nptr:=R.s}
R → +
T {R1.i:=mknode(‘+’,R.i,T.nptr)}
R1 {R.s:=R1.s}
R → －
T {R1.i:=mknode(‘－ ’,R.i,T.nptr)}
R1 {R.s:=R.s}
R →? {R.s:=R.i}
T → (
E
) {T.nptr:=E.nptr}
T → id {T.nptr:=mkleaf(id,id.entry)}
T → num {T.nptr:=mkleaf(num,num.val)}
例：下述文法是 LL(1)的，因此可以用于自顶向下的分析。
非终结符 E,R,T的函数及其参数类型
function E:↑AST-node;
function R(in:↑AST-node),↑AST-node;
function T,↑AST-node;
用 oddop代表＋和－
R → oddop
T {R1.i:=mknode(addop,lexme,R.i,T.nptr)}
R1 {R.s:=R1.s}
R→? {R.s:=R.i}
产生式 R→addop TR|?的递归分析过程
procedare R;
begin
if sym=addop then begin
advance;T; R
end
else begin /*do nothing*/
end
end;
function R (in:↑AST-node),↑AST-node;
var nptr,i1,s1,s,↑AST-node;
addoplexeme,char;
begin
if sym=addop then begin
/*产生式 R→addop TR */
addoplexeme:=lexval;
advance;
nptr:=T;
i1:=mknode (addoplexeme,in,nptr);
s1:=R (i1)
s:=s1
end
else s:=in;
return s
end;
2.6.5 自下而上计算继承属性在自下而上的分析过程中实现 L-属性文法的方法可实现任何基于 LL（ 1）文法的 L-属性文法，还可以实现许多（不是所有）基于
LR（ 1）文法的 L-属性文法
2.6.5.1 从翻译模式中去掉嵌入在产生式中间的动作在自下而上的分析方法中，要求把所有的语义动作都放在产生式的末尾转换方法，它可以使所有嵌入的动作都出现在产生式的末尾
在基础文法中加入一些新的产生式，形如：
M→?
把嵌入在产生式中的每个语义动作用不同的标记非终结符 M代替，并把这个动作放在产生式 M→?的末尾转换举例翻译模式
E → TR
R → ＋ T {print (‘＋ ’ )} R | － T {print
(‘－ ’ )}R|?
T → num {print (num.val)}
转换为
E → TR
R → ＋ TMR | － TNR |?
T → num {print (num.val)}
M →? {print (‘＋ ’ )}
N →? {print (‘－ ’ )}
分析栈中的继承属性形如 Y.i＝ X.s的规则称为复制规则在自底向上的语法分析中，复制规则在继承属性的计算过程中起 着重要作用。
例：要实现的类型说明文法翻译模式如下：
D→T {L.in,= T.type }
L
T→int {T.type,= integer}
T→real {T.type,= real }
L→{ L1.in,=L.in}
L1,id{addtype(id.entry,L.in)}
L→id {addtype(id.entry,L.in) }
分析栈中的继承属性分析自底向上语法分析器在输入
real p,q,r上所做的移动。
用合成属性代替继承属性有时可通过改写基础文法来避免使用继承属性。
如,Pascal语言的类型声明文法如下：
D?L:T
T?integer|char
L?L,id | id
由于标识符由 L产生，但类型却不在 L的子树中，
因此仅用合成属性不能把标识符与类型联系在一起。
不是 L-属性用合成属性代替继承属性但可改写文法为：
D?id,L
L?,id L |,T
T?integer | real
将类型变为标识符表的最后一个元素，
化为子结点，类型变成合成属性。
当标识符由 L产生时，其类型可填入符号表中。
