編譯原理測驗(yàn)題

1、2001年編譯原理試題 1. (10分)處于/*和*/之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種 注解的DFA的狀態(tài)轉(zhuǎn)換圖。 2. (10分)為語言 L = ambn | 0 m TL T ； int | real L id R R , id R | ； 4. （15分）就下面文法 S t ( L) | a L t L . S | S *給出一個(gè)語法制導(dǎo)定義，它輸出配對括號的個(gè)數(shù)。 給出一個(gè)翻譯方案，它輸出每個(gè) a的嵌套深度。 女口句子(a, (a, a),第一小題的輸出是2,第二小題的輸出是1 2 2。 5. (10分)Pascal語言for語句的含義見教材第222頁習(xí)題7.13。請為

2、該語句設(shè) 計(jì)一種合理的中間代碼結(jié)構(gòu)。你可以按第 215頁圖7.17的方式或者第219頁圖 7.19的方式寫出你的設(shè)計(jì)，不需要寫產(chǎn)生中間代碼的語法制導(dǎo)定義。 6. (5分)一個(gè)C語言程序如下： fun c(i1,i2,i3) long i1,i2,i3; long j1,j2,j3; printf(Addresses of i1,i2,i3 = %o,%o,%on, prin tf(Addresses of j1,j2,j3 = %o,%o,%on, mai n() long i1,i2,i3; fun c(i1,i2,i3); 該程序在某種機(jī)器的Linux上的運(yùn)行結(jié)果如下： Addresses

3、 of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434 從上面的結(jié)果可以看出，func函數(shù)的3個(gè)形式參數(shù)的地址依次升高，而3 個(gè)局部變量的地址依次降低。試說明為什么會(huì)有這個(gè)區(qū)別。 7. (15分)一個(gè)C語言程序及其在某種機(jī)器linux操作系統(tǒng)上的編譯結(jié)果如下。 根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的作用域、生存期和置初值方式等 方面的區(qū)別。 static long aa = 10; short bb = 20; fun c()

4、 static long cc = 30; short dd = 40; .file static.c .versio n 01.01 gcc2_compiled.: .data .alig n 4 .typeaa,object .sizeaa,4 aa: .long 10 .globl bb .alig n 2 .typebb,object .sizebb,2 bb: .value 20 .alig n 4 .type cc.2,object .size cc.2,4 cc.2: .long 30 .text .alig n 4 .globl func .typefun c,fu nctio

5、n func: pushl %ebp movl %esp,%ebp subl $4,%esp movw $40,-2(%ebp) 丄1: leave ret .Lfe1: .sizefun c,.Lfe1-f unc .ident GCC: (GNU)egcs-2.91.66 19990314/Linux (egcs-1.1.2 release) 8. (10分)C語言是一種類型語言，但它不是強(qiáng)類型語言，因?yàn)榫幾g時(shí)的類型檢 查不能保證所接受的程序沒有運(yùn)行時(shí)的類型錯(cuò)誤。例如，編譯時(shí)的類型檢查一般 不能保證運(yùn)行時(shí)沒有數(shù)組越界。請你再舉一個(gè)這樣的例子說明C語言不是強(qiáng)類型 9. ( 10分)如果在A機(jī)

6、器上我們有C語言編譯器CCa，也有它的源碼Sa (用C 語言寫成)。如何利用它通過盡量少的工作來得到 B機(jī)器的C語言編譯器CCb。 10. (5 分)表達(dá)式( x.( yz.(x + y) + z) 3) 4 5 和( x.( yz.(x + y) + z) 3 5) 4 有同樣的 結(jié)果。在抽象機(jī)FAM 上,哪一個(gè)表達(dá)式對應(yīng)的目標(biāo)代碼的執(zhí)行效率高？為什么？ 2001年編譯原理試題參考答案 1. 2. LR (1)文法 S AB|aABb A aaAb | : LR (1)文法 S AB A aaAb | ab | ； B Bb | ； 二義文法 S AASb| A - a | ； B Bb |

7、 : 3. int real id J $ D D TL D TL T T； int T real L L id R R R , id R R r ； 4. S S prin t(S .num) S (L) S.num := =L.num +1 S a S.num := =0 L L1,S L. num := :L 1. num + S.num L S L.num := :S.num S J S.depth := 0 S S ； L.depth := S.depth +1 (L) S ； a print(S.depth) L - Li .depth := L.depth L 1, S.dept

8、h := L.depth S L - S.depth := L.depth S 5. t1 := in itial t2 := final if t1 t2 goto L1 v := t1 L2: stmt if v = t2 goto L1 v := v + 1 goto L2 L1: 6. 由于實(shí)參表達(dá)式是反序進(jìn)入活動(dòng)記錄，而局部變量是順序在活動(dòng)記錄中分配。 7. aa是靜態(tài)外部變量，而bb是外部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)(由.data 偽指令開始)，但是bb由偽指令.globl指明為全局的，用來解決其它文件中對 bb 的外部引用，而aa只能由本文件引用。cc是靜態(tài)局部變量，同aa和bb

9、 一樣， 它的生存期是整個(gè)程序并分配在靜態(tài)數(shù)據(jù)區(qū)。由于cc在源程序中的作用域是函 數(shù)func的體，而在目標(biāo)文件中，它的作用域至少已是整個(gè)文件了，為避免同源 文件中外部變量和其它函數(shù)的靜態(tài)局部變量的名字沖突，所以要對它進(jìn)行改名， 成了 cc.2。由于cc不是全局的，因此cc.2前面沒有偽指令.globl。dd是自動(dòng)變量， 其作用域是函數(shù)func的體，其生存期是該函數(shù)激活期間，因此它分配在棧區(qū)， 并且置初值是用運(yùn)行時(shí)的賦值來實(shí)現(xiàn)。 8. 例如聯(lián)合體的類型檢查一般也不可能在編譯時(shí)完成，雖然下面例子是可靜態(tài) 判斷類型錯(cuò)誤的。 union U int u1; int *u2; u; int p; u.u

10、l = 10; p = u.u2; p = 0; 9. 修改源碼Sa的代碼生成部分，讓它產(chǎn)生B機(jī)器的代碼，稱結(jié)果程序?yàn)镾b。 *將Sb提交給CCa進(jìn)行編譯，得到一個(gè)可執(zhí)行程序。 將Sb提交給上述可執(zhí)行程序進(jìn)行編譯，得到所需的編譯器CCb。 10. 第一個(gè)表達(dá)式在執(zhí)行-yz.(x+ y) + z) 3時(shí)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況，因此有 FUNVAL的值進(jìn)入棧頂，然后發(fā)現(xiàn)參數(shù)個(gè)數(shù)不足，又把它做成FANVAL的情況。 而第二個(gè)表達(dá)式執(zhí)行的是( yz.(x + y) + z) 3 5，不會(huì)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況。因 此第二個(gè)表達(dá)式的執(zhí)行效率比第一個(gè)表達(dá)式的咼。 2003年編譯原理試題 1. (20分)寫

