編譯原理試題及答案

1、歷年試題及答案一 （每項(xiàng)選擇2分，共20分）選擇題1將編譯程序分成若干個(gè)“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2構(gòu)造編譯程序應(yīng)掌握_d_。a.源程序 b.目標(biāo)語(yǔ)言c.編譯方法 d.以上三項(xiàng)都是3變量應(yīng)當(dāng)c。a.持有左值 b.持有右值c.既持有左值又持有右值 d.既不持有左值也不持有右值4編譯程序絕大多數(shù)時(shí)間花在_d_上。a.出錯(cuò)處理 b.詞法分析c.目標(biāo)代碼生成 d.管理表格5詞法分析器的輸出結(jié)果是_c_。a.單詞的種別編碼 b.單詞在符號(hào)表中的位置c.單詞的種別編碼和自身值 d.

2、單詞自身值6正規(guī)式mi和m2等價(jià)是指_c_。a. mi和m2的狀態(tài)數(shù)相等 b.ml和m2的有向弧條數(shù)相等。c.m1和m2所識(shí)別的語(yǔ)言集相等 d. ml和m2狀態(tài)數(shù)和有向弧條數(shù)相等7中間代碼生成時(shí)所依據(jù)的是c。 a語(yǔ)法規(guī)則 b詞法規(guī)則 c語(yǔ)義規(guī)則 d等價(jià)變換規(guī)則8后綴式ab+cd+/可用表達(dá)式_b_來(lái)表示。 a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d9程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為_(kāi)c_管理技術(shù)。 a.動(dòng)態(tài)存儲(chǔ) b.棧式存儲(chǔ) c.靜態(tài)存儲(chǔ) d.堆式存儲(chǔ)10.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_d_原則。 a.先請(qǐng)先放 b.先請(qǐng)后放 c

