武漢理工編譯原理復(fù)習(xí)題目很全哦.doc

《武漢理工編譯原理復(fù)習(xí)題目很全哦.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《武漢理工編譯原理復(fù)習(xí)題目很全哦.doc（13頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 一.名詞解釋： 1)前綴 答：前綴——是指符號(hào)串任意首部。 2)可歸前綴 答：可歸前綴——是指規(guī)范句型的一個(gè)前綴，這種前綴包含句柄且不含句柄之后的任何符號(hào)。 3)活前綴 答：活前綴——規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。 或給定文法規(guī)范句型的可歸前綴的任意首部。 4)簡(jiǎn)單短語 答：簡(jiǎn)單短語——設(shè)G[Z]是給定文法,w=xuy∈V+，為該文法的句型,如果滿足下面兩個(gè)條件: ① Z xUy； ② Uu； 則稱句型xuy 中的子串u是句型xuy的簡(jiǎn)單短語。 5)掃描遍 答：掃描遍——指編譯程

2、序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。 6)句柄 答：句柄——給定句型中的最左簡(jiǎn)單短語就是句柄。 7)句型 答：句型——設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Sx(其中x∈V*),則稱x是文法的一個(gè)句型。 * 8)句子 答：句子——設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S x（其中x∈VT*），則稱x是文法的一個(gè)句子。 9)非終結(jié)符 答：非終結(jié)符——出現(xiàn)在文法產(chǎn)生式的左部且能派生出符號(hào)或符號(hào)串的那些符號(hào)稱為非終結(jié)符號(hào)。 10)終結(jié)符 答：終結(jié)符——出現(xiàn)在文法產(chǎn)生式的右部且不能派生出符號(hào)或符號(hào)串的那些符號(hào)稱為終結(jié)符號(hào)。 11）屬性文法 答：一

3、個(gè)屬性文法形式的定義為一個(gè)三元組AG，AG=（G，V，E）。 其中G為一個(gè)上下文無關(guān)文法；V為屬性的有窮集；E為一組語義規(guī)則。 12）語法制導(dǎo)翻譯 答：語法制導(dǎo)翻譯——語法制導(dǎo)翻譯就是在語法分析的過程中，當(dāng)進(jìn)行推導(dǎo)或歸約時(shí)同步完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語義處理。 或：為文法中每個(gè)產(chǎn)生式配上一組語義規(guī)則，并且在語法分析過程中，隨著分析的步步進(jìn)展，當(dāng)進(jìn)行推導(dǎo)或歸約時(shí)同步完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動(dòng)作，從而進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。 13）后綴式 答：后綴式——一種把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）的表示法。

4、 14）短語 答：短語——設(shè)G[Z]是給定文法,w=xuy∈V+，為該文法的句型,如果滿足下面兩個(gè)條件: ① Z xUy； ② U u； 則稱句型xuy 中的子串u是句型xuy的短語。 或：句型語法樹的全部子樹的葉從左到右排列起來構(gòu)成的符號(hào)串均是句型的短語。 15）基本塊 答：基本塊——源程序或者中間代碼程序中只有一個(gè)入口和一個(gè)出口的順序執(zhí)行的代碼段。 16）語義規(guī)則 答：對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。 17）語法分析 答：語法分析——按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。

5、 18）四元式 答：四元式——是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為操作符域、左運(yùn)算對(duì)象域、右運(yùn)算對(duì)象域及運(yùn)算結(jié)果域。 二．簡(jiǎn)答題： 1) 什么是句子？ 什么是語言? * 解答：句子——設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S x（其中x∈VT*），則稱x是文法的一個(gè)句子。 語言——語言是句子的集合。 或——設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)＝{x│Sx,x∈VT*} 。 2) DFA與NFA有何區(qū)別 ? 解答:DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以有若干個(gè)開始狀態(tài)，而DFA僅只有一個(gè)開始狀態(tài)。另一方

