搜索
1第6章属性文法和语法制导翻译7.下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：试设计求S.val的属性文法，其中，已知B的综合属性c,给出由B产生的二进位的结果值。例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。【答案】产生式语义规则S→L1.L2{S.val:=L1.val+L2.val*2－L2.length}S→L{S.val:=L.val}L→L1B{L.val:=L1.val*2+B.val;L.length:=L1.length+1}L→B{L.val:=B.val;L.length:=1}B→0{B.val:=0}B→1{B.val:=1}11.设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。【答案】产生式语义规则L→idL1{S.val:=L1.val+L2.val*2－L2.length}L→,idL1{S.val:=L.val}L→:T{L.val:=L1.val*2+B.val;L.length:=L1.length+1}T→integer{L.val:=B.val;L.length:=1}T→real{B.val:=0}S→L.L∣LL→LB∣BB→0∣1L→idLL→,idL∣:TT→integer∣real2第7章语义分析和中间代码产生1.给出下面表达式的逆波兰表示（后缀式）：【答案】原式后缀式(1)a*(-b+c)ab-c+*(2)a+b*(c+d/e)abcde/+*+(3)–a+b*(-c+d)a-bc-d+*+(4)notAornot(CornotD)AnotCDnotornotor(5)(AandB)or(notCorD)ABandCnotDoror(6)(AorB)and(CornotDandE)ABorCDnotEandorand(7)if(x+y)*z=0then(a+b)↑celsea↑b↑cifxy+z*0=thenab+c↑elseab↑c↑3.请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4.按7.3节所说的办法，写出下面赋值句A:=B*(－C+D)的自下而上语法制导翻译过程。给出所产生的三地址代码。【答案】三元式(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)四元式(1)uminusc／T1(2)+T1DT2(3)*BT2T3(4):=T3／A35.按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码：A[i,j]:=B[i,j]+C[A[k,l]]+d[i+j]【答案】6.按7.4.1和7.4.2节的翻译办法，分别写出布尔式Aor(Bandnot(CorD))的四元式序列。【答案】用作数值计算时产生的四元式：用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。7.用7.5.1节的办法，把下面的语句翻译成四元式序列：WhileACandBDdoifA=1thenC:=C+1elsewhileA≦DdoA:=A+2;【答案】中间代码中间代码(1)T1:=i*NA2(13)T10:=WA*T8(2)T1:=T1+j(14)T11:=T9[T10](3)T2:=A-CA(15)T12:=C-Cc(4)T3:=WA*T1(16)T13:=Wc*T11(5)T4:=i*NB2(17)T14:=T12[T13](6)T4:=T4+j(18)T15:=T7+T14(7)T5:=B-CB(19)T16:=i+j(8)T6:=WB*T4(20)T17:=d-Cd(9)T7:=T5[T6](21)T18:=Wd*T16(10)T8:=k*NA2(22)T19:=T17[T18](11)T8:=T8+l(23)T20:=T15+T19(12)T9:=A-CA(24)T2[T3]:=T20四元式(1)orCDT1(2)notT1／T2(3)andBT2T3(4)orAT3T4四元式四元式(1)(jnz,A,-,0)(5)(jnz,C,-,(4))(2)(j,-,-,(3))(6)(j,-,-,(7))(3)(jnz,B,-,(5))(7)(jnz,D,-,(5))(4)(j,-,-,0)(8)(j,-,-,(1))四元式四元式4(1)(j,A,C,(3))(9)(j,-,-,(1))(2)(j,-,-,0)(10)(j≦,A,D,(12))(3)(j,B,D,(5))(11)(j,-,-,(1))(4)(j,-,-,0)(12)(+,A,2,T2)(5)(j=,A,1,(7))(13)(:=,T2,-,A)(6)(j,-,-,(10))(14)(j,-,-,(10))(7)(+,C,1,T1)(15)(j,-,-,(1))(8)(:=,T1,-,C)5第9章运行时存储空间组织4.下面是一个Pascal程序：当第二次(递归地)进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？【答案】第1次进入F后，运行栈的内容：第2次进入F后，运行栈的内容：第2次进入F后，Display内容为：5.对如下的Pascal程序，画出程序执行到(1)和(2)点时的运行栈。104908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址00171116015n(形参)141(形参个数)139(全局display)12返回地址114104908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址00110programPP(input,output);VARk:integer;FUNCTIONF(n:integer):integer;beginifn=0thenF:=1elseF:=n*F(n-1);end;beginK:=F(10);…end.主程序PF主程序P第1次F第2次FprogramTr(input,output);VARi:integer;d:integer;procedureA(k:real);VARp:char;6【答案】运行到(1)时的运行栈：（静态链）运行到(2)时的运行栈：（静态链）15c140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i201返回地址0015c140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i201返回地址00procedureB;VARc:char;Begin…(1)…end;{B}procedureC;VARt:real;Begin…(2)…end;{C}Begin……B;C;……end;{A}Begin{main}…A(d);…end.TrABTrAC7【答案】运行到(1)时的运行栈：（Display表）运行到(2)时的运行栈：（Display表）6.有如下示意的Pascal源程序，并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和Display的内容。(1)已开始而尚未执行完毕标号为10的语句；(2)已开始而尚未执行完毕标号为11的语句；20c1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址0020t1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址00主程序TrAB主程序TrACprogrammain;VARa,b,c:integer;procedureX(i,j:integer);{X}VARd,e:real;procedureY;{Y}VARf,g:real;Begin……end;{Y}procedureZ(k:integer);{Z}VARh,i,j:real;Begin……end;{Z}8【答案】(1)运行到标号10时，运行栈的内容：(2)运行到标号11时，运行栈的内容：main→X(a,b)→Ymain→X(a,b)→Y→Z26j25i24h231622621020k191(形参个数)1812(全局display)17返回地址16615e14d13612011j10i92(形参个数)82(全局display)7返回地址605c4b3a20(display)1返回地址0024g23f2216216200190(形参个数)1812(全局display)17返回地址16615e14d13612011j10i92(形参个数)82(全局display)7返回地址605c4b3a20(display)1返回地址00Begin……10:Y;……11:Z;……end;{X}Begin{main}……X(a,b);……end.{main}mainX(a,b)YmainX(a,b)Z9第10章优化1.试把以下程序划分为基本块并作出其程序流图。【答案】2.试把以下程序划分为基本块并作出其程序流图。【答案】realCA:=0B:=1L1:A:=A+BifB≧CgotoL2B:=B+1gotoL1L2:writeAhaltrealCA:=0B:=1L1:A:=A+BifB≧CgotoL2B:=B+1gotoL1L2:writeAhaltrealA,BF:=1C:=A*AD:=B*BifCDgotoL1E:=A*AF:=F+1E:=E+FwriteEhaltL1:E:=B*BF:=F+2E:=E+FwriteEifE100gotoL2haltL2:F:=F-1gotoL1realA,BF:=1C:=A*AD:=B*BifCDgotoL1L2:F:=F-1gotoL1E:=A*AF:=F+1E:=E+FwriteEhaltL1:E:=B*BF:=F+2E:=E+FwriteEifE100gotoL2halt103.试对以下基本块B1和B2：分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：(1)假设只有G,L,M在基本块后面还要被引用；(2)假设只有L在基本块后面还要被引用。【答案】B1基本块：(1)G,L,M可用(2)L可用B2基本块：(1)G,L,M可用(2)L可用B1:A:=B*CD:=B/CE:=A+DF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=LB2:B:=3D:=A+CE:=A*CG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L(1)G:=B*C(2)H:=G*G(3)L:=H*G(4)M:=L(1)G:=B*C(2)H:=G*G(3)L:=H*G(1)D:=A+C(2)E:=A*C(3)G:=3*F(4)J:=D+E(5)L:=15+J(6)M:=L(1)D:=A+C(2)E:=A*C(3)J:=D+E(4)L:=15+J