第四章語義剖析和中間代碼生成達(dá)成以下選擇題：(1)四元式之間的聯(lián)系是經(jīng)過實現(xiàn)的。a.指示器b.暫時變量c.符號表d.程序變量(2)間接三元式表示法的長處為。采納間接碼表，便于優(yōu)化辦理節(jié)儉儲存空間，不便于表的改正便于優(yōu)化辦理，節(jié)儉儲存空間節(jié)儉儲存空間，不便于優(yōu)化辦理(3)表達(dá)式(┐A∨B)∧(C∨D)的逆波蘭表示為。a.┐AB∨∧CD∨b.A┐B∨CD∨∧c.AB∨┐CD∨∧d.A┐B∨∧CD∨有一語法制導(dǎo)翻譯以下所示：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何謂“語法制導(dǎo)翻譯”試給出用語法制導(dǎo)翻譯生成中間代碼的重點，并用一簡例予以說明?！窘獯稹空Z法制導(dǎo)翻譯(SDTS)直觀上說就是為每個產(chǎn)生式配上一個翻譯子程序(稱語義動作或語義子程序)，而且在語法剖析的同時履行這些子程序。也即在語法剖析過程中，當(dāng)一個產(chǎn)生式獲取般配(關(guān)于自上而下剖析)或用于歸約(關(guān)于自下而上剖析)時，此產(chǎn)生式相應(yīng)的語義子程序進(jìn)入工作，達(dá)成既定的翻譯任務(wù)。用語法制導(dǎo)翻譯(SDTS)生成中間代碼的重點以下：按語法成分的實質(zhì)辦理次序生成，即按語義要求生成中間代碼。注意地點返填問題。不要遺漏必需的辦理，如無條件跳轉(zhuǎn)等。比以下邊的程序段：if(i>0)a=i+e-b*d;elsea=0;在生成中間代碼時，條件“i>0”為假的轉(zhuǎn)移地點沒法確立，而要等到辦理“else”時方可確立，這時就存在一個地點返填問題。別的，按語義要求，當(dāng)辦理完(i>0)后的語句(即“i>0”為真時履行的語句)時，則應(yīng)轉(zhuǎn)出目前的if語句，也即此時應(yīng)加入一條無條件跳轉(zhuǎn)指令，而且這個轉(zhuǎn)移地點也需要待辦理完else以后的語句后方可獲取，就是說相同存在著地點返填問題。關(guān)于賦值語句a=i+e-b*d，其辦理次序(也即生成中間代碼次序)是先生成i+e的代碼，重生成b*d的中間代碼，最后才產(chǎn)生“-”運(yùn)算的中間代碼，這類次序不可以顛倒。令為文法G[S]生成的二進(jìn)制數(shù)的值，比如對輸入串，則=。依據(jù)語法制導(dǎo)翻譯方法的思想，給出計算的相應(yīng)的語義規(guī)則，G(S)以下：G[S]:S→|LL

→LB|BB

→0|1【解答】計算的文法G′[S]及語義動作以下：產(chǎn)生式語義動作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試結(jié)構(gòu)一個翻譯方案，僅使用綜合屬性，把每個表記符的種類填入符號表中(對所用到的過程，僅說明功能即可，不用詳細(xì)寫出)?！窘獯稹勘绢}只要要對說明語句進(jìn)行語義剖析而不需要產(chǎn)生代碼，但要求把每個表記符的種類填入符號表中。對D、L、T，為其設(shè)置綜合屬性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;}寫出翻譯過程調(diào)用語句的語義子程序。在所生成的四元式序列中，要求在轉(zhuǎn)子指令以前的參數(shù)四元式par按反序出現(xiàn)(與實現(xiàn)參數(shù)的次序相反)。此時，在翻譯過程調(diào)用語句時，能否需要語義變量(行列)queue【解答】為使過程調(diào)用語句的語義子程序產(chǎn)生的參數(shù)四元式par按反序方式出現(xiàn)，過程調(diào)用語句的文法為S→calli(arglist)arglist→Earglist→arglist(1),E依據(jù)該文法，語法制導(dǎo)翻譯程序不需要語義變量行列queue，但需要一個語義變量棧STACK，用來實現(xiàn)按反序記錄每個實在參數(shù)的地點。翻譯過程調(diào)用語句的產(chǎn)生式及語義子程序以下：(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));}設(shè)某語言的while語句的語法形式為S→whileEdoS(1)其語義解說如圖4-1所示。寫出合適語法制導(dǎo)翻譯的產(chǎn)生式；寫出每個產(chǎn)生式對應(yīng)的語義動作。E的代碼真S(1)的代碼