6、面，DFA的映象M是從K∑到K，而NFA的映象M是從K∑到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。 3) 自頂向下的語法分析方法的基本思想是什么? 解答:從文法的開始符號(hào)開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。 4) 自底向上的語法分析方法的基本思想是什么? 解答:從給定的輸入串（終結(jié)符串）開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開始符號(hào)。 5) 一個(gè)上下文無關(guān)文法G包括哪四個(gè)組成部分？ 解答:一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組產(chǎn)生式。

7、6) 在自底向上的語法分析方法中，分析的關(guān)鍵是什么？ 解答:關(guān)鍵是尋找句柄。 7) 在自頂向下的語法分析方法中，分析的關(guān)鍵是什么？ 解答:關(guān)鍵是選擇候選式。 8) 編譯程序中語法分析器接收以什么為單位的輸入？ 解答: 接收以單詞為單位的輸入。 9) 若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子是可枚舉的嗎？ 解答: 它所產(chǎn)生的語言的句子不是可枚舉的，而是無窮多個(gè)。 10) 編譯程序生成的目標(biāo)程序是不是一定是機(jī)器語言的程序？ 解答:不一定是機(jī)器語言的程序。 11) 詞法分析器是用于做什么的？ 解答:詞法分析器是用于識(shí)別單詞的。 12) “用高級(jí)語言書寫的源程序都必須通過編譯

8、,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法正確嗎？ 解答: 不正確。 13) 把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由什么完成的？ 程序代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū) 棧區(qū) 堆區(qū) 解答: 由匯編器（匯編程序）完成的。 14)圖示運(yùn)行時(shí)存儲(chǔ)空間的劃分（分為哪幾個(gè)區(qū)）。 解答: 一般分為靜態(tài)區(qū)和動(dòng)態(tài)區(qū)： 程序代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū) 15)詞法分析的主要任務(wù)是什么？ 解答:詞法分析器的任務(wù)是對(duì)構(gòu)成源程序的字符串從左到右逐個(gè)字符逐個(gè)字符地進(jìn)行掃描，依次把它們識(shí)別為一個(gè)一個(gè)具有獨(dú)立意義的單詞，并確定其屬性，再轉(zhuǎn)換為長(zhǎng)度統(tǒng)一的屬性

9、字并輸出。 16)常用的中間語言種類有哪幾種？ 解答: 常用的中間語言種類有逆波蘭表示、三元式、四元式和樹形表示。 17）文法G所描述的語言是什么的集合？ 解答:是由文法的開始符號(hào)推出的所有終結(jié)符串的集合?；蛘f是句子的集合。 18）喬姆斯基把文法分為四種類型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文無關(guān)文法。 19）編譯程序是一種解釋程序嗎？還是什么程序？ 解答:編譯程序是一種翻譯程序。 20）按邏輯上劃分，編譯程序第二步工作是什么？ 解答: 編譯程序第二步工作是語法分析。 21）源程序是用高級(jí)語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編語言程

10、序 ，則其翻譯程序稱為什么？ 解答: 其翻譯程序稱為編譯程序。 22）編譯方式與解釋方式的根本區(qū)別為什么？ 解答:編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。 23）常見的動(dòng)態(tài)存貯分配策略有哪兩種？ 解答:常見的兩種動(dòng)態(tài)存貯分配策略是棧式動(dòng)態(tài)分配策略和堆式動(dòng)態(tài)分配策略。 24）常用的參數(shù)傳遞方式有哪三種？ 解答:常見的參數(shù)傳遞方式有傳地址、傳值和傳名三種方式。 25）語法分析的任務(wù)是什么？ 解答:語法分析的任務(wù)是識(shí)別給定的終結(jié)符串是否為給定文法的句子。 26）局部?jī)?yōu)化是局限于一個(gè)什么范圍內(nèi)的一種優(yōu)化？ 解答: 是局限于一個(gè)基本塊范圍內(nèi)的一種優(yōu)化。 27）文法等價(jià)的

