大學《編譯原理》模擬試題及答案(六)

大學《編譯原理》試題及答案一、是非題(請在括號內(nèi)，正確的劃J,錯誤的劃X)(每個2分，共20分).設r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。(X).確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。(J)3．詞法分析作為單獨的一遍來處理較好。(X)4.構(gòu)造LR分析器的任務就是產(chǎn)生LR分析表。(J)5．規(guī)范歸約和規(guī)范推導是互逆的兩個過程。(X)6．同心集的合并有可能產(chǎn)生新的“移進”/“歸約”沖突。(X)7.LR分析技術(shù)無法適用二義文法。(X)8．樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(X).程序中的表達式語句在語義翻譯時不需要回填技術(shù)。(J).對中間代碼的優(yōu)化依賴于具體的計算機。(X)二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)TOC\o"1-5"\h\z編譯程序絕大多數(shù)時間花在 上。A.()出錯處理B.()詞法分析C.()目標代碼生成D.()表格管理編譯程序是對 。A.()匯編程序的翻譯B.()高級語言程序的解釋執(zhí)行C.()機器語言的執(zhí)行D.()高級語言的翻譯采用自上而下分析，必須 。A.()消除左遞歸B.()消除右遞歸C.()消除回溯D.()提取公共左因子4．在規(guī)范歸約中，用 來刻畫可歸約串。A．()直接短語B．()句柄C．()最左素短語D．()素短語.若a為終結(jié)符，則A->a?aS為項目。A．()歸約B．()移進C．()接受D．()待約TOC\o"1-5"\h\z.間接三元式表示法的優(yōu)點為 。A.()采用間接碼表，便于優(yōu)化處理B.()節(jié)省存儲空間，不便于表的修改C.()便于優(yōu)化處理，節(jié)省存儲空間D.()節(jié)省存儲空間，不便于優(yōu)化處理.基本塊內(nèi)的優(yōu)化為 。A.()代碼外提，刪除歸納變量B.()刪除多余運算，刪除無用賦值C.()強度削弱，代碼外提D.()循環(huán)展開，循環(huán)合并.在目標代碼生成階段，符號表用 。A.()目標代碼生成B.()語義檢查C.()語法檢查D.()地址分配.若項目集Ik含有A->a?，則在狀態(tài)k時，僅當面臨的輸入符號a￡FOLLOW(A)時，才采取“A->a?”動作的一定是。A.()LALR文法B.()LR(0)文法C.()LR(1)文法D.()SLR(1)文法10.堆式動態(tài)分配申請和釋放存儲空間遵守 原則。A.()先請先放B.()先請后放C.()后請先放D.()任意三、填空題(每空1分，共10分).詞法分析基于__正則___文法進行，即識別的單詞是該類文法的句子。.語法分析基于__上下文無關___文法進行，即識別的是該類文法的句子。語法分析的有效工具是__語法樹___。.分析句型時，應用算符優(yōu)先分析技術(shù)時，每步被直接歸約的是__最左素短語___，而應用LR分析技術(shù)時，每步被直接歸約的是—句柄_。4．語義分析階段所生成的與源程序等價的中間表示形式可以有__逆波蘭___、___四無式表示__與___三元式表示__等。5.按Chomsky分類法，文法按照—規(guī)則定義的形式—進行分類。6．一個文法能用有窮多個規(guī)則描述無窮的符號串集合(語言)是因為文法中存在有___遞歸__定義的規(guī)則。四、簡答題(20分)文法G[S]為：S->Ac|aBA->abB->bc寫出L(G[S])的全部元素。解：S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}構(gòu)造正規(guī)式1(0|1)*101相應的DFA。解：先構(gòu)造NFA：確定化：重新命名，令AB為B、AC為C、ABY為D得：所以，可得DFA為：文法S->a|N(T)T->T,S|S對(a,(a,a)和(((a,a),A,(a)),a)的最左推導。解：對(a,(a,a)的最左推導為：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))對(((a,a)A(a)),a)的最左推導為：S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a/,S),S)=>(((a,a)A(T)),S)=>(((a,a)A(S)),S)=>(((a,a)A(a)),S)=>(((a,a)A(a)),a)文法：S->MH|aH->LSo|sK->dML|sL->eHfM->K|bLM判斷G是否為LL(1)文法，如果是，構(gòu)造LL(1)分析表。解：各符號的FIRST集和FOLLOW集為：預測分析表為：由于預測分析表中無多重入口，所以可判定文法是LL(1)的。五.計算題(10分)已知文法G[S]為：S->a|N(T)T->T,S|S計算G[S]的FIRSTVT和LASTVT。構(gòu)造G[S]的算符優(yōu)先關系表并說明G