2023年編譯原理期末試卷及答案資料

20２３-202３學(xué)年第一學(xué)期期末考試答案及評(píng)分標(biāo)準(zhǔn)《編譯原理》(Ｂ)卷命題教師：毛靜命題教師：毛靜任課教師：毛靜課程代碼：22801204合用班級(jí)：計(jì)本12級(jí)教研室主任審核(署名)：教學(xué)主任(署名）:題號(hào)一二三四五總分評(píng)卷人分值得分得分MACROＢUＴＴO(shè)NAcｃeｐtＡlｌChａngesInDoc選擇題(每小題2分,共20分）1、編譯程序和解釋程序的區(qū)別是：【B】A、解釋程序產(chǎn)生目的程序,編譯程序不生成目的代碼B、解釋程序不產(chǎn)生目的,編譯程序生成目的代碼?C、解釋程序和編譯程序都生成目的代碼D、解釋程序和編譯程序2、將編譯程序提成若干個(gè)“遍”是為了：?【B】?A、提高程序的執(zhí)行效率 B、使程序的結(jié)構(gòu)更加清楚?Ｃ、運(yùn)用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率??D、運(yùn)用有限的機(jī)器內(nèi)存但減少了機(jī)器的執(zhí)行效率3、詞法分析器的輸出結(jié)果是: 【C】A、單詞的種別編碼 ?B、單詞在符號(hào)表中的位置Ｃ、記號(hào)流? Ｄ、單詞自身值4、編譯的各個(gè)階段中,與源程序打交道的階段是:【C】 Ａ、語(yǔ)法分析? B、語(yǔ)義分析?C、詞法分析 Ｄ、代碼優(yōu)化５、語(yǔ)法分析中的立法機(jī)構(gòu)是： 【Ｂ】 A、正規(guī)式? Ｂ、上下文無關(guān)文法C、上下文有關(guān)文法 ?D、預(yù)測(cè)分析器6、移近-歸約分析表中指導(dǎo)分局發(fā)生變化的動(dòng)作涉及:【C】Ａ、移近、歸約? Ｂ、移近、歸約、接受C、移近、接受、歸約、犯錯(cuò) ?D、移近，歸約、犯錯(cuò)7、中間代碼生成時(shí)所依據(jù)的是:?【Ａ】?A、語(yǔ)義規(guī)則 Ｂ、詞法規(guī)則?Ｃ、語(yǔ)法規(guī)則 D、等價(jià)變換規(guī)則８、程序所需的數(shù)據(jù)空間在程序運(yùn)營(yíng)前就可擬定,稱為：【Ｂ】 A、動(dòng)態(tài)存儲(chǔ)??B、靜態(tài)存儲(chǔ)?C、棧式存儲(chǔ) ?Ｄ、堆式存儲(chǔ)9、代碼生成階段的重要任務(wù)是:【C】 A、把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言?B、把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言 C、把中間代碼變換成依賴具體機(jī)器的目的代碼? Ｄ、把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言10、代碼優(yōu)化的方法中不包含： 【Ｄ】 Ａ、窺孔優(yōu)化? B、強(qiáng)度削弱?Ｃ、構(gòu)造流圖? D、基本塊優(yōu)化得分得分二、MACROBUTTONAcceptAllChangesInDoc填空題（每空1分，共10分）1、每個(gè)階段將程序完整分析一遍的工作模式稱為_＿_(dá)＿＿一遍掃描＿＿_(dá)__。2、將高級(jí)語(yǔ)言寫的源程序翻譯成目的語(yǔ)言的程序，這種翻譯過程稱為編譯_____＿。3、若有限自動(dòng)機(jī)M和Ｍ’_＿_(dá)_辨認(rèn)同一正規(guī)集＿＿_(dá)__,則稱M和M’是等價(jià)的。４、若文法G對(duì)同一句子產(chǎn)生不止一棵分析樹,則稱文法G___具有二義性＿_(dá)_。5、后綴式aｂ+ｃd+/可用表達(dá)式＿_(dá)_＿（a＋ｂ)／(ｃ+d）_＿_(dá)_來表達(dá)。6、程序設(shè)計(jì)語(yǔ)言的運(yùn)營(yíng)時(shí)存儲(chǔ)管理方案,重要分為兩大類，即_＿靜態(tài)存儲(chǔ)分派___和＿_(dá)＿_(dá)動(dòng)態(tài)存儲(chǔ)分派___方案。7、通過編譯所得到的目的程序是__機(jī)器語(yǔ)言程序___或者＿＿匯編語(yǔ)言程序。。8、局部?jī)?yōu)化是局限于一個(gè)__基本塊___范圍內(nèi)的一種優(yōu)化。得分得分三、MACROBUTTONAcceptAllChangesInDoc判斷題（對(duì)的的在題號(hào)后括號(hào)內(nèi)填寫“V”,錯(cuò)誤的填寫“X”）（每小題2分，共20分）1.編譯程序和機(jī)器硬件有關(guān),和具體的語(yǔ)言無關(guān)。（X）2.ＮAＦ在辨認(rèn)記號(hào)的時(shí)候會(huì)產(chǎn)生大量的回溯。(V)3．每個(gè)文法都能改寫為ＬL(1）文法。(Ｘ）4.LR分析表是由動(dòng)作表和轉(zhuǎn)移表兩部分組成的。（Ｖ）5.代碼優(yōu)化的目的是把編譯程序進(jìn)行等價(jià)變換。（X）6．引用調(diào)用中,實(shí)參與形參共用同一個(gè)內(nèi)存空間。(Ｖ)7．綜合屬性的計(jì)算方式是自上而下包含自身。(X)8.一個(gè)完整程序執(zhí)行的控制流,是對(duì)它的活動(dòng)樹的一次深度優(yōu)先遍歷。(Ｖ）9．在名字綁定的概念下，對(duì)一個(gè)常量的賦值包含了兩次映射,即環(huán)境映射和狀態(tài)映射。（X)10.通過拷貝語(yǔ)句進(jìn)行值的傳遞的語(yǔ)句稱為復(fù)寫傳播。（V）得分四、MＡCROBUTTONAcｃeptＡllChａngｅsIｎDｏｃ簡(jiǎn)答題(第１小題7分,第2小題６分，第3小題7分,共２０分)1、（７分）簡(jiǎn)述如何從正規(guī)式構(gòu)造詞法分析器。答:從正規(guī)式構(gòu)造詞法分析器的基本環(huán)節(jié)如下:用正規(guī)式對(duì)模式進(jìn)行描述(１分）；為每個(gè)正規(guī)式構(gòu)造一個(gè)ＮFＡ，它辨認(rèn)正規(guī)式所表達(dá)的正規(guī)集(1分）；將構(gòu)造出的ＮFＡ轉(zhuǎn)換成等價(jià)的DFA，這一過程也被稱為擬定化（2分);優(yōu)化DFA,使其狀態(tài)數(shù)最少,這一過程也被稱為最小化(2分）；從優(yōu)化后的DFA構(gòu)造詞法分析器(1分）。2、(6分）下述文法哪些文法是LL(1)文法,哪些不是LL（１）文法,為什么？（1）S->Rａ｜aR->Sb｜b(２)S->aAc|bA－＞a|b|ε（3）Ｓ->aA|AaA-＞b|ε答：不是ＬL(1）文法,S=>Ra=>Sba具有間接左遞歸，因此不是不是LL(1)文法。-----－----－---－----------（2分)是LL(1)文法,由于滿足推論3.2的3條規(guī)則。－-----－-------------－---－（2分)（３)不是LL(1)文法。對(duì)于S-＞Aa｜Aａ，求得Firsｔ（aA)與First(Aa）的交集為a,所以不是ＬL(1)文法,----－-----－--－－－－---－----（2分）3、（７分）寫出表達(dá)式x=a-b＊c-a+（ｂ／2＋ｃ）的后綴式，三元式序列,四元式序列。答:后綴式：aｂｃ＊-a-b2/c++ｘ=－--－--－---－-----－-－－-－---（1分）三元式序列:----－----－----－------－-－-（3分)(１)(＊，b,c)(2)(-,a，（1))（3）（-,(2),a)(4)(/,ｂ,2)(5)（+,(4），ｃ)(6）（+,(3),(5)）(７)(＝,x,(6))四元式序列:－-－-----------－-------－--（3分)(*,b,c,T1)（-,a,T1,T2)(-,Ｔ２,a,T3)(/,b,2,T4)(＋,T4,c,T5)(+,Ｔ３,T５，T6)(=,ｘ,T６,T7)得分五、ＭACROBUTＴＯNAcceｐtAｌlＣhangesInDoc論述題(每小題15分,共30分）1、(15分）已知某NＦA的狀態(tài)轉(zhuǎn)換矩陣如下表1所示，將此NFA擬定化,構(gòu)造器最小化DFA，規(guī)定寫出具體解題過程。表1NFA的狀態(tài)轉(zhuǎn)換矩陣ａｂcd13２2４2363５47355４6６7６答:從上表中可以看出,該NFＡ已經(jīng)是DFＡ，所以直接對(duì)其進(jìn)行最小化（5分）。初始分劃Π0:終態(tài)組｛６,7｝,非終態(tài)組{1,２,3，４,5}------－--－--－-----－--（２分)對(duì){1，2,3,4,5}進(jìn)行審查:{１，２｝輸入b到達(dá)｛２｝，而{3,４｝輸入b到達(dá){６，７}，{５}輸入b不會(huì)有任何動(dòng)作，故得到新分劃{1,２}{３,4}{５}-－-－-－-----－－-－-－－-----（2分）Π１:{1,2}?{３，4｝ {5｝｛6,７}Π1即是最后劃分,--－--------－--－-------(2分)重新命名,以1，3，5,6代替{1,2｝{3,4}｛５｝{6,７}得最小化的DFA如下表2所示表2最小化后的DFAａｂcd131363553６6336b1abcb5da－－－---－----－－--------－-－---－--－（4分)2、（1５分)已知文法G[S]：Ｓ→ａBｃ｜bABA→aAb|bB→b|ε(1)構(gòu)造其ＬL（１)分析表（12分);（２)使用自上而下的分析方法判斷字符串baabbb是否為該文法的句子（３分)。答：（1）一方面計(jì)算所有終結(jié)符的FIRST集合和FOLLOＷ集合。FIRST（B)=｛b,ε｝FIＲＳT(A)={a,b}FＩRSＴ（S)={a,b}ＦOＬLOW(S)＝{#}FOLLOW(A)={b，#｝FOLＬOW（B)={c,#}-----－----－-------－---------－----－---(6分)預(yù)測(cè)分析表如下所示:ａｂc＃SＳ→aＢｃS→bＡBＡA→aAbA→ｂBB→bB→εB→ε－－----－-－-－－--－---------－－－------－---（6分)(2)自上