北京理工大學(xué)2012級軟件學(xué)院編譯原理期末試題A卷(2015.06)

1、課程編號： COM08010 北京理工大學(xué) 20142015 學(xué)年第二學(xué)期2012 級軟件學(xué)院編譯原理期末試題 A 卷 (2015.06)班級 學(xué)號 姓名 成績題號 一 二 三 四 五 六 七 八 總分成績* 注意：一二三七八題必須答在試卷上，四五六題答在答題紙上。一 單項(xiàng)選擇題 （在下面答題表中填上正確答案的序號） 。 （20 分）題號 1 2 3 4 5 6 7 8 9 10答案1. 下面對 LR 分析器的構(gòu)成描述正確的是 A） LR 總控程序、 LR 分析表和分析棧 B） LR 總控程序和 LR 分析表C） LR 總控程序、 LR 分析表和被分析的源程序串D） LR 總控程序、 acti

2、on 表和 goto 表2. 規(guī)范歸約的可歸約串是A ）短語 B）素短語C）最左素短語 D）句柄3. 自下而上分析的主要動作是A ）移進(jìn)歸約 B）推導(dǎo)匹配C）推導(dǎo)歸約 D）移進(jìn)匹配4. 語法分析的任務(wù)是A ）分析單詞是怎樣構(gòu)成的B）分析單詞是如何構(gòu)成語句的C）根據(jù)文法識別語法范疇并對源程序進(jìn)行語法檢查D）根據(jù)文法對源程序進(jìn)行語法檢查5. 下面文法中， 屬于 LL(1) 文法的是A) SA|B, AaA|a, B bB|b B) SA| Aa|bC) SaB|b, B Bb| D) SA|B, Aab|bc, Bbc|cd11a6. 設(shè)有文法 G(S)： S AS|bb A AB|aa 是A）

3、aa B） bb C） cc7. 自下而上語法分析中，開始分析的是A ）文法的開始符號 B）句子B ccB| 則不是句子 aaccbb直接短語的D）C）句型 D）句柄8. 下面對 NFA 和 DFA 的主要區(qū)別描述不正確的是 A） DFA 的轉(zhuǎn)換函數(shù)是單值映射C） NFA 的狀態(tài)轉(zhuǎn)換函數(shù)值是一個狀態(tài)子集B） NFA 可以包含轉(zhuǎn)換D） NFA 的狀態(tài)集合是無窮集9. 編譯程序的實(shí)現(xiàn)語言叫 A ）源語言C）宿主語言B）目標(biāo)語言D）元語言10. 下面關(guān)于逆波蘭表達(dá)式的描述不正確的是A) 逆波蘭表達(dá)式中不帶括號 B) 運(yùn)算符的出現(xiàn)順序與計(jì)算順序不一致C) 運(yùn)算符直接跟在其操作數(shù)后面 D) 用棧能夠高效

4、實(shí)現(xiàn)逆波蘭表達(dá)式的求值二填空題。 （20 分）1. 對下圖所示的 DFA ，按狀態(tài)之間的狀態(tài)等價關(guān)系進(jìn)行劃分，狀態(tài)集合 q0， q1， q2 ， q3，q4， q5劃分為【_0 b c b3aab2baaac4b b5c2. 設(shè)字母表 = a,b,c 上的語言 S= ai bj c n | 0 i j ,ni +j ，滿足 L( G)=S 的文法 G 為【 】。3. 如下為一基本塊的四元式代碼，2d2： t=t+m d4： j=t+kOP=*=*=Arg13.142At1At2Arg2bbResultabt1ct2d則該基本塊的 DAG 為【 】假設(shè)在該基本塊出口只有變量 c， d 活躍，則該

5、基本塊優(yōu)化后的四元式代碼為（每個四元式用括號包含） ：【 】d1： t=24. 右圖所示為某一程序段的流圖。根據(jù)流圖，變量 t 在 d6 點(diǎn)的du 鏈為【 】。d3： m=t+k d5： b=j+md6： t=t*m5、右圖所示為某程序的流圖，流圖首結(jié)點(diǎn)為 0，該程序段中有【 】個循環(huán)，其中入口節(jié)點(diǎn)為 0 的循環(huán)包含的節(jié)點(diǎn)為【 】102433三判斷題（在下面答題表中填上“ ”或“”）題號 1 2 3 4 5答案。 （10 分）6 7 8 9 101. 源程序編譯生成目標(biāo)程序，必須經(jīng)過詞法分析、語法分析、語義處理與中間代碼生 成、代碼優(yōu)化及目標(biāo)代碼生成 5 個階段。2. 自上而下語法分析必須實(shí)施

6、最左推導(dǎo)。3. 文法 G 是 LALR(1) 文法則一定是 LR(1)文法。4. SLR(1)與 LL(1) 中的 “ 1含”義不相同。5. 歸約與推導(dǎo)是互逆的兩個過程。6. PL/0 編譯器是單遍編譯器。7. 只有一棵語法分析樹的句子只有唯一的一個最左推導(dǎo)。8. 四元式比三元式便于做優(yōu)化。9. 局部優(yōu)化中使用的 DAG 圖反映了基本塊之間的關(guān)系。10. 類型檢查是在詞法分析階段完成的。四解答題 （10 分）設(shè)確定的有限自動機(jī) M 的狀態(tài)表表示如下：Q 0 10* 0 11* 2 12* 3 03* / 11. 給出 M 的狀態(tài)圖表示2. 給出 M 描述語言的正規(guī)式表示，要求給出求解的過程。五

7、 解答題 （10 分）4A設(shè)非確定的有限自動機(jī) M 的狀態(tài)圖表示如下：0 1A 25a637BB48將上面的 NFA M 確定化為 DFA M，使得 L(M)=L(M)，要求給出確定化的過程。六解答題設(shè)有文法 G(S)：S AB | BAAAab |B Bbc | c1. 求文法 嗎？是2. 求文法 法嗎？G(S)的 LR(0) 項(xiàng)目集規(guī)范族的初始項(xiàng)目集 SLR(1)文法嗎？為什么？G(S)的 LR(1) 項(xiàng)目集規(guī)范族的初始項(xiàng)目集（10 分）I0 ；據(jù) I0 判定文法 G(S)是 LR(0) 文法I0; 據(jù) I0 判定文法 G(S)是 LR(1) 文七 解答題 （10 分）設(shè)有文法 G(S)： S (L) |aS| a L L， S | S1. 求 FIRSTVT （L）、 FIRSTVT （S）、 LASTVT （L）；52. 填寫如下的優(yōu)先關(guān)系表：( ) a ，()a，八解答題 （10 分）設(shè)有 C 語句if(i+j10)for(m=0;mk;m+)x=k+j;if(yz)a=y;elsea=z;根據(jù) C