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

1、優(yōu)質(zhì)參考文檔?編譯原理?第一次作業(yè)參考答案以下正那么表達(dá)式定義了什么語(yǔ)言用盡可能簡(jiǎn)短的自然語(yǔ)言描述？1. bRabRabRR所有含有偶數(shù)個(gè) a的由a和b組成的字符串.2. cRaa|cRba|b|cR|cRbb|cRa a|b|cR答案一：所有至少含有1個(gè)a和1個(gè)b的由a，b和c組成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c組成的字符串.說(shuō)明：答案一要比答案二更好，因?yàn)橛米匀徽Z(yǔ)言描述是為了便于和非專業(yè)的人員交流，而非專業(yè)人員很可 能不知道什么是“子序列，所以相比較而言，答案一要更“自然設(shè)字母表 號(hào)a,b，用正那么表達(dá)式只使用a, b, ；, | , R, +,?描述以下語(yǔ)言

2、：1. 不包含子串a(chǎn)b的所有字符串.bRaR2. 不包含子串a(chǎn)bb的所有字符串.bRab?R3. 不包含子序列abb的所有字符串.bRaRb?aR注意：關(guān)于子串substring和子序列subsequence的區(qū)別可以參考課本第1佃頁(yè)方框中的內(nèi)容.仝仝仝/仝/仝/仝/仝/仝?編譯原理?第二次作業(yè)參考答案考慮以下NFA1. 這一 NFA接受什么語(yǔ)言用自然語(yǔ)言描述？所有只含有字母 a和b，并且a出現(xiàn)偶數(shù)次或b出現(xiàn)偶數(shù)次的字符串2. 構(gòu)造接受同一語(yǔ)言的 DFA.答案一直接構(gòu)造通常得到這一答案：優(yōu)質(zhì)參考文檔start正那么語(yǔ)言補(bǔ)運(yùn)算3. 畫(huà)出一個(gè)DFA該DFA恰好識(shí)別所有不含 011子串的所有二進(jìn)制串

3、start0,1 J1. 畫(huà)出一個(gè)DFA該DFA恰好識(shí)別所有不含 011子串的所有二進(jìn)制串規(guī)律：構(gòu)造語(yǔ)言L的補(bǔ)語(yǔ)言L的DFA可以先構(gòu)造出接受 L的DFA再把這一 DFA的接受狀態(tài)改為非接受 狀態(tài)，非接受狀態(tài)改為接受狀態(tài)，就可以得到識(shí)別L的DFA.說(shuō)明：在上述兩題中的 D狀態(tài)，無(wú)論輸入什么符號(hào)， 都不可能再到達(dá)接受狀態(tài)，這樣的狀態(tài)稱為“死狀態(tài).在畫(huà)DFA時(shí)，有時(shí)為了簡(jiǎn)明起見(jiàn)，“死狀態(tài)及其相應(yīng)的弧(上圖中的綠色局部)也可不畫(huà)出2. 再證明：對(duì)任一正那么表達(dá)式R, 定存在另一正那么表達(dá)式R，使得L(R)是L(R)的補(bǔ)集.證明：根據(jù)正那么表達(dá)式與 DFA的等價(jià)性，一定存在識(shí)別語(yǔ)言 L(R)的DFA.設(shè)

4、這一 DFA為M那么將M的所有接 受狀態(tài)改為非接受狀態(tài)， 所有非接受狀態(tài)改為接受狀態(tài)， 得到新的DFAIM .易知M識(shí)別語(yǔ)言L(R)的補(bǔ)集. 再由正那么表達(dá)式與 DFA的等價(jià)性知必存在正那么表達(dá)式 R,使得L(R)是L(R)的補(bǔ)集.設(shè)有一門小小語(yǔ)言僅含 z、o、/ (斜杠)3個(gè)符號(hào)，該語(yǔ)言中的一個(gè)注釋由/ o開(kāi)始、以0/結(jié)束，并且注釋禁止嵌套1. 請(qǐng)給出單個(gè)正那么表達(dá)式，它僅與一個(gè)完整的注釋匹配，除此之外不匹配任何其他串書(shū)寫(xiě)正那么表達(dá)式時(shí)，要求僅使用最根本的正那么表達(dá)式算子；，|，R, +,?.參考答案一：/ooRz|/Ro+/思路：根本思路是除了最后一個(gè)0/，在注釋中不能出現(xiàn) 0后面緊跟著/

