2014-2015學(xué)年1學(xué)期12級(jí)《編譯原理》期末考試試題(A卷)

1、北京郵電大學(xué)世紀(jì)學(xué)院20142015學(xué)年第1學(xué)期期末考試試題（a卷）考試科目編譯原理姓名考試專業(yè)/班級(jí)軟工專業(yè)/12級(jí)1-3班學(xué)號(hào)考試形式閉卷考試時(shí)間120分鐘考 試 注息 事 項(xiàng)一、學(xué)生參加考試須帶學(xué)生證，術(shù)帶學(xué)生證者不允許參加考試。學(xué)生必須按照監(jiān)考教師指定座位就坐。二、書本、參考資料、書包等與考試無關(guān)的東西一律放到監(jiān)考教師指定的位置。三、學(xué)生不得另行攜帶、 使用稿紙，要遵守北京郵酎大學(xué)世紀(jì)學(xué)院考場(chǎng)規(guī)則 ，有考場(chǎng)違紀(jì)或作弊行為者，按相應(yīng)規(guī)定嚴(yán)肅處理。四、學(xué)生不允許攜帶手機(jī)進(jìn)入考場(chǎng)。注意：所有答案一律寫在答題紙上，寫在試卷上無效。一、單項(xiàng)選擇題（共15小題，每小題2分，共30分）1. 一個(gè)上下

2、文無關(guān)文法g包括四個(gè)組成部分：一組終結(jié)符，一組非終結(jié)符, 一個(gè)開始符號(hào)，以及一組（）。a.字符串b.產(chǎn)生式c.開始符號(hào)d.文法2. 一個(gè)句型中稱為句柄的是該句型的最左（）a.非終結(jié)符號(hào)b.短語(yǔ)c.句子d.直接短語(yǔ)3 .自動(dòng)機(jī)識(shí)別的語(yǔ)言是（）a. 0型語(yǔ)言b. 1型語(yǔ)言c. 2型語(yǔ)言d. 3型語(yǔ)言4 .編譯程序各階段工作都涉及（）a. 詞法分析b.表格管理c.語(yǔ)法分析d.語(yǔ)義分析5代碼生成階段的主要任務(wù)是 （）a 把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言b.把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言c 把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼d 把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言6作為編譯程序的源語(yǔ)言，不能是（ ）a. 高級(jí)語(yǔ)言b.c 語(yǔ)言

3、c.低級(jí)語(yǔ)言d.pascal 語(yǔ)言7詞法分析器的輸入是（）a. 單詞符號(hào)串b.源程序c.語(yǔ)法單位d. 目標(biāo)程序8.給定文法a-ba | cc,下面符號(hào)用中不是該文法的句子的是（）cc bcbc bcbcc bccbcc bbbcca.b. c. d. 9.若b是非終結(jié)符，則a-a.abb為（）項(xiàng)目a.移進(jìn)b.待約c.接受d 規(guī)約10文法 g：sf b|a|(t)t- t,s|s 則 firstvt(t)結(jié)果是()。a. b, a ,(b. b, a ,)c.b,a,j d.b, a,), 11 常用的中間代碼形式不含( )a 三元式b.四元式c 逆波蘭式d 語(yǔ)法樹12.正規(guī)式 m 1 和 m

4、2 等價(jià)是指( ) 。a m1 和 m2 的狀態(tài)數(shù)相等b m1 和 m2 的有向邊條數(shù)相等c m1 和 m2 所識(shí)別的語(yǔ)言集相等d m1 和 m2 狀態(tài)數(shù)和有向邊條數(shù)相等13.文法g: s-xsx|y所識(shí)別的語(yǔ)言是()。a xyxb (xyx)*c. xnyxn (n0)d x*yx*14.如果文法g是無二義的，則它的任何句子a ()。a 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同c 最左推導(dǎo)和最右推導(dǎo)必定相同d 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同15詞法分析器的輸出結(jié)果是( ) 。a. 單詞的種別編碼b.單詞在符號(hào)表中的位置c.單詞的種別

5、編碼和自身值d.單詞自身值二、填空題（本大題共10 空，每空 2 分，共 20 分）1對(duì)于文法ge ：e-t|e+tt-f|t*fffpaf|pp-（e）|i,句型 t+t*f+i 的句柄是 ，最左素短語(yǔ)是。2編譯器常用的語(yǔ)法分析方法有和兩種。3算符優(yōu)先分析法每次都是對(duì) 進(jìn)行歸約。4 編譯程序的工作過程主要分為如下幾個(gè)階段：詞法分析、語(yǔ)法分析、 、 、目標(biāo)代碼生成。5 .假設(shè)有文法gs: s-sa對(duì)該文法消除左遞歸后得到的文法為（注：新 的符號(hào)用s表示）。6 .對(duì)于文法g,僅含終結(jié)符號(hào)的句型稱為 。三、簡(jiǎn)答題（共6題，每題 5 分，共 30分）1 .已知文法gz: z-azb |ab,寫出l

6、（g （z）的全部元素。2 .已知文法 gs為s - asb|sb|b,試證明文法 gs為二義文法。3設(shè)有文法e- e+t | tt-t*f | f一 （e） i i求下列表達(dá)式的最左推導(dǎo)和語(yǔ)法樹 1） 1） 3+4*5+6 2） 3* （4+5）4.將如下正規(guī)文法轉(zhuǎn)換為自動(dòng)機(jī)。s-0a|1ba -1s|1b-0s|05已知文法gs ：s-a i （t）tftbs | s（1）寫出句型（tbs）ba）的語(yǔ)法樹（ 2）寫出該句型短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)6.有文法gs ：0） s -bb1） b -ab|b構(gòu)造此文法的 lr（ 0）項(xiàng)目集規(guī)范簇，并寫出識(shí)別活前綴的dfa四、綜合應(yīng)用（共2 題，共 20 分）1 構(gòu)造下列正規(guī)式 1（0i1）*101 相應(yīng)的 dfa（ 1）由正規(guī)表達(dá)式構(gòu)造nfa（ 2）由轉(zhuǎn)換系統(tǒng)nfa 構(gòu)造確定的有窮自動(dòng)機(jī)dfa（ 3） dfa 的最小化2已知文法gs ：0）