胡元義編譯原理教程第2版課后習(xí)題答案.ppt

1、第四章 語義分析和中間代碼生成,4.1 完成下列選擇題： (1) 四元式之間的聯(lián)系是通過 實(shí)現(xiàn)的。 a. 指示器 b. 臨時(shí)變量 c. 符號表 d. 程序變量 (2) 間接三元式表示法的優(yōu)點(diǎn)為 。 a. 采用間接碼表，便于優(yōu)化處理 b. 節(jié)省存儲空間，不便于表的修改 c. 便于優(yōu)化處理，節(jié)省存儲空間 d. 節(jié)省存儲空間，不便于優(yōu)化處理,(3) 表達(dá)式(AB)(CD)的逆波蘭表示為 。 a. ABCD b. ABCD c. ABCD d. ABCD (4) 有一語法制導(dǎo)翻譯如下所示： SbAb print1 A(B print2 Aa print3 BAa) print4 若輸入序列為b(aa)

2、a)a)b，且采用自下而上的分析方法，則輸出序列為 。,a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何謂“語法制導(dǎo)翻譯”？試給出用語法制導(dǎo)翻譯生成中間代碼的要點(diǎn)，并用一簡例予以說明。 【解答】 語法制導(dǎo)翻譯(SDTS)直觀上說就是為每個產(chǎn)生式配上一個翻譯子程序(稱語義動作或語義子程序)，并且在語法分析的同時(shí)執(zhí)行這些子程序。也即在語法分析過程中，當(dāng)一個產(chǎn)生式獲得匹配(對于自上而下分析)或用于歸約(對于自下而上分析)時(shí)，此產(chǎn)生式相應(yīng)的語義子程序進(jìn)入工作，完成既定的翻譯任務(wù)。,用語法

3、制導(dǎo)翻譯(SDTS)生成中間代碼的要點(diǎn)如下： (1) 按語法成分的實(shí)際處理順序生成，即按語義要求生成中間代碼。 (2) 注意地址返填問題。 (3) 不要遺漏必要的處理，如無條件跳轉(zhuǎn)等。 例如下面的程序段： if (i0) a=i+e-b*d; else a=0;,在生成中間代碼時(shí)，條件“i0”為假的轉(zhuǎn)移地址無法確定，而要等到處理“else”時(shí)方可確定，這時(shí)就存在一個地址返填問題。此外，按語義要求，當(dāng)處理完(i0)后的語句(即“i0”為真時(shí)執(zhí)行的語句)時(shí)，則應(yīng)轉(zhuǎn)出當(dāng)前的if語句，也即此時(shí)應(yīng)加入一條無條件跳轉(zhuǎn)指令，并且這個轉(zhuǎn)移地址也需要待處理完else之后的語句后方可獲得，就是說同樣存在著地址返填

4、問題。對于賦值語句a=i+e-b*d，其處理順序(也即生成中間代碼順序)是先生成i+e的代碼，再生成b*d的中間代碼，最后才產(chǎn)生“-”運(yùn)算的中間代碼，這種順序不能顛倒。,4.3 令S.val為文法GS生成的二進(jìn)制數(shù)的值，例如對輸入串101.101，則S.val=5.625。按照語法制導(dǎo)翻譯方法的思想，給出計(jì)算S.val的相應(yīng)的語義規(guī)則，G(S)如下： GS: SL.L|L LLB|B B0|1 【解答】 計(jì)算S.val的文法GS及語義動作如下： 產(chǎn)生式 語義動作 GS：SS print(S.val) SL1L2 S.val:=L1.val + L2.val/2L2.length,SL S.va

5、l:=L.val LL1B L.val:=L1.val*2 + B.val L.length:=L1.length +1 LB L.val:=B.val L.length:=2 B1 B.val:=1 B0 B.val:=0,4.4 下面的文法生成變量的類型說明： Did L L,id L|:T Tinteger|real 試構(gòu)造一個翻譯方案，僅使用綜合屬性，把每個標(biāo)識符的類型填入符號表中(對所用到的過程，僅說明功能即可，不必具體寫出)。,【解答】 此題只需要對說明語句進(jìn)行語義分析而不需要產(chǎn)生代碼，但要求把每個標(biāo)識符的類型填入符號表中。對D、L、T，為其設(shè)置綜合屬性type，而過程enter(

6、name,type)用來把名字name填入到符號表中，并且給出此名字的類型type。翻譯方案如下： Did L enter (, L.type); L,id L(1) enter (, L(1).type); L.type=L(1).type;,L:T L.type=T.type; Tinteger T.type=integer; Treal T.type=real; 4.5 寫出翻譯過程調(diào)用語句的語義子程序。在所生成的四元式序列中，要求在轉(zhuǎn)子指令之前的參數(shù)四元式par按反序出現(xiàn)(與實(shí)現(xiàn)參數(shù)的順序相反)。此時(shí)，在翻譯過程調(diào)用語句時(shí)，是否需要語義變量(隊(duì)列)queue

7、？,【解答】 為使過程調(diào)用語句的語義子程序產(chǎn)生的參數(shù)四元式par按反序方式出現(xiàn)，過程調(diào)用語句的文法為 Scall i(arglist) arglistE arglistarglist(1),E 按照該文法，語法制導(dǎo)翻譯程序不需要語義變量隊(duì)列queue，但需要一個語義變量棧STACK，用來實(shí)現(xiàn)按反序記錄每個實(shí)在參數(shù)的地址。翻譯過程調(diào)用語句的產(chǎn)生式及語義子程序如下：,(1) arglistE 建立一個arglist.STACK棧，它僅包含一項(xiàng)E.place (2) arglistarglist(1)，E 將E.place壓入arglist(1). STACK棧，arglist. STACK=arg