5、的情況；還有需要考慮的是最后一個(gè)0/之前也可以出現(xiàn)假設(shè)干個(gè)0.參考答案二梁曉聰、梁勁、梁偉斌等人提供：/0/Rz/R|oRo/2. 給出識(shí)別上述正那么表達(dá)式所定義語(yǔ)言確實(shí)定有限自動(dòng)機(jī) DFA .你可根據(jù)問(wèn)題直接構(gòu)造DFA不必運(yùn)用機(jī)械的算法從上一小題的正那么表達(dá)式轉(zhuǎn)換得到DFA.start仝/仝/仝/仝仝仝仝仝?編譯原理?第三次作業(yè)參考答案考慮以下DFA的狀態(tài)遷移表，其中 0, 1為輸入符號(hào)，AH代表狀態(tài):01ABABACCDBDDAEDFFGEGFGHGD其中A為初始狀態(tài)，D為接受狀態(tài)，請(qǐng)畫(huà)出與此 DFA等價(jià)的最小DFA并在新的DFA狀態(tài)中標(biāo)明它對(duì)應(yīng)的原DFA狀態(tài)的子集.startB00EDH

6、1說(shuō)明：有些同學(xué)沒(méi)有畫(huà)出狀態(tài)H,因?yàn)闊o(wú)法從初始狀態(tài)到達(dá)狀態(tài)H.從實(shí)用上講，這是沒(méi)有問(wèn)題的.不過(guò)，如果根據(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)與本問(wèn)題無(wú) 關(guān).輸入符號(hào)只有0和1.這樣的DFA總共有729種不同的狀態(tài)遷移函數(shù)，因?yàn)閷?duì)于每一狀態(tài)和每一輸入符號(hào)， 可能遷移到3個(gè)狀態(tài)中的一個(gè)，所以總共有3A6=729種可能.在這729個(gè)DFA中，有多少個(gè)p和q是不可區(qū)分的indistinguishable ?解釋你的答案.解：考慮對(duì)于p和q,在輸入符號(hào)為0時(shí)的情況，在這種情況下有5種可能使p和q無(wú)法區(qū)分：p和

7、q在輸入0時(shí)同時(shí)遷移到r 1種可能，或者p和q在輸入0時(shí)，都遷移到p或q 4種可能.類似地，在輸入符號(hào)為 1時(shí)，也有5種可能使p和q無(wú)法區(qū)分.如果再考慮r的遷移，r的任何遷移對(duì)問(wèn)題沒(méi)有影響.于是r在輸入0和輸入1時(shí)各有3種可能的遷移，總共有3R3=9種遷移.因此，總共有 5R5R9=225個(gè)DFA,其中p和q是不可區(qū)分的.三、證明：所有僅含有字符a，且長(zhǎng)度為素?cái)?shù)的字符串組成的集合不是正那么語(yǔ)言證明：用反證法假設(shè)含有素?cái)?shù)個(gè)a的字符串組成的集合是正那么語(yǔ)言，那么必存在一個(gè)DFA接受這一語(yǔ)言，設(shè)此DFA為D.由于D的狀態(tài)數(shù)有限，而素?cái)?shù)有無(wú)限多個(gè)，所以必存在兩個(gè)不同的素?cái)?shù)p和q 設(shè)paABe=aAbc

