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

1、編譯原理第一次作業(yè)參考答案 一、 下列正則表達(dá)式定義了什么語言（用盡可能簡短的自然語言描述）？1. b*(ab*ab*)*所有含有偶數(shù)個(gè)a的由a和b組成的字符串.2. c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1個(gè)a和1個(gè)b的由a，b和c組成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c組成的字符串.說明：答案一要比答案二更好，因?yàn)橛米匀徽Z言描述是為了便于和非專業(yè)的人員交流，而非專業(yè)人員很可能不知道什么是“子序列”，所以相比較而言，答案一要更“自然”.二、 設(shè)字母表=a,b，用正則表達(dá)式（只使用a，b，e，|，*，+，？

2、）描述下列語言：1. 不包含子串a(chǎn)b的所有字符串.b*a*2. 不包含子串a(chǎn)bb的所有字符串.b*(ab?)*3. 不包含子序列abb的所有字符串.b*a*b?a*注意：關(guān)于子串（substring）和子序列（subsequence）的區(qū)別可以參考課本第119頁方框中的內(nèi)容.()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/編譯原理第二次作業(yè)參考答案 一、 考慮以下NFA：1. 這一NFA接受什么語言（用自然語言描述）？所有只含有字母a和b，并且a出現(xiàn)偶數(shù)次或b出現(xiàn)偶數(shù)次的字符串.2. 構(gòu)造接受同一語言的DFA.答案一（直接構(gòu)造通常得到這一答案）：答案二（由NFA構(gòu)造DFA得到這一

3、答案）：二、 正則語言補(bǔ)運(yùn)算3. 畫出一個(gè)DFA，該DFA恰好識(shí)別所有不含011子串的所有二進(jìn)制串.1. 畫出一個(gè)DFA，該DFA恰好識(shí)別所有不含011子串的所有二進(jìn)制串. 規(guī)律：構(gòu)造語言L的補(bǔ)語言L的DFA，可以先構(gòu)造出接受L的DFA，再把這一DFA的接受狀態(tài)改為非接受狀態(tài)，非接受狀態(tài)改為接受狀態(tài)，就可以得到識(shí)別L的DFA.說明：在上述兩題中的D狀態(tài)，無論輸入什么符號，都不可能再到達(dá)接受狀態(tài)，這樣的狀態(tài)稱為“死狀態(tài)”. 在畫DFA時(shí)，有時(shí)為了簡明起見，“死狀態(tài)”及其相應(yīng)的?。ㄉ蠄D中的綠色部分）也可不畫出.2. 再證明：對任一正則表達(dá)式R，一定存在另一正則表達(dá)式R，使得L(R)是L(R)的補(bǔ)集

4、.證明：根據(jù)正則表達(dá)式與DFA的等價(jià)性，一定存在識(shí)別語言L(R)的DFA. 設(shè)這一DFA為M，則將M的所有接受狀態(tài)改為非接受狀態(tài)，所有非接受狀態(tài)改為接受狀態(tài)，得到新的DFA M. 易知M識(shí)別語言L(R)的補(bǔ)集. 再由正則表達(dá)式與DFA的等價(jià)性知必存在正則表達(dá)式R，使得L(R)是L(R)的補(bǔ)集.三、 設(shè)有一門小小語言僅含z、o、/（斜杠）3個(gè)符號，該語言中的一個(gè)注釋由/o開始、以o/結(jié)束，并且注釋禁止嵌套.1. 請給出單個(gè)正則表達(dá)式，它僅與一個(gè)完整的注釋匹配，除此之外不匹配任何其他串. 書寫正則表達(dá)式時(shí)，要求僅使用最基本的正則表達(dá)式算子（e，|，*，+，？）.參考答案一：/o(o*z|/)*o+