3、.后請(qǐng)先放 d.任意二（每小題10分，共80分）簡(jiǎn)答題1.畫出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。2.已知文法ge: eet+|tttf* | fff | a 試證：ff*是文法的句型，指出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄. 3為正規(guī)式(a|b) *a(a|b)構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)。4設(shè)文法g(s)： s(l)|a s|a ll，s|s (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的first和follow； (3) 構(gòu)造預(yù)測(cè)分析表。5 已知文法 a-aad| aab| 判斷該文法是否slr（1）文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。6構(gòu)造算符文法gh的算符優(yōu)

4、先關(guān)系（含）。 gh：hh;m|m md|ahb7已構(gòu)造出文法g（s）（1）s bb（2）b ab（3）b b1）。給出dfa圖2）.給出lr分析表3）假定輸入串為abaab，請(qǐng)給出lr分析過(guò)程（即狀態(tài)，符號(hào)，輸入串的變化過(guò)程）。8將下面的語(yǔ)句翻譯成四元式序列： while acba(1) a-aad(2)a- aab(3)a- (2)構(gòu)造識(shí)別活前綴的dfa follow(a)=d,b,# 對(duì)于狀態(tài)i0：follow(a)a= 對(duì)于狀態(tài)i1：follow(a)a= 因?yàn)?，在dfa中無(wú)沖突的現(xiàn)象，所以該文法是slr(1)文法。 (3)slr(1)分析表 狀態(tài) action goto a b d

5、# a 0 s2 r3 r3 r3 1 1 acc 2 s2 r3 r3 r3 3 3 s5 s4 4 r1 r1 r1 5 r2 r2 r2 (4)串a(chǎn)b#的分析過(guò)程 步驟 狀態(tài)棧 符號(hào)棧 當(dāng)前字符 剩余字符串 動(dòng)作 1 0 # a b# 移進(jìn) 2 02 #a b # 歸約a- 3 023 #aa b # 移進(jìn) 4 0235 #aab # 歸約a- aab 5 01 #a # 接受 6 【解答】 由md和ma得：firstvt(m)=d,a； 由h-h;得：firstvt(h)=； 由hm得：firstvt(m) cfirstvt(h)，即firstvt(h)=;,d,a 由md和mb得：l

6、astvt(m)=d,b； 由h-，；m得：lastvt(h)=； 由hm得：lastvt（m）clastvt(h），即lastvt(h)=;,d,b 對(duì)文法開(kāi)始符h,有#h#存在，即有=，#,也即；，#d. #, b#。 對(duì)形如pab，或paqb，有a=b，由ma|b得：a=b； 對(duì)形如par，而bfirstvt(r)，有ab。 由h；m得：；firstvt(m)，即：d，：a 由mah得：afirstvt(h)，即：a；，a;，即：；，d；，b； 由mhb得：lastvt(h)b，即：；b，db，bb 由此得到算符優(yōu)先關(guān)系表，見(jiàn)表3.5。7 【解答】（1）lr分析表如下：（2）分析表狀態(tài)

7、action goto a b # s b0 s3 s4 1 21 acc 2 s3 s4 53 s3 s4 64 r3 r3 5 r1 r1 r1 6 r2 r2 r2 (3) 句子abaab的分析過(guò)程表:句子abaab的分析過(guò)程步驟 狀態(tài) 符號(hào)棧 輸入串 所得產(chǎn)生式0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# bb3 #036 #ab aab# bab4 #02 #b aab# 5 #023 #ba ab# 6 #0233 #baa b# 7 #02334 #baab # 8 #02336 #baab # 9 #0236 #bab ad# 10

8、#025 #bb ad# 11 #01 #s d# 12 # # d# 13 識(shí)別成功 8 【解答】該語(yǔ)句的四元式序列如下（其中e1、e2和e3分別對(duì)應(yīng)：acbd, a=1和ad并且關(guān)系運(yùn)算符優(yōu)先級(jí)高）： 100 (j,a,c,102) 101(j,_,_,113） /*e1為f*/ 102 (j2，4-3 (3)求出流圖中的循環(huán): 回邊5-2對(duì)應(yīng)的循環(huán)：2、5、3、4； 回邊4-3對(duì)應(yīng)的循環(huán)：3、4編譯原理模擬試題一一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。()2在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。()3

9、甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 a-a ， a-bb, a,bvn ， a 、 bvt 。 ()5每個(gè)文法都能改寫為 ll(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()7算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()8自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。 ()9lr 法是自頂向下語(yǔ)法分析方法。 ()10簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1 一個(gè)編譯程序中，不僅包含詞法分析，_

10、，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。a( ) 語(yǔ)法分析 b( )文法分析c( )語(yǔ)言分析d( )解釋分析2 詞法分析器用于識(shí)別_。 a( ) 字符串b( )語(yǔ)句c( )單詞d( )標(biāo)識(shí)符3 語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的_。a( ) 語(yǔ)義錯(cuò)誤 b( ) 語(yǔ)法和語(yǔ)義錯(cuò)誤c( ) 錯(cuò)誤并校正 d( ) 語(yǔ)法錯(cuò)誤4 下面關(guān)于解釋程序的描述正確的是_。 (1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼 (2) 解釋程序適用于 cobol 和 fortran 語(yǔ)言 (3) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的 a( ) (1)(2) b( ) (1) c( ) (1)(2)(3) d

11、( ) (2)(3)5 解釋程序處理語(yǔ)言時(shí) , 大多數(shù)采用的是_方法。a( ) 源程序命令被逐個(gè)直接解釋執(zhí)行 b( ) 先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行c( ) 先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行 d( ) 以上方法都可以6 編譯過(guò)程中 , 語(yǔ)法分析器的任務(wù)就是_。 (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的 (3) 分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu) a( ) (2)(3) b( ) (2)(3)(4)c( ) (1)(2)(3) d( ) (1)(2)(3)(4)7 編譯程序是一種_。a. ( ) 匯編程序 b( ) 翻譯程序c

12、( ) 解釋程序 d( ) 目標(biāo)程序8 文法 g 所描述的語(yǔ)言是_的集合。 a. ( ) 文法 g 的字母表 v 中所有符號(hào)組成的符號(hào)串b( ) 文法 g 的字母表 v 的閉包 v* 中的所有符號(hào)串c( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串d. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串9 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_。a. ( ) 短語(yǔ)文法 b( ) 正則文法c( ) 上下文有關(guān)文法d( ) 上下文無(wú)關(guān)文法10 一個(gè)上下文無(wú)關(guān)文法 g 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 _。a( ) 句子 b( ) 句型c( ) 單

13、詞 d( ) 產(chǎn)生式三、填空題(每空1分，共10分)1編譯程序的工作過(guò)程一般可以劃分為詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理_和 _出錯(cuò)處理_。 2若源程序是用高級(jí)語(yǔ)言編寫的,_目標(biāo)程序_是機(jī)器語(yǔ)言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。4對(duì)編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_目標(biāo)程序_。5產(chǎn)生式是用于定義_語(yǔ)法成分_的一種書寫規(guī)則。 6語(yǔ)法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡(jiǎn)答題（20分）1. 什么是句子？ 什么是語(yǔ)言 ? 答：(1)

14、設(shè)g是一個(gè)給定的文法，s是文法的開(kāi)始符號(hào)，如果s x(其中xvt*),則稱x是文法的一個(gè)句子。 (2)設(shè)gs是給定文法，則由文法g所定義的語(yǔ)言l(g)可描述為： l(g)xs x,xvt* 。參考答案：(每個(gè)2分，共4分)答：(1)設(shè)g是一個(gè)給定的文法，s是文法的開(kāi)始符號(hào)，如果s x(其中xvt*),則稱x是文法的一個(gè)句子。 (2)設(shè)gs是給定文法，則由文法g所定義的語(yǔ)言l(g)可描述為： l(g)xs x,xvt* 。 2. 寫一文法，使其語(yǔ)言是偶正整數(shù)的集合,要求： (1)允許0打頭；(2) 不允許0打頭。解：(1)gs=(s,p,d,n,0,1,2,9,p,s) p: s-pd|d p-

15、np|n d-0|2|4|6|8 n-0|1|2|3|4|5|6|7|8|9 (2)gs=(s,p,r,d,n,q ,0,1,2,9,p,s) p: s-pd|p0|d p-nr|n r-qr|q d-2|4|6|8 n-1|2|3|4|5|6|7|8|9 q-0|1|2|3|4|5|6|7|8|9 3. 已知文法 ge 為： et|e+t|e-t tf|t*f|t/f f （ e ） |i 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？ 請(qǐng)給出該文法的終結(jié)符號(hào)集合 vt 和非終結(jié)符號(hào)集合 vn 。 找出句型 t+t*f+i 的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解： 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是e。 該文法的

16、終結(jié)符號(hào)集合vt=+、-、*、/、（、）、i。 非終結(jié)符號(hào)集合vn=e、t、f。 句型t+t*f+i的短語(yǔ)為i、t*f、第一個(gè)t、t+t*f+i; 簡(jiǎn)單短語(yǔ)為i、t*f、第一個(gè)t;句柄為第一個(gè)t。4. 構(gòu)造正規(guī)式相應(yīng)的 nfa : 1(0|1)*101 解1(0|1)*101對(duì)應(yīng)的nfa為 5. 寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示和三元式序列。逆波蘭表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)五.計(jì)算題（10分）構(gòu)造下述文法 gs 的自動(dòng)機(jī)： s-a0 a-a0|s1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。解：由于該

17、文法的產(chǎn)生式s-a0，a-a0|s1中沒(méi)有字符集vt的輸入，所以不是確定的自動(dòng)機(jī)。 要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把s?a0代入產(chǎn)生式a?s1有：a=a0|a01|0=a(0|01)|0=0(0|01)*。 代入s-a0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動(dòng)機(jī)為： 由于狀態(tài)a有3次輸入0的重復(fù)輸入，所以上圖只是nfa，下面將它確定化： 下表由子集法將nfa轉(zhuǎn)換為dfa:由上表可知dfa為：編譯原理模擬試題二一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1“ 用高級(jí)語(yǔ)言書寫的源程序都必須通過(guò)編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這

18、種說(shuō)法。( )2若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( )3一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 ()4在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 ( )5僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。 ( )6削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 ( )7在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 ( )8算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()9數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ()10編譯程序與具體的機(jī)器有關(guān),與具體的語(yǔ)言無(wú)關(guān)。 ( )二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)

19、(每個(gè)4分，共40分)1 通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括_。a( ) 模擬執(zhí)行器b( ) 解釋器 c( ) 表格處理和出錯(cuò)處理 d( ) 符號(hào)執(zhí)行器2 文法 gn= （ b ， n ， b ， n ， nbbb ， bbn ），該文法所描述的語(yǔ)言是 a( ) l(gn)=bii0 b( ) l(gn)=b2ii0 c( ) l(gn)=b2i+1i0 d( ) l(gn)=b2i+1i13 一個(gè)句型中的最左_稱為該句型的句柄。a( ) 短語(yǔ) b( ) 簡(jiǎn)單短語(yǔ) c( ) 素短語(yǔ) d( ) 終結(jié)符號(hào) 4 設(shè) g 是一個(gè)給定

20、的文法， s 是文法的開(kāi)始符號(hào)，如果 s-x( 其中 xv*), 則稱 x 是文法 g 的一個(gè)_。a( ) 候選式 b( ) 句型 c( ) 單詞 d( ) 產(chǎn)生式 5 文法 ge ： ete t tft f fa （ e ） 該文法句型 e f (e t) 的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的_。 （ e t ） e t f f (e t) a( ) 和 b( ) 和 c( ) 和 d( ) 6 若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子_。a( ) 是無(wú)窮多個(gè) b( ) 是有窮多個(gè) c( ) 是可枚舉的 d( ) 個(gè)數(shù)是常量 7 詞法分析器用于識(shí)別_。a( ) 句子 b( ) 句型 c( ) 單詞

21、d( ) 產(chǎn)生式 8 在語(yǔ)法分析處理中， first 集合、 follow 集合、 select 集合均是_。a. ( ) 非終極符集 b( ) 終極符集 c( ) 字母表 d. ( ) 狀態(tài)集 9 在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是_。 a.( ) 尋找句柄 b.( ) 尋找句型 c.( ) 消除遞歸 d.( ) 選擇候選式 10 在 lr 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型_的 dfa 狀態(tài)。 a.( )句柄 b.( ) 前綴 c.( )活前綴 d.( ) lr(0) 項(xiàng)目 三、填空題(每空1分，共10分)1設(shè)g是一個(gè)給定的文法，s是文法的開(kāi)始符號(hào)，如果s-x( 其中 xvt

22、*), 則稱 x是文法的一個(gè)_句子_。 2遞歸下降法不允許任一非終極符是直接_左_遞歸的。3自頂向下的語(yǔ)法分析方法的基本思想是：從文法的_開(kāi)始符號(hào)_開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)出文法的_句子_，使之與給定的輸入串_匹配_。 4自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接歸約_ ，力求歸約到文法的_開(kāi)始符號(hào)_。 5常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 6在使用高級(jí)語(yǔ)言編程時(shí),首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部_語(yǔ)法_錯(cuò)誤和語(yǔ)義部分錯(cuò)誤。四、簡(jiǎn)答題（20分）1. 已知文法 gs 為： sdab

23、 aaa|a bbb| gs 產(chǎn)生的語(yǔ)言是什么？ 答：gs產(chǎn)生的語(yǔ)言是l(gs)=danbmn1,m0。2. 簡(jiǎn)述 dfa 與 nfa 有何區(qū)別 ? 答：dfa與nfa的區(qū)別表現(xiàn)為兩個(gè)方面:一是nfa可以若干個(gè)開(kāi)始狀態(tài)，而dfa僅只一個(gè)開(kāi)始狀態(tài)。 另一方面，dfa的映象m是從k到k，而nfa的映象m是從k到k的子集， 即映象m將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。3. 構(gòu)造正規(guī)式相應(yīng)的 dfa : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0對(duì)應(yīng)的nfa為：4. 已知文法g(s) sa|(t) tt，s|s 寫出句子

24、(a，a)，a)的規(guī)范歸約過(guò)程及每一步的句柄。解：句型歸約規(guī)則句柄 (a，a)，a)saa (s，a)，a)tss (t，a)，a)saa (t，s)，a)tt，s t，s (s)，a) tss (t)，a) ss(t) (t) (s，a) tss (t，a) saa (t，s) tt，s t，s (t) s(t)(t) s5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？1)優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。 (2) 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五.計(jì)算題（10分） 對(duì)下面的文法 g ： e-te e-+e| t-ft t -t| f