11、出字母表I = a, b上語言L = w | w中a的個(gè)數(shù)是偶數(shù)的正規(guī)式， 并畫出接受該語言的最簡 DFA。 2. (15分)考慮下面的表達(dá)式文法，它包括數(shù)組訪問、加和賦值： E T EE | E + E | E = E | (E) | id 該文法是二義的。請寫一個(gè)接受同樣語言的LR(1)文法，其優(yōu)先級從高到低依次 是數(shù)組訪問、加和賦值，并且加運(yùn)算是左結(jié)合，賦值是右結(jié)合。 3. (10分)下面是產(chǎn)生字母表1 = 0, 1,2上數(shù)字串的一個(gè)文法： S D S D | 2 D 0 | 1 寫一個(gè)語法制導(dǎo)定義，它打印一個(gè)句子是否為回文數(shù)（一個(gè)數(shù)字串，從左向右讀 和從右向左讀都一樣時(shí)，稱它為回文數(shù)）

12、。 4. （10分）教材上721節(jié)的翻譯方案 P D D D ; D D id : T T - integer J real offset := 0 en ter(id. name T.type, offset); offset := offset + T.width T.type := in teger; T.width := 4 T.type := real; T.width := 8 使用了變量offset。請重寫該翻譯方案，它完成同樣的事情，但只使用文法符號 的屬性，而不使用變量。 5. （5分）一個(gè)C語言程序如下： void fun（ struct int x; double r;

13、val） mai n() struct int x; double r; val; fun( val); 該程序在X86/Linux機(jī)器上的用cc命令編譯時(shí)，報(bào)告的錯(cuò)誤信息如下： 1: warning: structure defi ned in side parms 1: warning: anonym ous struct declared in side parameter list 1: warning: its scope is only this definition or declaration, 1: warning: which is probably not what yo

