清華大學(xué)本科生考試試題編譯原理

1、清華大學(xué)本科生考試試題專用紙考試課程 編譯原理 （A卷） 2007年 7 月 3 日學(xué)號： 姓名： 一.（15%）簡答題const a=25;var x,y;procedure p; var z; begin end; procedure r; var x, s; procedure t; var v; begin end; begin /*here*/ end; begin end. 圖1 作用域與可見性1(3 %) 圖1 是支持嵌套過程說明的語言 PL0的一段程序。 若每個(gè)作用域棧都有各自的符號表，則在編譯器處理到/*here*/時(shí)，哪些作用域是開作用域？哪些作用域是閉作用域？作用域棧的棧

2、頂對應(yīng)哪個(gè)作用域？ 注：該段程序包含下列作用域 a, x, y, p, r z x, s, t v2(3 %) 如下是一個(gè)類 Pascal 程序片斷。試分別給出遵循靜態(tài)作用域規(guī)則和動(dòng)態(tài)作用域規(guī)則時(shí)運(yùn)行該段程序時(shí)的輸出結(jié)果。var r: realprocedure show; begin write(r:5:3) end;procedure small; var r:real; begin r:=0.125; show end;begin r:=0.25; show; small; writeln; show; small; writeln;end. 注：write(r:5:3) 表示按照一定格

3、式（總寬度為5，小數(shù)點(diǎn)后有三位數(shù)字）輸出 r；writeln 表示輸出一個(gè)換行符。3(3 %) 若按照某種運(yùn)行時(shí)組織方式，如下函數(shù) p 被激活時(shí)的過程活動(dòng)記錄如圖2所示。其中d是動(dòng)態(tài)數(shù)組。static int N；void p( int a) float b; float c10; float dN; float e; 試指出函數(shù) p 中訪問 di（0 £ i < N）時(shí)相對于活動(dòng)記錄基址的 Offset 值如何計(jì)算？若將數(shù)組 c 和 d 的聲明次序顛倒，則di（0 £ i < N）又如何計(jì)算？（對于后一問題默認(rèn)采用同樣的運(yùn)行時(shí)組織方式，若你認(rèn)為可能有歧義，請予

4、以說明）4 (3 %) 簡述實(shí)現(xiàn)參數(shù)傳遞方式 call-by-value 和 call-by-reference 的異同(指出實(shí)參的存儲(chǔ)與訪問策略)。5(3 %) 已知語言 L 已在機(jī)器 A 上實(shí)現(xiàn)，即已有一個(gè)在機(jī)器 A 上運(yùn)行的 L 語言的本地編譯程序 X。試給出一種實(shí)現(xiàn)方案，可以將機(jī)器 A 上的語言 L 移植到另一機(jī)器 B，即獲得一個(gè)運(yùn)行于機(jī)器 B 上的L 語言的本地編譯程序。二 (12%) 1(8 %) 圖3 流圖以基本塊為單位的到達(dá)-定值（reaching definitions）數(shù)據(jù)流方程可表示為 OUT B = GEN B （IN B - KILL B） IN B = pÎ

5、;PB OUT p 其中，PB 為 B 的所有前驅(qū)基本塊；GEN B 為在 B 中定值并可到達(dá) B 出口的所有定值點(diǎn)集合；KILL B 為 B 之外的那些定值點(diǎn)集合, 其定值的變量在 B 中又重新定值；IN B 為可到達(dá) B 入口處的各變量所有定值點(diǎn)的集合；OUT B為 B 出口處的各變量所有定值點(diǎn)的集合。對于圖3 所給出的流圖，分別求出 B1，B2，B3， B4 入口處及出口處的到達(dá)-定值點(diǎn)集合，即分別計(jì)算 In(B1)，Out(B1)，In(B2)，Out(B2)，In(B3)，Out(B3)，In(B4)，Out(B4)。初始時(shí)，假設(shè) In(B1)為空。2 (2%) 指出圖3 所示流圖中

6、存在的自然循環(huán)。3 (2%) 對于圖3 所示流圖，指出語句（3）中變量 c 和 b 在基本塊 B2 范圍內(nèi)的待用（Next Use）信息。三 (18%) 如下是一個(gè)簡單的FTP客戶端程序?qū)?yīng)的翻譯模式（省略函數(shù)的細(xì)節(jié)），其基礎(chǔ)文法為 GS：S ® A bye EXIT ( ); A ® A C ½ e C ® open ip num OPEN (ip . val, num . val ); ½ cd id CWD (id . val); ½ ls LIST ( ); ½ put id PUT_FILE (id . val);

7、 ½ get id GET_FILE (id . val); 其中小寫并帶下劃線的符號均為終結(jié)符。1. (6 pts) 試寫出該文法GS的LL(1)分析表，并根據(jù)分析表說明該文法不是LL(1)文法。2. (5 pts) 試通過消去文法GS中的左遞歸得到一個(gè)LL(1)文法GS，并給出一個(gè)以 GS為基礎(chǔ)文法的翻譯模式，其語義處理過程等效于上述以 GS為基礎(chǔ)文法的翻譯模式。3. (7 pts) 針對上述以 GS 作為基礎(chǔ)文法設(shè)計(jì)的翻譯模式，構(gòu)造一個(gè)自上而下的遞歸下降（預(yù)測）翻譯程序：注：可以直接使用類似于講稿中的 MatchToken 函數(shù)。為簡潔，可以直接用文法終結(jié)符作為參數(shù)，例如 Ma