8、Be=abbcBe=abbcde2. 用最右推導(dǎo)rightmostderivation推導(dǎo)出句子 abbcde. S=aABe=aAde=aAbcde=abbcde3. 畫(huà)出句子abbcde對(duì)應(yīng)的分析樹(shù)parsetree.三、考慮以下文法：S aSbS aSSb1. 這一文法產(chǎn)生什么語(yǔ)言用自然語(yǔ)言描述？所有n個(gè)a后緊接m個(gè)b,且n=m的字符串.2. 證明這一文法是二義的.對(duì)于輸入串a(chǎn)ab,有如下兩棵不同的分析樹(shù)3. 寫(xiě)出一個(gè)新的文法, 答案一：S aSb|TT aT| ；答案二：S TST aT| ；S aSb| ;(仝)/(仝(仝(仝(仝)/(仝)/(仝)/?編譯原理?第五次作業(yè)參考答案考慮

9、以下文法：S aTUV|bVT U|UUU |bVV |cV寫(xiě)出每個(gè)非終端符號(hào)的FIRST集和FOLLOW集.FIRST(S)=a,bFIRST(T)?bFIRST(U)=?,bFIRST(V)=?c FOLLOW(S)=$FOLLOW(T)=b,c,$FOLLOW(U)=b,c,$FOLLOW(V)=b,c,$ 考慮以下文法：S (L)|aL L,S|S1. 消除文法的左遞歸.S (L)|aL SLL ,SL| ；2. 構(gòu)造文法的LL(1分析表.FIRST(S)= ( , a FIRST(L)=, a FIRST(L )=,FOLLOW(S)= :,$) FOLLOW(L)= ) FOLLO

10、W(L )=) NONTERMINALINPUTSRMBOL()a,$SS (L)1S aLL SLL SLLL ,SL3.對(duì)于句子(a,(a,a)，給出語(yǔ)法分析的詳細(xì)過(guò)程(參照課本228頁(yè)的圖).MATCHEDSTACKINPUTACTIONS$(a,(a,a)$(L)$(a,(a,a)$outputs (L)(L)$a,(a,a)$(SL)$a,(a,a)$outputL SL(aL)$a,(a,a)$outputS a(aL)$,(a,a)$(a,SL)$,(a,a)$outputL ,SL(a,SL)$(a,a)$(a,(L)L)$(a,a)$outputs (L)(a,(L)L)$a

11、,a)$(a,(SL)L)$a,a)$outputL SL(a,(aL)L)$a,a)$outputS a(a,(aL)L)$,a)$(a,(a,SL)L)$,a)$outputL ,SL(a,(a,SL)L)$a)$(a,(a,aL)L)$a)$outputS a(a,(a,aL)L)$)$(a,(a,a)L)$)$outputL z(a,(a,a)L)$)$(a,(a,a)$)$outputL z(a,(a,a)$二、考慮以下文法：S aSbS|bSaS| ；這一文法是否是 LL1文法？給出理由.這一文法不是 LL1文法，因?yàn)?S有產(chǎn)生式 S ；，但 FIRSTS=a,b, FOLLOWS