14、u want. 7: in compatible type for argume nt 1 of fun 請問，報(bào)告最后一行的錯(cuò)誤的原因是什么？如何修改程序，使得編譯時(shí)不再出現(xiàn) 這個(gè)錯(cuò)誤信息。 6. (10分)一個(gè)C語言程序如下: typedef struct _a short i; short j; short k; a; typedef struct _b long i; short k; b; mai n() prin tf(Size of short. Io ng, a and b = %d,%d,%d,%dn, sizeof(short), sizeof(long),sizeof(a

15、),sizeof(b); 該程序在X86/Linux機(jī)器上的運(yùn)行結(jié)果如下： Size of short, long, a and b = 2, 4, 6, 8 已知short類型和long類型分別對齊到2的倍數(shù)和4的倍數(shù)。試問，為什么類型 b的size會(huì)等于8？ 7. (15分)一個(gè)C語言程序如下： int fact(i) int i; if(i=0) return 1; else return i*fact(i-1); mai n() prin tf(%dn, fact(5); prin tf(%dn, fact(5,10,15); prin tf(%dn, fact(5.0); prin

16、tf(%dn, fact(); 該程序在X86/Linux機(jī)器上的運(yùn)行結(jié)果如下： 120 120 1 Segme ntati on fault (core dumped) 請解釋下面問題： 第二個(gè)fact調(diào)用：結(jié)果為什么沒有受參數(shù)過多的影響？ 第三個(gè)fact調(diào)用：為什么用浮點(diǎn)數(shù)5.0作為參數(shù)時(shí)結(jié)果變成1? 第四個(gè)fact調(diào)用：為什么沒有提供參數(shù)時(shí)會(huì)出現(xiàn)Segmentation fault? 8. (5分)C語言的賦值操作并非僅對簡單類型而言，例如若有類型聲明long a100, b100;，則賦值a=b是允許的。同樣，若a和b是同一類型的兩個(gè)結(jié)構(gòu)， 則賦值a=b也是允許的。 用教材上第七章所給

17、出的三地址語句，我們能否為這種賦值產(chǎn)生中間代碼？ 若你持肯定態(tài)度，請你給出對應(yīng)這種賦值的中間代碼序列； 否則請你為這種賦值 設(shè)計(jì)一種三地址語句。你所選用或設(shè)計(jì)的三地址語句要便于目標(biāo)代碼的生成。 9. (5分)一個(gè)C程序的三個(gè)文件的內(nèi)容如下： head.h: short int a = 10; filel.c: #in elude head.h mai n() file2.c: #in clude head.h 在X86/Linux機(jī)器上的編譯命令如下： cc file1.c file2.c 編譯結(jié)果報(bào)錯(cuò)的主要信息如下： multiple defi niti on of a 試分析為什么會(huì)報(bào)這樣

18、的錯(cuò)誤。 10. (5分)按照教材上介紹的方法，把下面C+語言的函數(shù)翻譯成C的函數(shù) void zoom (GraphicalObj / 將中心點(diǎn)移至原點(diǎn) (0, 0) obj.scale (zoom_factor);/ 縮放 2003年編譯原理試題參考答案 1 .語言L的正規(guī)式是： * * * * * (a b a | b)或 b (a b a b ) 接受該語言的最簡DFA是： start b a 2. E T = E | T T T + F | F F FE | (E) | id 3. S S prin t(S.val) S Di Si D2 S.val = =(Di.val = D2.v

19、al) and Si .val S 2 S.val = =true D 0 D.val = =0 D i D.val = =i 4. 文法符號D的屬性offsetl是繼承屬性，代表在分析D前原來使用的變量offset 的大?。粚傩詏ffset2是綜合屬性，代表在分析D后原來使用的變量offset的大小。 P的屬性offset是綜合屬性，記錄該過程所分配的空間。 P t D.offsetl := 0 D P.offset := D.offset2 D 、Di.offsetl := D.offsetl Di ; D2.offset1 := D i .offset2 D2 D.offset2 :=

20、D2.offset2 D id : T en ter ( id. name T.type, D.offsetl); D.offset2 := D.offset1 +width T 一: integer T.type := integer; T.width := 4 7 real T.type := real; T.width := 8 5. C語言對所有的類型都采用結(jié)構(gòu)等價(jià)，唯有結(jié)構(gòu)類型例外，采用名字等價(jià)。 這里的類型不相容是因?yàn)閮蓚€(gè) val不是名字等價(jià)的。 要消除這個(gè)錯(cuò)誤，包括所有的警告，程序修改如下： struct s int x; double r; ; void fun( struct

21、 s val) mai n() struct s val; fun( val); 6. 個(gè)數(shù)組的size等于數(shù)組元素的size乘以數(shù)組元素的個(gè)數(shù)，這是一個(gè)原則。 對于結(jié)構(gòu)類型b來說，它的一個(gè)變量只需6個(gè)字節(jié)就夠了。如果聲明結(jié)構(gòu)類 型b的一個(gè)數(shù)組，有兩種可能： (a) 結(jié)構(gòu)類型b的size是6,數(shù)組元素之間空兩個(gè)字節(jié)，以保證每個(gè)數(shù)組 元素的地址都是4的倍數(shù)(因?yàn)榈谝粋€(gè)域i的類型是long,要求對齊到4的倍數(shù))。 (b) 結(jié)構(gòu)類型b的size是8，以保證它作為數(shù)組元素的類型時(shí)，數(shù)組元素 之間不用再考慮對齊問題。 方法(a)違反了我們一開始提到的原則，因此只能取方法(b)。 7. (1)參數(shù)表達(dá)式逆

22、序計(jì)算并進(jìn)棧，fact能夠取到第一個(gè)參數(shù)。 (2) 參數(shù)5.0轉(zhuǎn)換成雙精度數(shù)進(jìn)棧，占8個(gè)字節(jié)。它低地址的4個(gè)字節(jié)看成 整數(shù)時(shí)正好是0。 (3) 由于沒有提供參數(shù)，fact把老ebp (控制鏈)(main的活動(dòng)記錄中保存 的ebp)當(dāng)成參數(shù)，它一定是一個(gè)很大的整數(shù)，使得活動(dòng)記錄棧溢出。 8. 教材上的中間代碼有形如x := y的復(fù)寫語句，用它就可以了。但是生成目標(biāo) 代碼時(shí)，必須考慮x和y的類型。若x和y不是簡單類型，則應(yīng)該根據(jù)它們類型 的size,產(chǎn)生一連串的值傳送指令。 9. 由于file1.c和file2.c兩個(gè)文件都包含文件 head.h,而head.h中有short int a = 10

23、. 因此該程序有兩個(gè)a的強(qiáng)符號定義。 10.按照教材上介紹的方法，函數(shù)的翻譯結(jié)果如下： void zoom (GraphicalObj / 將中心點(diǎn)移至原點(diǎn)(0, 0) obj.vptr1 (obj, zoom_factor);/ 縮放 2004年編譯原理試題 1. (20分)寫出字母表I = a, b上語言L = w | w的最后兩個(gè)字母是aa或bb 的正規(guī)式，并畫出接受該語言的最簡DFA。 2. (15分)說明下面的文法不是SLR(1)文法，并重寫一個(gè)等價(jià)的SLR(1)文法。 S M a | b M c | d c | b d a M d 3. (10分)為下面的語言寫一個(gè)無二義的文法：

24、ML語言中用分號分隔語句的語句塊，例如： (s ; s ) ; ( s ; s ; s ) ; s ) ; ( s ; s ) 4. (20分)考慮一個(gè)類Pascal的語言，其中所有的變量都是整型(不需要顯式 聲明)，并且僅包含賦值語句、讀語句、寫語句，條件語句和循環(huán)語句。下面的 產(chǎn)生式定義了該語言的語法(其中l(wèi)it表示整型常量；0P的產(chǎn)生式?jīng)]有給出，因 為它和下面討論的問題無關(guān))。 定義Stmt的兩個(gè)屬性：MayDef表示它可能定值的變量集合，MayUse表示 它可能引用的變量集合。 (1) 寫一個(gè)語法制導(dǎo)定義或翻譯方案，它計(jì)算 Stmt的MayDef和MayUse 屬性。 (2) 基于 M

25、ayDef 和 MayUse屬性，說明 Stmti;Stmt2和 Stmt2；Stmti 在什么情 況下有同樣的語義。 Program- Stmt Stmt T id := Exp Stmt T read Qd ) Stmt T write ( Exp ) Stmt T Stmt ; Stmt Stmt T if ( Exp ) then begin Stmt end elsebegin Stmt end Stmt T while ( Exp ) do begin Stmt end Exp T id Exp T lit Exp T Exp OP Exp 5. (10分)下面是一個(gè)C語言程序：

26、mai n() long i; long a04; long j; i = 4; j = 8; printf(“ d, %”，sizeof(a), a00) 雖然出現(xiàn)long a04這樣的聲明，在X86/Linux機(jī)器上該程序還是能通過編譯并 生成目標(biāo)代碼。請回答下面兩個(gè)問題： (1) sizeof(a)的值是多少，請說明理由。 (2) a00的值是多少，請說明理由。 6. (15分)考慮下面的三地址語句序列： b := 1 b := 2 if w = x goto L2 e := b goto L2 L1: goto L3 L2: c:= 3 b := 4 c := 6 L3: if y M

27、 a | b M c | d c | b d a M 、 d 因?yàn)閍是M的后繼符號之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn) -歸約 沖突。 等價(jià)的SLR文法是 S d a | b d c | d c | b d a 2. 3.SL S|SL;S S s|(SL) 4. (1) Program 一; Stmt Stmt t id := Exp Stmt.MayDef := id. nam ; Stmt.MayUse:= Exp.MayUse Stmt 一 read (id ) Stmt. MayUse :=; Stmt.MayDef := id. nam弓 Stmt write ( Exp )