11、定義是什么？ 解答: 設(shè)G1和G2是給定的文法，如果有L（G1）= L（G2），則稱G1與G2等價(jià)。 28）在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是什么集合？ 解答: 均是終結(jié)符集。 29）通常一個(gè)編譯程序中應(yīng)包括哪七個(gè)部分？ 解答: 通常一個(gè)編譯程序中應(yīng)包含詞法分析，語法分析，語義分析與中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成以及表格處理和出錯(cuò)處理等七個(gè)部分。 32）如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為哪三個(gè)階段？ 解答: 源程序的執(zhí)行分為三個(gè)階段: 編譯階段，匯編階段和運(yùn)行階段。 33）翻譯程序是這樣一種程序，它能夠?qū)⒂檬?/p>

12、么轉(zhuǎn)換成與其等價(jià)的用乙語言書寫的程序？ 解答:能夠?qū)⒂眉渍Z言書寫的程序轉(zhuǎn)換成與其等價(jià)的用乙語言書寫的程序。 34）說明下面文法G[S]是二義性文法：S→SaS|SbS|cSd|eS|f 解答:fafbf是文法G[S]的一個(gè)句子，并且有兩個(gè)不同的最右推導(dǎo)。 （1）S => SaS => SaSbS => SaSbf=> Safbf=> fafbf （2）S => SbS => Sbf=> SaSbf => Safbf=> fafbf 因此說明此文法有二義性。 35）在屬性文法中，綜合屬性與繼承屬性是如何傳遞信息的？ 解答: 綜合屬性用于自下而上傳遞信息，繼承屬性用于自上而

13、下傳遞信息。 36）代碼優(yōu)化的主要目標(biāo)是什么？ 解答: 代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運(yùn)行速度和如何減少目標(biāo)程序運(yùn)行時(shí)所需的空間。 37）寫一個(gè)文法，使其語言是無符號(hào)二進(jìn)制實(shí)數(shù)（不含指數(shù)）。 解答:文法G(N)： 　　　　　 　N→L.L|L 　　　　　 　L→LB|B 　　　　　 　B→0|1 三．應(yīng)用題 1）消除下列文法G[A]的左遞歸。 E→E-T∣T T→T/F∣F F→( E )∣i 解答：消除文法G[E]的左遞歸后得到： E→TE′ E’→-T E′∣ε T→FT′ T’→/FT′∣ε F→( E )∣i 2） 消除下列文法G[A]

14、的左遞歸。 A→AaB∣B B→BbC∣C C→eD∣D D→(A)∣d 解答：消除文法G[A]的左遞歸后得到： A →BAˊ Aˊ→aBAˊ∣ε B →CBˊ Bˊ→bcBˊ∣ε C→eD∣D D→(A)∣d 3）給定下列自動(dòng)機(jī)： 其中：開始狀態(tài)：0 終止?fàn)顟B(tài)：2 a a a 0 b b b 1 2 把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)DFA。 a b 0 01 2 01 01 2 －2 1 2 1

15、 2 a b 0 0,1 2 1 2 －2 1 2 解答： 有狀態(tài)矩陣如圖： - 0 2 a a b a 1 01 b b b 0 2 b a b b 1 極小化后： a 從而可得DFA如圖： 4）正規(guī)式（a|b）*a(a|b) 構(gòu)造一個(gè)等價(jià)的有限自動(dòng)機(jī)。 解答： a,b a a b 0 1 2 四．設(shè)計(jì)題 （1）給定文法G[S′] 及相應(yīng)翻譯方案為： 1

16、．S→S {print:“a”} 2．S→r D {print:“b”} 3．D→D，i {print:“c”} 4．D→i {print:“d”} a. 按chomsky分類法，文法G屬于哪一型文法？ b. 符號(hào)串ri,i,i是不是該文法的一個(gè)句型，請(qǐng)證實(shí)。 c. 若是句型，寫出該句型的所有短語、簡(jiǎn)單短語，以及句柄。 d. 構(gòu)造識(shí)別該文法的活前綴的DFA。 e. 判斷該文法是LR（0）還是SLR（1），并構(gòu)造其相應(yīng)的語法分析表。 f. 對(duì)于ri,i,i這個(gè)輸入符號(hào)串，經(jīng)該翻譯方案翻譯后

