編譯原理試題A及答案 2

1、編譯原理試題A得 分一、單項選擇題（每題1分，共20分）1、哪個不是編譯系統(tǒng)的組成部分 （ C ）A 詞法分析器 B. 代碼生成器C 設(shè)備管理程序 D. 語法分析器2. 設(shè)有表達式a*b-c，將其中a*b識別為表達式的編譯階段是什么（ B ）A詞法分析 B. 語法分析C語義分析 D. 代碼生成3. 下面不能用于對文法進行描述的是 （ A ）A源語言 B. EBNF CBNF D. 語法圖4. 設(shè)有文法GS: SS1|S0|Sa|Sc|a|b|c，下列符號串中不是該文法的句子的是 （A ）A ab0 B. a0c01 C aaa D. bc105. 文法GS:SaAAbBBa|aS ,則L(G)

2、為 （C ）A(ab)na|n1 B. a (ba)n|n1C(aba)n|n1 D. (aba)n|n06. 哪個不是DFA的構(gòu)成成分 （B ）A 有窮字母表 B. 初始狀態(tài)集合C 終止?fàn)顟B(tài)集合 D. 有限狀態(tài)集合7.詞法分析器的輸入是 （B ）A單詞符號串 B.源程序 C語法單位 D.目標(biāo)程序8.在詞法分析階段不能識別的是 （C ）A標(biāo)識符 B. 運算符 C四元式 D. 常數(shù)9.設(shè)有一段C語言程序while(i&&+j) c=2.19; j+=k; i+; ,經(jīng)過詞法分析后可以識別的單詞個數(shù)是 （ B ）A19 B.20 C21 D.2310自上而下語法分析的主要動作是 （

3、B ）A移進 B. 推導(dǎo) C規(guī)約 D. 匹配11.下面不屬于LL(1)分析器的組成部分是 （D ）ALL(1)總控程序 B. LL(1)分析表C分析棧 D.源程序串12.設(shè)有文法GS為SAB|bC， A|b，B|aD，CAD|b，DaS|c則FOLLOW(A)為 （A ）Aa,c,# B.c,# Ca,# D.#13.設(shè)有文法GS:SAp|Bq，Aa|cA，Bb|dB ，則FIRST(Ap)為 （ C ）Ap,q B. b,d Ca,c D. 其他14.自下而上語法分析的主要分析動作是 （D ）A推導(dǎo) B. 規(guī)約 C匹配 D. 移進-規(guī)約15.算法優(yōu)先分析中，可規(guī)約串是 （ C ） A句柄 B

4、活前綴 C最左素短語 D素短語16. 設(shè)有文法G=S,a,SSaS|,S，該文法是 （B ）ALL(1)文法 B二義性文法 CSLR(1)文法 D算法優(yōu)先文法17、中間代碼生成時所以據(jù)的是 （C  ） A語法規(guī)則     B  詞法規(guī)則 C語義規(guī)則     D 等價變換規(guī)則18、給定文法G: EE+T|T，TT*F|F，F(xiàn)i|(E)則L(G)中的一個句子i+i+(i*i)*i的逆波蘭表示為 （ C）Aiii*i+ Bii+iii*+ Cii+ii*i*+ D其他19在編譯程序

5、中與生成中間代碼的目的無關(guān)的是 （B） A便于目標(biāo)代碼優(yōu)化                B便于存儲空間的組織 C便于目標(biāo)代碼的移植            D便于編譯程序的移植20中間代碼是介于源語言程序和什么之間的一種代碼 （D ）A源代碼 B. 機器語言 C. 匯編語言 D. 目標(biāo)代碼 得 分二簡答（每題3分，共12分）1. 什么是編

6、譯程序？編譯程序是將源語言程序翻譯為目標(biāo)語言程序的程序。2. 詞法分析器的主要任務(wù)是什么？ 詞法分析器的主要任務(wù)是逐步掃描和分解構(gòu)成源程序的字符串，識別出一個一個的單詞符號。3 有限自動機有哪幾部分組成？有限自動機是一個五元組，由非空的有限狀態(tài)集、輸入字母表、狀態(tài)轉(zhuǎn)換函數(shù)、唯一的起始狀態(tài)和接受狀態(tài)集組成。4. 語法分析的基本任務(wù)是什么？在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單元。得 分三、解答題(本大題共6小題，每小題4分，共24分)1.寫正則式：所有小寫字母a開頭和結(jié)尾的串。a(a|b|z)*a2.構(gòu)造有限自動機M，使得：L(M)=anbn|n1。應(yīng)是L(M)=an

7、bm|n,m13.給定文法GS:SaAcB|BdS，BaScA|cAB|b，ABaB|aBc|a，試檢驗aacbccb是不是其句子。不是其句子4.文法GS:SAc|aB，Aab，Bbc，寫出L(G)的全部元素。L(G)=abc題目應(yīng)該是寫出文法的全部元素：開始符號：S；VT=a,b,c;VN=S,A,B;P= SAc, SaB, Aab，Bbc 5.把下列表達式變換成后綴表達式：（x:=x+3）*4xx3+:=4*6. 把下列表達式變換成后綴表達式：(not A and B) or (C or not D)A not B and C D not or or得 分四、求解題（本大題共5小題，每小

8、題6,共30分)1 設(shè)文法GE: EE+T|E-T|T，TT*F|T/F|F，F(xiàn)FP|P，P(E)|i，求T*(T-i)+P的短語、直接短語、素短語和句柄。短語T,i, T-i ,(T-i)，T*(T-i), P,T*(T-i)+P直接短語T, i , P素短語i句柄T2. 對文法GR:RR | T | T，TTF|F，F(xiàn)F*|C，C(R)|a|b，消除文法左遞歸。 RTR1,R1|TR1|, TFT1,T1FT1|, FCF1, F1*F1|，C(R)|a|b3. 給定程序： void fun(int x,int y) x+;y+;main() int x=0; fun(x,x); prin

9、tf(x);調(diào)用函數(shù)fun時，若參數(shù)傳遞機制是1）按值傳遞，那么輸出結(jié)果為多少？ 2）按引用傳遞，那么輸出結(jié)果為多少？ 3）按值-結(jié)果傳遞，那么輸出結(jié)果為多少？答：1）按值傳遞，輸出0 2）按引用傳遞，輸出2 3）按值-結(jié)果傳遞，輸出14. 把下列表達式翻譯成三地址代碼：i:=(j+k)*(10+m)。t1:= j+kt2:=10+mi:=t1*t25.已知文法G的EBNF表示為： AB，BXA，X(a|b)a|b，試用C語言寫出其遞歸下降子程序。AB，BXA，X(a|b)a|b即ABBXAX(a|b)a|b可以先變換：BX B A() if ( sym= ) scaner(); B(); e

10、lse error();B() X();if(sym= ) scaner(); while(sym=) scaner();B(); else error();X()if(sym=a) scanner();else if(sym=b) scanner(); else error();while(sym=a or sym=b) scanner();得 分五、綜合題(本大題共2小題，每小題7分，共14分)1將下列NFA確定化，并畫出最小化的DFA。 輸入a 輸入b0 0，1 1 1 0,1 1 0，1 0,1 10 1,2 f(1,a)=2 f(2,a)=2 f(1,b)=1 f(2,b)=11,2等