1、#编译原理答案第五章练习5.1解答：输入(4*7+1*2n,带注释的分析树如下：练习5.2解答: (1根据表5.3中的语法制导定义建立表达式(a+(b的分析树和语法树 (2根据图5.17的翻译模式构造(a+(b的分析树和语法树练习5.3解答:设置下面的函数和属性：expr1|expr2:把表达式expr2拼写在表达式expr1后面。deletep(expr:去掉表达式expr左端的。E.expr,T.expr,F.expr:属性变量，分别表示E，T，F的表达式。E.add,T.add,F.add,属性变量，若为true，则表示其表达式中外层有号，否则无号。E.pmark,T.pmark,F.p
2、mark,属性变量，若为true，表示E,T,F的表达式中左端为 E1 +Tif(T.pmark=true THEN E.expr=E1.expr|+|deletep(T.expr ELSE E.expr:=E1.expr|+|T.expr。E.add:=true。E.pmark:=false。E - Tif(T.pmark=true THEN E.expr:=deletep(T.expr ELSE E.expr:=T.expr。E.add:=T.add。E.pmark:=false。T - T1*FT.expr:=T1.expr|*|F.expr。 T.add:=false。T.pmark:
3、=false。T - FT.expr:=F.expr。 T.add:=F.add。T.pmark:=F.pmark。F - (Eif(E.add=false THEN BEGIN F.expr:=E.expr。 F.add:=false。 F.pmark:=false。 END ELSE BEGIN F.expr:=(|E.expr|。 F.add:=true。 F.pmark:=true。 END。F - idF.expr:=id.lexval。 F.add:=false。F.pmark:=false。练习5.4解答: (1语法制导定义如下：产生式语义规则E - E1+Tif(E1.type
4、=int AND (T.type=int THEN E.type:=int ELSE E.type:=real。 E - TE.type:=T.type。 T - numT.type:=int。 T - num.numT.type:=real。 (2设E.pf和T.pf分别是E和T的前缀形式，|是两个字符串的连接，语法制导定义如下：产生式语义规则E - E1+Tif(E1.type=int AND (T.type=int THEN E.type:=int ELSE BEGIN E.type:=real。 if(E1.type=int AND (T.type=real THEN E1.pf:=i
5、nttoreal|E1.pf ELSE if(E1.type=realAND(T.type=int THEN T.pf:=inttoreal|T.pf END。E.pf:=+|E1.pf|T.pf。 E - TE.type:=T.type。 E.pf:=T.pf。 T - numT.type:=int。 T.pf:=int.lexval。 T - num.numT.type:=real。 T.pf:=real.lexval。练习5.5解答: (1用综合属性决定s.val的语法制导定义：产生式语义规则 S - LS.val:=L.val。 S - L1.L2S.val:=L1.val+L2.va
6、l*L2.p。 L - BL.val:=B.val。 L.p:=2-1。 L - L1BL.val:=L1.val*2+B.val。 L.p:=L.p*2-1。 B - 0B.val:=0。 B - 1B.val:=1。 注：L.p表示恢复L.val的因子。 (2分析：设B.c是B的综合属性，是B产生的位对最终值的贡献。要求出B.c，必须求出B产生位的 权，设B.i。B.i的求法请参看下面的图示： 另外，设L.fi为继承因子，L.fs为综合因子，语法制导定义如下：产生式语义规则 S - LL.i:=1。 L.fi:=2。 L.fs:=1。 S.val:=L.val。 S - L1.L2L1.i
7、=1。 L1.fi=2。 L1.fs:=1。 L2.i=2-1。 L2.fi=1。 L2.fs:=2-1。S.val:=L1.val+L2.val。 L - BL.s:=L.i。 B.i:=L.s。 L.val:=B.c。 L - L1BL1.i:=L.i*L1.fi。 L.s:=L1.s*L1.fs。B.i:=L.s。L.val:=L1.val+B.c。 B - 0B.c:=0。 B - 1B.c:=B.i。 若把文法改写成如下形式，则语法制导定义会更清楚： S - L.R | L L - LB | B R - RB | B B - 0 | 1产生式语义规则 S - LL.i:=1。 S.v
8、al:=L.val。 S - L.RL.i=1。 R.i=2-1。 S.val:=L.val+R.val。 L - L1BB.i:=L.i。 L1.i:=L.i*2。 L.val:=L1.val+B.c。 L - BB.i:=L.i。 L.val:=B.c。 R - R1BR1.i:=R.i。 R.s:=R1.s*2-1。 B.i:=R.s。 R - BR.s:=R.i。 B.i:=R.s。 R.val:=B.c。 B - 0B.c:=0。 B - 1B.c:=B.i。练习5.6解答: 产生式语义规则 D - D1,idD.type:=D1.type。 addtype(id.entry,D1.
9、type。 D - T idD.type:=T.type。 addtype(id.entry,T.type。 T - intT.type:=int。 T - realT.type:=real。练习5.7解答: (1产生式语义规则 E - TRR.i:=T.type。 E.type:=R.s。 R - +TR1if(R.i=int AND (T.type=int THEN R1.i:=int ELSE R1.i:=real。R.s:=R1.s。 R - R.s:=R.i。 T - num.numT.type:=real。 T - numT.type:=int。 (2产生式语义规则 E - TRR
10、.itype:=T.type。 R.ipf:=T.pf。 E.pf:=R.spf。 E.type:=R.stype。 R - +TR1if(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=intAND(T.type=real THEN R.ipf:=inttoreal|R.ipf END。R1.ipf:=+|R.ipf|T.pf。R.stype:=R
11、1.stype。 R.spf:=R1.spf。 R - R.stype:=R.itype。 R.spf:=R.ipf。 T - numT.type:=int。 T.pf:=int.lexval。 T - num.numT.type:=real。 T.pf:=real.lexval。 注： R.ipf是R的继承属性，是它的前缀表示。 R.spf是R的综合属性，是它的前缀表示。练习5.8解答:设计两个函数lookup(name和enter(name,type,lookup(name查找符号表，若查到，则返回name在符号表中的地址；否则返回NULL。enter(name,type在符号表中建立na
12、me的符号表项，并填写上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练习5.9解答:(1 翻译模式如下： D - id L addtype(id.entry,L.type L - , id L1 L.type:
13、=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.t
14、ype:(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=integ
15、er THEN BEGIN match(integer。 T.type:=id.lexval END ELSE if(lookahead=real THEN BEGIN match(real。 T.type:=id.lexval。 END ELSE ERROR。 return (T.type。 END。 练习5.10解答: (1 对于F1 sub F2 sub F3,其最左推导和分析树如下： S = L = B = B sub F3 = B sub F2 sub F3 = F1 sub F2 Sub F3 显然，F3.ps:=shrink(F2.ps。 F2.ps:=shrink(F1.ps。
16、 为此，为B设一个综合属性B.pt，其值等于其下标F的继承属性F.ps。语法制导定义如下： 产生式语义规则 S - LL.ps:=10。 S.ht:=L.ht。 L - BB.ps:=L.ps。 L.ht:=B.ht。 L - L1BL1.ps:=L.ps。 B.ps:=L.ps。 L.ht:=max(L1.ht,B.ht。 B - B1 sub FB1.ps:=B.ps。 F.ps:=shrink(B1.pt。 B.ht:=disp(B1.ht,F.ht。B.pt:=F.ps。 B - FF.ps:=B.ps。 B.ht:=F.ht。 B.pt:=B.ps。 F - LL.ps:=F.ps。
17、 F.ht:=L.ht。 F - textF.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 LF.ht:=L.ht
18、 F - text F.ht:=text.h*F.ps 练习5.11解答:(1 假设基础文法含左递归的翻译模式如下： 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。(2 设基础文法含左递归的翻译模式
19、如下： 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 考虑XY1Y2Y3，其继承属性的计算如下： 消除基础文法中的左递归后，基础文法为： A - XR R - YR | 继承属性的计算如下图所示：当识别出X后，并不能计算出X的继承属性，因而，也就无法计算有关X的其他属性。只好把X的源表示或中间表示作为继承传给R，继续沿R传下去，然后再作为综合属性传回来。直到能计算出X.i,再对X的成分进行翻译。Y1,Y2,Y3的翻译思想和X类似，具体的翻译模式省略。练习5.12解答: S - L.ps:
20、=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.13解答: (1栈输入动作 $
21、abbb$ 初始 $Mabbb$ 规约 M - $MMabbb$ 规约 M - $MMMabbb$ 规约 M - $MMMabbb$ 移进 $MMMLbbb$ 规约 L - a $MMMLbbb$ 移进 $MMLbb$ 规约 L - MLb $MMLbb$ 移进 $MLb$ 规约 L - MLb $MLb$ 移进 $L$ 规约 L - MLb接受(2 构造文法的LR(1项目的识别文法活前缀的DFA: 在项目集I0,I2,I2中，存在移进-规约冲突，因此，它不是LR(1的。练习5.14解答:(1 把表5.10的语法制导定义改写成下面的翻译模式： S - L B.ps:=L.s B S.ht:=B
22、.ht L - L.s:=10 B - B1.ps:=B.ps B1 M.i:=B.ps M B2.ps:=M.s B2 B.ht:=max(B1.ht,B2.ht M - M.s:=M.i B - B1.ps:=B.ps B1 sub N.i:=B.ps N B2.ps:=N.s B2 B.ht:=disp(B1.ht,B2.ht B - text B.ht:=text.h*B.ps N - N.s:=shrink(N.i(b 设一个栈ps，管理继承属性B.ps的值。栈的三个操作为 push(ps,值,pop(ps,top(ps. 翻译模式如下： S - L B.ps:=top(ps B S
23、.ht:=B.ht L - push(ps,10 B - B1.ps:=top(ps B1 B2.ps:=top(ps B2 B.ht:=max(B1.ht,B2.ht B - B1.ps:=top(ps B1 sub N (B2.ps:=top(ps B2 B.ht:=disp(B1.ht,B2.ht。 pop(ps B - text B.ht:=text.h*B.ps N - push(ps,shrink(top(ps练习5.15解答:A B C D 练习5.16解答:(1 FALSE (2 TRUE (3 TRUE (4 FALSE (5 TRUE (6 FALSE练习5.17解答: a
24、type: ARRAY(0.9, ARRAY(-10.10, integer。 cell: RECORD(a integer (binteger。 pcell: POINTER(cell。 或 : POINTER(RECORD(a integer (b integer。 foo: ARRAY(1.100, cell。 或 : ARRAY(1.100, RECORD(a integer (b integer。 bar: integer cellpcell。 或 : integer cellPOINTER(RECORD(ainteger (binteger。练习5.18解答:D - id:T ad
25、dtype(id.entry,T.typeT - char T.type:=charT - integer T.type:=integerT - list of T1 T.type:=list(T1.typeE - num E.type:=integerE - id E.type:=lookup(id.entryE - Literal E.type:=charE - (L E.type:=list(L.typeL - E,L1 L.type:=IF (E.type=L1.type THEN E.type ELSE type_errorL - E L.type:=E.type练习5.19解答:(
26、1S - id:=E S.type:= IF id.type=E.type THEN E.type ELSE type_error。 S.val:= IF id.type=E.type THEN E.val ELSE val_errorS - IF E THEN S1 S.type:= IF E.type=boolean THEN S1.type ELSE type_error。 S.val:= IF E.type=boolean THEN S1.val ELSE val_errorS - WHILE E DO S1 S.type:= IF E.type=boolean THEN S1.typ
27、e ELSE type_error。 S.val:= IF E.type=boolean THEN S1.val ELSE val_errorS - S1。S2 S.type:=S2.type。 S.val:=S2.val(2E - E1 AND E2 E.type:= IF(E1.type=booleanAND(E2.type=boolean THEN boolean ELSE type_errorE - E1 OR E2 E.type:= IF(E1.type=booleanAND(E2.type=boolean THEN boolean ELSE type_errorE - NOT E1 E.type:= IF(E1.type=boolean THEN boolean ELSE type_errorE - E1 op E2 E.type:= IF(E1.type=E2.type TH