假圖4-1習(xí)題的語句結(jié)構(gòu)圖【解答】本題的語義解說圖已經(jīng)給出了翻譯后的中間代碼結(jié)構(gòu)。在語法制導(dǎo)翻譯過程中，當(dāng)掃描到while時，應(yīng)記著E的代碼地點；當(dāng)掃描到do時，應(yīng)付E的“真出口”進(jìn)行回填，使之轉(zhuǎn)到S(1)代碼的進(jìn)口處；當(dāng)掃描到S(1)時，除了應(yīng)將E的進(jìn)口地點傳給S(1).chain以外，還要形成一個轉(zhuǎn)向E進(jìn)口處的無條件轉(zhuǎn)移的四元式，而且將持續(xù)傳下去。所以，應(yīng)把S→whileEdoS(1)改寫為以下的三個產(chǎn)生式：W→whileA→WEdoS→AS(1)每個產(chǎn)生式對應(yīng)的語義子程序以下：W→while{=nxq;}A→WEdo{Backpatch,nxq);=;=;}S→AS(1){Backpatch(S(1).chain,;emit(j,_,_,;=;}改寫布爾表達(dá)式的語義子程序，使得i(1)ropi(2)不按往常方式翻譯為下邊的接踵兩個四元式：(jrop,i(1),i(2),0)(j,__,__,0)而是翻譯成以下的一個四元式：(jnrop,i(1),i(2),0)使適當(dāng)i(1)ropi(2)為假時發(fā)生轉(zhuǎn)移，而為真時其實不發(fā)生轉(zhuǎn)移(即次序履行下一個四元式)，進(jìn)而產(chǎn)奏效率較高的四元式代碼?！窘獯稹堪匆蟾脑烀枥L布爾表達(dá)式的語義子程序以下：(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表示關(guān)系運(yùn)算符與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);}依據(jù)三種基本控制結(jié)構(gòu)文法將下邊的語句翻譯成四元式序列：while(A<C∧B<D){if(A≥1)C=C+1;elsewhile(A≤D)A=A+2;}【解答】該語句的四元式序列以下(此中E1、E2和E3分別對應(yīng)A＜C∧B＜D、A≥1和A≤D，而且關(guān)系運(yùn)算符優(yōu)先級高)：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)/*轉(zhuǎn)回內(nèi)層while語句開始處*/112(j,_,_,100)/*轉(zhuǎn)回外層while語句開始處*/113已知源程序以下：prod=0;i=1;while(i≤20){prod=prod+a[i]*b[i];i=i+1;}試按語法制導(dǎo)翻譯法將上述源程序翻譯成四元式序列(設(shè)A是數(shù)組a的開端地點，B是數(shù)組b的開端地點；機(jī)器按字節(jié)編址，每個數(shù)組元素占四個字節(jié))。【解答】源程序翻譯為以下四元式序列：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]的每個產(chǎn)生式寫出相應(yīng)的翻譯子程序，使句型AacAbcBaAdbed經(jīng)該翻譯方案后，輸出為?！窘獯稹?1)依據(jù)文法G[S]畫出AacAbcBaAdbed對應(yīng)的語法樹如圖4-2所示。由圖4-2可知AacAbcBaAdbed是文法G[S]的一個句型。SSaAABcSdAAbB圖4-2AacAbcBaAdbed對應(yīng)的語法樹AbBecSd由圖4-2S可知a，A句型AacAbcBaAdbed中的短語為ABB,BaA,cBaAd,AbcBaAd,e,cBaAdbe,cAbcBaAdbed,A,AacAbcBaAdbed從圖4-2可看出，句型AacAbcBaAdbed中相鄰終結(jié)符對應(yīng)的優(yōu)先關(guān)系以下(層次靠下的優(yōu)先級高)：#?a?c?b?c?a?d?b?e?d?#素短語為BaA和e。句柄(最左直接短語)為A。采納修剪語法樹的方法，按句柄方式自下而上歸約，每當(dāng)一個產(chǎn)生式獲取般配時，則按歸約的先后次序與所給的輸出次序進(jìn)行對應(yīng)。如：第一個