28、Stmt. MayDef :=; Stmt.MayUse:= Exp.MayUse Stmt Stmt1 ; Stmt? Stmt.MayUse := Stmti.MayUse 一 Stmt2.MayUse ; Stmt.MayDef := Stmti.MayDef u Stmt2.MayDef Stmt ； if ( Exp ) then begin Stmti end elsebegin Stmt2 end Stmt.MayUse := Stmti.MayUse - Stmt2.MayUse - Exp.MayUse; Stmt.MayDef := Stmti.MayDef u StmbM

29、ayDef Stmt = while ( Exp ) do begin Stmti end Stmt.MayUse := Stmti.MayUse - Exp.MayUse; Stmt.MayDef := Stmti.MayDef Exp id Exp.MayUse := id. nam弓 Exp一； lit Exp.MayUse := Exp ； Expi OP Exp? Exp. MayUse := Expi.MayUse - Exp2.MayUse (2)Stmti.MayDef Stmt2.MayUse =and Stmt2.MayDef Stmti.MayUse =and Stmti

30、.MayDef Stmt2. MayDef = 5. (1)按照數(shù)組size的計(jì)算公式，sizeof(a)的值一定是0。 (2) a00的值是4。雖然a的size是0,但它仍然有起始地址，并且a00 的地址等于a的起始地址。由于X86/Linux機(jī)器上，活動(dòng)記錄棧向低地址方向增 長，另外由于低地址放低位字節(jié)，因此a00的地址和i的地址一致，其值和i 的值一樣，等于4。 b := 1 b := 2 if w = x goto L2 (1) e := b goto L2 (2) L1: goto L3 (3) L2: c := 3 b := 4 c := 6 (4) L3: if y A a |

31、b A c | d c | b d a A ： d 活前綴的DFA見下圖。請根據(jù)這個(gè) DFA來構(gòu)造該文法的 SLR(1)分析表，并說明該文法為 什么不是SLR(1)文法。 3. (10分)現(xiàn)有字母表Z= a ，寫一個(gè)和正規(guī)式a*等價(jià)的上下文無關(guān)文法，要求所寫的文 法既不是LR文法，也不是二義文法。 4. ( 20 分) (a) 下面的文法定義語言 L = a nbncm | m, n 1。寫一個(gè)語法制導(dǎo)定義，其語義規(guī)則的 作用是：對不屬于語言L的子集Li= a nbncn | n _ 1的句子，打印出錯(cuò)信息。 SD C D j a D b | a bCC c | c (b) 語句的文法如下：

