清華大學(xué)編譯原理期末試題

1、清華大學(xué)本科生考試試題專用紙考試課程編譯原理（樣題）06級07級試題合并而成（以07級試題為基礎(chǔ)，第九題改為06級試題，附加了 06級的第一題）學(xué)號：姓名：（07 級）1.1#對于右圖中的Decaf/Mi nd 程序，根據(jù)第二階段實驗建立符 號表的過程，當(dāng)處理到圖中所 標(biāo)出的for語句時，當(dāng)前作用 域棧中含哪些開作用域？它們 對應(yīng)的符號表中分別包含哪些 符號？class Computer int cpu;void Crash(int numTimes) int i;for (i = 0; i < numTimes; i = i + 1)Print("sadn");cl

2、ass Mac extends Computer int mouse;void Crash(int numTimes) Print("ack!");class Main static void main() class Mac powerbook; powerbook = new Mac(); powerbook.Crash(2);#2. 對于上圖（第1小題圖）中的 Decaf/Mind程序，根據(jù)課程實驗所采取的運行時存儲 組織方式，當(dāng)powerbook所指向的對象創(chuàng)建后，其對象存儲空間中含有哪些內(nèi)容？ class Mac的vtable中包含哪些內(nèi)容？3.若按照某種運行時存

3、儲組織方 式，如下函數(shù)p被激活時的過 程活動記錄如右圖所示。其中 d是動態(tài)數(shù)組。static int N ；void p( int a) float b;float c10; float dN; float e;e指向d空間的指針d的上界（N）控制信息<Offset =30+2N- Offset =30- Offset =28- Offset =27-*Offset =26Offset = 6一Offset= 4- Offset= 3tOffset= 0#試指出函數(shù) p中訪問di（ 0 < i < N）時相對于活動記錄基址的Offset值如何計算?#var a,b; proc

4、edure p ;(1)(2)(3)(4)(5)(6) (8)若將數(shù)組c的聲明改為float cN,那么你將如何修改函數(shù)p活動記錄的組織（說明一種可行方案的思路即可）？(06 級)1. PL0編譯器的符號表采用一個全局的單符號表棧結(jié)構(gòu)。對于下圖左邊的PL0程序,PL0編譯器在處理到第L行時符號表棧中的符號有哪些？var x;procedure r ;var x, y;begina := 0;if a < b the n call q;en d;begincall r ;end ; procedure q ;var x;begin(L)if a < b then call p ;en

5、d ;begina := 1;b := 2; call q;end .2. 對于PL0的棧式動態(tài)存儲分配（過程活動記錄中的控制信息包括靜態(tài)鏈SL，動態(tài)鏈DL，以及返回地址 RA），上圖左邊的PL0程序執(zhí)行到過程 p被第二次激活時，運 行棧的當(dāng)前狀態(tài)如上圖右邊所示（棧頂指向單元26）。試補齊該運行狀態(tài)下，單元18、19、21、22、及23中的內(nèi)容。3. 針對靜態(tài)作用域規(guī)則和動態(tài)作用域規(guī)則，分別指出上圖左邊的 PL0程序執(zhí)行到過程q被第二次激活時，第 L行代碼中所訪問的變量a的值各是多少？.（07級）1. 設(shè)有如下無二義文法 GS:S t A b A B cA t a A aB > b試給出

6、句型 aA b c的所有短語、直接短語和句柄；即填充下表:句型短語直接短語句柄a A b c2. 給定文法GS:S ； AB A > : |aAbB4#下表中已給出針對文法 GE各產(chǎn)生式右部文法符號串的 First集合，以及各產(chǎn)生式 左部非終結(jié)符的 Follow集合。試求出各產(chǎn)生式的預(yù)測集合 PS (即完成下表)，并指 出文法 GS是否LL(1)文法？G中的規(guī)則rFirst (rhs(r)Follow (lhs(r)PS (r)S t ABa， c#A T zzb,c,#A t aAbBab,c,#B t cAcb,c,#表中的rhs(r)表示產(chǎn)生式r右部的文法符號串，lhs(r)表示產(chǎn)