12、=a,b因而 FIRSTS|P FOLLOWS .根據(jù)LL1文法的定義知這一文法不是LL1文法.仝/仝/仝/仝/仝/仝/仝/仝/?編譯原理?第六次作業(yè)參考答案一、考慮以下文法：(O)EE(1)EE+TETTTFTF(5)FFRFaFb1. 寫(xiě)出每個(gè)非終端符號(hào)的FIRST集和FOLLOW集.FIRST(=FIRST(E)=FIRST(T)=FIRST(F)=a,b FOLLOW(E)=$FOLLOW(E)=+,$FOLLOW(T)=+,$,a,bFOLLOW(F)=+,R,$,a,b2. 構(gòu)造識(shí)別這一文法所有活前綴(viableprefiRes)的LR(0) 自動(dòng)機(jī)(參照課本 462節(jié)圖4.31

13、 ).優(yōu)質(zhì)參考文檔io ETE E?E+T E?T T?TF T?F F?F* F夕a F?b“ IlE*T*FF?F步FF?bETEE9E+TacceptabF沁15FTbTTFFTF片12bTTTFF9F*118FTF札EYETTFF?F*F?b19E9E-TT?TFT?FF?F*F?a 16F?b3. 構(gòu)造這一文法的 SLR分析表參照課本 463節(jié)圖.STATEACTIONGOTOab+R$ETF0s4s512p 3 n1s6accept2s4s5r2r273P r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s

14、4s5r1r174.給出SLR分析器識(shí)別輸入串 a+abR的過(guò)程參照課本 464節(jié)圖STACKSRMBOLSINPUTACTION(1)0a+abR$shift(2)04a+abR$reducebRF a(3)03F+abR$reducebRT F(4)02T+abR$reducebRE T(5)01r e+abR$shift(6)016E+abR$shift(7)0164P E+abR$reducebRF a(8)0163r e+fbR$reducebRT F(9)0169E+TbR$shift(10)01695E+TbR$reducebRF b(11)01697E+TFR$shift(12

15、)016978E+TFR$reducebRF FR(13)01697r E+TF$reducebRT TF(14)0169E+T$reducebRE E+T(15)01E$accept話 W /話 W /仝 /仝/仝 /話 W /話 W /話 W /?編譯原理?第八次作業(yè)參考答案考慮以下語(yǔ)法制導(dǎo)定義SRntaRDirectedDefinition：語(yǔ)法規(guī)那么語(yǔ)義規(guī)那么S ABCDA gBaB B1bB.val=B1.valR2B bB.val=2C CicC.va=6valR3C cC.val=3D dD.val=1對(duì)于輸入串gbbabbccd構(gòu)造帶注釋的分析樹(shù)annotatedparsetr

16、ee.最終答案：34以下文法定義了二進(jìn)制浮點(diǎn)數(shù)常量的語(yǔ)法規(guī)那么：S L.L|LL LB|B B 0|1試給出一個(gè)S屬性的語(yǔ)法制導(dǎo)定義，其作用是求出該二進(jìn)制浮點(diǎn)數(shù)的十進(jìn)制值，并存放在開(kāi)始符號(hào) S相關(guān)聯(lián)的一個(gè)綜合屬性 value 中。例如，對(duì)于輸入串 101.101 , S的value 屬性值結(jié)果應(yīng)該是 。要求在編寫(xiě)語(yǔ) 法制導(dǎo)定義時(shí)，不得改寫(xiě)文法！參見(jiàn)05級(jí)期末考答案.優(yōu)質(zhì)參考文檔答案貝注意這類題口通常存在名種合理的警案u在語(yǔ)法制導(dǎo)定文中，B的屬性值“丄晦記錄B柞齒0或1本9的值：L有3個(gè)屬性值Il jitegzsal 記錄L柞為整數(shù)局部時(shí)的值 T fldlCt iiDTL 記錄L柞為小數(shù)局部時(shí)的

17、值.length 記最L作為少數(shù)9!分吋的性度、H便訂算B向右增t&BJ fraction的值語(yǔ)法觀那么語(yǔ)義觀那么SLj T RS .vaIh* 二 Lt - integral + L2. fractionT LS vi 1 u.5 = X * i ntegralLf LiBL , integral 二 Ll . int：ei呂 1 * 2+ B valueIj . length = Li . length 十 1L- frACtion = Li - fraction + B. value / 21-UbLt BL int&gral - E* valueL length = 1* 上一工 _ 5 一一Kg _r_ -二 f c 匸 * b-1 ii hL . iJzactiOEl B ./ ZB 0E . vlIu.* - 1R評(píng)分標(biāo)準(zhǔn)習(xí)產(chǎn)生式1和2的語(yǔ)義動(dòng)作有錯(cuò)那么每個(gè)錯(cuò)碾扣24分；產(chǎn)生式3和4的語(yǔ)義動(dòng)作有錯(cuò)那么每個(gè) 錯(cuò)謀扣4-5企 產(chǎn)生式5和6的說(shuō)義功作有錯(cuò)那么毎個(gè)錯(cuò)泯抑2分&、選做課本 和 中的一題.產(chǎn)生式語(yǔ)義規(guī)那么E E1+TE.eRpr=E1.eRpr+E.op=+E TT T1RFif(T1.op= +if(F.op=+)T.eRp