32、S id := E | if E then S | while E do S | begin S ; S end | break 寫一個(gè)翻譯方案，其語義動(dòng)作的作用是：若發(fā)現(xiàn)break不是出現(xiàn)在循環(huán)語句中，及時(shí)報(bào)告錯(cuò) 誤。 5. ( 5分)C程序設(shè)計(jì)的教材上說，可以用兩種形式表示字符串：其一是用字符數(shù)組存放一 個(gè)字符串，另一種是用字符指針指向一個(gè)字符串。教材上同時(shí)介紹了這兩種形式的很多共同 點(diǎn)和不同點(diǎn)，但是有一種可能的區(qū)別沒有介紹。下面是一個(gè)包含這兩種形式的C程序： char c1= good!”； char*c2= good!”； mai n() c10= G printf( c仁sn ”，c

33、1); c20= G printf( c2=%sn ”，c2); 該程序在X86/Linux機(jī)器上運(yùn)行時(shí)的信息如下: c仁Good! Segme ntati on fault (core dumped) 請問，出現(xiàn) Segmentation fault的原因是什么? 6. ( 15分)下面是一個(gè) C語言程序： long f1( i ) long i; return(i*10); long f2(lo ng i) return(i*10); main () printf( “ fl = %d, f2 = %” , f1(10.0), f2(1O.0 ); 其中函數(shù)fl和f2僅形式參數(shù)的描述方式不

34、一樣。該程序在X86/Linux機(jī)器上的運(yùn)行結(jié)果如 下： fl = 0, f2 = 100 請解釋為什么用同樣的實(shí)在參數(shù)調(diào)用這兩個(gè)函數(shù)的結(jié)果不一樣。 7. ( 10分)下面是一個(gè) C語言程序和在 X86/Linux機(jī)器上編譯(未使用優(yōu)化)該程序得到 的匯編代碼(為便于理解，略去了和討論本問題無關(guān)的部分，并改動(dòng)了一個(gè)地方)。 (a) 為什么會(huì)出現(xiàn)一條指令前有多個(gè)標(biāo)號的情況，如.L2和丄4，還有丄5、丄3和.L1 ?從 控制流語句的中間代碼結(jié)構(gòu)加以解釋。 (b) 每個(gè)函數(shù)都有這樣的標(biāo)號丄1 ,它的作用是什么，為什么本函數(shù)沒有引用該標(biāo)號的地 方？ main () long i,j; if ( j )

35、 i+; else while ( i ) j+; 將老的基地址指針壓棧 將當(dāng)前棧頂指針作為基地址指針 為局部變量分配空間 main: pushl %ebp movl %esp,%ebp subl $8,%esp cmpl $0,-8(%ebp) je .L2 incl -4(%ebp) jmp 丄3 丄2: 丄4: cmpl $0,-4(%ebp) jne 丄6 jmp 丄5 丄6: incl -8(%ebp) jmp 丄4 丄5: 丄3: 丄1: leave和下一條指令一起完成恢復(fù)老的基地址指針，將棧頂 ret指針恢復(fù)到調(diào)用前參數(shù)壓棧后的位置，并返回調(diào)用者 應(yīng)怎樣翻譯？ 2005年編譯原理

36、和技術(shù)試題參考答案 1. (a)語言 ( ), ( ) ( ), ( ), ( ) ( ) ( ) ( ) ( )是正規(guī)語言，因?yàn)樵撜Z言只包括有限個(gè)句子， 它可以用正規(guī)式定義如下： ()| ( )( ) | ( ) | ()()()()() (b)我們分析正規(guī)式(;| 0) 1* )*表示的語言。可以看出正規(guī)式(;| 0) 1*描述的語言是集合 , 1, 11, 111,0, 01,011,0111,，它含長度為1的兩個(gè)串0和1。那么，(0 | 1)*所描述 的語言是(:| 0) 1* )*所描述的語言的子集，因?yàn)?0 | 1)*表示字母表0, 1上所有串的集合， . * * 因此(；I 0)

37、 1 )所描述的語言不可能再有更多的句子，因而也是表示字母表0, 1上所有串 的集合。 2 分析表如下。因?yàn)橛袃商幱幸七M(jìn)歸約沖突，所以該文法不是SLR(1)文法。 注：Fallow(A) = a, c 狀態(tài) 動(dòng)作 轉(zhuǎn)移 a b c d $ S A 0 s3 s4 1 2 1 acc 2 s5 3 s7 6 4 r5 s8, r5 5 r1 6 s9 s10, r5 8 9 10 r3 r2 r4 3 滿足條件的一個(gè)文法如下: S a S a | a | ； 4. (a)語法制導(dǎo)的定義如下: if D.le ngth = C.le ngth then print ( error ) D a b

38、D a D1 b C c C C1 c (b)翻譯方案如下： S r S.loop := falseS S ： id := E D.le ngth := 1 D.length := D 1.length + 1 C.le ngth := 1 C.length := C 1.length + 1 S if E then S1.I00P := S.loopS 1 S while E do S 1.loop := trueS 1 S begin S1 .loop := S.loopS 1 ; S2.loop := S.loopS 2 end S break if not S.loop the n p