7、生式r左部的非終結(jié)符。三( 07 級)1.給定 SLR(1)文法 GS:S > a A bS - cA > A SA > S如下是基于GS的一個S屬性文法/翻譯模式:/ :=為賦值號 S.x := A.x + 1 S > c A A1 S Sx := 0 A.x := A1.X + S.x A.x := S.x (1)輸入串a(chǎn)acbacbb的一棵語法分析樹如下圖所示。試針對該語法分析樹進行標(biāo)注 (即得到一棵帶標(biāo)注的語法分析樹，標(biāo)出分析樹中各結(jié)點所對應(yīng)文法符號的屬性 值，本題中的終結(jié)符不對應(yīng)屬性值)。（2）如果在LR分析過程中根據(jù)該翻譯模式進行自下而上翻譯，試寫出在按每個

8、產(chǎn)生 式歸約時語義處理的一個代碼片斷（設(shè)語義棧由向量v表示，歸約前棧頂位置為top，終結(jié)符不對應(yīng)語義值，而每個非終結(jié)符的綜合屬性都只對應(yīng)一個語義值，可用 vi.x表示；不用考慮對 top的維護）。2.變換如下翻譯模式， 使嵌在產(chǎn)生式中間的語義動作集中僅含復(fù)寫規(guī)則，并使得在自底向上的語法分析過程中，文法符號的所有繼承屬性均可以通過歸約前已出現(xiàn)在分析棧 中的確定的綜合屬性進行訪問：D Di ; T L.type :=type; L.offset := Di .width ; L.width := T.width LD.width := Di.width + L.num T.width D r T

9、L.type := T.type; L.offset := 0 ; L.width := T.width LD.width := L.numT.width T integer T.type := int ; T.width := 4 T real T.type := real ; T.width := 8 L Li. type := L. type ; Li. offset := L. offset ; Li. width := L. width ; Li , id enter (id. name, L. type, L. offset + Li.num L. width) ; L.num :

10、= Li.num +i L id enter (id. name, L. type, L. offset) ; L.num := i四（07級）如下是以LL（i）文法GS作為基礎(chǔ)文法設(shè)計的翻譯模式，試針對該翻譯模式構(gòu)造 一個自上而下的遞歸下降（預(yù)測）翻譯程序：/ ：=為賦值號S -； F P.i := F.val P print (P.s) P > + F Pi.i := P.i + F.val Pi P.s := Pi.s P > ; P.s := P.i Fa F. val := i (可以直接使用講稿中的 MatchToken函數(shù))五(07級)給定文法G(S):S ； A b

