1、編譯原理第一次作業(yè)參考答案 一、 下列正則表達(dá)式定義了什么語言（用盡可能簡短的自然語言描述）？1. b*(ab*ab*)*所有含有偶數(shù)個a的由a和b組成的字符串.2. c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1個a和1個b的由a，b和c組成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c組成的字符串.說明：答案一要比答案二更好，因為用自然語言描述是為了便于和非專業(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ǔ)運算3. 畫出一個DFA，該DFA恰好識別所有不含011子串的所有二進(jìn)制串.1. 畫出一個DFA，該DFA恰好識別所有不含011子串的所有二進(jìn)制串. 規(guī)律：構(gòu)造語言L的補(bǔ)語言L的DFA，可以先構(gòu)造出接受L的DFA，再把這一DFA的接受狀態(tài)改為非接受狀態(tài)，非接受狀態(tài)改為接受狀態(tài)，就可以得到識別L的DFA.說明：在上述兩題中的D狀態(tài)，無論輸入什么符號，都不可能再到達(dá)接受狀態(tài)，這樣的狀態(tài)稱為“死狀態(tài)”. 在畫DFA時，有時為了簡明起見，“死狀態(tài)”及其相應(yīng)的弧（上圖中的綠色部分）也可不畫出.2. 再證明：對任一正則表達(dá)式R，一定存在另一正則表達(dá)式R'，使得L(R'

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

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

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

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

8、A接受這一語言，設(shè)此DFA為D. 由于D的狀態(tài)數(shù)有限，而素數(shù)有無限多個，所以必存在兩個不同的素數(shù)p和q（設(shè)p<q），使得從D的初始狀態(tài)出發(fā)，經(jīng)過p個a和q個a后到達(dá)同一狀態(tài)s，且s為接受狀態(tài). 由于DFA每一步的遷移都是確定的，所以從狀態(tài)s出發(fā)，經(jīng)過(q-p)個a，只能到達(dá)狀態(tài)s. 考慮僅含有字母a，長度為p+p(q-p)的字符串T. T從初始狀態(tài)出發(fā)，經(jīng)過p個a到達(dá)狀態(tài)s，再經(jīng)過(q-p)個a仍然到達(dá)s；同樣，經(jīng)過p(q-p)個a后仍然到達(dá)s. 因此，從初始狀態(tài)出發(fā)，經(jīng)過p+p(q-p)個a后必然到達(dá)狀態(tài)s. 由于p+p(q-p)=p(q-p+1)是合數(shù)，而s為接受狀態(tài)，因而得出矛盾.

9、 原命題得證.()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 編譯原理第四次作業(yè)參考答案 一、 用上下文無關(guān)文法描述下列語言：1. 定義在字母表=a, b上，所有首字符和尾字符相同的非空字符串.S à aTa | bTb | a | bT à aT | bT | 說明：1. 用T來產(chǎn)生定義在字母表=a, b上的任意字符串；2. 注意不要漏了單個a和單個b的情況.2. L=0i1j|ij2i且i0.S à 0S1 | 0S11 | 3. 定義在字母表=0, 1上，所有含有相同個數(shù)的0和1的字符串（包括空串）.S à 0S1 | 1S0 |

10、SS | 思路：分兩種情況考慮.1) 如果首尾字母不同，那么這一字符串去掉首尾字母仍應(yīng)該屬于我們要定義的語言，因此有S à 0S1 | 1S0；2) 如果首尾字母相同，那么這一字符串必定可以分成兩部分，每一部分都屬于我們要定義的語言，因此有S à SS.二、 考慮以下文法：S à aABeA à Abc|bB à d1. 用最左推導(dǎo)（leftmost derivation）推導(dǎo)出句子abbcde.S => aABe => aAbcBe => abbcBe => abbcde2. 用最右推導(dǎo)（rightmost deriv

11、ation）推導(dǎo)出句子abbcde.S => aABe => aAde => aAbcde => abbcde3. 畫出句子abbcde對應(yīng)的分析樹（parse tree）.三、 考慮以下文法：S à aSbS à aSS à e1. 這一文法產(chǎn)生什么語言（用自然語言描述）？所有n個a后緊接m個b，且n>=m的字符串.2. 證明這一文法是二義的.對于輸入串a(chǎn)ab，有如下兩棵不同的分析樹3. 寫出一個新的文法，要求新文法無二義且和上述文法產(chǎn)生相同的語言.答案一：S à aSb | TT à aT | e答案二：S &

12、#224; TST à aT | eS à aSb | e()/ ()/ ()/ ()/ ()/ ()/ ()/編譯原理第五次作業(yè)參考答案 一、 考慮以下文法：S à aTUV | bVT à U | UUU à e | bVV à e | cV寫出每個非終端符號的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 , $二

13、、 考慮以下文法：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 à

14、 ,SL3. 對于句子(a, (a, a)，給出語法分析的詳細(xì)過程（參照課本228頁的圖4.21）.MATCHEDSTACKINPUTACTIONS$(a, (a, 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,

15、(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,SL)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 | bSa

16、S | e這一文法是否是LL(1)文法？給出理由.這一文法不是LL(1)文法，因為S有產(chǎn)生式S à e，但FIRST(S) = a, b, e， FOLLOW(S) = a, b，因而FIRST(S)FOLLOW(S)Æ. 根據(jù)LL(1)文法的定義知這一文法不是LL(1)文法.()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/編譯原理第六次作業(yè)參考答案 一、 考慮以下文法：(0) E à E(1) E à E+T(2) E à T(3) T à TF(4) T à F(5) F à F*(6) F &#

17、224; a(7) F à b1.寫出每個非終端符號的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)造識別這一文法所有活前綴（viable prefixes）的LR(0)自動機(jī)（參照課本節(jié)圖4.31）.3.構(gòu)造這一文法的SLR分析表（參照課本節(jié)圖4.37）.STATEACTIONGOTOab+*$ETF0s4s51231s6accept2s4s5r2r273r4r4r

18、4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r174.給出SLR分析器識別輸入串a(chǎn)+ab*的過程（參照課本節(jié)圖4.38）STACKSYMBOLSINPUTACTION(1)0a+ab*$shift(2)04a+ab*$reduce by Fàa(3)03F+ab*$reduce by TàF(4)02T+ab*$reduce by EàT(5)01E+ab*$shift(6)016E+ab*$shift(7)0164E+ab*$reduce by Fàa(8)0163E+F

19、b*$reduce by TàF(9)0169E+Tb*$shift(10)01695E+Tb*$reduce by Fàb(11)01697E+TF*$shift(12)016978E+TF*$reduce by FàF*(13)01697E+TF$reduce by TàTF(14)0169E+T$reduce by EàE+T(15)01E$accept()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 編譯原理第八次作業(yè)參考答案 一、 考慮以下語法制導(dǎo)定義（Syntax Directed Definition）：語法規(guī)則語義

20、規(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)制浮點數(shù)常量的語法規(guī)則： S à L.L | LL à LB | BB à 0 | 1試給出一個S屬性的語法制導(dǎo)定義，其作用是求出該二進(jìn)制浮點數(shù)的十進(jìn)制值，并存放在開始符號S相關(guān)聯(lián)的一個綜合屬性value中。例如，對于輸入串101.101，S的value屬性值結(jié)果應(yīng)該是5.625。要求在編寫語法制導(dǎo)定義時，不得改寫文法！參見05級期末考答案.三、 選做課本Exercise和中的一題.產(chǎn)生式語義規(guī)則EàE1+TE.expr = E1.expr + + + T.exprE.op = +EàT