39、rint( error ”) 5. c1是字符數(shù)組，c1= good!看成是對這個(gè)數(shù)組的元素逐個(gè)地賦值。c2是字符指針，它 所指向的good!看成是一個(gè)字符串常量，常量的值不允許修改，因此編譯器把這個(gè)字符串 常量分配在只讀數(shù)據(jù)區(qū)。 當(dāng)執(zhí)行賦值c20= G 時(shí)，試圖對只讀數(shù)據(jù)區(qū)賦值，因此報(bào)告錯(cuò)誤。 6 .歷史上，C語言中有參函數(shù)定義的一般形式是： 類型標(biāo)識符函數(shù)名(形式參數(shù)列表) 形式參數(shù)聲明 對于這種形式的聲明，C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢 查的。如本題中函數(shù) f1的聲明是這種形式。 現(xiàn)在，ANSI新標(biāo)準(zhǔn)允許使用另一種方法聲明形式參數(shù)，即在函數(shù)名后的括號中列出形

40、 式參數(shù)的同時(shí)，聲明形式參數(shù)的類型。本題中函數(shù)f2的聲明是這種形式。C語言編譯器對 于這種形式的函數(shù)聲明是要進(jìn)行實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的。 因此，在編譯函數(shù)調(diào)用f2(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成整數(shù)10,并產(chǎn)生將整數(shù)10 壓棧的指令。因此函數(shù)調(diào)用f2(10.0)的結(jié)果是100。 而在編譯函數(shù)調(diào)用f1(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成雙精度型(參見編譯原理習(xí)題 精選第5.8題),并產(chǎn)生將該雙精度型數(shù)壓棧的指令。雙精度型數(shù)占8個(gè)字節(jié)。它低地址 的4個(gè)字節(jié)看成整數(shù)時(shí)正好是0。因此函數(shù)調(diào)用f1(10.0)的結(jié)果是0 (參見 http: 上 2003 年編譯原理試題

41、第7 題)。 7. (a)條件語句和循環(huán)語句的中間代碼結(jié)構(gòu)如下： if (E) then S 1 else S2 while (E) do S E的代碼 L4: E的代碼 假轉(zhuǎn)L2 真轉(zhuǎn)L6 S1的代碼 轉(zhuǎn)L5 轉(zhuǎn)L3 L6: S的代碼 L2: S2的代碼 轉(zhuǎn)L4 L3: L5: 用這種代碼結(jié)構(gòu)，當(dāng)while語句作為條件語句的S2時(shí)，就會(huì)出現(xiàn)題目所給的這種情況。 (b)丄1標(biāo)號定義的入口是返回調(diào)用者時(shí)該執(zhí)行的指令，在函數(shù)內(nèi)部有return語句時(shí)就會(huì) 跳轉(zhuǎn)到.L1。 Stmt Stmt if ( Exp ) then begin Stmt end elsebegin Stmt end Stmt

42、while ( Exp ) do begin Stmt end Expid Exprlit ExpExp OP Exp 6、 ( 15分)賦值語句 Ax, y:= z (其中A是10 5的數(shù)組)的注釋分析樹如下圖。請根據(jù) 教材上7.3.4節(jié)的翻譯方案，把圖中的屬性值都補(bǔ)上(像圖 7.9那樣)，并且把每步歸約產(chǎn)生 的中間代碼寫在相應(yīng)產(chǎn)生式的旁邊。 L.offset := Elist .place := Elist. ndim := Elist .array := L.place := L.offset := z Elist.place :=E.place := Elist. ndim := El

43、ist.array :=L.place := L.offset := A E.place := y L.place := L .offset := x 7、( 15分)通常，函數(shù)調(diào)用的返回值是簡單類型時(shí)，用寄存器傳遞函數(shù)值。當(dāng)返回值是結(jié) 構(gòu)類型時(shí)需要采用別的方式。下面是一個(gè)C語言文件和它在 x86/Linux上經(jīng)某版本GCC編 譯器編譯生成的匯編代碼。 (備注，該匯編碼略經(jīng)修改，以便于閱讀。該修改沒有影響結(jié)果。) (a) 請你分析這些代碼，總結(jié)出函數(shù)返回值是結(jié)構(gòu)類型時(shí)，返回值的傳遞方式。 (b) 若m函數(shù)的語句 s = f(10)改成s.i = f(10).i + f(20).i + f(30

44、).i，你認(rèn)為 m函數(shù)的局部存 儲(chǔ)分配應(yīng)該怎樣修改，以適用該語句的計(jì)算。 源文件return.c的內(nèi)容如下： typedef structl ong i;S; S f(k) long k; S s; s.i =k; return s; m() S s; s.i = 20; s = f(10); 匯編文件return.s的內(nèi)容如下： .file return.c .text .globl f .type f, function f: pushl%ebp movl%esp, %ebp subl$4, %esp movl8(%ebp), %eax movl12(%ebp), %edx movl%ed

45、x, -4(%ebp) movl-4(%ebp), %edx movl%edx, (%eax) leave ret .size f, .-f .globl m .type m, function m: pushl%ebp movl%esp, %ebp subl$4, %esp movl$20, -4(%ebp) leal-4(%ebp), %eax pushl$10 pushl%eax call f addl$8, %esp leave ret .size m, .-m .section .no te.GNU-stack,progbits .ide nt GCC: (GNU) 3.3.5 (D

46、ebia n 1:3.3.5-13) int func(f) float f; int fun c(double); int fun c(float f) 9、( 5分)教材上第342頁倒數(shù)第7行說“將C+語言中一個(gè)類的所有非靜態(tài)屬性構(gòu)成一個(gè) C語言的結(jié)構(gòu)類型，取類的名字作為結(jié)構(gòu)類型的名字”。在這一章都學(xué)過后，你認(rèn)為這句話 需要修改嗎？ 2006年編譯原理和技術(shù)試題參考答案 (b)見下圖。若不允許前綴的無效 First Follow S a, b, z $ A a, b a, b, $ B a, b a, b, $ 2、開始符號集合和后繼符號集合 3、S E a b $ S S t a B S

47、 S t b A S S T Z A A t a A t b A A B B t a B B B t b E ； while E do E | A A ； id := A | T T ： T + F | F F id |(E) 4、語法制導(dǎo)的定義如下： S ； E E while E1 do E2 E id := E E E1 + E2 E id E (E1) prin t(S .lo op); E.loop := max(E 1.I0 op, E2.I0 op) +1; E.loop := E 1.lo op; E.loop := max(E 1.I0 op, E2.I0 op); E.lo

48、op := 0; E.loop := E 1.lo op; 1、(a) b*(abb*)* (a|；) 0,則去掉狀態(tài)0上的0轉(zhuǎn)換。 5、(a)計(jì)算Stmt的Def和MayUse屬性的語法制導(dǎo)定義如下： Program r Stmt Program. MayUse := Stmt. MayUse Stmt id := Exp Stmt. Def := id .name -Exp.MayUse ; Stmt.MayUse:= Exp. MayUse Stmt read (id ) Stmt. MayUse := *; Stmt. Def := Stmt write ( Exp )

49、 Stmt. Def := ; Stmt. MayUse:= Exp. MayUse Stmt Stmti ; Stmt2 Stmt.MayUse := Stmti.MayUse(Stmt2.MayUse - Stmti.Def); Stmt.Def := Stmti.Def (Stmt2.Def Stmti.MayUse) Stmt if ( Exp ) then begin Stmti end elsebegin Stmt2 end Stmt.MayUse := Stmti.MayUseStmt2.MayUseExp.MayUse; Stmt.Def := (Stmti.Def Stmt2

50、.Def) - Exp.MayUse Stmt while ( Exp ) do begin Stmti end Stmt.MayUse := Stmti.MayUseExp. MayUse; Stmt.Def := Stmti .Def - Exp. MayUse Exp id Exp. MayUse := Expt lit Exp. MayUse := Exp r Expi OP Exp2 Exp. MayUse := Exp i.MayUse Exp2.MayUse (b) Program的屬性MayUse就是程序可能未賦初值的變量集合。 6、 t3 := ti - 4

51、L.offset := t3 E.place := z ti := x - 5 ti := ti + y Elist.place := ti Elist. ndim := 2 Elist.array := A L.place := z L.offset := null Elist .place := x ，E.place := y Elist .n dim := i Elist .array := A L.place := y L.offset := null E.place := x y L.place := x L.offset := null 7、 (a)調(diào)用函數(shù)m把實(shí)在參數(shù)壓棧后，將存

52、放返回值的地址壓棧，然后調(diào)用fo f在返回前， 將結(jié)果送到 m提供的存放返回值的地址。 (b) m要為3次f調(diào)用分配存放結(jié)果值的空間，并且這3次存放結(jié)果值的空間不重疊。 在每次調(diào)用f時(shí)，將相應(yīng)的存放返回值的地址壓棧。 請指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。 3、 ( 10分)下面是C語言兩個(gè)函數(shù)f和g的概略(它們不再有其它的局部變量)： int f (int x) int i; return i +1; int g (int y) int j;f (j +1); 請按照教材上例 6.5中圖6.13的形式，畫出函數(shù) g調(diào)用f, f的函數(shù)體正在執(zhí)行時(shí)，活動(dòng)記

53、錄棧的內(nèi)容及相關(guān)信息，并按圖 6.12左側(cè)箭頭方式畫出控制鏈。假定函數(shù)返回值是通過寄 存器傳遞的。 4、( 10分)C語言函數(shù)f的定義如下： int f (int x, int py, int ppz) z ppz +=1; py +=2; x +=3; return x + py + 心 ppz; 變量a是指向b的指針，變量b是指向c的指針，c是整型變量并且當(dāng)前值是4。那么執(zhí)行 f (c, b, a)的返回值是多少？ 5、（10分）Java語言的實(shí)現(xiàn)通常把對象和數(shù)組都分配在堆上，把指向它們的指針分配在棧 上，依靠運(yùn)行時(shí)的垃圾收集器來回收堆上那些從棧不可達(dá)的空間（垃圾）。這種方式提高了 語言的

54、安全性，但是增加了運(yùn)行開銷。編譯時(shí)能否采用一些技術(shù)，以降低垃圾收集所占運(yùn)行 開銷？概述你的方案。 6、 （ 5分）在面向?qū)ο笳Z言中，編譯器給每個(gè)對象分配空間的第1個(gè)域存放虛方法表的指針。 是否可以把虛方法表指針作為最后1個(gè)域而不是第1個(gè)域？請簡要說明理由。 7、（ 15分）考慮一個(gè)簡單語言，其中所有的變量都是整型（不需要顯式聲明），并且僅包含 賦值語句、讀語句和寫語句。下面的產(chǎn)生式定義了該語言的語法（其中l(wèi)it表示整型常量； OP的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯栴}無關(guān)）。 Program =StmtList StmtList Stmt StmtList | Stmt Stmt id :=