17、的輸出是什么？ 解答： a．文法G屬于2型(上下文無關(guān))文法。 b．符號(hào)串r i,i,i是該文法的一個(gè)句型。 證：SSrDrD，i rD，i，i r i，i，i，得證。 或證：構(gòu)造語法樹見圖4，可知符號(hào)串r i,i,i是該文法的一個(gè)句型。 c．句型r i,i,i的短語有：①r i,i,i；② i,i,i；③i,i；④ 第一個(gè)i 簡(jiǎn)單短語有：第一個(gè)i 句柄有：第一個(gè)i d．求得文法G的識(shí)別全部活前綴的DFA見圖3： I1: S→S. I0: S′→.S S→.rD I2: S→r.D D→.D，i D→.i

18、r I4: S→rD. D→D.，i D ， S I5: D→D，.i I3: D→i. i i I6: D→D，i. 圖3 識(shí)別全部活前綴的DFA e．∵在項(xiàng)目集I4中存在沖突項(xiàng)目，∴文法G不是LR（0）文法。 FOLLOW(S)={#} FOLLOW(S)={#} FOLLOW(D)={ ，,#} 而由于{ ，}∩FOLLOW(S)={ ，}∩{#}=Φ，所以文法G是SLR（1）文法。 S r S D D i ， i D i ， 圖4 句子的語法樹 求得文法G的SLR（1）

19、分析表見表1： ACTION GOTO r ， i # S D 0 S2 1 1 acc 2 S3 4 3 R4 R4 4 S5 R2 5 S6 6 R3 R3 表1 SLR（1）分析表 f．可以先求得該句子的語法樹（見圖4），然后通過剪枝的方式進(jìn)行歸約， 最后歸約到文法的開始符號(hào)，在歸約的過程中同步產(chǎn)生輸出符號(hào)串dccba。 即對(duì)于r i,i,i這個(gè)輸入符號(hào)

20、串，該翻譯方案的輸出是：dccba （2）給定文法: （1）S→bTc （2）S→a （3）T→R （4）R→R/S （5）R→S a)符號(hào)串ba/ac是不是該文法的一個(gè)句子，請(qǐng)證實(shí)。 b)若是句子，寫出該句子的所有短語、簡(jiǎn)單短語和句柄。 c)為該文法設(shè)計(jì)翻譯方案，使句型bR/bTc/bSc/ac經(jīng)該翻譯方案翻譯后,輸出下列串： S b c R R S / a S T a 0342031320 解答： a) 符號(hào)串ba/ac是該文法的一個(gè)句子。 ∵SbTcbRcbR/ScbS/Scba/Scba/ac， ∴得證。 或：給出符

21、號(hào)串ba/ac的語法樹如右圖，則判定 符號(hào)串ba/ac是該文法的一個(gè)句子。 b)給出句型ba/ac的語法樹如右圖： 則可求得句型adbb的短語有：ba/ac,a/a,第1個(gè)a, 第2個(gè)a 簡(jiǎn)單短語有：第1個(gè)a, 第2個(gè)a 句柄有：第1個(gè)a c)給出句型bR/bTc/bSc/ac的語法樹如右圖： S b c R R S / S a R R S R S b c T / / T b c T 按照歸約過程，則給定文法的相應(yīng)翻譯方案為： （1）

22、S→bTc {print(“0”)} （2）S→a {print(“1”)} （3）T→R {print(“2”)} （4）R→R/S {print(“3”)} （5）R→S {print(“4”)} （3）設(shè)有基本塊： t1:=3*A t2:=2*C t3:=t1+t2 t4:=t3+5 t5:=2*C t6:=3*A t7:=t6+t5 E:=t7-1 F:=t4-E a)畫出DAG圖； b)假設(shè)基本塊出口時(shí)只有E，F(xiàn)還被引用，請(qǐng)寫出優(yōu)化后的三地址代碼序列。 5 － + *