25、- pf f- *f| p-(e)|a|b| (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 first 集和 follow 集。 (4分) (2) 證明這個(gè)方法是 ll(1) 的。(4分) (3) 構(gòu)造它的預(yù)測(cè)分析表。(2分) 解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的first集和follow集。 first集合有： first(e)=first(t)=first(f)=first(p)=(,a,b,; first(e)=+, first(t)=first(f)=first(p)=(,a,b,; first(t)=first(t)=(,a,b,; first(f)=first(p)=(,a,b,; fir

26、st(f)=first(p)=*,; first(p)=(,a,b,; follow集合有： follow(e)=),#; follow(e)=follow(e)=),#; follow(t)=first(e)follow(e)=+,),#;/不包含 follow(t)=follow(t)=first(e)follow(e)=+,),#; follow(f)=first(t)follow(t)=(,a,b,+,),#;/不包含 follow(f)=follow(f)=first(t)follow(t)=(,a,b,+,),#; follow(p)=first(f)follow(f)=*,(,a

27、,b,+,),#;/不包含 (2)證明這個(gè)方法是ll(1)的。 各產(chǎn)生式的select集合有： select(e-te)=first(t)=(,a,b,; select(e-+e)=+; select(e-)=follow(e/)=),# select(t-ft)=first(f)=(,a,b,; select(t-t)=first(t)=(,a,b,; select(t-)=follow(t/)=+,),#; select(f-pf)=first(p)=(,a,b,; select(f-*f)=*; select(f-)=follow(f)=(,a,b,+,),#; select(p-(e)

28、=( select(p-a)=a select(p-b)=b select(p-)= 可見(jiàn)，相同左部產(chǎn)生式的select集的交集均為空，所以文法ge是ll(1)文法。 (3)構(gòu)造它的預(yù)測(cè)分析表。 文法ge的預(yù)測(cè)分析表如下： 編譯原理模擬試題三一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1對(duì)于數(shù)據(jù)空間的存貯分配，fortran采用動(dòng)態(tài)貯存分配策略。()2甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。( )3遞歸下降分析法是自頂向上分析方法。( )4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ()5lr 法是自頂向下語(yǔ)法分析方法。 ( )6

29、在 slr （ 1 ）分析法的名稱中，s的含義是簡(jiǎn)單的。()7綜合屬性是用于 “ 自上而下 ” 傳遞信息。( )8符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 ()9程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。 ()10解釋程序適用于 cobol 和 fortran 語(yǔ)言。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1 文法 g 產(chǎn)生的_的全體是該文法描述的語(yǔ)言。a( ) 句型 b( ) 終結(jié)符集 c( ) 非終結(jié)符集 d( ) 句子2 若文法 g 定義的語(yǔ)言是無(wú)限集，則文法必然是 _。 a(

30、 ) 遞歸的 b( ) 前后文無(wú)關(guān)的 c( ) 二義性的 d( ) 無(wú)二義性的3 四種形式語(yǔ)言文法中，1型文法又稱為 _文法。a( ) 短語(yǔ)結(jié)構(gòu)文法 b( ) 前后文無(wú)關(guān)文法 c( ) 前后文有關(guān)文法 d( ) 正規(guī)文法 4 一個(gè)文法所描述的語(yǔ)言是_。a( ) 唯一的 b( ) 不唯一的 c( ) 可能唯一，好可能不唯一 d( ) 都不對(duì)5 _和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。a( ) 語(yǔ)法分析b( ) 中間代碼生成 c( ) 詞法分析 d( ) 目標(biāo)代碼生成 6_是兩類程序語(yǔ)言處理程序。 a( ) 高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序 b( ) 解釋程序和編譯程序 c( ) 編譯程序和操作系統(tǒng)

31、d( ) 系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_的信息。a. ( ) 維數(shù) b( ) 類型 c( ) 維上下界 d( ) 各維的界差 8. 一個(gè)上下文無(wú)關(guān)文法 g 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 _。 a( ) 句子 b( ) 句型c( ) 單詞 d( ) 產(chǎn)生式9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_。a. ( ) 短語(yǔ)文法 b( ) 正則文法 c( ) 上下文有關(guān)文法d( ) 上下文無(wú)關(guān)文法10文法 g 所描述的語(yǔ)言是_的集合。 a. ( ) 文法 g 的字母表 v 中所有符號(hào)組成的符號(hào)串b( )

32、文法 g 的字母表 v 的閉包 v* 中的所有符號(hào)串c( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串d. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串三、填空題(每空1分，共10分)1一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的_句柄_。 2對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語(yǔ)義規(guī)則_ 。3一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語(yǔ)法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。4 從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)執(zhí)行性_語(yǔ)句和_說(shuō)明性_語(yǔ)句兩大類。5 掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。 6 產(chǎn)生式是用于定義_語(yǔ)法

33、范疇_的一種書寫規(guī)則。 四、簡(jiǎn)答題（20分）1. 寫一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。解：文法g(n)： nab|b aac|d b1|3|5|7|9 db|2|4|6|8 c0|d2. 設(shè)文法g(s)： s(l)|a s|a ll，s|s (1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的first和follow。解：(1) s(l)|as ss| lsl lsl| (2) first)s)(，afollow(s)#，) first(s)，a,follow(s)#，) first(l)(，afollow(l) ) first(l)，follow(l )3. 已知文法g(e)

34、 et|et tf|t *f f(e)|i (1)給出句型(t *fi)的最右推導(dǎo)； (2)給出句型(t *fi)的短語(yǔ)、素短語(yǔ)。解：(1) 最右推導(dǎo)： e-t-f-(e)-(et)-(ef)-(ei) -(ti)-(t*fi) (2) 短語(yǔ)：(t*fi)，t*fi，t*f，i 素短語(yǔ)：t*f,i 4. whilea0 b0do begin x：x1； if a0 then a：a1 else b：b1 end； 翻譯成四元式序列。解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，1，t1) (6) (：，t1，) (7) (j

35、，a，0，9) (8) (j，12) (9) (，a，1，t2) (10) (：，t2，a) (11) (j，1) (12) (，b，1， t3) (13) (：，t3，b) (14) (j，1) (15)五.計(jì)算題（10分）已知 nfa= （ x,y,z,0,1,m,x,z ），其中：m(x,0)=z,m(y,0)=x,y,m(z,0)=x,z,m(x,1)=x, m(y,1)= ,m(z,1)=y, 構(gòu)造相應(yīng)的dfa并最小化。 解：根據(jù)題意有nfa圖: 下表由子集法將nfa轉(zhuǎn)換為dfa： 下面將該dfa最小化： (1) 首先將它的狀態(tài)集分成兩個(gè)子集：p1=a,d,e,p2=b,c,f (2

36、) 區(qū)分p2:由于f(f,1)=f(c,1)=e,f(f,0)=f并且f(c,0)=c,所以f，c等價(jià)。由于f(b,0)=f(c,0)=c, f(b,1)=d,f(c,1)=e,而d，e不等價(jià)（見(jiàn)下步），從而b與c，f可以區(qū)分。有p21=c,f,p22=b。 (3) 區(qū)分p1:由于a，e輸入0到終態(tài)，而d輸入0不到終態(tài)，所以d與a，e可以區(qū)分，有p11=a,e,p12=d。 (4) 由于f(a,0)=b,f(e,0)=f,而b，f不等價(jià)，所以a，e可以區(qū)分。 (5) 綜上所述，dfa可以區(qū)分為p=a，b，d，e，c，f。所以最小化的dfa如下： 編譯原理模擬試題四一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1一個(gè) ll(l)文法一定是無(wú)二義的。 ( )2正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( )3一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。 ()4目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )5逆波蘭法表示的表達(dá)式亦稱前綴式 。 ( )6如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。 ( )7lr 法是自頂向下語(yǔ)法分析方法。 ( )8