编译原理教程课后习题-第四章

第四章语义剖析和中间代码生成达成以下选择题：(1)四元式之间的联系是经过实现的。a.指示器b.暂时变量c.符号表d.程序变量(2)间接三元式表示法的长处为。采纳间接码表，便于优化办理节俭储存空间，不便于表的改正便于优化办理，节俭储存空间节俭储存空间，不便于优化办理(3)表达式(┐A∨B)∧(C∨D)的逆波兰表示为。a.┐AB∨∧CD∨b.A┐B∨CD∨∧c.AB∨┐CD∨∧d.A┐B∨∧CD∨有一语法制导翻译以下所示：S→bAb{print″1″}A→(B{print″2″}A→a{print″3″}B→Aa){print″4″}若输入序列为b(((aa)a)a)b，且采纳自下而上的剖析方法，则输出序列为。b.d.【解答】(1)b(2)a(3)b(4)b何谓“语法制导翻译”试给出用语法制导翻译生成中间代码的重点，并用一简例予以说明。【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，而且在语法剖析的同时履行这些子程序。也即在语法剖析过程中，当一个产生式获取般配(关于自上而下剖析)或用于归约(关于自下而上剖析)时，此产生式相应的语义子程序进入工作，达成既定的翻译任务。用语法制导翻译(SDTS)生成中间代码的重点以下：按语法成分的实质办理次序生成，即按语义要求生成中间代码。注意地点返填问题。不要遗漏必需的办理，如无条件跳转等。比以下边的程序段：if(i>0)a=i+e-b*d;elsea=0;在生成中间代码时，条件“i>0”为假的转移地点没法确立，而要等到办理“else”时方可确立，这时就存在一个地点返填问题。别的，按语义要求，当办理完(i>0)后的语句(即“i>0”为真时履行的语句)时，则应转出目前的if语句，也即此时应加入一条无条件跳转指令，而且这个转移地点也需要待办理完else以后的语句后方可获取，就是说相同存在着地点返填问题。关于赋值语句a=i+e-b*d，其办理次序(也即生成中间代码次序)是先生成i+e的代码，重生成b*d的中间代码，最后才产生“-”运算的中间代码，这类次序不可以颠倒。令为文法G[S]生成的二进制数的值，比如对输入串，则=。依据语法制导翻译方法的思想，给出计算的相应的语义规则，G(S)以下：G[S]:S→|LL

→LB|BB

→0|1【解答】计算的文法G′[S]及语义动作以下：产生式语义动作G′[S]：S′→S{print}S→L1·L2{:=+2L}S→L

{:=}L

→L1B:=+1}

{:=*2+L→B{:=:=2}B→1{:=1}B→0{:=0}下边的文法生成变量的种类说明：D→idLL→,idL|:TT→integer|real试结构一个翻译方案，仅使用综合属性，把每个表记符的种类填入符号表中(对所用到的过程，仅说明功能即可，不用详细写出)。【解答】本题只要要对说明语句进行语义剖析而不需要产生代码，但要求把每个表记符的种类填入符号表中。对D、L、T，为其设置综合属性type，而过程enter(name,type)用来把名字name填入到符号表中，而且给出此名字的种类type。翻译方案以下：D→idL{enter,;}L→,idL(1){enter,L(1).type);=L(1).type;}L→:T{=;}T→integer{=integer;}T→real{=real;}写出翻译过程调用语句的语义子程序。在所生成的四元式序列中，要求在转子指令以前的参数四元式par按反序出现(与实现参数的次序相反)。此时，在翻译过程调用语句时，能否需要语义变量(行列)queue【解答】为使过程调用语句的语义子程序产生的参数四元式par按反序方式出现，过程调用语句的文法为S→calli(arglist)arglist→Earglist→arglist(1),E依据该文法，语法制导翻译程序不需要语义变量行列queue，但需要一个语义变量栈STACK，用来实现按反序记录每个实在参数的地点。翻译过程调用语句的产生式及语义子程序以下：(1)arglist→E{成立一个栈，它仅包括一项}(2)arglist→arglist(1)，E{将压入arglist(1).STACK栈，arglist.STACK=arglist(1).STACK}(3)S→calli(arglist){while≠nulldobegin将栈顶项弹出并送入p单元之中；emit(par,_,_,p);end;emit(call,_,_,entry(i));}设某语言的while语句的语法形式为S→whileEdoS(1)其语义解说如图4-1所示。写出合适语法制导翻译的产生式；写出每个产生式对应的语义动作。E的代码真S(1)的代码

