編譯原理試題.doc

中間語言與語法制導(dǎo)翻譯重點(diǎn)與難點(diǎn) 重點(diǎn)：語法制導(dǎo)翻譯的基本思想，屬性文法，翻譯模式，說明語句的翻譯方案。 三地址碼，各種語句的目標(biāo)代碼結(jié)構(gòu)、屬性文法與翻譯模式。難點(diǎn)：屬性的意義，對(duì)綜合屬性，繼承屬性，固有屬性的理解，屬性計(jì)算，怎么通過屬性來表達(dá)翻譯。布爾表達(dá)式的翻譯，對(duì)各種語句的目標(biāo)代碼結(jié)構(gòu)、屬性文法與翻譯模式的理解。基本要求掌握語法制導(dǎo)翻譯的基本思想，屬性文法，綜合屬性，繼承屬性，固有屬性，屬性計(jì)算，S_屬性文法，L_屬性文法，說明語句的翻譯方案，翻譯模式、屬性文法的實(shí)現(xiàn)掌握中間語言與語義分析的基本概念；熟練掌握語法（結(jié)構(gòu)）樹、三地址代碼、賦值與控制語句的翻譯、說明語句的翻譯；掌握組合數(shù)據(jù)說明的翻譯、過程調(diào)用翻譯。例題解析例1 給定文法 E - T R.i := T.p R E.p := R.s R - addopT R1.i := mknode( addop.val, R.i, T.p ) R R.s := R1.s R - e R.s := R1.s T - ( E ) T.p := E.p T - id T.p := mkleaf( id, id.entry ) T - num T.p := mkleaf( num, num.val ) (1) 指出文法中的各非終結(jié)符具有哪些綜合屬性和哪些繼承屬性 畫出按本翻譯模式處理表達(dá)式 a + 20 + ( b - 10 ) 時(shí)所生成的語法樹【解】(1)E的綜合屬性 p，R的繼承屬性i，綜合屬性s；T的綜合屬性p(2) 處理表達(dá)式 a + 20 + ( b - 10 ) 時(shí)所生成的語法樹如下 +(ID, a) +（NUM, 20） - ( ID, b) (NUM, 10)例2 定義一個(gè)計(jì)算器的屬性文法,完成一個(gè)輸入表達(dá)式值的計(jì)算和顯示,【解】計(jì)算器的文法L E E E1 + T | T T T1 * F | FF ( E ) | digit引進(jìn)屬性val，計(jì)算器的屬性文法：L E print( E.val )（L的虛屬性）E E1 + T E.val := E1.val + T.valE T E.val := T.valT T1 * F T.val := T1.val * F.valT F T.val := F.valF ( E ) F.val := E.valF digit F.val := digit.lexvallexval 是單詞 digit 的屬性例3給出對(duì)輸入串6-3 3*5+4 的分析樹與屬性計(jì)算【解】3*5+4 的分析樹與屬性計(jì)算+ *E.val=19E.val=15T.val=4T.val=15F.val=4digit.lexval=4F.val=5T.val=3F.val=3digit.lexval=3 LPrint(19)digit.lexval=5例4定義一個(gè)說明語句的屬性文法【解】說明語句的文法D T LT intT real L L1,idL id要解決的問題：記錄標(biāo)識(shí)符的類型和類型信息傳遞方法：引進(jìn)屬性type,和in,用T.type記錄類型信息，并傳給L.in, 說明語句的屬性文法如下: D T LL.in := T.typeT int T.type := integerT realT.type := realL L1,idL1.in := L.in addtype( id.entry, L.in )L idaddtype( id.entry, L.in )entry 單詞 id 的屬性addtype 在符號(hào)表中為變量填加類型信息例5 給出輸入串real id1,id2,id3 的分析樹和屬性計(jì)算 D T.type=realL.in=real real, Id3, Id2L.in=realL.in=realId1addtypeaddtype例6 設(shè)下列文法生成變量的類型說明 D id L L , id L | : T T integer | real 試構(gòu)造一個(gè)翻譯模式，把每個(gè)標(biāo)識(shí)符的類型存入符號(hào)表。【解】解題思路這是一個(gè)對(duì)說明語句進(jìn)行語義分析的題目，不需要產(chǎn)生代碼，但要求把每個(gè)標(biāo)識(shí)符的類型填入符號(hào)表中。解答對(duì)D，L，T設(shè)置綜合屬性type。過程addtype(id,type)用來把標(biāo)識(shí)符id及其類型type填入到符號(hào)表中。翻譯模式如下：D id Laddtype(id.entry,L.type)L ,id L1 addtype(id.entry,L1.type);L.type:=L1.type;L : T L.type:=T.typeT integer T.type:=intergerT real T.type:=real例7文法G的產(chǎn)生式如下： S (L) | a L L , S | S (1)試寫出一個(gè)語法制導(dǎo)定義，它輸出配對(duì)括號(hào)個(gè)數(shù); (2)寫一個(gè)翻譯方案，打印每個(gè)a的嵌套深度。如(a),a),打印2,1?！窘狻拷忸}思路本題包括兩部分，第1部分要求寫語法制導(dǎo)定義，第2部分要求寫翻譯方案。語法制導(dǎo)定義（或?qū)傩晕姆ǎ┛梢钥醋魇顷P(guān)于語言翻譯的高級(jí)規(guī)范說明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來。翻譯方案（也稱翻譯模式）給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，把某些實(shí)現(xiàn)細(xì)節(jié)表示出來。讀者從下面解答中可體會(huì)兩者的區(qū)別。解答為S、L引入屬性h,代表配對(duì)括號(hào)個(gè)數(shù)。語法制導(dǎo)定義如下：產(chǎn)生式語義規(guī)則S (L)S.h:=L.h+1S aS.h:=0L L1 , SL.h:=L1.h+S.hL SL.h:=S.hSSprint(S.h)(2)為S、L引入d，代表a的嵌套深度。翻譯方案如下：SS.d:=0;SS (L.d:=S.d+1; L )S aprint(S.d);L L1.d:=L.d; L1 S.d:=L.d; SL S.d:=L.dS例8下列文法對(duì)整型常數(shù)和實(shí)型常數(shù)施用 加法運(yùn)算符“+”生成表達(dá)式;當(dāng)兩個(gè)整型數(shù)相加時(shí)，結(jié)果仍為整型數(shù)，否則，結(jié)果為實(shí)型數(shù)： E E+T | T T num.num | num (1)試給出確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法。 (2)擴(kuò)充(1)的屬性文法，使之把表達(dá)式翻譯成后綴形式，同時(shí)也能確定結(jié)果的類型。應(yīng)該注意使用一元運(yùn)算符inttoreal把整型數(shù)轉(zhuǎn)換成實(shí)型數(shù)，以便使后綴形如加法運(yùn)算符的兩個(gè)操作數(shù)具有相同的類型。【解】解題思路確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法是比較容易定義的。關(guān)鍵是如何擴(kuò)充此屬性文法，使之把表達(dá)式翻譯成后綴形式。我們將不在name或num.num向T歸約的時(shí)候輸出該運(yùn)算對(duì)象，而是把運(yùn)算對(duì)象的輸出放在T或ET向E歸約的時(shí)候。這是因?yàn)榭紤]輸出類型轉(zhuǎn)換算符inttoreal的動(dòng)作可能在ET歸約的時(shí)候進(jìn)行，如果這時(shí)兩個(gè)運(yùn)算對(duì)象都在前面name或num.num向T歸約的時(shí)候已輸出，需要為第1個(gè)運(yùn)算對(duì)象輸出類型轉(zhuǎn)換算符時(shí)就已經(jīng)為時(shí)太晚。還要注意的是，在ET向E歸約時(shí)，該加法運(yùn)算的第1個(gè)運(yùn)算對(duì)象已經(jīng)輸出。所以EET的語義規(guī)則不需要有輸出E運(yùn)算對(duì)象的動(dòng)作。解答（1）為文法符號(hào)E和T配以綜合屬性type,用來表示它們的類型。類型值分別用int和real來表示。確定每個(gè)子表達(dá)式結(jié)果類型的屬性文法如下：產(chǎn)生式語義規(guī)則EE1TT.type:=if E1.type=int and T.type=int then int else realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=int(2)下面屬性文法將表達(dá)式的后綴表示打印輸出，其中l(wèi)exeme屬性表示單詞的拼寫。產(chǎn)生式語義規(guī)則EE1Tif E1.type=real and T.type=int then begin E.type:=real; print(T.lexeme); print(inttoreal); endelse if E1.type=int and T.type=real then begin E.type:=real; print(inttoreal); print(T.lexeme); endelse beginE.type:=E1.type;print(T.lexeme);endprint(+);ETE.type:=T.type;print(T.lexeme);Tnum.numT.type:=real;T.lexeme:=num1.lexeme|“.”|num2.lexemeTnumT.type:=int;T.lexeme:=num.lexeme;例9 將下列語句翻譯為逆波蘭表示(后綴式)、三元式和四元表示： a:=(b+c)*e+(b+c)/f【解】解題思路把中綴式轉(zhuǎn)換為后綴式的簡單方法：按中綴式中各運(yùn)算符的優(yōu)先規(guī)則，從最先執(zhí)行的部分開始寫，一層層套。如ab+cada+be，先把b+c寫為bc+；然后把a(bǔ)套上去，成為abc+；再把a(bǔ)d表示為ad；然后把套上去，成為abc+ad，依此類推。四元式由4個(gè)部分組成：算符op、第1和第2運(yùn)算量arg1和arg2，以及運(yùn)算結(jié)果result。運(yùn)算量和運(yùn)算結(jié)果有時(shí)指用戶自定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。如果op是一個(gè)算術(shù)或邏輯算符，則result總是一個(gè)新引進(jìn)的臨時(shí)變量，用于存放運(yùn)算結(jié)果。三元式只需3個(gè)域：op、arg1和arg2。與四元式相比，三元式避免了臨時(shí)變量的填入，而是通過計(jì)算這個(gè)臨時(shí)變量的語句的位置來引用這個(gè)臨時(shí)變量。我們很容易把一個(gè)算術(shù)表達(dá)式或一個(gè)賦值句表示為四元式序列或三元式序列。解答逆波蘭表示為：bc+e*bc+f/+:=三元式序列為：(1)(+，b，c)(2)(* ，(1) ，e)(3)(+ ，b，c)(4)(/ ，(3) ，f)(5)(+ ，(2) ，(4)(6)(:= ，a，(5)四元式序列為：(1)(+ ，b，c，T1)(2)(* ，T1，e，T2)(3)(+ ，b，c，T3)(4)(/ ，T3，f，T4)(5)(+ ，T2，T4，T5)(6)(:= ，T5，-，a)例10 利用回填技術(shù)把語句while a0 or b0 doif c0 and d0 or b0將被翻譯為：if a0 goto Ltruegoto L1L1: if b0 goto Ltruegoto Lfalse而c0 and d0 goto L3goto LfalseL3: if d0 goto L2 goto L1L1：if b0 goto L2 goto LnextL2：if c0 goto L3 goto L0L3：if d0 goto L4 Goto L0L4：T1:=y+1 x:=T1 goto L0Lnext：例11 C語言中的for語句的一般形式為：for(E1;E2;E3) s 其意義如下：E1；while(E2) do beginS;E3;end試構(gòu)造一個(gè)屬性文法和翻譯模式，把C語言的for語句翻譯成三地址代碼。【解】解題思路本題既要求構(gòu)造屬性文法，也要求構(gòu)造相應(yīng)的翻譯模式。因此，有必要回憶一下屬性文法和翻譯模式的區(qū)別。我們知道，屬性文法(有時(shí)也稱語法制導(dǎo)定義)可以看作是關(guān)于語言翻譯的高級(jí)規(guī)范說明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來；而翻譯模式(也稱為翻譯方案)是一種適合語法制導(dǎo)翻譯的描述形式，它給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，這樣就可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來。為了明確翻譯目標(biāo)，我們首先給出for語句的中間代碼結(jié)構(gòu)如圖1所示。根據(jù)C語言的for語句的語義和以上中間代碼結(jié)構(gòu)可以構(gòu)造出屬性文法。為了構(gòu)造屬性文法相應(yīng)的翻譯模式，通常可采用兩種方法：一種方法是在原有產(chǎn)生式中引入必要的標(biāo)記非終結(jié)符；另一種方法是對(duì)文法進(jìn)行分解和改造。兩種方法的目的都是為了便于語法制導(dǎo)翻譯。翻譯把C語言的for語句翻譯成三地址代碼的屬性文法如下：產(chǎn)生式語義動(dòng)作Sfor(E1;E2;E3) S1E2.lable:=newlable;E3.lable:=newlable;E2.true:=newlable;E2.false:=S.next;S1.next:=E3.lable;S.code:=E1.code|gen(E2.lable:)|E2.code|gen(E3.lable:)|E3.code|gen(gotoE2.lable)|gen(E2.true:)|S1.code|gen(gotoE3.lable)下面我們用兩種方法構(gòu)造相應(yīng)上述屬性文法的翻譯模式。方法一：引入M1、M2和N這3個(gè)標(biāo)記非終結(jié)符。M1用來記住E2的開始地址，M2用來記住M3的開始地址。N是用來產(chǎn)生E3后面的goto語句，從上面的中間代碼結(jié)構(gòu)來看，產(chǎn)生這個(gè)goto語句時(shí)，轉(zhuǎn)移地址應(yīng)該是已知的了，但語句是在N歸約時(shí)產(chǎn)生的，這時(shí)不能訪問M1的屬性，因此這個(gè)轉(zhuǎn)移的目標(biāo)地址是回填。所求的翻譯模式如下：Sfor(E1;M1E2;M2E3) N S1 emit(gotoM2.next); backpatch(E2.truelist,N.next); backpatch(S1.nextlist,M2.next); backpatch(N.nextlist,M1.next); S.nextlist:=E2.falselist;M M.next:=nextquadN N.nextlist:=makelist(nextquad); emit(goto_); N.ne