編譯原理試題.doc

中間語言與語法制導(dǎo)翻譯重點與難點 重點：語法制導(dǎo)翻譯的基本思想，屬性文法，翻譯模式，說明語句的翻譯方案。 三地址碼，各種語句的目標(biāo)代碼結(jié)構(gòu)、屬性文法與翻譯模式。難點：屬性的意義，對綜合屬性，繼承屬性，固有屬性的理解，屬性計算，怎么通過屬性來表達翻譯。布爾表達式的翻譯，對各種語句的目標(biāo)代碼結(jié)構(gòu)、屬性文法與翻譯模式的理解。基本要求掌握語法制導(dǎo)翻譯的基本思想，屬性文法，綜合屬性，繼承屬性，固有屬性，屬性計算，S_屬性文法，L_屬性文法，說明語句的翻譯方案，翻譯模式、屬性文法的實現(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é)符具有哪些綜合屬性和哪些繼承屬性 畫出按本翻譯模式處理表達式 a + 20 + ( b - 10 ) 時所生成的語法樹【解】(1)E的綜合屬性 p，R的繼承屬性i，綜合屬性s；T的綜合屬性p(2) 處理表達式 a + 20 + ( b - 10 ) 時所生成的語法樹如下 +(ID, a) +（NUM, 20） - ( ID, b) (NUM, 10)例2 定義一個計算器的屬性文法,完成一個輸入表達式值的計算和顯示,【解】計算器的文法L E E E1 + T | T T T1 * F | FF ( E ) | digit引進屬性val，計算器的屬性文法：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給出對輸入串6-3 3*5+4 的分析樹與屬性計算【解】3*5+4 的分析樹與屬性計算+ *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定義一個說明語句的屬性文法【解】說明語句的文法D T LT intT real L L1,idL id要解決的問題：記錄標(biāo)識符的類型和類型信息傳遞方法：引進屬性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 在符號表中為變量填加類型信息例5 給出輸入串real id1,id2,id3 的分析樹和屬性計算 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)造一個翻譯模式，把每個標(biāo)識符的類型存入符號表?！窘狻拷忸}思路這是一個對說明語句進行語義分析的題目，不需要產(chǎn)生代碼，但要求把每個標(biāo)識符的類型填入符號表中。解答對D，L，T設(shè)置綜合屬性type。過程addtype(id,type)用來把標(biāo)識符id及其類型type填入到符號表中。翻譯模式如下：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)試寫出一個語法制導(dǎo)定義，它輸出配對括號個數(shù); (2)寫一個翻譯方案，打印每個a的嵌套深度。如(a),a),打印2,1。【解】解題思路本題包括兩部分，第1部分要求寫語法制導(dǎo)定義，第2部分要求寫翻譯方案。語法制導(dǎo)定義（或?qū)傩晕姆ǎ┛梢钥醋魇顷P(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來。翻譯方案（也稱翻譯模式）給出了使用語義規(guī)則進行計算的次序，把某些實現(xiàn)細(xì)節(jié)表示出來。讀者從下面解答中可體會兩者的區(qū)別。解答為S、L引入屬性h,代表配對括號個數(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下列文法對整型常數(shù)和實型常數(shù)施用 加法運算符“+”生成表達式;當(dāng)兩個整型數(shù)相加時，結(jié)果仍為整型數(shù)，否則，結(jié)果為實型數(shù)： E E+T | T T num.num | num (1)試給出確定每個子表達式結(jié)果類型的屬性文法。 (2)擴充(1)的屬性文法，使之把表達式翻譯成后綴形式，同時也能確定結(jié)果的類型。應(yīng)該注意使用一元運算符inttoreal把整型數(shù)轉(zhuǎn)換成實型數(shù)，以便使后綴形如加法運算符的兩個操作數(shù)具有相同的類型?！窘狻拷忸}思路確定每個子表達式結(jié)果類型的屬性文法是比較容易定義的。關(guān)鍵是如何擴充此屬性文法，使之把表達式翻譯成后綴形式。我們將不在name或num.num向T歸約的時候輸出該運算對象，而是把運算對象的輸出放在T或ET向E歸約的時候。這是因為考慮輸出類型轉(zhuǎn)換算符inttoreal的動作可能在ET歸約的時候進行，如果這時兩個運算對象都在前面name或num.num向T歸約的時候已輸出，需要為第1個運算對象輸出類型轉(zhuǎn)換算符時就已經(jīng)為時太晚。還要注意的是，在ET向E歸約時，該加法運算的第1個運算對象已經(jīng)輸出。所以EET的語義規(guī)則不需要有輸出E運算對象的動作。解答（1）為文法符號E和T配以綜合屬性type,用來表示它們的類型。類型值分別用int和real來表示。確定每個子表達式結(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)下面屬性文法將表達式的后綴表示打印輸出，其中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ōu)先規(guī)則，從最先執(zhí)行的部分開始寫，一層層套。如ab+cada+be，先把b+c寫為bc+；然后把a套上去，成為abc+；再把ad表示為ad；然后把套上去，成為abc+ad，依此類推。四元式由4個部分組成：算符op、第1和第2運算量arg1和arg2，以及運算結(jié)果result。運算量和運算結(jié)果有時指用戶自定義的變量，有時指編譯程序引進的臨時變量。如果op是一個算術(shù)或邏輯算符，則result總是一個新引進的臨時變量，用于存放運算結(jié)果。三元式只需3個域：op、arg1和arg2。與四元式相比，三元式避免了臨時變量的填入，而是通過計算這個臨時變量的語句的位置來引用這個臨時變量。我們很容易把一個算術(shù)表達式或一個賦值句表示為四元式序列或三元式序列。解答逆波蘭表示為：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)造一個屬性文法和翻譯模式，把C語言的for語句翻譯成三地址代碼。【解】解題思路本題既要求構(gòu)造屬性文法，也要求構(gòu)造相應(yīng)的翻譯模式。因此，有必要回憶一下屬性文法和翻譯模式的區(qū)別。我們知道，屬性文法(有時也稱語法制導(dǎo)定義)可以看作是關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來；而翻譯模式(也稱為翻譯方案)是一種適合語法制導(dǎo)翻譯的描述形式，它給出了使用語義規(guī)則進行計算的次序，這樣就可把某些實現(xiàn)細(xì)節(jié)表示出來。為了明確翻譯目標(biāo)，我們首先給出for語句的中間代碼結(jié)構(gòu)如圖1所示。根據(jù)C語言的for語句的語義和以上中間代碼結(jié)構(gòu)可以構(gòu)造出屬性文法。為了構(gòu)造屬性文法相應(yīng)的翻譯模式，通?？刹捎脙煞N方法：一種方法是在原有產(chǎn)生式中引入必要的標(biāo)記非終結(jié)符；另一種方法是對文法進行分解和改造。兩種方法的目的都是為了便于語法制導(dǎo)翻譯。翻譯把C語言的for語句翻譯成三地址代碼的屬性文法如下：產(chǎn)生式語義動作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個標(biāo)記非終結(jié)符。M1用來記住E2的開始地址，M2用來記住M3的開始地址。N是用來產(chǎn)生E3后面的goto語句，從上面的中間代碼結(jié)構(gòu)來看，產(chǎn)生這個goto語句時，轉(zhuǎn)移地址應(yīng)該是已知的了，但語句是在N歸約時產(chǎn)生的，這時不能訪問M1的屬性，因此這個轉(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