编译原理作业集 第六章 属性文法和语法制导翻译
产生式 E → TR 语义规则 R.itype:=T.type; R.ipf:=T.pf; E.pf:=R.spf; E.type:=R.stype; if(R.itype==int) AND (T.type==int) THEN R1.itype:=int ELSE BEGIN R1.itype:=real; if(R.itype==real) AND (T.type==int) THEN T.pf:='inttoreal'||T.pf ELSE if(R.itype==int)AND(T.type==real) THEN R.ipf:='inttoreal'||R.if END; R1.ipf:='+'||R.ipf||T.pf; R.stype:=R1.stype; R.spf:=R1.spf; R.stype:=R.itype; R.spf:=R.ipf; T.type:=int; T.pf:=int.lexval; R → +TR1 R → ε T → num T → num.num T.type:=real; T.pf:=real.lexval; 注： R.ipf是R的继承属性，是它的前缀表示。R.spf是R的综合属性，是它的前缀表示。
10. 给出一个检查同一个标识符不在标识符表中出现两次的翻译模式。
10. 答案：设计两个函数lookup(name)和enter(name,type)。lookup(name)查找符号表，若查到，则返回name在符号表中的地址；否则返回NULL。enter(name,type)在符号表中建立name的符号表项，并填写上name的类型type。翻译模式如下：
D → T {L.in:=T.type} L L → {L1.in:=L.in}
L1,id {if(lookup(id.name)) then error
else enter(id.name,L.in)} L → id {if(lookup(id.name)) then error
else enter(id.name,L.in)} T → int {T.type:=int} T → real {T.type:=real}
11. 假设说明是由下列文法产生的： D→id L L→,id L|:T T→ingeger |real
（1）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （2）从（1）中的翻译模式构造一个预翻译程序。
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 16 -
编译原理作业集 第六章 属性文法和语法制导翻译
11.答案： (1) 翻译模式如下：
D → id L {addtype(id.entry,L.type)}
L → , id L1 {L.type:=L1.type; addtype(id.entry,L.type)} L → : T {L.type:=T.type} T → integer {T.type:=integer} T → real {T.type:=real}
(2) 预测翻译程序由如下过程组成： PROCEDURE D;
VAR L.type:(integer,real); id.entry:^id-entry; BEGIN
id.entry:=id.lexval; match(id); L.type:=L;
addtype(id.entry,L.type) END;
FUNCTION L:(integer,real);
VAR L.type,L1.type:(integer,real); id.entry:^id-entry; BEGIN
if(lookahead==',') THEN BEGIN match(','); match(id);
id.entry:=id.lexval; L1.type:=L; L.type:=L1.type;
addtype(id.entry,L.type); END
ELSE BEGIN match(':'); L.type:=T; END;
return(L.type); END;
FUNCTION T:(integer,real); VAR T.type:(integer,real); BEGIN
if(lookahead=='integer') THEN BEGIN match(integer); T.type:=id.lexval
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 17 -
编译原理作业集 第六章 属性文法和语法制导翻译
END ELSE
if(lookahead=='real') THEN BEGIN match(real);
T.type:=id.lexval; END;
ELSE ERROR; return (T.type); END;
12. 已知关于盒子大小和高度的属性文法如下： 产生式 S?B 语义规则 B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) B ? B1 B2 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
下面的文法是上表中上下文无关文法的无二义性形式，其中的花括号｛ ｝只用于把盒子分组，并将在翻译过程中被消除。 S→L L→LB|B B→B sub F|F F→{L}|text
（1）用上面的文法修改上表中的语法制导定义。 （2）把（1）中的语法制导定义转化成翻译模式。 （3）消除翻译模式中的左递归。
12. (1) 对于F1 sub F2 sub F3,其最左推导和分析树如下： S => L => B
=> B sub F3
=> B sub F2 sub F3 => F1 sub F2 Sub F3
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 18 -
编译原理作业集 第六章 属性文法和语法制导翻译
显然，F3.ps:=shrink(F2.ps); F2.ps:=shrink(F1.ps);
为此，为B设一个综合属性B.pt，其值等于其下标F的继承属性F.ps。语法制导定义如下：
产生式 S → L L → B L → L1B 语义规则 L.ps:=10; S.ht:=L.ht; B.ps:=L.ps; L.ht:=B.ht; L1.ps:=L.ps; B.ps:=L.ps; L.ht:=max(L1.ht,B.ht); B1.ps:=B.ps; F.ps:=shrink(B1.pt); B → B1 sub F B.ht:=disp(B1.ht,F.ht); B.pt:=F.ps; B → F F → {L} F → text F.ps:=B.ps; B.ht:=F.ht; B.pt:=B.ps; L.ps:=F.ps; F.ht:=L.ht; F.ht:=text.h*F.ps (2) 翻译模式如下：
S → {L.ps:=10} L {S.ht:=L.ht} L → {B.ps:=L.ps} B {L.ht:=B.ht}
L → {L1.ps:=L.ps} L1 {B.ps:=L.ps} B {L.ht:=max(L1.ht,B.ht)}
B → {B1.ps:=B.ps} B1 sub {F.ps:=shrink(B1.pt)} F {B.ht:=disp(B1.ht,F.ht); B.pt:=F.ps}
B → {F.ps:=B.ps} F {B.ht:=F.ht; B.pt:=B.ps} F → {L.ps:=F.ps} {L}{F.ht:=L.ht} F → text {F.ht:=text.h*F.ps}
（3）S → {L.ps:=10; L.iht:=0} L {S.ht:=L.ht}
L → {B.ps:=L.ps} B {L.ht:=max(L.iht,B.ht)}
L → {B.ps:=L.ps} B {L1.iht:=max(L.iht,B.ht); L1.ps:=L.ps} L1 {L.ht:=L1.ht} B → {F.ps:=B.ps} F sub {B1.ps:=shrink(B.ps)} B1 {B.ht:=disp(F.ht,B1.ht)} B → {F.ps:=B.ps} F {B.ht:=F.ht} F → {L.ps:=F.ps} {L} {F.ht:=L.ht} F → text {F.ht:=text.h*F.ps}
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 19 -
编译原理作业集 第六章 属性文法和语法制导翻译
13. 自定向下翻译模式中，有下面翻译模式： A→A1Y {A.a:=g(A1.a,Y.y)} A→X {A.a:=f(X.x)} 该翻译模式消除左递归后变为： 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 }
下面要求扩充上面消除左递归的转换，使上面的翻译模式中的非终结符号A允许：（1）由复写规则决定的继承属性。 （2）继承属性。
13. 答案：
(a) 假设基础文法含左递归的翻译模式如下：
A → {A1.i:=A.i} A1 {Y.i:=A.i} Y {A.a:=g(A1.a,Y.y)} A → {X.i:=A.i} X {A.a:=f(X.x)}
消除基础文法左递归后的翻译模式如下：
A → {X.i:=A.i} X {R.i:=f(X.x); R.yi:=A.i} R {A.a:=R.s}
R → {Y.i:=R.yi} Y {R1.i:=g(R.i,Y.y); R1.yi:=R.yi} R1 {R.s:=R1.s} R → ε {R.s:=R.i}
属性R.yi用于传递A.i给Y。
(b) 设基础文法含左递归的翻译模式如下：
A－> {A1.i:=h1(A.i)} A1 {y.i:=h2(A.i)} Y {A.a:=g(A1.a,Y.y)} A → {X.i:=h3(A.i)} X {A.a:=f(X.x)}
考虑XY1Y2Y1，其继承属性的计算如下：
消除基础文法中的左递归后，基础文法为： A → XR R → YR | ε
继承属性的计算如下图所示：
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 20 -