11、S、A B c A ； a AA > aB b51. 下圖表示該文法的LR(O)自動機，部分狀態(tài)所對應(yīng)的項目集未給出，試補齊之(即分 別給出狀態(tài)10, 12, 13 ,14，I5，I6和I7對應(yīng)的項目集。IoIl6#2. 指出該LR(0)自動機中沖突的狀態(tài)(并指出是哪種類型的沖突)，以說明該文法不是LR(0)文法。3. 說明該文法是 SLR(1)文法。六(07級)為文法GE態(tài)機如下圖所示:增加產(chǎn)生式S > E，得到增廣文法G'S，并構(gòu)造相應(yīng)得LR( 0)有限狀I(lǐng)oI3I6I8G(E)E -(LH E )E -FL TL II EL >EF >(F)Fd給定如下文

12、法(1)1. 該LR ( 0)有限狀態(tài)機中存在兩個沖突的狀態(tài)，試指出它們，并分別說明這兩個狀 態(tài)是否可用SLR(1)分析方法解決？2. 根據(jù)課程的講解，對于不可用SLR(1)分析方法解決的沖突狀態(tài)，實際上可以根據(jù)句柄實際所期望的后跟符號來解決這一沖突。試通過分析該LR(0)有限狀態(tài)機，指出相應(yīng)句柄實際所期望的后跟符號，并說明你的結(jié)論是通過觀察哪幾個狀態(tài)得到 的？七(07級)給定文法G(S):S -； S S a S b ；LR(1)項目集(狀態(tài))/歸約沖突的項目集(狀態(tài))/歸約沖突的項目集(狀態(tài))在該文法的LR(1)自動機中，存在有沖突的1. 給出這些項目集(狀態(tài))中任意一個存在移進2. 給出

13、這些項目集(狀態(tài))中任意一個存在歸約八(07級)B31. 對于上圖所給出的流圖，為基本塊B2構(gòu)造DAG圖。2. 對于上圖所給出的流圖，根據(jù)采用迭代求解數(shù)據(jù)流方程對活躍變量信息進行分析的 方法，求出 B2出口處、B2入口處以及 B4入口處的活躍變量集合，即LiveOut(B2)，Liveln(B2)和 Liveln (B4)的值。假設(shè)迭代開始時LiveOut(B4)=。3. 利用LiveOut(B2)的結(jié)果，指出在語句(4)和語句(5)之間的程序點，哪些變量 是活躍的。4. 求該流圖范圍內(nèi)，d在定值點(4)的DU鏈。九 以下是語法制導(dǎo)生成 TAC語句的一個S-屬性文法(翻譯模式)：(06級)S

14、> if E then M S1 backpatch(E.truelist,M.gotostm);S.n extlist := merge(E.falselist, S 1. nextlist) S if E the n M 1 S1 N else M2 S2 backpatch(E.truelist, M 1.gotostm);backpatch(E.falselist, M 2.gotostm);S.n extlist := merge(S 1.n extlist, mergS > while M 1 E then M2 Si backpatch(Si.nextlist, Mi

15、.gotostm); backpatch(E.truelist, M 2.gotostm); S.n extlist := E.falselist;emit( goto' , M1.gotostm) S > S1; M S2 backpatch(S1.nextlist, M.gotostm) ; S.nextlist := S 2.nextlist S ； S' S.nextlist := S '.nextlist) S' id := A S'. nextlist :='emit (id .place := ' A . place)

16、 E j E1 or M E2 backpatch(E1.falselist,M.gotostm); E.truelist := merge(E 1.truelist, E 2.truelist); E.falselist := E 2.falselist E E1 and M E2 backpatch(E1.truelist,M.gotostm); E.falselist := merge(E 1.falselist, E 2 .falselist); E.truelist := E 2 .truelist Enot E1 E.truelist := E 1 .falselist ; E.f

17、alselist := E 1.truelist E > (E1 ) E.truelist := E 1.truelist ; E.falselist := E 1 .falselist E id 1 rop id 2 E.truelist := makelist ( n extstm); E.falselist := makelist ( n extstm+ 1); emit ( if id1.place rop.op id 2.place goto _);' emit ( ' goto _ 'Ar A1 + A2 A .place := n ewtemp;em

18、it( A .place ':= ' A1 . place + A 2 . place) Ar A1 ” A2 A .place := n ewtemp;emit( A .place ':= ' A1 . place - A. place) A > id A .place := newtemp;emit ( A .place := id .place) A > const A .place := newtemp;emit ( A .place := const .val ./*這里略去關(guān)于算術(shù)表達式更多的部分*/M > ； M.gotostm

19、:= n extstm N 一； N.nextlist := makelist(nextstm); emit( goto _' ) 其中，所用到的語義函數(shù)與講稿中一致，列舉如下：makelist（i）:創(chuàng)建只有一個結(jié)點i的表，對應(yīng)存放目標(biāo) TAC語句數(shù)組的一個下標(biāo)merge（pi,p2）:連接兩個鏈表 pi和p2，返回結(jié)果鏈表backpatch（p,i）:將鏈表p中每個元素所指向的跳轉(zhuǎn)語句的標(biāo)號置為inextstm :下一條TAC語句的地址emit （）:輸出一條TAC 語句，并使 nextstm加1newtemp :返回一個未使用過的名字屬性 E .truelist , E .falselist , S .nextlist, S 'extlist, A .place, M .gotostm, N .nextlist以及所涉及到的 TAC語句與講稿中一致，另外，要注意到本題中使用的文法非終結(jié)符含義：S （所有語句），S'（賦值語句），E（布爾表達式），A （算術(shù)表達式）。（此外，假設(shè)在語法制導(dǎo)處理過程中遇到的二義性問題可以按照某種原則處理比如規(guī)定 優(yōu)先級，else匹配之前最近的if,運算的結(jié)合性，等等，這里