編譯原理半期考試答案

畢節(jié)學(xué)院課程考試一試卷紙畢節(jié)學(xué)院期中課程試卷2009~2010學(xué)年度第二學(xué)期《編譯原理》計科系07級計算機(jī)科學(xué)與技術(shù)專業(yè)班姓名學(xué)號得分主考教師：黃正鵬試卷種類：（半期考試）得分評卷人一、填空題（每空1分，共20分）1．編譯程序的工作過程一般能夠區(qū)分為詞法剖析,語法剖析,語義剖析,中間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有__表格辦理___和___犯錯辦理__。2．若源程序是用高級語言編寫的,___目標(biāo)程序__是機(jī)器語言程序或匯編程序,則其翻譯程序稱為___編譯程序__。3．編譯方式與解說方式的根本差別在于__能否生成目標(biāo)代碼___。4．對編譯程序而言,輸入數(shù)據(jù)是___源程序_目標(biāo)程序___。_,輸出結(jié)果是__5．若兩個正規(guī)式e1和e2所表示的正規(guī)集同樣,則e1和e2等價,寫作e1=e2。6．一個句型中的最左簡單短語稱為該句型的___句柄__。7．詞法剖析鑒于__正則___文法進(jìn)行，即識其余單詞是該類文法的句子。二、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃×）（每個1分，共10分）得分評卷人1．計算機(jī)高級語言翻譯成初級語言只有解說一種方式。(×)2．在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中全部錯誤。(×)3．甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必需條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完整同樣。(√)4．正則文法其產(chǎn)生式為A->a，A->Bb,A,B∈VN，a、b∈VT。(×)5．每個文法都能改寫為LL(1)文法。(√)（2班做）畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁1畢節(jié)學(xué)院課程考試一試卷紙6.有窮自動機(jī)接受的語言是正規(guī)語言。(√)（1班做）7.對任何一個NFAM都存在一個DFAM’,使得L(M’)=L(M).(√)8．設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。(×)9．確立的自動機(jī)以及不確立的自動機(jī)都能正確地辨別正規(guī)集。(√)10．詞法剖析作為獨(dú)自的一遍來辦理較好。(×)11．有窮自動機(jī)接受的語言是正規(guī)語言。（√）得分評卷人三、選擇題（每題2分，共20分）1．文法G產(chǎn)生的_____的全體是該文法描繪的語言。A．( )句型B．( )終結(jié)符集C．( )非終結(jié)符集D．( )句子2．若文法G定義的語言是無窮集，則文法必定是_____。A．( )遞歸的B．( )前后文沒關(guān)的C．( )二義性的D．( )無二義性的3．四種形式語言文法中，1型文法又稱為_____文法。A．( )短語結(jié)構(gòu)文法B．( )前后文沒關(guān)文法C．( )前后文相關(guān)文法D．( )正規(guī)文法4．一個文法所描繪的語言是_____。A．( )獨(dú)一的B．( )不獨(dú)一的C．( )可能獨(dú)一，好可能不獨(dú)一D．( )都不對5．_____和代碼優(yōu)化部分不是每個編譯程序都必需的。A．( )語法剖析B．( )中間代碼生成C．( )詞法剖析D．( )目標(biāo)代碼生成6．_____是兩類程序語言辦理程序。A．( )高級語言程序和初級語言程序B．( )解說程序和編譯程序C．( )編譯程序和操作系統(tǒng)D．( )系統(tǒng)程序和應(yīng)用程序7．編譯程序是對_____。A．( )匯編程序的翻譯B．( )高級語言程序的解說履行C．( )機(jī)器語言的履行D．( )高級語言的翻譯8．采納自上而下剖析，一定_____。（2班做）A．( )除去左遞歸B．( )除去右遞歸C．( )除去回溯D．( )提取公共左因子9．在規(guī)范歸約中，用_____來刻畫可歸約串。（2班做）A．( )直接短語B．( )句柄C．( )最左素短語D．( )素短語畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁2畢節(jié)學(xué)院課程考試一試卷紙10．詞法剖析器用于辨別_____。A．( )字符串B．( )語句C．( )單詞D．( )表記符11．文法分為四種種類，即0型、1型、2型、3型。此中0型文法是_____。A.( )短語文法B．( )正則文法C．( )上下文相關(guān)文法D．( )上下文沒關(guān)文法12．一個上下文沒關(guān)文法G包含四個構(gòu)成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組_____。A．( )句子B．( )句型C．( )單詞D．( )產(chǎn)生式得分評卷人四、簡答題（每題5分，共30分）1.高級語言程序有哪兩種履行方式？其特色是什么？答：高級語言程序有編譯程序和解說程序兩種履行方式；編譯程序（Compiler）——將高級程序設(shè)計語言程序翻譯成邏輯上等價的初級語言(匯編語言,機(jī)器語言)程序的翻譯程序。解說程序（Interpreter）——將高級程序設(shè)計語言寫的源程序作為輸入，邊解說邊履行源程序自己，而不產(chǎn)生目標(biāo)程序的翻譯程序。2、考慮文法G[S]：S→aSbS|bSaS|(1)試用最左推導(dǎo)說明此文法是二義性的（2）關(guān)于句子abab結(jié)構(gòu)兩個相應(yīng)的最右推導(dǎo)（3）關(guān)于句子abab結(jié)構(gòu)兩個相應(yīng)的剖析樹解答：句子abab有以下兩個不一樣的最左推導(dǎo)：S=>aSbS=>abS=>abaSbS=>ababS=>ababS=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab因此此文法是二義性的。句子abab的兩個相應(yīng)的最右推導(dǎo)：=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>ababS=>aSbS=>aSb=>abSaSb=>abSab=>abab句子abab的兩棵剖析樹：畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁3畢節(jié)學(xué)院課程考試一試卷紙(a)(b)3、已知文法G[E]為：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i①該文法的開始符號（辨別符號）是什么？②請給出該文法的終結(jié)符號會合VT和非終結(jié)符號會合VN。③找出句型T+T*F+i的全部短語、簡單短語和句柄。解：①該文法的開始符號（辨別符號）是E。②該文法的終結(jié)符號會合VT={+、-、*、/、（、）、i}。非終結(jié)符號會合VN={E、T、F}。③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個T。4.結(jié)構(gòu)正規(guī)式相應(yīng)的NFA:1(0|1)*101解：1(0|1)*101對應(yīng)的NFA為5.畫出接受以/*和*/括起來的說明的狀態(tài)變換圖。．解答：畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁4畢節(jié)學(xué)院課程考試一試卷紙6.用狀態(tài)變換圖表示辨別偶數(shù)個0或偶數(shù)個1的字符串的有窮自動機(jī)。解答：得分評卷人五.計算題（10分）1、結(jié)構(gòu)下述文法G[S]的自動機(jī)：S->A0②A->A0|S1|0該自動機(jī)是確立的嗎？若不確立，則對它確立化。解：因?yàn)樵撐姆ǖ漠a(chǎn)生式S->A0，A->A0|S1中沒有字符集VT的輸入，因此不是確立的自動機(jī)。要將其余確立化，一定先用代入法獲得它對應(yīng)的正規(guī)式。把S->A0代入產(chǎn)生式A->S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入S->A0有該文法的正規(guī)式：0(0|01)*0，因此，改寫該文法為確立的自動機(jī)為：因?yàn)闋顟B(tài)A有3次輸入0的重復(fù)輸入，因此上圖不過NFA，下邊將它確立化：下表由子集法將NFA變換為DFA:畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁5畢節(jié)學(xué)院課程考試一試卷紙由上表可知DFA為：2、設(shè)計一個狀態(tài)數(shù)最小的DFA,其輸入字母表是{0,1}，它能接受以00或01結(jié)尾的全部序列，并給出相應(yīng)的正規(guī)文法。（1班做）解答：正規(guī)式為：(0|1)*(00|01)化簡：(0|1)*0(0|1)不確立的有窮自動機(jī)為：確立化，并最小化獲得：正規(guī)文法為：S→1S|0AA→0B|0|1C|1B→0B|0|1C|1C→1S|0A3、對下邊的文法G:E→TE’E’→+E|畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁6畢節(jié)學(xué)院課程考試一試卷紙T→FT’’→T|F→PF’’→*F’|P→(E)|a|b|∧(1)計算這個文法的每個非終結(jié)符的First集和Folow集；證明這個文法是LL(1)的；結(jié)構(gòu)它的展望剖析表。解答：求First和Follow集First(E)=First(T)={(,a,b,∧}⑦First(E')={+,}⑥First(T)=First(F)={(,a,b,∧}④First(T')=｛(,a,b,∧,｝⑤First(F)=First(P)={(,a,b,∧}③First(F')=｛*，｝②First(P)={(,a,b,∧}①（計算次序）Follow(E)={#,)}Follow(E')=Follow(E)={#，)}(1)（使用的產(chǎn)生式）Follow(T)=First(E')＼{}∪Follow(T')(1,2)={+}∪{),#}={+,),#}Follow(T')=Follow(T)={+,},#}(3)Follow(F)=First(T')＼{}∪Follow(T)(3,4)={(,a,b,∧,+,),#}Follow(F')=Follow(F)(5)={(,a,b,∧,+,),#}Follow(P)=First(F')＼{}∪Follow(F)(5,6)={*,(,a,b,∧,+,),#}(2)證明:∵a.文法不含左遞歸；b.每個非終結(jié)符的各個侯選式的First集不訂交；c.First(E')∩Follow(E')={+,}∩{#,),}=First(T')∩Follow(T')={(,a,b,∧,}∩{+,)}=First(F')∩Follow(F')={*,}∩{,a,(∧,+,},#}=畢節(jié)學(xué)院《編譯原理》課程試卷第頁共8頁7畢節(jié)學(xué)院課程考試一試卷紙∴改造后的