《北方工业大学编译原理第7章习题》由会员分享,可在线阅读,更多相关《北方工业大学编译原理第7章习题(17页珍藏版)》请在金锄头文库上搜索。
1、第七章第七章 语义分析和中间代码产生语义分析和中间代码产生 作业:作业: 7.1,7.3,7.4,7.5,7.6,7.7,7.8,7.9 第七章第七章 语义分析和中间代码产生语义分析和中间代码产生 7.1 给出下面表达式的逆波兰表示(后缀式):给出下面表达式的逆波兰表示(后缀式): 解解: a*(-b+c)notA or not (C or not D) a+b*(c+d/e)(Aand B) or (not C or D) -a+b*(-c+d)(A or B) and (C or not D and E) if (x+y)*zthen (a+b) c else abc 表达式表达式后缀式后
2、缀式 a*(-b+c)ab-c+* a+b*(c+d/e)abcde/+*+ -a+b*(-c+d)a-bc-d+*+ notA or not (C or not D)A not C D not or not or (Aand B) or (not C or D)A B and C not D or or (A or B) and (C or not D and E)A B or C D not E and or and if (x+y)*zthen (a+b) c else abc 后缀式为后缀式为xy+z* p1 Jez ab+c p2 Jump p1:abc p2: 7.3 请将表达式请
3、将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三分别表示成三元式、间接三 元式和四元式序列。元式和四元式序列。 三元式:三元式: (1)+ab (2)-(1)- (3)+cd (4)*(2)(3) (5)+ab (6)+(5)c (7)-(4)(6) 四元式:四元式:(1) +abT1 (2)-T1-T2 (3)+cdT3 (4)*T2T3T4 (5)+abT5 (6)+T5cT6 (7)-T4T6T7 间接三元式:间接三元式: (1)+ab (2)-(1)- (3)+cd (4)*(2)(3) (5)+(1)c (6)-(4)(5) 7.4 写出下面赋值句写出下面赋值
4、句 A:=B*(-C+D) 的自下而上语法制导翻译过程。的自下而上语法制导翻译过程。 给出所产生的三地址代码。给出所产生的三地址代码。 输入输入栈栈PLACE四元式四元式 A:=B*(-C+D) :=B*(-C+D) iA B*(-C+D) i:=A_ *(-C+D) i:= iA_B *(-C+D) i:=EA_B (-C+D) i:=E*A_B_ -C+D) i:=E*(A_B_ _ C+D) i:=E*(-A_B_ _ _ +D) i:=E*(-iA_B_ _ _C +D) i:=E*(-EA_B_ _ _C +D) i:=E*(EA_B_ _T1(-,C,-, T1) D) i:=E*
5、(E+A_B_ _T1_ ) i:=E*(E+iA_B_ _ T1_D ) i:=E*(E+EA_B_ _T1_D ) i:=E*(EA_B_ _T2(+,T1,D, T2) i:=E*(E)A_B_ _T2_ i:=E*EA_B_ T2 i:=EA_T3(*,B, T2, T3) S(:=,T3,_,A) 7.5 写出下面赋值句的中间代码写出下面赋值句的中间代码 AI,J:=BAI+1,J+1+BI+J 设设A,B数组每维下界为数组每维下界为1,每维的上界:,每维的上界:high1、high2,每维的,每维的 长度:长度:n1=high1-low1+1,n2=high2-low2+1,数组每
6、个元素宽度为,数组每个元素宽度为 w,则设则设A数组数组C1= (1*n2)+1)*w , B 数组数组C2= 1 w = w T10:=B- C2 T11:=W*T9 T12:=T10T11/*BAI+1,J+1 T12*/ T13:=I+J T14:=W*T13 T15:=T10T14 T16:=T12+T15 T2T3=T16 T1:=I*n2 T1:=T1+J T2:=A-C1 T3:=W*T1 /* T2T3即为即为AI,J */ T4:=I+1 T5:=T4*n2 T6:=J+1 T6:=T5+T6 T7:=A-C1 T8:=W*T6 T9:=T7T8 /*AI+1,J+1 T9*
7、/ 7.6 按照作为条件控制的布尔式翻译写出布尔式按照作为条件控制的布尔式翻译写出布尔式 A or (B and not (C or D)的四元式序列。的四元式序列。 (3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist 解:四元式序列为:解:四元式序列为: 100(jnz,A,_,0) /*为真为真*/ 101 (j,_,_,102) 102 (jnz,B,_,104) 103 (j,_,_,0)
8、/*为假为假*/ 104 (jnz,C,_,103) /*为假为假*/ 105 (j,_,_,106) 106 (jnz,D,_,104) /*假链链首假链链首*/ 107 (j, _,_,100) /*真链链首真链链首*/ 其中:真链为其中:真链为107,100,链首,链首 E.truelist=107,假链为,假链为 106,104,103,链首,链首 E.falselist=106 7.6 按照作为条件控制的布尔式翻译写出布尔式按照作为条件控制的布尔式翻译写出布尔式 A or (B and not (C or D)的四元式序列。的四元式序列。 (5) Eid1relop id2 E.tr
9、uelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop , id 1.place , id2.place, 0); emit(j, -, -, 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id.place , -,0); emit( j, -, -, 0) 解:四元式序列为:解:四元式序列为: 100(jnz,A,_,0) /*为真为真*/ 101 (j,_,_,10
10、2) 102 (jnz,B,_,104) 103 (j,_,_,0) /*为假为假*/ 104 (jnz,C,_,103) /*为假为假*/ 105 (j,_,_,106) 106 (jnz,D,_,104) /*假链链首假链链首*/ 107 (j, _,_,100) /*真链链首真链链首*/ 其中:真链为其中:真链为107,100,链首,链首 E.truelist=107,假链为,假链为 106,104,103,链首,链首 E.falselist=106 7.6 按照作为条件控制的布尔式翻译写出布尔式按照作为条件控制的布尔式翻译写出布尔式 A or (B and not (C or D)的四
11、元式序列。的四元式序列。 解:四元式序列为:解:四元式序列为: 100(jnz,A,_,0) /*为真为真*/ 101 (j,_,_,102) 102 (jnz,B,_,104) 103 (j,_,_,0) /*为假为假*/ 104 (jnz,C,_,103) /*为假为假*/ 105 (j,_,_,106) 106 (jnz,D,_,104) /*假链链首假链链首*/ 107 (j, _,_,100) /*真链链首真链链首*/ 其中:真链为其中:真链为107,100,链首,链首 E.truelist=107,假链为,假链为 106,104,103,链首,链首 E.falselist=106
12、(1) EE1or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist (2) EE1and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) E1.code To E.true To E1.false E2.code To E.true To E.false E1.
13、code To E. false To E1. true E2.code To E.true To E.false 7.7 把下面的语句翻译成四元式序列:把下面的语句翻译成四元式序列: while A C and B D do if A = 1 then C:=C + 1 else while A = D do A:= A + 2; 7.7 把下面的语句翻译成四元式序列:把下面的语句翻译成四元式序列: while A C and B D do if A = 1 then C:=C + 1 else while A = D do A:= A + 2; 7.7 把下面的语句翻译成四元式序列:把下面
14、的语句翻译成四元式序列: while A C and B D do if A = 1 then C:=C + 1 else while A D then if A D */ 101 ( j , _ , _ , 112 ) 102( jnz , B , _ , 104) 103( j , _ , _ , 112 ) 104 ( j , C , D , 106 ) 105 ( j , _ , _ , 112 ) 106 ( j , A , B , 108 ) /* A B */ 107 ( j , _ , _ , 110 ) 108( := , 1 , _ , F ) /* F:=1 */ 109
15、( j , _ , _ ,0) 110( := , 0 , _ , F )/* F:=0 */ 111 ( j , _ , _ , 109) 112(+ , G , 1 , T1) 113 ( := , T1, _ , G ) 7.9 对下面的文法,只利用综合属性获得类型信息。对下面的文法,只利用综合属性获得类型信息。 请给出该文法各个产生式的语义子程序。请给出该文法各个产生式的语义子程序。 D L,id | L L T id T int | real 解:解:DL,id D.type:=L.type addtype(id.type,L.type) DL D.type:=L.type LT id L.type:=T.type addtype(id.type,T.type) Tint T.type:=integer Treal T.type:=real