編譯原理作業(yè)答案

計算機科學系2010春天學期《編譯原理》第一次作業(yè)參照答案一、以下正則表達式定義了什么語言(用盡可能簡潔的自然語言描繪）?1.b*（ab＊ab＊）＊全部含有偶數個a的由a和b組成的字符串。2.c*a（a|c)＊（a｜b｜＊|c*b（b|c)*a(a|b｜c)*答案一：全部最少含有1個a和1個b的由，b和c組成的字符串.答案二：全部含有子序列ab或子序列ba的由a，b和c組成的字符串.說明：答案一要比答案二更好,因為用自然語言描繪是為了便于和非專業(yè)的人員溝通，而非專業(yè)人員很可能不知道什么是“子序列”,所以比較較而言答案一要更“自然”。二、設字母表={a,b，b,，|，*,+，？)描繪以下語言：1.不包含子串ab的全部字符串。＊a*2.不包含子串abb的全部字符串。＊(ab？)＊3.不包含子序列abb的全部字符串。＊a*b？a＊注意：對于子串（substring）和子序列(subsequence）的差別能夠參照課本第119頁方框中的內容.~\(≧▽≦)/～～\(≧▽≦（≧▽≦)/～（≧▽≦（≧▽≦)/~～\(≧▽≦)/~~\(≧▽≦)/~～（≧▽≦)/～《編譯原理》第二次作業(yè)參照答案一、考慮以下NFA:1.這一NFA接受什么語言（用自然語言描繪）？全部只含有字母a和b，而且a出現(xiàn)偶數次或b出現(xiàn)偶數次的字符串。2.結構接受同一語言的DFA.答案一（直接結構平時獲得這一答案）：1計算機科學系2010春天學期答案二由NFA結構DFA獲得這一答案）：二、正則語言補運算3.畫出一個DFA，該恰巧鑒識全部不含011子串的全部二進制串.1.畫出一個DFA，該恰巧鑒識全部不含011子串的全部二進制串。2計算機科學系2010春天學期規(guī)律:結構語言L的補語言L’的DFA，能夠先結構出接受L的DFA，再把這一DFA的接受狀態(tài)改為非接受狀態(tài)，非接受狀態(tài)改為接受狀態(tài),就能夠獲得鑒識L'的DFA.說明：在上述兩題中的D狀態(tài)，不論輸入什么符號，都不行能再抵達接受狀態(tài),這樣的狀態(tài)稱為“死狀態(tài)"。在畫時,有時為了簡潔起見，“死狀態(tài)”及其相應的?。ㄉ蠄D中的綠色部分)也可不畫出。2.再證明：對任一正則表達式R,必定存在另一正則表達式’，使得L(R'）是L(R)的補集。證明：依據正則表達式與DFA的等價性,必定存在鑒識語言L(R)的DFA.設這一DFA為M的全部接受狀態(tài)改為非接受狀態(tài),全部非接受狀態(tài)改為接受狀態(tài)，獲得新的DFAM'.易知’鑒識語言（R)的補集。再由正則表達式與的等價性知必存在正則表達式R',使得L(R')是L(R）的補集.三、設有一門小小語言僅含z、o、/（斜杠）3個符號，該語言中的一個說明由/o開始、以o/結束，而且說明嚴禁嵌套。1.請給出單個正則表達式,它僅與一個完好的說明般配，除此以外不般配任何其余串。書寫正則表達式時,要求僅使用最基本的正則表達式算子(｜，＊，+參照答案一：/o（o*z|/）＊o+/思路：基本思路是除了最后一個o/o后邊緊隨著/的狀況;還有需要考慮的是最后一個o/以前也能夠出現(xiàn)若干個。參照答案二（梁曉聰、梁勁、梁偉斌等人供給）：/o/＊（z/*|o)*o/2.給出鑒識上述正則表達式所定義語言確實定有限自動機（DFA你可依據問題直接結構DFA，不用運用機械的算法從上一小題的正則表達式變換獲得DFA.～\(≧▽≦)/~～\(≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦）/~~\(≧▽≦）/～～（≧▽≦)/~~\(≧▽≦（≧▽≦)/~《編譯原理》第三次作業(yè)參照答案一、考慮以下DFA的狀態(tài)遷徙表此中，1為輸入符號,A～H代表狀態(tài):3計算機科學系2010春天學期01ABABACCDBDDAEDFFGEGFGHGD此中A為初始狀態(tài)，D為接受狀態(tài)，請畫出與此DFA等價的最小DFA,并在新的DFA狀態(tài)中注明它對應的原DFA狀態(tài)的子集。說明有些同學沒有畫出狀態(tài)H,因為沒法從初始狀態(tài)抵達狀態(tài)H。從適用上講，這是沒有問題的。可是，如果依據算法的步驟履行，最后是應當有狀態(tài)H的。二、考慮全部含有3個狀態(tài)(設為，q，r）的DFA.設只有r是接受狀態(tài)。至于哪一個狀態(tài)是初始狀態(tài)與本問題沒關.輸入符號只有0和1.這樣的總合有729種不同樣的狀態(tài)遷徙函數，因為對于每一狀態(tài)和每一輸入符號,可能遷徙到3個狀態(tài)中的一個，所以總合有3^6=729種可能。在這729個DFA中，有多少個p和q是不可劃分的(indistinguishable）？解說你的答案。解考慮對于p和在輸入符號為0時的狀況，在這類狀況下有5種可能使p和q沒法劃分：p和q在輸入0時同時遷徙到r(1種可能），或許p和q在輸入0時，都遷徙到p或（4種可能）。近似地，在輸入符號為1時，也有5種可能使p和q沒法劃分.假如再考慮r的遷徙，r的任何遷徙對問題沒有影響。于是r在輸入0和輸入1時各有3種可能的遷徙總合有3*3=9種遷徙。所以，總合有5*5*9=225個DFA，此中p和q是不行劃分的。三、證明：全部僅含有字符a，且長度為素數的字符串組成的會合不是正則語言.證明:用反證法。假定含有素數個a的字符串組成的會合是正則語言，則必存在一個DFA接受這一語言，設此DFA為D.因為D的狀態(tài)數有限，而素數有無窮多個，所以必存在兩個不同樣的素數p和（設〈qD的初始狀態(tài)出發(fā)，經過p個a和q個a后抵達同一狀態(tài)s，且s為接受狀態(tài)。因為DFA每一步的遷徙都是確立的，所以從狀態(tài)s出發(fā)，經過(q—）個a,只好抵達狀態(tài)s.考慮僅含有字母a，長度為p+p(q-p)的字符串T.T從初始狀態(tài)出發(fā)，經過p個a抵達狀態(tài)s，再經過(q-p）個a仍舊抵達s；相同，經過（q-p)個a后仍舊抵達s.所以，從初始狀態(tài)出發(fā)，經過p+p（—p）個a后必然抵達狀態(tài)s。因為p+p（—p)=p（—p+1)是合數，而s為接受狀態(tài)，因此得出矛盾。原命題得證.~\(≧▽≦（≧▽≦)/～～（≧▽≦)/~～\(≧▽≦）/～～（≧▽≦）/～~\(≧▽≦)/～～\(≧▽≦)/~4計算機科學系2010春天學期（≧▽≦）/～《編譯原理》第四次作業(yè)參照答案一、用上下文沒關文法描繪以下語言：1.定義在字母表={a,b｝上，全部首字符和尾字符相同的非空字符串。SaTa｜bTb|a｜bTaT｜bT|?說明：。用T來產生定義在字母表={a,b｝上的隨意字符串；。注意不要漏了單個a和單個b的狀況。2.L=｛0ij|ij2i且i0}。S0S1｜0S11|?3.定義在字母表｛0,1}上，全部含有相同個數的0和1的字符串（包含空串）.S0S1｜1S0|SS|?思路:分兩種狀況考慮。1)假如首尾字母不同樣，那么這一字符串去掉首尾字母仍應當屬于我們要定義的語言所以有S0S1｜1S0；2)假如首尾字母相同，那么這一字符串必定能夠分紅兩部分，每一部分都屬于我們要定義的語言，所以有SSS。二、考慮以下文法：SaABeAAbc|bBd1.用最左推導(leftmostderivation）推導出句子abbcde。S==〉aABe==>aAbcBe==〉abbcBe==>abbcde2.用最右推導（rightmostderivation）推導出句子abbcde.S==〉aABe==〉aAde==>aAbcde==>abbcde3.畫出句子abbcde對應的解析樹（parsetree三、考慮以下文法:SaSbSaSS1.這一文法產生什么語言（用自然語言描繪）？全部n個a后緊接m個，且n>=m的字符串.2.證明這一文法是二義的.對于輸入串aab，有以下兩棵不同樣的解析樹5計算機科學系2010春天學期3.寫出一個新的文法，要求新文法無二義且和上述文法產生相同的語言.答案一:SaSb｜TTaT｜答案二：STS’TaT|’aSb|（≧▽≦)/～（≧▽≦）/~～（≧▽≦）/～（≧▽≦)/~～\(≧▽≦）/～～\(≧▽≦）/～~\(≧▽≦)/～《編譯原理》第五次作業(yè)參照答案一、考慮以下文法：SaTUV|bVTU|UUU|bVV|cV寫出每個非終端符號的FIRST集和集。FIRST（S)=｛a,b｝FIRST(T)=｛，｝FIRST(U）={，b}FIRST（V)={c}FOLLOW(S)=｛＄｝FOLLOW(T）={b，c,＄}FOLLOW（U)=｛b,c,＄｝FOLLOW（），c,＄}二、考慮以下文法：S(L）｜aL，S｜S1.除去文法的左遞歸.S（L)|aLSL’L',SL'｜2.結構文法的LL(1)解析表.FIRST(S）=｛‘，(a’FIRST（L)=,‘’)={‘,’FOLLOW（）={’,,FOLLOW(L)={‘’){NON—TERMINALINPUTSYMBOL（)a，$6計算機科學系2010春天學期SS(L)SaLLSL'LSL’’L'’,SL’3.對于句子(a,（a,a,給出語法解析的詳盡過程（參照課本228頁的圖。21MATCHEDSTACKINPUTACTIONS$（a，（a，a))＄（）＄(a，（a,a）)＄outputS(L）(L)$a,(a,a）)$（SL')$a，(a，a))$outputLSL'（aL)$a,(a，a）)$outputSa（a,（a,a$（a,SL$,(a,a)）$outputL'，SL’(a，SL)＄（a，a$（a,(L）(a，a）)$outputS(L）（，(））$a，a$(a，(SL')L')$a,a))$outputLSL’(a,(aLa，a)）＄outputSa（a,（aL')＄,a(a，(a，SLL'）＄,a）)$outputL',SL’（，(a，SLL')＄a)）＄（a,（，aLL'）$a）)$outputSa（，(a,a）＄）)＄(a,（a,a）＄)）＄outputL’(a,(a,a)）＄（a,(a,a)）$）＄outputL’(a，a)）$＄三、考慮以下文法：SaSbS|bSaS|這一文法是不是LL(1）文法？給出原因.這一文法不是LL（1）文法，因為S有產生式S，但FIRST(S）={a，b，},FOLLOW（）=｛，b}，因此FIRST（S)∩FOLLOW（）≠。依據文法的定義知這一文法不是LL(1）文法.～（≧▽≦）/~～（≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦)/～～\(≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦）/~~\(≧▽≦)/~《編譯原理》第六次作業(yè)參照答案一、考慮以下文法：(0)’E(1）EE+T(2）ET(3)TTF(4）TF（5)F＊7計算機科學系2010春天學期（6)Fa(7)Fb。寫出每個非終端符號的FIRST集和FOLLOW集。FIRST(E)=FIRST（E)=FIRST(T)=FIRST(F=｛a,b}FOLLOW(E={$｝FOLLOW(E）={+,$}FOLLOW（T)={+，＄，a,b｝FOLLOW（）=｛+,＊，$，a,｝2.結構鑒識這一文法全部活前綴（viableprefixes）的LR(0）自動機（參照課本4.6。2節(jié)圖4.313.結構這一文法的解析表（參照課本節(jié)圖。37STATEACTIONGOTOab+＊$ETF0s4s51231s6accept2s4s5r2r273r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r174.給出解析器鑒識輸入串a+ab*的過程（參照課本節(jié)圖4.38)8計算機科學系2010春天學期STACKSYMBOLSINPUTACTION（）0a+ab*$shift(2）04a+ab＊$reducebyFa（）03F＊＄reducebyTF（4)02T＊＄reducebyET（5)01E＊＄shift(6）016E+ab＊＄shift(7）0164E+ab*$reducebyFa(8)0163E+Fb＊$reducebyTF(9)0169E+T＊＄shift(10）01695E+Tb＊$reducebyFb(11)01697E+TF＊＄shift（12）016978E+TF＊＄reducebyFF*（13）01697E+TF$reducebyTTF(14)0169E+T$reducebyEE+T（15）01E$accept～\(≧▽≦（≧▽≦）/~～\(≧▽≦）/～～（≧▽≦）/～～\(≧▽≦）/～～\(≧▽≦）（≧▽≦）/～～（≧▽≦)/～《編譯原理》第八次作業(yè)參照答案一、考慮以下語法制導定義(SyntaxDirectedDefinition）:語法例則語義規(guī)則SABCD。val=A.val+B.val+。val+。valAgBaA。val=B。val*5B1b。val=B1。val＊2BbB.val=2C1cC.val=.val*3Cc。val=3DdD。val=1對于輸入串gbbabbccd結構帶說明的解析樹（annotatedparsetree）.最后答案:34二、以下文法定義了二進制浮點數常量的語法例則：SL.L|LLLB|BB0｜1試給出一個S屬性的語法制導定義其作用是求出該二進制浮點數的十進制值并寄存在開始符號S有關系的一個綜合屬性value中。比方對于輸入串101.101的value屬性值結果應當是5.625定義時不得改寫文法！拜見05級期末考答案.9計算機科學系2010春天學期三