55、 Exp; | read (id ); | write ( Exp ); Exp id | lit | Exp OP Exp 我們把不影響 write語句輸出值的賦值（包括通過read語句來賦值）稱為無用賦值，寫 一個(gè)語法指導(dǎo)定義, 它確定一個(gè)程序中出現(xiàn)過賦予無用值的變量集合 （不需要知道無用賦值 的位置）和沒有置初值的變量集合（不影響write語句輸出值的未置初值變量不在考慮之中） 非終結(jié)符StmtList和Stmt用下面3個(gè)屬性（你根據(jù)需要來定義其它文法符號的屬性） （1）usesn：在本語句表或語句入口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后 的輸出。 （2） uses_out:在本語

56、句表或語句出口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后 的輸出。 （3）useless：本語句表或語句中出現(xiàn)的無用賦值變量集合。 char p = “123” ,“ 456” ; 從編譯生成的下列匯編代碼可以看出對數(shù)組a和指針p的存儲(chǔ)分配是不同的。試依據(jù)這里的 存儲(chǔ)分配，為置了初值后的數(shù)組 a和指針p寫出類型表達(dá)式。 .file a” array.c .globl a .data .type a, object a: .size a, 8 .stri ng “123” .stri ng “ 456” 丄CO: .secti on .rodata 丄C1: .stri ng “123” .st

