編譯原理復(fù)習(xí)題及答案(編輯修改稿)
2024-09-01 11:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ，b，d，e }T{b，d，ε}{e}H{d，ε}{e}由于predict（D→STe）∩predict（D→ε）={a}∩{ ，b ，d ，e }= predict（T→bH）∩predict（T→H）=∩{e }= predict（H→d）∩predict（H→ε）={ d }∩{ e }=所以該文法是LL(1)文法，LL(1)分析表如下表：aebdS→aD.D→STe→ε→ε→ε→εT→H.→bH→H.H→ε→d.6． 判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表?！ →aD D→STe|ε T→bM M→bH H→M|ε答：文法的 FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集S{a}.....{ ，b}D{a ，ε}{ ，b}T.....{e}....M.....{e}....H{b ，ε}{e}....由于predict（D→STe）∩predict（D→ε）={a}∩{ ，b}=predict（H→M）∩predict（H→ε）={ b }∩{ e }=所以該文法是LL(1)文法，LL(1)分析表如下表：aebS→aD.D→STe→ε→εT→bMM→bHH→ε→M.7． 某語(yǔ)言的拓廣文法G′為： (0) S′→S (1) S → Db|B (2) D → d|ε (3) B → Ba|ε證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G39。，增加產(chǎn)生式S39?！鶶在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目D →d 歸約項(xiàng)目D →和B →存在移進(jìn)歸約和歸約歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋?0) S39?！鶶(1) S → Db(2) S → B(3) D → d(4) D →ε(5) B → Ba(6) B →εG′的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖：由產(chǎn)生式知Follow(S)={} Follow(D)= Follow(B)= {a ,}在I0中:Follow(D) ∩nhcuj7d3={ b} ∩nhcuj7d3=Follow(B) ∩nhcuj7d3= { a ,} ∩nhcuj7d3=Follow(D) ∩ Follow(B)= ∩{a ,} =在I3中:Follow(S) ∩{a}={}∩{a}=所以在I0，I3中的移進(jìn)歸約和歸約歸約沖突可以由Follow集解決,所以G是SLR(1)文法, 構(gòu)造的SLR(1)分析表如下表：狀態(tài)ACTIONGOTObdaSDB0r4S4r6r61231acc2S53S6r24r35r16r5r58． 給出與正規(guī)式R＝（ab）*（a|b*）ba等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖9． 給出與正規(guī)式R＝（(ab)*|b）*（a|(ba)*）a 等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖10． 給出與正規(guī)式 R＝（aba）*（(ba)*|b）b等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖11． 將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態(tài){X,1,2}{1,2}..{1,2,3}{1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X123確定化后如下圖：12． 將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態(tài){X,0,1,3}{0,1,3}..{2,3,Y}..{1,3}....{2,Y}....{Y}......{0,1,3}{0,1,3}{1,3}.......{1,3}.......{2,3,Y}{2,3,Y}{Y}....{2,Y}..{Y}........X1234Y確定化后如下圖13． 某語(yǔ)言的拓廣文法G′為：(0) S′→T (1) T →aBd|ε(2) B →Tb|ε 證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G39。，增加產(chǎn)生式S39?！鶷 在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目T →aBd和歸約項(xiàng)目T →存在移進(jìn)歸約沖突，所以G不是LR(0)文法。 若產(chǎn)生式排序?yàn)椋?(0) S39?！鶷(1) T →aBd(2) T →ε (3) B →Tb(4) B →εG39。的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖所示：識(shí)別G′活前綴的DFA由產(chǎn)生式知：Follow(T)={,b} Follow(B)= nhcuj7d3在I0中： Follow(T) ∩{a}={ ，b} ∩{a}=在I2中：Follow(B) ∩{a}= nhcuj7d3 ∩{a}=Follow(T) ∩{a}={ ，b} ∩{a}=Follow(B) ∩ Follow(T) = nhcuj7d3∩{ ，b}=所以在I0，I2，中的移進(jìn)歸約和歸約歸約沖突可以由Follow集解決，所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabdTB0S2r2r211acc2S2r2r4r2433S54S6
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1