山東科技大學(xué)《編譯原理》期末考試試題(A卷)

1、山東科技大學(xué) 20152016學(xué)年第二學(xué)期A 班級(jí)題號(hào)得分姓名學(xué)號(hào)總得審核分一、單項(xiàng)選擇題(共15 小題，每小題 2 分，共30 分)1. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分：一組終結(jié)符，一組非終結(jié)符，一個(gè)開始符號(hào)，以及一組（ A 字符串B 產(chǎn)生式C 開始符號(hào)D 文法2一個(gè)句型中稱為句柄的是該句型的最左（ ）A非終結(jié)符號(hào)B短語C句子D直接短語3自動(dòng)機(jī)識(shí)別的語言是（ ）A0 型語言B1 型語言C2 型語言D3 型語言4編譯程序各階段工作都涉及（ ）A.詞法分析B.表格管理5C.語法分析D.語義分析5代碼生成階段的主要任務(wù)是 （）A把高級(jí)語言翻譯成匯編語言B把高級(jí)語言翻譯成機(jī)器語言C把中間代

2、碼變換成依賴具體機(jī)器的目標(biāo)代碼D把匯編語言翻譯成機(jī)器語言6作為編譯程序的源語言，不能是( )A.高級(jí)語言B.C語言C.低級(jí)語言D.Pascal語言7詞法分析器的輸入是（ ）A.單詞符號(hào)串B.源程序C.語法單位D.目標(biāo)程序8給定文法A-bAcc,下面符號(hào)串中不是該文法的句子的是（ ）cc bcbc bcbcc bccbcc bbbccAB. C. D. 9若B是非終結(jié)符，則A-a.aBb為（ ）項(xiàng)目A移進(jìn)B待約C接受D規(guī)約10文法G：Sb|(T)5TT,S|S 則FIRSTVT(T)結(jié)果是（ A. b,(B. b,)C.b,(,，D.b,),，11常用的中間代碼形式不含（ ）A三元式B四元式C逆

3、波蘭式D語法樹12.正規(guī)式 M 1 和 M 2 等價(jià)是指（ AM1和M2的狀態(tài)數(shù)相等BM1和M2的有向邊條數(shù)相等CM1和M2所識(shí)別的語言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等13.文法G：SxSx|y所識(shí)別的語言是（ AxyxB(xyx)*Cxyx (n0)nnDx*yx*14如果文法G是無二義的，則它的任何句子（ A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同15詞法分析器的輸出結(jié)果是（ A.單詞的種別編碼B.單詞在符號(hào)表中的位置C.單詞的種別編碼和自身值D.單詞自身值5二、填

4、空題（本大題共10空，每空2分，共20分）1對(duì)于文法GE：ET|E+TTF|T*FFPF|PP(E)|i，句型T+T*F+i的句柄是_，最左素短語是 _。2編譯器常用的語法分析方法有_和_兩種。3算符優(yōu)先分析法每次都是對(duì)_ 進(jìn)行歸約。4編譯程序的工作過程主要分為如下幾個(gè)階段：詞法分析、語法分析、_、_、_、目標(biāo)代碼生成。新的符號(hào)用S表示）_。6對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為_ 。三、簡(jiǎn)答題（共6題，每題5分，共30分）1已知文法GZ：ZaZb |ab，寫出 。2已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。3設(shè)有文法EE+T | TTT*F | FF(E) | i求下列表達(dá)式的最左推導(dǎo)和語法樹（1）3+4*5+6（2）3*（4+5）4.將如下正規(guī)文法轉(zhuǎn)換為自動(dòng)機(jī)。S0A|1BA1S|1B0S|05已知文法GS：5Sa| (T)TTbS| S（1）寫出句型(TbS)ba)的語法樹（2）寫出該句型短語、簡(jiǎn)單短語、句柄、素短語6.有文法GS：0) SBB1) BaB|b構(gòu)造此文法的LR（0）項(xiàng)目集規(guī)范簇，并寫出識(shí)別活前綴的DFA四、綜合應(yīng)用（共2題，共20分）1構(gòu)造下列正規(guī)式1(0|1)*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