8、tchToken(ip)，假設(shè)其含義如下：（1）若當(dāng)前掃描的單詞與終結(jié)符 ip 匹配，設(shè)置 ip . val，讀下一個(gè)單詞；（2）否則，顯示詞法錯(cuò)誤，退出處理。（若自己假設(shè)了不同的 MatchToken 函數(shù)或其他自定義函數(shù)，請予以說明）四 (12%) 給定文法G(S)：S ® A b ½ A B c A ® a A ½ aB ® b回答下列問題，并給出理由：1. 該文法是否 LR(0) 文法？2. 該文法是否 SLR(1) 文法？3. 該文法是否 LALR(1) 文法？4. 該文法是否二義文法？五 (8%) 給定文法G(S)：（1）S

9、74; A a（2）S ® b A c（3）S ® d c（4）S ® b d a（5）A ® d該文法的 LR(1) 自動(dòng)機(jī)如圖4所示：圖4 LR(1) 自動(dòng)機(jī)1. 該文法是否 LR(1) 文法？ (1分)2. 該文法是否 LALR(1) 文法？ (1分)3. 給出對應(yīng)的 LR(1) 分析表。 (6分)六 (9%) 已知某擴(kuò)展文法GS的LALR(1)分析表如下：狀態(tài)ACTIONGOTOatgc#S0s11s8s411s2acc2s33s11s8s4164s55s66s77r1r1r18s99s1010s11s8s41411s11s8s41212s13s

10、213s11s8s41514r4s2r415r2s2r216r3s2r3并且已知各規(guī)則右邊語法符號的個(gè)數(shù)以及左邊的非終結(jié)符如下：規(guī)則編號1234右部長度4444左部符號SSSS1. 請寫出使用上述LALR(1)分析器分析下面串的過程（只需寫出前10步，列出所有可能的ri, sj 序列，注意先后次序）：acaaccgtgccaacgatgccaa ×××2. 試指出該串相對于上述文法的句柄。七 (10%) 以下是語法制導(dǎo)生成某類TAC語句的一個(gè)L-屬性文法（對應(yīng)講稿中的相應(yīng)內(nèi)容）：S ® if E then S1 E .true := newlabel ;

11、 E .false := S .next ; S1.next := S .next ;S .code := E .code | gen(E.true :) | S1 .codeS ® if E then S1 else S2 E .true := newlabel;E .false := newlabel; S1 .next := S .next ; S2 .next := S .next ;S .code := E .code | gen(E.true :) | S1 .code | gen(goto S.next) | gen(E .false :)| S2 .codeS

12、74; while E do S1 E .true := newlabel ; E .false := S .next ; S1 .next := newlabel ;S .code := gen(S1 .next :)| E .code| gen(E.true :) | S1 .code | gen(goto S1 .next)S ® S1; S2 S1 .next := newlabel ;S2 .next := S .next ; S .code := S1 .code | gen(S1 .next :) | S2 .codeS ® S S.next := S .ne

13、xt ;S .code := S .codeS ® id := E p := lookup (); if （ p ¹ nil ) then S . code := E.code | gen (p := E . place) else error E ® E1 or E2 E1 .true := E . true ; E1 . false := newlabel ;E2 . true := E . true ; E2 . false := E . false ; E .code := E1 .code | gen(E1 . false :) | E2

14、.code. /*這里略去關(guān)于布爾表達(dá)式更多的部分*/E ® E1 + E2 E .place := newtemp;E .code := E1 .code | E2 .code | gen( E .place := E1 . place + E2 . place). /*這里略去關(guān)于算術(shù)表達(dá)式更多的部分*/其中，屬性 S .code , E .code , S .next , E.true , E.false，E .place, 語義函數(shù) newlabel , gen( )，lookup () , error 以及所涉及到的TAC語句與講稿中一致，“|”表示TAC語句

15、序列的拼接。（此外，假設(shè)在語法制導(dǎo)處理過程中遇到的二義性問題可以按照某種原則處理比如規(guī)定優(yōu)先級，else 匹配之前最近的 if，運(yùn)算的結(jié)合性，等等，這里不必考慮基礎(chǔ)文法的二義性。）若在基礎(chǔ)文法中增加對應(yīng) for-循環(huán)語句的產(chǎn)生式 S ® for (S; E ; S ) S，試參考上述控制語句的處理方法，給出相應(yīng)的的語義處理部分。注：這里，for-循環(huán)語句的控制語義類似 C 語言中的for-循環(huán)語句。另外，要注意到本題中使用的文法非終結(jié)符含義：S（所有語句），S（賦值語句），E（布爾表達(dá)式），E（ 算術(shù)表達(dá)式）。八 (16%) 設(shè)有如下翻譯模式，其基礎(chǔ)文法是GS： S ® E

16、 . Max := 32767 E print (E. Val) E ® E1 . Max := E . Max E1 + F . Max := E . Max F A . Max := E . Max ; A .v1 := E1 . Val ; A .v2 := F . Val A E . Val := A . Result E ® F . Max := E . Max F E . Val := F . Val F ® int C . Max := F. Max ; C . Val := int . Val C F . Val := C . Result F &

17、#174; ( E . Max := F. Max E ) F . Val := E . Val A ® e if (A .v1 + A .v2 > A . Max) error ( “add”) else A. Result := A .v1 + A .v2 C ® e if (C .Val > C . Max) error ( “l(fā)iteral”) else C. Result := C .Val 其中， +, *, (, ) 和 int 是終結(jié)符。1. 試變換上述翻譯模式，使嵌在產(chǎn)生式中間的語義規(guī)則集中僅含復(fù)寫規(guī)則，并使得在自底向上的LR分析和翻譯過程中，文法符號的所有繼承屬性均可以通過歸約前已出現(xiàn)在分析棧中的確定的綜合屬性進(jìn)行訪問。注： 只需要給出變化的部分。2. 根據(jù)1中變換后的翻譯模式，如果在LR分析過程中進(jìn)行自底向上的翻譯，文法符號的所有繼承屬性均可以通過