5、/思路：基本思路是除了最后一個(gè)o/，在注釋中不能出現(xiàn)o后面緊跟著/的情況；還有需要考慮的是最后一個(gè)o/之前也可以出現(xiàn)若干個(gè)o.參考答案二（梁曉聰、梁勁、梁偉斌等人提供）：/o/*(z/*|o)*o/2. 給出識(shí)別上述正則表達(dá)式所定義語言的確定有限自動(dòng)機(jī)（DFA）. 你可根據(jù)問題直接構(gòu)造DFA，不必運(yùn)用機(jī)械的算法從上一小題的正則表達(dá)式轉(zhuǎn)換得到DFA.()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 編譯原理第三次作業(yè)參考答案 一、 考慮以下DFA的狀態(tài)遷移表，其中0，1為輸入符號，AH代表狀態(tài)：01ABABACCDBDDAEDFFGEGFGHGD其中A為初始狀態(tài)，D為接受狀態(tài)，請畫

6、出與此DFA等價(jià)的最小DFA，并在新的DFA狀態(tài)中標(biāo)明它對應(yīng)的原DFA狀態(tài)的子集. 說明：有些同學(xué)沒有畫出狀態(tài)H，因?yàn)闊o法從初始狀態(tài)到達(dá)狀態(tài)H. 從實(shí)用上講，這是沒有問題的. 不過，如果根據(jù)算法的步驟執(zhí)行，最后是應(yīng)該有狀態(tài)H的.二、 考慮所有含有3個(gè)狀態(tài)（設(shè)為p，q，r）的DFA. 設(shè)只有r是接受狀態(tài). 至于哪一個(gè)狀態(tài)是初始狀態(tài)與本問題無關(guān). 輸入符號只有0和1. 這樣的DFA總共有729種不同的狀態(tài)遷移函數(shù)，因?yàn)閷τ诿恳粻顟B(tài)和每一輸入符號，可能遷移到3個(gè)狀態(tài)中的一個(gè)，所以總共有36=729種可能. 在這729個(gè)DFA中，有多少個(gè)p和q是不可區(qū)分的（indistinguishable）？解釋你

7、的答案.解：考慮對于p和q，在輸入符號為0時(shí)的情況，在這種情況下有5種可能使p和q無法區(qū)分：p和q在輸入0時(shí)同時(shí)遷移到r（1種可能），或者p和q在輸入0時(shí)，都遷移到p或q（4種可能）. 類似地，在輸入符號為1時(shí)，也有5種可能使p和q無法區(qū)分. 如果再考慮r的遷移，r的任何遷移對問題沒有影響. 于是r在輸入0和輸入1時(shí)各有3種可能的遷移，總共有3*3=9種遷移. 因此，總共有5*5*9=225個(gè)DFA，其中p和q是不可區(qū)分的.三、 證明：所有僅含有字符a，且長度為素?cái)?shù)的字符串組成的集合不是正則語言.證明：用反證法.假設(shè)含有素?cái)?shù)個(gè)a的字符串組成的集合是正則語言，則必存在一個(gè)DFA接受這一語言，設(shè)此

8、DFA為D. 由于D的狀態(tài)數(shù)有限，而素?cái)?shù)有無限多個(gè)，所以必存在兩個(gè)不同的素?cái)?shù)p和q（設(shè)p aABe = aAbcBe = abbcBe = abbcde2. 用最右推導(dǎo)（rightmost derivation）推導(dǎo)出句子abbcde.S = aABe = aAde = aAbcde = abbcde3. 畫出句子abbcde對應(yīng)的分析樹（parse tree）.三、 考慮以下文法：S aSbS aSS e1. 這一文法產(chǎn)生什么語言（用自然語言描述）？所有n個(gè)a后緊接m個(gè)b，且n=m的字符串.2. 證明這一文法是二義的.對于輸入串a(chǎn)ab，有如下兩棵不同的分析樹3. 寫出一個(gè)新的文法，要求新文法

9、無二義且和上述文法產(chǎn)生相同的語言.答案一：S aSb | TT aT | e答案二：S TST aT | eS aSb | e()/ ()/ ()/ ()/ ()/ ()/ ()/編譯原理第五次作業(yè)參考答案 一、 考慮以下文法：S aTUV | bVT U | UUU e | bVV e | cV寫出每個(gè)非終端符號的FIRST集和FOLLOW集.FIRST(S)=a, b FIRST(T)=, b FIRST(U)= , b FIRST(V)=, cFOLLOW(S)=$ FOLLOW(T)= b, c, $ FOLLOW(U)= b, c, $ FOLLOW(V)=b, c , $二、 考慮

10、以下文法：S (L) | aL L, S | S1. 消除文法的左遞歸.S (L) | aL SLL ,SL | e2. 構(gòu)造文法的LL(1)分析表.FIRST(S) = (, a FIRST(L) = (, a FIRST(L) = , eFOLLOW(S) = $, , ) FOLLOW(L) = ) FOLLOW(L) = )NON-TERMINALINPUT SYMBOL()a,$SS (L)S aLL SLL SLLL eL ,SL3. 對于句子(a, (a, a)，給出語法分析的詳細(xì)過程（參照課本228頁的圖4.21）.MATCHEDSTACKINPUTACTIONS$(a, (a

11、, a)$(L)$(a, (a, a)$output S (L)(L)$a, (a, a)$(SL)$a, (a, a)$output L SL(aL)$a, (a, a)$output S a(aL)$, (a, a)$(a,SL)$, (a, a)$output L ,SL(a,SL)$(a, a)$(a,(L)L)$(a, a)$output S (L)(a,(L)L)$a, a)$(a,(SL)L)$a, a)$output L SL(a,(aL)L)$a, a)$output S a(a,(aL)L)$, a)$(a,(a,SL)L)$, a)$output L ,SL(a,(a,S

12、L)L)$a)$(a,(a,aL)L)$a)$output S a(a,(a,aL)L)$)$(a,(a,a)L)$)$output L e(a,(a,a)L)$)$(a,(a,a)$)$output L e(a,(a,a)$三、 考慮以下文法：S aSbS | bSaS | e這一文法是否是LL(1)文法？給出理由.這一文法不是LL(1)文法，因?yàn)镾有產(chǎn)生式S e，但FIRST(S) = a, b, e， FOLLOW(S) = a, b，因而FIRST(S)FOLLOW(S). 根據(jù)LL(1)文法的定義知這一文法不是LL(1)文法.()/ ()/ ()/ ()/ ()/ ()/ ()/ (

13、)/編譯原理第六次作業(yè)參考答案 一、 考慮以下文法：(0) E E(1) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b1.寫出每個(gè)非終端符號的FIRST集和FOLLOW集.FIRST(E)= FIRST(E)= FIRST(T)= FIRST(F)=a, bFOLLOW(E)=$ FOLLOW(E)=+, $ FOLLOW(T)=+, $, a, b FOLLOW(F)= +, *, $, a, b2.構(gòu)造識(shí)別這一文法所有活前綴（viable prefixes）的LR(0)自動(dòng)機(jī)（參照課本節(jié)圖4.31）.3.構(gòu)造這一文法的SLR分析表（參照

14、課本節(jié)圖4.37）.STATEACTIONGOTOab+*$ETF0s4s51231s6accept2s4s5r2r273r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r174.給出SLR分析器識(shí)別輸入串a(chǎn)+ab*的過程（參照課本節(jié)圖4.38）STACKSYMBOLSINPUTACTION(1)0a+ab*$shift(2)04a+ab*$reduce by Fa(3)03F+ab*$reduce by TF(4)02T+ab*$reduce by ET(5)01E+ab*$shift(6)016E+ab

15、*$shift(7)0164E+ab*$reduce by Fa(8)0163E+Fb*$reduce by TF(9)0169E+Tb*$shift(10)01695E+Tb*$reduce by Fb(11)01697E+TF*$shift(12)016978E+TF*$reduce by FF*(13)01697E+TF$reduce by TTF(14)0169E+T$reduce by EE+T(15)01E$accept()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 編譯原理第八次作業(yè)參考答案 一、 考慮以下語法制導(dǎo)定義（Syntax Directed Defini

16、tion）：語法規(guī)則語義規(guī)則S ABCDS.val = A.val + B.val + C.val + D.valA gBaA.val = B.val * 5B B1bB.val = B1.val * 2B bB.val = 2C C1cC.val = C1.val * 3C cC.val = 3D dD.val = 1對于輸入串gbbabbccd構(gòu)造帶注釋的分析樹（annotated parse tree）.最終答案：34二、 以下文法定義了二進(jìn)制浮點(diǎn)數(shù)常量的語法規(guī)則： S L.L | LL LB | BB 0 | 1試給出一個(gè)S屬性的語法制導(dǎo)定義，其作用是求出該二進(jìn)制浮點(diǎn)數(shù)的十進(jìn)制值，并存

17、放在開始符號S相關(guān)聯(lián)的一個(gè)綜合屬性value中。例如，對于輸入串101.101，S的value屬性值結(jié)果應(yīng)該是5.625。要求在編寫語法制導(dǎo)定義時(shí)，不得改寫文法！參見05級期末考答案.三、 選做課本Exercise和中的一題.產(chǎn)生式語義規(guī)則EE1+TE.expr = E1.expr + + + T.exprE.op = +ETE.expr = T.exprE.op = T.opTT1*Fif (T1.op = +) if (F.op = +) T.expr = ( + T1.expr + ) + * + ( + F.expr + )else T.expr = ( + T1.expr + ) + * + F.exprelse if (F.op = +) T.expr = T1.expr + * + ( + F.expr + )T.op = *T-FT.expr = F.exprT.op = F.opF (E)F.expr = E.exprF.op = E.opFletterF.expr = letter.lexvalF.op = n產(chǎn)生式語義規(guī)則EE1+TE.expr = E1.expr + + + T.exprE.