編譯基本知識與技術(shù)模擬試題一

_模擬試題一一、填空題（10分）1.1從程序運行的角度看，編譯程序和解釋程序的主要區(qū)別是：。1.2編譯程序的基本組成有：詞法分析、、、中間代碼生成、代碼優(yōu)化、、和。1.3正規(guī)式r和s等價說明相同。1.4不含子串baa的所有a、b符號串的正規(guī)式是。1.5規(guī)范規(guī)約（最左歸約）和是互逆的兩個過程。1.6在賦值語句“x=y+2”中，常量2是右值，變量x提供，變量y提供右值。二、選擇題（20分）2.1文法的終結(jié)符集和非終結(jié)符集的交集一定為空。詞法分析器交給語法分析器的文法符號精品文檔放心下載一定是 ，它只能出現(xiàn)在產(chǎn)生式的右部。A.終結(jié)符 B.非終結(jié)符 C.產(chǎn)生式 D.起始符號謝謝閱讀2.2為數(shù)組聲明a:array[1..4,2..3]中a分配的存儲空間的首地址為base_a，且每個數(shù)組元精品文檔放心下載素占據(jù)一個存儲單元。若以行為主存放，數(shù)組元素a[3,3]在存儲空間中相對base_a的偏移謝謝閱讀量是。A.2B.3C.5D.62.3主流程序設(shè)計語言（如Pascal、C++等）均采用和最近嵌套原則，為此類語言的編譯器設(shè)計的符號表應(yīng)該具有后進先出的性質(zhì)。A.靜態(tài)作用域B.動態(tài)作用域C.靜態(tài)綁定D.動態(tài)綁定2.4參數(shù)傳遞中，值調(diào)用傳遞的是實參的右值（或值），引用調(diào)用傳遞的是實參的。A.右值B.左值C.名字D.結(jié)果2.5靜態(tài)數(shù)據(jù)區(qū)用于存放一對一的綁定、且編譯時就可確定存儲空間大小的數(shù)據(jù)；用于存放一對多的綁定且與活動同生存期的數(shù)據(jù)。A.棧B.堆C.數(shù)組D.鏈表2.6LR(1)分析法中，L的含義是，R的含義是最右推導(dǎo)的逆，1的含義是確定下一個動作向前看1個終結(jié)符。A.最左推導(dǎo)B.自左向右掃描輸入C.最左歸約D.自右向左掃描輸入2.7改寫文法或者規(guī)定文法符號的優(yōu)先級和結(jié)合性是的基本方法。A.代碼生成B.語法分析C.語義分析D.去除文法的二義性2.8是正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中的元素。A.135202cdeB.1202cC.302cdeD.52c_2.9表達式“(a+b)*(c-d)”的后綴表示為 。謝謝閱讀A.ab+cd-* B.abcd+-* C.ab+*cd- D.abcd*+-謝謝閱讀2.10若程序P經(jīng)編譯并鏈接后可執(zhí)行，則 。A.P是正確的程序 B.P中沒有語法錯誤C.P中沒有邏輯錯誤 D.P在運行中不會出錯精品文檔放心下載三、簡答題（30分）3.1（6分）有文法G：S→aSbS|bSaS|ε和G產(chǎn)生的一個句子ababab。謝謝閱讀該文法是二義的嗎？為什么？該文法產(chǎn)生的語言L(G)=？3.2（10分）有文法G：S→(L)|a,L→L,S|S。謝謝閱讀說明G不是LL(1)文法；將G改寫為LL(1)文法。3.3（5分）簡述過程的活動和活動的生存期。3.4（9分）給出語句while(a<b)doif(c<d)thenx:=y+z的中間代碼序列。精品文檔放心下載四、綜合題（40分）4.1（15分）有C++程序如下所示：#include<iostream.h>intf(intn){if(n<2)returnn;returnf(n-1)+f(n-2);精品文檔放心下載}voidmain(){inta=4;cout<<f(a)<<endl;}精品文檔放心下載(a)（5分）畫出程序運行時的活動樹；(b)（3分）給出程序的運行結(jié)果；(c)（5分）若控制棧從左向右增長（最右邊是棧頂），請問(main,f(4),f(1))是不是一個可能的控制棧狀態(tài)？為什么？精品文檔放心下載(d)（2分）為C語言設(shè)計的棧式存儲分配策略中，是否需要display？為什么？謝謝閱讀4.2（10分）某表達式的語法制導(dǎo)翻譯方案如下(運算符-,*,+的優(yōu)先級依次遞減)。感謝閱讀（1）M→ε {M.stat:=nextstat;}謝謝閱讀（2）E→E1+ME2 {backpatch(E1.fc，M.stat)；謝謝閱讀E.tc:=merge(E1.tc,E2.tc);E.fc:=E2.fc;}精品文檔放心下載（3）E→E1*ME2 {backpatch(E1.tc,M.stat)；謝謝閱讀_E.fc:=merge(E1.fc,E2.fc);E.tc:=E2.tc;}（4）E→-E1{E.tc:=E1.fc;E.fc:=E1.tc;}（5）E→(E1){E.tc:=E1.tc;E.fc:=E1.fc;}（6）E→id{E.tc:=mkchain(nextstat);E.fc:=mkchain(nextstat+1);emit('if'id.place'goto_');emit('goto_');}(a)（5分）給出表達式p*(-a)+b的注釋分析樹；精品文檔放心下載(b)（5分）根據(jù)上述翻譯方案，生成表達式p*(-a)+b的三地址碼序列。精品文檔放心下載4.3（15分）已知一個NFA如下圖所示。a,ba,bbb012(5分)用自然語言簡要敘述該自動機所識別的語言的特點，列舉兩個它可識別的串。感謝閱讀(2分)寫出與該自動機等價的正規(guī)式r。(c)（8分）用子集法構(gòu)造識別r的最小DFA。謝謝閱讀_模擬試題一參考答案一、填空題（10分）1.1從程序運行的角度看，編譯程序和解釋程序的主要區(qū)別是：運行目標(biāo)程序時控制權(quán)在解釋程序而不在目標(biāo)程序，或者是否生成目標(biāo)代碼，或者是否與機器相關(guān)。1.2編譯程序的基本組成有：詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、表格管理和出錯處理。1.3正規(guī)式r和s等價說明r和s表示的正規(guī)集相同。1.4不含子串baa的所有a、b符號串的正規(guī)式是a*(b|ba)*。1.5規(guī)范規(guī)約（最左歸約）和規(guī)范推導(dǎo)是互逆的兩個過程。1.6在賦值語句“x=y+2”中，常量2是右值，變量x提供左值，變量y提供右值。二、選擇題（20分）2.1文法的終結(jié)符集和非終結(jié)符集的交集一定為空。詞法分析器交給語法分析器的文法符號一定是A，它只能出現(xiàn)在產(chǎn)生式的右部。謝謝閱讀A.終結(jié)符 B.非終結(jié)符 C.產(chǎn)生式 D.起始符號精品文檔放心下載2.2為數(shù)組聲明a:array[1..4,2..3]中a分配的存儲空間的首地址為base_a，且每個數(shù)組元素占據(jù)一個存儲單元。若以行為主存放，數(shù)組元素a[3,3]在存儲空間中相對base_a的偏移謝謝閱讀量是C。A.2B.3C.5D.62.3主流程序設(shè)計語言（如Pascal、C++等）均采用A和最近嵌套原則，為此類語言的編譯器設(shè)計的符號表應(yīng)該具有后進先出的性質(zhì)。A.靜態(tài)作用域B.動態(tài)作用域C.靜態(tài)綁定D.動態(tài)綁定2.4參數(shù)傳遞中，值調(diào)用傳遞的是實參的右值（或值），引用調(diào)用傳遞的是實參的B。A.右值B.左值C.名字D.結(jié)果2.5靜態(tài)數(shù)據(jù)區(qū)用于存放一對一的綁定、且編譯時就可確定存儲空間大小的數(shù)據(jù)；A用于存放一對多的綁定且與活動同生存期的數(shù)據(jù)。A.棧B.堆C.數(shù)組D.鏈表2.6LR(1)分析法中，L的含義是B，R的含義是最右推導(dǎo)的逆，1的含義是確定下一個動作向前看1個終結(jié)符。A.最左推導(dǎo)B.自左向右掃描輸入C.最左歸約D.自右向左掃描輸入2.7改寫文法或者規(guī)定文法符號的優(yōu)先級和結(jié)合性是D的基本方法。A.代碼生成B.語法分析C.語義分析D.去除文法的二義性2.8B是正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中的元素。_A.135202cdeB.1202cC.302cdeD.52c2.9表達式“(a+b)*(c-d)”的后綴表示為A。A.ab+cd-*B.abcd+-*C.ab+*cd-D.abcd*+-2.10若程序P經(jīng)編譯并鏈接后可執(zhí)行，則B。A.P是正確的程序B.P中沒有語法錯誤C.P中沒有邏輯錯誤D.P在運行中不會出錯三、簡答題（30分）3.1（6分）有文法G：S→aSbS|bSaS|ε和G產(chǎn)生的一個句子ababab。謝謝閱讀(a)該文法是二義的嗎？為什么？(b)該文法產(chǎn)生的語言L(G)=？解：是二義文法，對句子ababab存在兩個分析樹如下所示：精品文檔放心下載SSaSbSaSbSbSaSεbSaSaSbSεbSaSεεεεεε(b) L(G)={a,b個數(shù)相等的a,b串}謝謝閱讀3.2（10分）有文法G：S→(L)|a,L→L,S|S。謝謝閱讀(a)說明G不是LL(1)文法；(b)將G改寫為LL(1)文法。解：因為FIRST(L,S)∩FIRST(S)={a}，即非終結(jié)符L產(chǎn)生式的兩個候選項有公共左因子，所以G不是LL(1)文法。謝謝閱讀G中有左遞歸，消除左遞歸如下：1．將沒有直接左遞歸的S代入有直接左遞歸的L產(chǎn)生式，得：感謝閱讀L→L,(L)|L,a|(L)|a （或：L→L,S|(L)|a）謝謝閱讀消除直接左遞歸，得：L→(L)L'|aL'L'→,(L)L'|,aL'|ε最后的消除左遞歸的文法G'：精品文檔放心下載G：S→(L)|aL→(L)L'|aL'L'→,(L)L'|,aL'|ε （或：L'→,SL'|ε）感謝閱讀_3.3（5分）簡述過程的活動和活動的生存期。解：過程的一次運行稱為過程的一次活動；活動的生存期是指從進入活動的第一條指令開始執(zhí)行，到離開活動的最后一條指令執(zhí)行完成的時間，其中包括被調(diào)用過程活動的生存期。感謝閱讀3.4（9分）給出語句while(a<b)doif(c<d)thenx:=y+z的中間代碼序列。感謝閱讀解：程序流圖：開始a<bN結(jié)束NYc<dYx:=y+z中間代碼：101(j<,a,b,103)102(j,-,-,108)103(j<,c,d,105)104(j,-,-,101)105(+,y,z,t1)106(:=,t1,-,x)107(j,-,-,101)108...或：101ifa<bgoto103102goto108103ifc<dgoto105104goto101105t1:=y+z106x:=t1107goto101108...四、綜合題（40分）4.1（15分）有C++程序如下所示：#include<iostream.h>intf(intn)_{if(n<2)returnn;returnf(n-1)+f(n-2);}voidmain(){inta=4;cout<<f(a)<<endl;}精品文檔放心下載(a)（5分）畫出程序運行時的活動樹；(b)（3分）給出程序的運行結(jié)果；(c)（5分）若控制棧從左向右增長（最右邊是棧頂），請問(main,f(4),f(1))是不是一個可能的控制棧狀態(tài)？為什么？感謝閱讀(d)（2分）為C語言設(shè)計的棧式存儲分配策略中，是否需要display？為什么？謝謝閱讀解：活動樹如下：main()f(4)f(3) f(2)f(2) f(1) f(1) f(0)f(1) f(0)程序的運行結(jié)果為：3不是一個可能的控制棧狀態(tài)，因為f(4)不能直接調(diào)用f(1)。從活動樹也可以看出，f(4)精品文檔放心下載所在的任何一條路徑上，f(4)和f(1)不相鄰。不需要，因為display是用于訪問非本地數(shù)據(jù)的。而C程序中不允許過程的嵌套定義，故C程序中的變量或者是全程的，或者是本地的，沒有所謂的非本地數(shù)據(jù)。感謝閱讀4.2（10分）某表達式的語法制導(dǎo)翻譯方案如下(運算符-,*,+的優(yōu)先級依次遞減)。謝謝閱讀（1）M→ε