23、+ * － t4 t1,t6 2 A 3 n11 n2 n3 n5 n6 n8 E n7 F 1 n4 t2,t5 t3,t7 n9 C n10 n11 n12 解答： a)構(gòu)造DAG：見右圖。 b)優(yōu)化后的三地址代碼序列為： t1:=3*A t2:=2*C t3:=t1+t2 t4:=t3+5 E:=t3-1 F:=t4-E 五．轉(zhuǎn)換題： 給定下列中綴式 (運(yùn)算符優(yōu)先級(jí)按常規(guī)理解) ，分別寫出等價(jià)的逆波蘭式和四元式。 1）a≤b∧a＞0∨b＜0 解答：逆波蘭式為：ab≤a

24、0＞∧b0＜∨ 寫出等價(jià)的四元式表示 1. (≤,a ,b ,T1) 2. (＞,a ,0 ,T2) 3. (∧,T1,T2,T3) 4. (＜,b ,0 ,T4) 5. (∨,T3,T4,T5) ― 2）―a＋b≤0∨a＜0∧(a―b)>2 解答：逆波蘭式為：a―b＋0≤a0＜ab―2＞∧∨； ― 四元式為：1.( ,a, ,T1) 2.( ＋,T1,b ,T2) 3.( ≤,T2,0 ,T3) 4.( ＜,a ,0 ,T4)

25、5.( ―,a ,b ,T5) 6.( ＞,T5,2 ,T6) 7.( ∧,T4,T6,T7) 8.( ∨,T3,T7,T8) 　　5、關(guān)于堅(jiān)持的名言， 你既然期望輝煌偉大的一生，那么就應(yīng)該從今天起，以毫不動(dòng)搖的決心和堅(jiān)定不移的信念，憑自己的智慧和毅力，去創(chuàng)造你和人類的快樂?！? 　　6、最可怕的敵人，就是沒有堅(jiān)強(qiáng)的信念。——羅曼羅蘭 　　7、只要持續(xù)地努力，不懈地奮斗，就沒有征服不了的東西?！麅?nèi)加 　　8、無論是美女的歌聲，還是鬢狗的狂吠，無論是鱷魚的眼淚，還是惡狼的嚎

26、叫，都不會(huì)使我動(dòng)搖?！∑章? 　　9、書不記，熟讀可記；義不精，細(xì)思可精；惟有志不立，直是無著力處?！祆? 　　10、既然我已經(jīng)踏上這條道路，那么，任何東西都不應(yīng)妨礙我沿著這條路走下去?！档? 　　11、堅(jiān)強(qiáng)的信念能贏得強(qiáng)者的心，并使他們變得更堅(jiān)強(qiáng)?！渍芴? 　　12、三軍可奪帥也，匹夫不可奪志也。——佚名 　　13、立志不堅(jiān)，終不濟(jì)事。——朱熹 　　14、富貴不能淫，貧賤不能移，威武不能屈。——孟子 　　15、關(guān)于堅(jiān)持的名言，意志目標(biāo)不在自然中存在，而在生命中蘊(yùn)藏?！湔咝÷穼?shí)篤 　　關(guān)于堅(jiān)持不懈的50條勵(lì)志名人名言 　　16、意志若是屈從，不論程度如何，它都幫助

27、了暴力。——但丁 　　17、只要有堅(jiān)強(qiáng)的意志力，就自然而然地會(huì)有能耐、機(jī)靈和知識(shí)?！铀纪滓蛩够? 　　18、功崇惟志，業(yè)廣惟勤?！? 　　19、能夠巋然不動(dòng)，堅(jiān)持正見，度過難關(guān)的人是不多的?！旯? 　　20、立志用功如種樹然，方其根芽，猶未有干；及其有干，尚未有枝；枝而后葉，葉而后花?！跏厝? 　　21、誰有歷經(jīng)千辛萬苦的意志，誰就能達(dá)到任何目的。——米南德 　　22、不作什么決定的意志不是現(xiàn)實(shí)的意志；無性格的人從來不做出決定。——黑格爾 　　23、執(zhí)著追求并從中得到最大快樂的人，才是成功者?！罅_ 　　24、有了堅(jiān)定的意志，就等于給雙腳添了一對(duì)翅膀?！獑特惱? 　　25、有百折不撓的信念的所支持的人的意志，比那些似乎是無敵的物質(zhì)力量有更強(qiáng)大的威力。——愛因斯坦