8、list(1).STACK (3) Scall i (arglist) while arglist.STACKnull do begin 將arglist.STACK棧頂項(xiàng)彈出并送入p單元之中； emit (par,_ ,_ ,p); end; emit (call,_ ,_ , entry (i);,4.6 設(shè)某語言的while語句的語法形式為 S while E do S(1) 其語義解釋如圖4-1所示。 (1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式； (2) 寫出每個產(chǎn)生式對應(yīng)的語義動作。,圖4-1 習(xí)題4.6的語句結(jié)構(gòu)圖,【解答】 本題的語義解釋圖已經(jīng)給出了翻譯后的中間代碼結(jié)構(gòu)。在語法制導(dǎo)翻譯

9、過程中，當(dāng)掃描到while時(shí)，應(yīng)記住E的代碼地址；當(dāng)掃描到do時(shí)，應(yīng)對E的“真出口”進(jìn)行回填，使之轉(zhuǎn)到S(1)代碼的入口處；當(dāng)掃描到S(1)時(shí)，除了應(yīng)將E的入口地址傳給S(1).chain之外，還要形成一個轉(zhuǎn)向E入口處的無條件轉(zhuǎn)移的四元式，并且將E.fc繼續(xù)傳下去。因此，應(yīng)把Swhile E do S(1) 改寫為如下的三個產(chǎn)生式： Wwhile AW E do SA S(1),每個產(chǎn)生式對應(yīng)的語義子程序如下： Wwhile W.quad=nxq; AW E do Backpatch(E.tc,nxq); A.chain=E.fc; A.quad=W.quad; SA S(1) Backpat

10、ch(S(1).chain,A.quad); emit(j,_,_,A.quad); S.chain=A.chain;,4.7 改寫布爾表達(dá)式的語義子程序，使得i(1) rop i(2)不按通常方式翻譯為下面的相繼兩個四元式： (jrop, i(1), i(2), 0) (j ,_ ,_ , 0 ) 而是翻譯成如下的一個四元式： (jnrop, i(1), i(2), 0) 使得當(dāng)i(1) rop i(2)為假時(shí)發(fā)生轉(zhuǎn)移，而為真時(shí)并不發(fā)生轉(zhuǎn)移(即順序執(zhí)行下一個四元式)，從而產(chǎn)生效率較高的四元式代碼。,【解答】 按要求改造描述布爾表達(dá)式的語義子程序如下： (1) Ei E.tc=null;E.f

11、c=nxq;emit(jez,entry(i),_ ,0); (2) Ei(1) rop i(2) E.tc=null;E.fc=nxq;emit(jnrop,entry(i(1),entry(i(2);) /* nrop表示關(guān)系運(yùn)算符與rop相反*/ (3) E(E(1) E.tc=E(1).tc; E.fc=E(1).fc; (4) EE(1) E.fc=nxq;emit(j,_ ,_ ,0);Backpatch(E(1).fc,nxq);,(5) EAE(1) EA.fc=E(1).fc; (6) EEAE(2) E.tc=E(2).tc;E.fc=merg(EA.fc,E(2).fc)

12、; (7) E0E(1) E0.tc=nxq;emit(j,_ ,_ ,0);Backpatch(E(1).fc,nxq); (8) EE0E(2) E.fc=E(2).fc;Backpatch(E0.tc,nxq);,4.8 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列： while (ACBD) if (A1) C=C+1; else while (AD) A=A+2; ,【解答】 該語句的四元式序列如下(其中E1、E2和E3分別對應(yīng)ACBD、A1和AD，并且關(guān)系運(yùn)算符優(yōu)先級高)： 100 (j,A,C,102) 101 (j,_,_,113) /*E1為F*/ 102 (j,B,

13、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語句開始處*/ 1

14、13,4.9 已知源程序如下： prod=0; i=1; while (i20) prod=prod+ai*bi; 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 (

15、* ,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,4.10 給出文法GS: SSaA | A AAbB | B BcSd | e (1) 請證實(shí)AacAbcBaAdbed是文法GS的一個句型； (2) 請寫出該句型的所有短語、素短語以及句柄； (3) 為文法GS的每個產(chǎn)生式寫出相應(yīng)的翻譯子程序，使句型AacAbcBaAdbed經(jīng)該翻譯方案后，輸出為131042521

16、430。,【解答】 (1) 根據(jù)文法GS畫出AacAbcBaAdbed對應(yīng)的語法樹如圖4-2所示。 由圖4-2可知AacAbcBaAdbed是文法GS的一個句型。,圖4-2 AacAbcBaAdbed對應(yīng)的語法樹,(2) 由圖4-2可知，句型AacAbcBaAdbed中的短語為 B, BaA, cBaAd, AbcBaAd, e, cBaAdbe, cAbcBaAdbed, A, AacAbcBaAdbed 從圖4-2可看出，句型AacAbcBaAdbed中相鄰終結(jié)符對應(yīng)的優(yōu)先關(guān)系如下(層次靠下的優(yōu)先級高)： #acbcadbed# 素短語為BaA和e。 句柄(最左直接短語)為A。,(3) 采用修剪語法樹的辦法，按句柄方式自