【正文】 T’ →εT’ →TT’ →εFF→PF’F→PF’F→PF’F→PF’F’F’ →εF’ →εF’ →εF’→*F’F’ →εF’ →εF’ →εF’ →εPP →aP →bP →(E)P →ε P144 6. 對下列文法，構造相應的FIRST和FOLLOW：（1）S∷＝aAdA∷＝BCB∷＝b |εC∷＝c |ε（2）A∷＝BCc | gDBB∷＝ε| bCDEC∷＝DaB | caD∷＝ε| dD E∷＝gAf | c解：（1）構造FIRST集FIRST(S)={a}FIRST(B)={b，ε}FIRST(C)={c，ε}FIRST(A)={b，c，ε}構造FOLLOW集規(guī)則一＃∈FOLLOW(S) FOLLOW(S)={}規(guī)則二d∈FOLLOW(A) FOLLOE(A)=nhcuj7d3FIRST(C){ ε}FOLLOW(B) FOLLOW(B)={c}規(guī)則三FOLLOW(A) FOLLOW(B) FOLLOW(B)={d，c}FOLLOW(A) FOLLOW(C) FOLLOW(C)=nhcuj7d3最后結果為：FIRST(S)={a} FIRST(A)={b，c，ε}FIRST(B)={b，ε}FIRST(C)={c，ε}FOLLOW(S)={}FOLLOW(A)=nhcuj7d3FOLLOW(B)={ε，c}FOLLOW(C)=nhcuj7d3（2）構造FIRST集規(guī)則二FIRST(A)={g},FIRST(B)={b，ε},FIRST(C)={ c}, FIRST(D)={d，ε},FIRST(E)={ g，c }.規(guī)則三FIRST(A)={g，b，c},FIRST(C)={a，c，d},FIRST(A)={ a，b，c，d，g}.構造FOLLOW集規(guī)則一＃∈FOLLOW(A) FOLLOW(A)={}規(guī)則二f∈FOLLOW(A) FOLLOE(A)={ f，＃} c∈FOLLOW(C) FOLLOE(C)={ c} a∈FOLLOW(D) FOLLOE(D)={ a} FIRST(Cc){ ε}FOLLOW(B) FOLLOW(B)={c，d，a}FIRST(B){ ε}FOLLOW(D) FOLLOW(D)={b，a}FIRST(DE){ ε}FOLLOW(C) FOLLOW(C)={d，g，c}FIRST(E) FOLLOW(D) FOLLOW(D)={b，c，a，g}規(guī)則三FOLLOW(A) FOLLOW(B) FOLLOW(B)={a，c，d，f，}FOLLOW(A) FOLLOW(D) FOLLOW(D)={a，b，c， f，g，＃}FOLLOW(B) FOLLOW(E) FOLLOW(E)= {a，c，d，f，}FOLLOW(C) FOLLOW(B) FOLLOW(B)={ a，c，d，g，f，}FOLLOW(B) FOLLOW(E) FOLLOW(E)= { a，c，d，g，f，}最后結果為：FIRST(A)={ a，b，c，d，g}, FIRST(B)={b，ε},FIRST(C)={a，c，d},FIRST(D)={d，ε},FIRST(E)={ g，c },FOLLOE(A)={ f，＃} FOLLOW(B)={ a，c，d，g，f，},FOLLOW(C)={d，g，c},FOLLOW(D)={a，b，c， f，g，＃},FOLLOW(E)= { a，c，d，g，f，}.P144 9. 設已給文法G[S]:S∷＝SaB | bBA∷＝SaB∷＝Ac（1）將此文法改寫為LL（1）文法（4）構造LL（1）分析表解：此題消除左遞歸之后，構造LL（1）分析表存在“多重入口”問題，故采用以下方法：（1）該寫為LL（1）文法：S∷＝bB{aB}A∷＝SaB∷＝Ac（4）FIRST(S)={ b }, FIRST(A)=,FIRST(B)=,FOLLOE(S)={a，＃},FOLLOW(A)={ c},FOLLOW(B)={a，＃}.abcSS∷＝bB{aB}AA∷＝SaBB∷＝Ac第九次作業(yè)：P144 10. 證明下述文法不是簡單優(yōu)先文法：（1） S∷＝bEbE∷＝E+T | T（2） S∷＝bEbE∷＝F | F+T | T | iT∷＝i | (E)證明：(1)畫語法樹： S╱ │ ╲b E b ╱ │ ╲E + T可以得出b=E和bE,因此該文法不是簡單優(yōu)先文法。P145 12. ，確定全部優(yōu)先關系：(a) E=+ +=T T=* *=F (=E E=) *( +F + I F* i* )+ T+ F+(b) 說明表=。=語句表 :==i BEGIN說明 BEGINREAL REALi 。變量 。 標識符表。 i:=P145 13. [E]的優(yōu)先關系矩陣，來分析符號串b(((aa)a)a)b和((aa)a)。)(（2）用迭代法構造優(yōu)先函數(shù)若R=S則f(R）=g(S)若RS則f(R）g(S)＋*↑()if111111g111111根據(jù)的優(yōu)先關系＋*↑()if333133g222212根據(jù)=的優(yōu)先關系＋*↑()if333133g244414循環(huán)―＋*↑()if355155g244414＋*↑()if355155g246616＋*↑()if355177g246616最終結果：＋*↑()if355177g246616（3）+*↑()i)(↑*+i優(yōu)先函數(shù)為：＋*↑()if466199g358718（4）用優(yōu)先關系表分析字符串i+i*i↑i符號棧關系輸入串最左素短語＃f()g(i)i+i*i↑i＃if(i)g(+)+i*i↑ii?！舊()g(+)+i*i↑i?！牛玣(+)g(i)i*i↑i＃∨＋if(i)g(*)*i↑ii?！牛舊(+)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)∨*∨＃∨＋∨f(+)g()∨＋∨?！懦晒146 19. 證明下面文法不是算符優(yōu)先文法: S∷＝A[] | [A∷＝aA | B]B∷＝a證明：∵S→A[ A→aA∴a]∵A→B]B→a ∴a] 和ai*i+i＃i*i+i＃∨*+ii?！?∨i?！?∨+i∨+∨?！?∨成功P146 22. 設有文法G[Z]: Z∷＝A | BA∷＝aAb | cB∷＝aBb | d（1） 試構造能識別此文法的全部活前綴DFA；（2） 試構造LR(0)分析表；（3） 試分析符號串a(chǎn)acbb是否為此文法的句子。Z Z’ ::= ZA Z::= AB Z ::= BaAb A ::= ab A ::=aAbaBb B ::= ab B ::= aBbd B::= dc A::= cZ Z::= B A ::= c B ::= d I1: Z’ ::= ZI4: A ::= aaAb A::=Bb B ::= dI3: Z ::= BI6: B::= dbI8:B ::=aBI9:A::= aAb解：()()(SSSI6: SS(S?),(,) SS?(S), (,)I5: SS(?S),(,) S? (,) S?S(S),(,)I7: SS(S)? ),(I4: SS(S)?,(I0: S’S, S?S(S),( S? ,(I3: SS(S?) ,( SS?(S), (,)I2: SS(?S),( S? (,) S?S(S),(,)I1: S’S?, SS?(S),(引入開始符號S’。其中r1: SS(S) r2: SεLR(1)分析表如下所示：狀態(tài)ACTIONGOTO（）S0r2r211S2acc2r2r233S5S44r1r15r2r266S5S77r1r1分析符號串（（））步驟狀態(tài)棧符號棧輸入串分析動作下一狀態(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文法。(3) 證明：構造其LR(1)項目集：I0: S’?S, S?aAa, S?aBb, S?bAb, I1: S’S?, I2: Sa?Aa, A?x, a Sa?Bb, B?x, bI3: Sb?Ab, A?x, bI4: Ax?, a Bx?, b（其余從略）此時由I4可知存在“歸約歸約”沖突，且FOLLOW(A)={a,b}∩FOLLOW(B)=≠Ф故該文法不是SLR(1)文法，但有ACTION[i, a]=“用產(chǎn)生式Ax進行歸約”，ACTION[i, b]=“用產(chǎn)生式Bx進行歸約”，所以是LR(1)文法。第十一次作業(yè)：P194 1. 按照語法制導翻譯的一般原理，給出表達式(5*4+8)*2的語法樹各結點并注明語義