{M.stat:=nextstat;}（2）E→E1+ME2

{backpatch(E1.fc，M.stat)；感謝閱讀E.tc:=merge(E1.tc,E2.tc);E.fc:=E2.fc;}謝謝閱讀（3）E→E1*ME2

{backpatch(E1.tc,M.stat)；感謝閱讀E.fc:=merge(E1.fc,E2.fc);E.tc:=E2.tc;}謝謝閱讀（4）E→-E1

{E.tc:=E1.fc;E.fc:=E1.tc;}精品文檔放心下載（5）E→(E1)

{E.tc:=E1.tc;E.fc:=E1.fc;}精品文檔放心下載（6）E→id

{E.tc:=mkchain(nextstat);E.fc:=mkchain(nextstat+1);謝謝閱讀emit('if'id.place'goto_');謝謝閱讀

emit('goto_');}(a)（5分）給出表達式p*(-a)+b的注釋分析樹；感謝閱讀(b)（5分）根據(jù)上述翻譯方案，生成表達式p*(-a)+b的三地址碼序列。精品文檔放心下載解：_（a）注釋分析樹如下：E.tc=(4,5)1.fc=(6)E.tc=(4)+M.stat=521.fc=(2,3)E.tc=(1)*M.stat=3E.tc=(4)4.fc=(2)25.fc=(3)p(E.tc=(4))6.fc=(3)-E.tc=(3)7.fc=(4)a(b)三地址碼序列如下：ifpgoto3goto5if