57、ri ng “ 456” .globl p .data .alig n 4 .type p, object .size p, 8 P： .lo ng 丄 CO .lo ng 丄 C1 .section.note.GNU- stack, ” , progbits .ident “ GCC: (GNU) 3.3.5 (Debian 1:335-13) ” 9、(10分)兩個(gè)C文件Iong.c和short.c的內(nèi)容分別是 long i = 32768 2; 和 exter n short i; mai n() pri ntf( %dn ”，i); 在X86/Linux機(jī)器上，用cc Iong.c s

58、hort.c命令編譯這兩個(gè)文件，能否得到可執(zhí)行目標(biāo)程序？ 若能得到目標(biāo)程序，運(yùn)行時(shí)是否報(bào)錯(cuò)？若不報(bào)錯(cuò)，則運(yùn)行結(jié)果輸出的值是否為65536 ?若不 等于65536,原因是什么？ 中國科學(xué)技術(shù)大學(xué) 2006 - 2007學(xué)年第二學(xué)期(A) 編譯原理和技術(shù)參考答案 1、A = 0, B = 0, 1, C = 0, 1,2, D = 0, 1,2, 3 轉(zhuǎn)換表 狀態(tài) 輸入符號 a b A B A B C B C C D D C D 再構(gòu)造SLR分析表如下: 狀態(tài) 動(dòng)作 轉(zhuǎn)移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1r 1 表中沒有多重定義的條目，因此該文法

59、是SLR(1)的。 (2)只有文法 E M E + id | id M ; 不是LR(1)文法。因?yàn)閷τ诰渥觟d+ id+id來說，分析器在面臨第一個(gè)id時(shí)需要做的空歸 約次數(shù)和句子中+ id的個(gè)數(shù)一樣多，而此時(shí)句子中+ id的個(gè)數(shù)是未知的。 3、 esp ebp 局部變量i 老ebp(控制鏈) 低地址 返回地址 參數(shù)x 局部變量j 老ebp (控制鏈) 返回地址 參數(shù)y 咼地址 4、參數(shù)傳遞使得 值和a的值一樣，指向b。 x的值和c的值一樣，都是 4; py的值和b的值一樣, 指向 c; ppz的 榊ppz +=1的執(zhí)行使得c的值為5。*py +=2的執(zhí)行使得c的值為7。x +=3的執(zhí)行使得

60、x 的值為7。這時(shí)x、“py和ppz的值都是7,因此返回值是21。 5、從兩方面考慮。 (1) 減少垃圾：用程序分析技術(shù)確定數(shù)據(jù)的生存期是否超過它的靜態(tài)作用域所對應(yīng)的 生存期，若沒有超過則將這樣的數(shù)據(jù)分配在棧上，而不必分配在堆上。 (2) 盡量靜態(tài)確定垃圾：用程序分析技術(shù)把能靜態(tài)確定的垃圾都標(biāo)注出來，可使得運(yùn) 行時(shí)對它們回收開銷很小。 6、不行。按書上目前的分配方式，若作為最后 視圖。 1個(gè)域，則難以為該對象產(chǎn)生它超類的 7、 Exp的屬性uses表示它引用的變量集合。 程序的無用賦值變量集合和未置初值變量集合。 Program 的 useless 禾口 no_initial 分另U表示 Pr