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

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