《编译原理》(陈火旺版)课后作业参考答案ch6-10

《编译原理》(陈火旺版)课后作业参考答案ch6-10《编译原理》(陈火旺版)课后作业参考答案ch6-10《编译原理》(陈火旺版)课后作业参考答案ch6-10《编译原理》(陈火旺版)课后作业参考答案ch6-10编制仅供参考审核批准生效日期地址：电话：传真:邮编:第6章属性文法和语法制导翻译7.下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：S→S→∣LL→LB∣BB→0∣1试设计求的属性文法，其中，已知B的综合属性c,给出由B产生的二进位的结果值。例如，输入时，=，其中第一个二进位的值是4，最后一个二进位的值是。【答案】产生式语义规则S→L1.L2{:=+*2－}S→L{:=}L→L1B{:=*2+;L.length:=+1}L→B{:=;L.length:=1}B→0{:=0}B→1{:=1}11.设下列文法生成变量的类型说明：L→L→idLL→,idL∣:TT→integer∣real构造一下翻译模式，把每个标识符的类型存入符号表；参考例。【答案】产生式语义规则L→idL1{:=+*2－}L→,idL1{:=}L→:T{:=*2+;L.length:=+1}T→integer{:=;L.length:=1}T→real{:=0}第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)+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)→(2)→(3)→(4)→(1)→(5)→(6)4.按节所说的办法，写出下面赋值句A:=B*(－C+D)的自下而上语法制导翻译过程。给出所产生的三地址代码。四元式(1)uminusc／T1(2)+T1DT2(3)*BT2T3(4):=T3／A【答案】5.按照节所给的翻译模式，把下列赋值句翻译为三地址代码：A[i,j]:=B[i,j]+C[A[k,l]]+d[i+j]【答案】中间代码中间代码(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]:=T206.按和节的翻译办法，分别写出布尔式Aor(Bandnot(CorD))的四元式序列。【答案】用作数值计算时产生的四元式：用作条件控制时产生的四元式：四元式(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))其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。7.用节的办法，把下面的语句翻译成四元式序列：WhileA<CandB<DdoifA=1thenC:=C+1elsewhileA≦DdoA:=A+2;【答案】四元式四元式(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)第9章运行时存储空间组织4.下面是一个Pascal程序：programPP(input,programPP(input,output);VARk:integer;FUNCTIONF(n:integer):integer;beginifn<=0thenF:=1elseF:=n*F(n-1);end;beginK:=F(10);…end.当第二次(递归地)进入F后，DISPLAY的内容是什么当时整个运行栈的内容是什么【答案】第1次进入F后，运行栈的内容：第2次进入F后，运行栈的内容：10主程序PF主程序PF908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址0017主程序P第1次F主程序P第1次F第2次F16015n(形参)141(形参个数)139(全局display)12返回地址114104908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址00第2次进入F后，Display内容为：1105.对如下的Pascal程序，画出程序执行到(1)和(2)点时的运行栈。programprogramTr(input,output);VARi:integer;d:integer;procedureA(k:real);VARp:char;procedureprocedureB;VARc:char;Begin…(1)…end;{B}procedureC;VARt:real;Begin…(2)…end;{C}Begin……B;C;……end;{A}Begin{main}…A(d);…end.【答案】运行到(1)时的运行栈：（静态链）运行到(2)时的运行栈：（静态链）15c140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i201返回地址0015TrATrAC140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i201返回地址00TrABTrAB【答案】运行到(1)时的运行栈：（Display表）运行到(2)时的运行栈：（Display表）20主程序TrA主程序TrAB1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址0020主程序TrA主程序TrAC1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址006.有如下示意的Pascal源程序，并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和Display的内容。(1)已开始而尚未执行完毕标号为10的语句；(2)已开始而尚未执行完毕标号为11的语句；programmain;programmain;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}BeginBegin……10:Y;……11:Z;……end;{X}Begin{main}……X(a,b);……end.{main}mainX(a,b)mainX(a,b)Z(1)运行到标号10时，运行栈的内容：(2)运行到标号11时，运行栈的内容：26j25i24h231622621020k191(形参个数)1812(全局display)17返回地址16615e14d13612011j10i92(形参个数)82(全局display)7返回地址605c4b3a20(display)1返回地址0024mainX(a,b)mainX(a,b)Y23f2216216200190(形参个数)1812(全局display)17返回地址16615e14d13612011j10i92(形参个数)82(全局display)7返回地址605c4b3a20(display)1返回地址00main→X(a,b)→Ymain→X(a,b)→Y→Z第10章优化1.试把以下程序划分为基本块并作出其程序流图。realCA:=0realCA:=0B:=1L1:A:=A+BifB≧CgotoL2B:=B+1gotoL1L2:writeAhaltrealCA:=0B:=1L1:A:=A+BifB≧CgotoL2B:=B+1gotoL1L2:writeAhalt2.试把以下程序划分为基本块并作出其程序流图。realrealA,BF:=1C:=A*AD:=B*BifC<DgotoL1E:=A*AF:=F+1E:=E+FwriteEhaltL1:E:=B*BF:=F+2E:=E+FwriteEifE>100gotoL2haltL2:F:=F-1gotoL1realA,BF:=1C:=A*AD:=B*BifC<DgotoL1L2:F:=F-1gotoL1E:=A*AF:=F+1E:=E+FwriteEhaltL1:E:=B*BF:=F+2E:=E+Fwrite