【正文】 第十一次作業(yè)：P194 1. 按照語法制導(dǎo)翻譯的一般原理，給出表達(dá)式(5*4+8)*2的語法樹各結(jié)點(diǎn)并注明語義值VAL。其中r1: SS(S) r2: SεLR(1)分析表如下所示：狀態(tài)ACTIONGOTO（）S0r2r211S2acc2r2r233S5S44r1r15r2r266S5S77r1r1分析符號(hào)串（（））步驟狀態(tài)棧符號(hào)棧輸入串分析動(dòng)作下一狀態(tài)00(())r2GOTO[0,S]=1101S(())S222012S(())r2GOTO[2,S]=330123S(S())S55401235S(S())r2GOTO[5,S]=65012356S(S(S))S7760123567S(S(S))r1GOTO[2,S]=370123S(S)S44801234S(S)r1GOTO[0,S]=1901Sacc成功P148 30. 給出如下文法： G1[S]: S∷＝aSbS | aS | c G2[S]: S∷＝aAa | aBb A∷＝x B∷＝x G3[S]: S∷＝aAa | aBb| bAb A∷＝x B∷＝x G4[S]: S∷＝aAa | aBb| bAb| bBa A∷＝x B∷＝x（1） 證明二義性文法G1[S]不是LR(0)文法；（2） 證明G2[S]是SLR(1)文法但不是LR(0)文法；（3） 證明G3[S]是LR(1)文法但不是SLR(1)文法；（4） 證明G4[S]是LR(1)文法但不是LALR文法。I9:A::= aAbI6: B::= dBb B ::= I4: A ::= ac B ::= Z Z::= d B::= daBb B ::= aaAb A ::= aA Z::= A成功P146 22. 設(shè)有文法G[Z]: Z∷＝A | BA∷＝aAb | cB∷＝aBb | d（1） 試構(gòu)造能識(shí)別此文法的全部活前綴DFA；（2） 試構(gòu)造LR(0)分析表；（3） 試分析符號(hào)串a(chǎn)acbb是否為此文法的句子。i?！?∨+i*i+i?！?] 和a的優(yōu)先關(guān)系＋*↑()if333133g222212根據(jù)=的優(yōu)先關(guān)系＋*↑()if333133g244414循環(huán)―＋*↑()if355155g244414＋*↑()if355155g246616＋*↑()if355177g246616最終結(jié)果：＋*↑()if355177g246616（3）+*↑()i)(↑*+i優(yōu)先函數(shù)為：＋*↑()if466199g358718（4）用優(yōu)先關(guān)系表分析字符串i+i*i↑i符號(hào)棧關(guān)系輸入串最左素短語＃f()g(i)i+i*i↑i＃if(i)g(+)+i*i↑ii＃∨f()g(+)+i*i↑i?！牛玣(+)g(i)i*i↑i?！牛玦f(i)g(*)*i↑ii＃∨＋∨f(+)g(*)*i↑i?！牛?f(*)g(i)i↑i?！牛?if(i)g(↑)↑ii?！牛?∨f(*)g(↑)↑i＃∨＋∨*∨↑f(↑)g(i)i?！牛?∨↑if(i)g()i?！牛?∨↑∨f(↑)g()∨↑∨?！牛?∨f(*)g)∨*∨?！牛舊(+)g()∨＋∨?！懦晒146 19. 證明下面文法不是算符優(yōu)先文法: S∷＝A[] | [A∷＝aA | B]B∷＝a證明：∵S→A[ A→aA∴a（2）用迭代法構(gòu)造優(yōu)先函數(shù)若R=S則f(R）=g(S)若R() i:=P145 13. [E]的優(yōu)先關(guān)系矩陣，來分析符號(hào)串b(((aa)a)a)b和((aa)a)。變量 。P145 12. ，確定全部?jī)?yōu)先關(guān)系：(a) E=+ +=T T=* *=F (=E E=) *( +F + I F* i* )+ T+ F+(b) 說明表=。FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=248。FIRST(T’)={+, , }}∩FIRST(ε)= 248。10aa, ba NFA狀態(tài)轉(zhuǎn)換圖解：設(shè)(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M：M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1]M ([0], a) =[0, 1] M ([0], b) =[1]S=[1]，Z={[0], [0, 1]}10abaa2b令[0, 1]=2，則其相應(yīng)的狀態(tài)轉(zhuǎn)換圖為：現(xiàn)在對(duì)該DFA進(jìn)行化簡(jiǎn)，先把狀態(tài)分為兩組：終態(tài)組 {0, 2} 和非終態(tài)組 {1}，易于發(fā)現(xiàn) {0, 2}不可以繼續(xù)劃分，因此化簡(jiǎn)后的狀態(tài)轉(zhuǎn)換圖如下：ab0, 21aP74 13. 構(gòu)造下列正規(guī)式的DFA： （1）b(a|b)*bab 此題的與P74第11題基本一樣，見上；P74 15. 用兩種方法將(NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z})，構(gòu)造相應(yīng)的DFA，其中：M (X, 0) = {Z} M (X, 1) = {X} M (Y, 0) = {X, Y}M (Y, 1) = Ф M (Z, 0) = {X, Z} M (Z, 1) = {Y}XZ101000Y0第一種方法：先畫出其狀態(tài)轉(zhuǎn)換圖，利用子集法：假設(shè)(DFA) M’=(K’, VT’, M’, S’, Z’)，其中K’={[X], [Y], [Z], [X,Y], [X, Z], [Y, Z], [X, Y, Z]}，VT’={0, 1}，M’的規(guī)則如下表：II0I1S0 1[X][Z][X]0 2 1[Y][X, Y]Ф1 3 Ф[Z][X, Z][Y]2 4 1[X, Y][X, Y, Z][X]3 6 0[X, Z][X, Z][X, Y]4 4 3[Y, Z][X, Y, Z][Y]5 6 1[X, Y, Z][X, Y, Z][X, Y]6 6 301100013001124, 60其中[Y, Z]為不可到達(dá)狀態(tài)，應(yīng)該刪去，所以S’={[X]}，Z’={[Z], [X, Z], [X, Y, Z]}，再進(jìn)行化簡(jiǎn)，發(fā)現(xiàn)4和6兩狀態(tài)等價(jià)，最后其DFA如下所示：XZ’101000Y0ZSεε第二種方法：先構(gòu)造其對(duì)應(yīng)的轉(zhuǎn)換系統(tǒng)：由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：II0I1S0 1{S, X}{Z, Z’}{X}0 1 2{Z, Z’}{X, Z, Z’}{Y}1 3 4{X}{Z, Z’}{X}2 1 2{X, Z, Z’}{X, Z, Z’}{X, Y}3 3 5{Y}{X, Y}Ф4 5 Ф{X, Y}{X, Y, Z, Z’}{X}5 6 2{X, Y, Z, Z’}{X, Y, Z, Z’}{X, Y}6 6 5141050001013, 610, 2先化簡(jiǎn)，分為非終態(tài)集 {2, 4, 5, 0} 和終態(tài)集 {6, 1, 3}，易于發(fā)現(xiàn)可劃分為{0, 2}，{1}，{3, 6}，{4}，{5}，其DFA如下所示：P74 16. 已知e1= (a|b)*，e2=(a*b*)*，試證明e1= e2。 M (B, b)=B M (B, b)=C M (B, c)=248。解：先求右線性文法S→cA A→bA A→a | aE其左線性文法G=（VN, VT, P, S）VN={A, S} VT={a, b, c}P: A→c A→Ab S→AaP74 10. 已知正規(guī)文法G = ({S, B, C}, {a, b, c}, P, S)，其中P內(nèi)包含如下產(chǎn)生式：S::=aS | aB ……①B::=bB | bC ……②C::=cC | c ……③ 請(qǐng)構(gòu)造一個(gè)等價(jià)的有窮自動(dòng)機(jī)。解：構(gòu)造一個(gè)如下的自動(dòng)機(jī)(DFA) M’， (DFA) M’={K, {a, b}, M’, S, Z}S的元素是[A] [B] [A, B]由于M（A, a）={A, B}，故有M’（[A], a）=[A, B]同樣 M’（[A]，b）=[B]M’（[B]，a）= 248。 M（Z，0）=248。由狀態(tài)圖可知只有eefe是該文法的合法句子。解 目標(biāo)= V1=V2=V3=(目標(biāo)= V1=V2=V3=)V1*=)V2*=)V3*=)(*目標(biāo)= V1=V2=iV3=i(目標(biāo)= V1=V2=V2+V3=V3+V3=(+V3=(+(目標(biāo)= V1=V1iV2= V1iV3= V1i(=V2i(=V2+V3i(=V2+( i(=V3+( i(=(+(i(目標(biāo)= V1=V1iV2= V2iV2= V2+V3iV2= V3+V3iV2= (+V3iV2=(+)V1*iV2=(+) V1iV2*iV2=(+) V2iV2*iV2=(+) V3iV2*iV2=(+) (iV2*iV2=(+) (iV2*iV2=(+) (iV3*iV2=(+) (i(*iV2=(+) (i(*iV3=(+) (i(*i(P41 24. 下面文法那些是短語結(jié)構(gòu)文法，上下文有關(guān)文法，上下文無關(guān)文法，及正規(guī)文法？::=aB B::= cB B::=b C::=c::=aB B::=bc C::=c C::=ε::=aAb aA::=aB aA::=aaA B::=b A::=a::=aCd aC::=B aC::=aaA B::=b::=AB A::=a B::=bC B::=b C::=c6. S::=AB A::=a B::=bC C::=c C::=ε7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b8. S::=aA S::= ε A::=bAb A::=a正規(guī)文法 1上下文無關(guān)文法 2 5 6 7 8上下文有關(guān)文法 3 短語結(jié)構(gòu)文法 4P41 26. 給出產(chǎn)生下列語言L（G）={W|W∈{0，1}+且W不含相鄰1}的正規(guī)文法。P4