編譯原理試題A及答案

編譯原理試題A、單項選擇題(每題1分，共20分)代碼生成器語法分析器1、哪個不是編譯系統(tǒng)的組成部分A.詞法分析器 B.代碼生成器語法分析器C.設備管理程序D.設有表達式a*b-c，將其中a*b識別為表達式的編譯階段是什么(B)A.詞法分析 B. 語法分析C.語義分析 D. 代碼生成(A(A)語法圖A.源語言 B.EBNFC.BNFD.設有文法G[S]:S-S1|S0|Sa|Sc|a|b|c，下列符號串中不是該文法的句子的是A.ab0B.aOcO1C .aaaD.bc10(A)5.文法G[S]:SfaAA—bBBfa|aS,貝UL(G)為(C)A.{(ab)na|n>1}B.{a(ba)n|n>1}C.{(aba)n|n>1}D.{(aba)n|n>0}6.哪個不是DFA的構成成分(B)A. 有窮字母表B.初始狀態(tài)集合C. 終止狀態(tài)集合D.有限狀態(tài)集合7.詞法分析器的輸入是(B)A.單詞符號串 B.源程序C.語法單位 D.目標程序8.在詞法分析階段不能識別的是 (C)A.標識符B.運算符C.四元式D.常數(shù)9.設有一段C語言程序while(i&&++j){c=2.19;

j+=k;i++；},經(jīng)過詞法分析后可以識別的單詞個數(shù)是 (B)A.19 B.20C .21 D.2310?自上而下語法分析的主要動作是A.j+=k;i++；},經(jīng)過詞法分析后可以識別的單詞個數(shù)是 (B)A.19 B.20C .21 D.2310?自上而下語法分析的主要動作是A.移進B.推導C.規(guī)約D.匹配(B)11.下面不屬于LL(1)分析器的組成部分是 (D)A.LL(1)總控程序B.LL(1) 分析表C.分析棧 D. 源程序串12.設有文法G[S]為S—AB|bC,Ar|b,Bf|aD,C—AD|b,D^aS|c貝UFOLLOW(A為A.{a,c,#} B.{c,#}C .{a,#} D.{#}(A)13.設有文法G[S]:S—Ap|Bq,A—a|cA,B—b|dB,貝UFIRST(Ap)為A.{p,q}B.{b,d}C .{a,c}D.其他14.自下而上語法分析的主要分析動作是 (D)A.推導B.規(guī)約C.匹配D.移進-規(guī)約15.算法優(yōu)先分析中，可規(guī)約串是A.句柄B .活前綴 C .最左素短語 D(C).素短語設有文法G={{S},{a},{S —SaS|￡},S},該文法是 (B)A.LL(1)文法 B .二義性文法C.SLR(1)文法 D .算法優(yōu)先文法17、中間代碼生成時所以據(jù)的是 (C)A.語法規(guī)則換規(guī)則B.詞法規(guī)則C.語義規(guī)則 D. 等價變18、給定文法G:E—E+T|T,T—T*F|F,F—i|(E)則L(G)中的一個句子i+i+(i*i)*i 的逆波蘭表示為 (C)A.iii*i++B.ii+iii**+ C.ii+ii*i*+D.其他19.在編譯程序中與生成中間代碼的目的無關的是19.在編譯程序中與生成中間代碼的目的無關的是(B)A?便于目標代碼優(yōu)化的組織B?便于存儲空間C?便于目標代碼的移植D.便于編譯程序的移植A?便于目標代碼優(yōu)化的組織B?便于存儲空間C?便于目標代碼的移植D.便于編譯程序的移植20?中間代碼是介于源語言程序和什么之間的一種代碼(D)A.源代碼B. 機器語言C.匯編語言D.目標代碼.簡答(每題3分，共12分)什么是編譯程序？編譯程序是將源語言程序翻譯為目標語言程序的程序。2?詞法分析器的主要任務是什么？詞法分析器的主要任務是逐步掃描和分解構成源程序的字符串， 識別出一個一個的單詞符號。有限自動機有哪幾部分組成？有限自動機是一個五元組，由非空的有限狀態(tài)集、輸入字母表、狀態(tài)轉換函數(shù)、唯一的起始狀態(tài)和接受狀態(tài)集組成。語法分析的基本任務是什么？在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單元。得分| 三、解答題(本大題共6小題，每小題4分，共24分)寫正則式：所有小寫字母a開頭和結尾的串。*a(a|b|…|z)a構造有限自動機M使得：L(M)={anbn|n>1}。應是L(M)={anb]n,m>1}

給定文法G[S]:S—aAcB|BdS,4aScA|cAB|b,A—BaB|aBc|a,試檢驗aacbccb是不是其句子。不是其句子文法G[S]:S—Ac|aB,A—ab,B—be,寫出L(G)的全部元素L(G)={abc}題目應該是寫出文法的全部元素：開始符號：S；VT={a,b,c};Vn={S,A,B}；P={S—Ac,S—aB,A—ab,B—bc}把下列表達式變換成后綴表達式：（x:=x+3）*4xx3+:=4*把下列表達式變換成后綴表達式：(notAandB)or(CornotD)AnotBandCDnotoror四、求解題（本大題共5小題，每小題6,共30分）設文法G[E]:E—E+T|E-T|T,T—T*F|T/F|F,F—FTP|P,P—(E)|i，求T*(T-i)+P的短語、直接短語、素短語和句柄。,T*(T-i),P,T*(T-i)+P短語T,i,T-i,（T-i）直接短語T,i,P素短語,T*(T-i),P,T*(T-i)+P句柄T對文法G[R]:R-R'I'T|T,T-TF|F,F-F*|C,C^(R)|a|b，消除文法左遞歸。R—TR,R1—'|'TR|￡,T—FT,T1—FT|&,F—CF,F1—*F1|￡,C-(R)|a|b給定程序：voidfun(intx,inty){x++;y++;}main(){intx=0;fun(x,x);printf(x);}調(diào)用函數(shù)fun時，若參數(shù)傳遞機制是1)按值傳遞，那么輸出結果為多少？2 )按引用傳遞，那么輸出結果為多少？3 )按值-結果傳遞，那么輸出結果為多少？答：1)按值傳遞，輸出02)按引用傳遞，輸出23)按值-結果傳遞，輸出1把下列表達式翻譯成三地址代碼：i:=(j+k)*(10+m)。t1:=j+kt2:=10+mi:=t1*t2已知文法G的EBNF表示為：Af[B,B-X]{A},Xf(a|b){a|b}，試用C語言寫出其遞歸下降子程序A—[B，BfX]{A}，Xf(a|b){a|b} 即Af[BBfX]{A}Xf(a|b){a|b}可以先變換：BfX]{[B}A(){if(sym=='[‘){scaner();B();}elseerror();}B(){X();if(sym==']‘){scaner();while(sym=='[‘){scaner();B();}}elseerror();}X(){if(sym=='a‘){scanner();}elseif(sym== 'b‘){scanner();}elseerror();while(sym=='a‘orsym=='b‘)

{seanner();}{seanner();}五、綜合題（本大題共2小題，每小題7分，共14分）1.將下列NFA確定化，并畫出最小化的DFA輸入a輸入輸入a輸入b{0} {0,1}{1}{1}{0,1}{1}{0,1}{0,1}{1}{0}{1,2}f(1,a)=2f(2,a)=2f(1,b)=1f(2,b)=1{1,2}等價給定文法G[S]:S—