假图4-1习题的语句结构图【解答】本题的语义解说图已经给出了翻译后的中间代码结构。在语法制导翻译过程中，当扫描到while时，应记着E的代码地点；当扫描到do时，应付E的“真出口”进行回填，使之转到S(1)代码的进口处；当扫描到S(1)时，除了应将E的进口地点传给S(1).chain以外，还要形成一个转向E进口处的无条件转移的四元式，而且将持续传下去。所以，应把S→whileEdoS(1)改写为以下的三个产生式：W→whileA→WEdoS→AS(1)每个产生式对应的语义子程序以下：W→while{=nxq;}A→WEdo{Backpatch,nxq);=;=;}S→AS(1){Backpatch(S(1).chain,;emit(j,_,_,;=;}改写布尔表达式的语义子程序，使得i(1)ropi(2)不按往常方式翻译为下边的接踵两个四元式：(jrop,i(1),i(2),0)(j,__,__,0)而是翻译成以下的一个四元式：(jnrop,i(1),i(2),0)使适当i(1)ropi(2)为假时发生转移，而为真时其实不发生转移(即次序履行下一个四元式)，进而产奏效率较高的四元式代码。【解答】按要求改造描绘布尔表达式的语义子程序以下：(1)E→i{=null;=nxq;emit(jez,entry(i),__,0);}(2)E→i(1)ropi(2){=null;=nxq;emit(jnrop,entry(i(1)),entry(i(2));)/*nrop表示关系运算符与rop相反*/(3)E→(E(1)){=E(1).tc;=E(1).fc;}(4)E→┐E(1){=nxq;emit(j,__,__,0);Backpatch(E(1).fc,nxq);}(5)EA→E(1)∧{=E(1).fc;}E→EAE(2){=E(2).tc;=merg,E(2).fc);}E0→E(1)∨{=nxq;emit(j,__,__,0);Backpatch(E(1).fc,nxq);}E→E0E(2){=E(2).fc;Backpatch,nxq);}依据三种基本控制结构文法将下边的语句翻译成四元式序列：while(A<C∧B<D){if(A≥1)C=C+1;elsewhile(A≤D)A=A+2;}【解答】该语句的四元式序列以下(此中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，而且关系运算符优先级高)：100(j<,A,C,102)101(j,_,_,113)/*E1为F*/102(j<,B,D,104)/*E1为T*/103(j,_,_,113)/*E1为F*/104(j=,A,1,106)/*E2为T*/105(j,_,_,108)/*E2为F*/106(+,C,1,C)/*C:=C+1*/107(j,_,_,112)/*跳过else后的语句*/108(j≤,A,D,110)/*E3为T*/109(j,_,_,112)/*E3为F*/110(+,A,2,A)/*A:=A+2*/111(j,_,_,108)/*转回内层while语句开始处*/112(j,_,_,100)/*转回外层while语句开始处*/113已知源程序以下：prod=0;i=1;while(i≤20){prod=prod+a[i]*b[i];i=i+1;}试按语法制导翻译法将上述源程序翻译成四元式序列(设A是数组a的开端地点，B是数组b的开端地点；机器按字节编址，每个数组元素占四个字节)。【解答】源程序翻译为以下四元式序列：100(=,0,_,prod)101(=,1,_,i)102(j≤,i,20,104)103(j,_,_,114)104(*,4,i,T1)105(-,A,4,T2)106(=[],T2,T1,T3)107(*,4,i,T4)108(-,B,4,T5)109(=[],T5,T4,T6)110(*,T3,T6,T7)111(+,prod,T7,prod)112(+,i,1,i)113(j,_,_,102)114给出文法G[S]:S→SaA|AA→AbB|BB→cSd|e请证明AacAbcBaAdbed是文法G[S]的一个句型；请写出该句型的全部短语、素短语以及句柄；(3)为文法G[S]的每个产生式写出相应的翻译子程序，使句型AacAbcBaAdbed经该翻译方案后，输出为。【解答】(1)依据文法G[S]画出AacAbcBaAdbed对应的语法树如图4-2所示。由图4-2可知AacAbcBaAdbed是文法G[S]的一个句型。SSaAABcSdAAbB图4-2AacAbcBaAdbed对应的语法树AbBecSd由图4-2S可知a，A句型AacAbcBaAdbed中的短语为ABB,BaA,cBaAd,AbcBaAd,e,cBaAdbe,cAbcBaAdbed,A,AacAbcBaAdbed从图4-2可看出，句型AacAbcBaAdbed中相邻终结符对应的优先关系以下(层次靠下的优先级高)：#?a?c?b?c?a?d?b?e?d?#素短语为BaA和e。句柄(最左直接短语)为A。采纳修剪语法树的方法，按句柄方式自下而上归约，每当一个产生式获取般配时，则按归约的先后次序与所给的输出次序进行对应。如：第一个