【文章內(nèi)容簡介】 )L(b*))*={{a}**}*={a, b}*； 因此e1= e2（得證）P74 18. 根據(jù)下面正規(guī)文法構(gòu)造等價(jià)的正規(guī)表達(dá)式：S::=cC | a ……①A::=cA | aB ……②B::=aB | c ……③C::=aS | aA | bB | cC | a ……④解：由③式可得 B= aB + c → B=a*c 由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a 由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) →C= c*( aS + ac*aa*c + ba*c + a) → S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a)P74 19. Σ＝{a, b}，寫出下列正規(guī)集：（1）(a | b)*(aa | bb)(a | b)*解：L((a | b)*(aa | bb)(a | b)*) = L((a | b)*) L((aa | bb)) L((a | b)*) =(L (a | b))* {aa, bb} (L (a | b))* = {a, b}*{aa, bb}{a, b}*P75 20. 證明下列關(guān)系式成立，其中A、B是任意正規(guī)表達(dá)式。（1）A | A = A （3）A* = ε| AA*（1）解：L(A | A) = L(A)∪L(A) = L(A)，所以A | A = A；（3）解：L(A*) = (L(A))*，L(ε| AA*) = L(A)L(A*) = (L(A))*，所以A* = ε| AA*；第七次作業(yè)：P142 1. 試分別消除下列文法的直接左遞歸（采用兩種方法——重復(fù)法和改寫法）（1）G[E]:E::=T | EAT ……①T::=F | TMF ……②F::=(E) | i ……③A::=+ | ……④ M::=* | / ……⑤解：先采用“重復(fù)法”： 再采用“改寫法”：E::=T{AT} E::=TE’T::=T{MF} E’::= ATE’ | εF::=(E) | I T::=FT’A::=+ | T’::=MFT’ | εM::=* | / F::=(E) | I A::=+ | M::=* | /（4）G[Z]:Z::=V1 ……①V1::=V2 | V1iV2 ……②V2::=V3 | V2+V3 ……③V3::=)V1* | ( ……④解：先采用“重復(fù)法”： 再采用“改寫法”：Z::=V1 Z::=V1V1::=V2 {iV2} V1::=V2 V1’V2::=V3 {+V3} V1’::=i V2 V1’ | εV3::=)V1* | ( V2::=V3 V2’ V2’::=+V3 V2’ | εV3::=)V1* | (P142 2. 試分別消除下列文法的間接左遞歸（2）G[Z]:Z::=AZ | b ……① A::=Z A | a ……②解：將②式代入①式可得，Z::=ZAZ | aZ | b 消除左遞歸后得到： Z::=(aZ | b)Z’ Z’::=AZZ’ | ε A::=ZA | aP142 4. 試分別用兩種方法（框圖法和類Pascal語言或類C語言）寫一個(gè)識(shí)別下面文法句子的遞歸子程序文法G[A]:A::=[B ……①B::=X] | BA ……②X::=Xa | Xb | a | b ……③解：消除該文法的左遞歸和回溯，得到文法如下： A::=[B B::=X]B’ B’::=AB’ |ε X::=aX’ | bX’ X’::= aX’ | bX’ |ε用類Pascal語言寫出其遞歸子程序：P(A): SCIN IF ch=’[‘ THEN READ (ch) ELSE ERROR P(B) SCOUTP(B): SCIN P(X) IF ch=’]‘ THEN READ (ch) ELSE ERROR P(B’) SCOUTP(B’): SCIN IF ch=ε THEN SCOUT ELSE P(A) P(B’) SCOUTP(X): SCIN IF ch=’a‘ THEN { READ (ch) P(X’) } ELSE IF ch=’b‘ THEN { READ (ch) P(X’) } ELSE ERROR SCOUTP(X’): SCIN IF ch=ε THEN SCOUT ELSE IF ch=’a‘ THEN { READ (ch) P(X’) } ELSE IF ch=’b‘ THEN { READ (ch) P(X’) } ELSE ERROR SCOUT用框圖法來表述：（此處僅給出P(A)和P(X’)的框圖形式，其余相似從略）SCIN1ch=ε?=32READP(X’)SCOUT4107ch=a?=5P(X’)6ch=b?=8READ9ERRORP(A): P(X’):SCIN1ch=[?3ERROR2READP(B)SCOUT=456第八次作業(yè)：P143 5. 對下面的文法G[E]: E::=TE’ E’::=+E |ε T::=FT’T’::=T |ε F::=PF’F’::=*F’ |ε P∷＝(E) |a |b |∧（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符號(hào)的FIRST和FOLLOW；（2）證明這個(gè)文法是LL（1）文法；（3）構(gòu)造它的LL（1）分析表并分析符號(hào)串a(chǎn)*b+b。解:（1）構(gòu)造FIRST集：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧)FIRST(T’)={ (，a，b, ε，∧}構(gòu)造FOLLOW 集：規(guī)則一?！蔉OLLOW(E) FOLLOW(E)={}規(guī)則二)∈FOLLOW(E) FOLLOE(E)={ )，}FIRST(E’){ε}FOLLOW(T) FOLLOW(T)={+}FIRST(T’){ε}FOLLOW(F) FOLLOW(F)={ (，a，b，∧}FIRST(F’){ε}FOLLOW(P) FOLLOW(P)={*}規(guī)則三FOLLOW(E) FOLLOW(E’) FOLLOW(E’)={ ，)}FOLLOW(E) FOLLOW(T) FOLLOW(T)={＋，＃，）}FOLLOW(T) FOLLOW(T’) FOLLOW(T’)= {＋，＃，）}FOLLOW(T) FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧}FOLLOW(F) FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧}FOLLOW(F) FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*}最后結(jié)果為：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧}FIRST(T’)={ (，a，b, ε，∧)FOLLOE(E)={ ), ＃}FOLLOW(E’)={＃，)}FOLLOW(T)={＋，＃，）}FOLLOW(T’)= {＋，＃，）}FOLLOW(F)={ (，)，a，b，＋，＃，∧}FOLLOW(F’)={ (，)，a，b，＋，＃，∧}FOLLOW(P)= { (，)，a，b，＋，＃，∧,*}（2）證明該文法是LL（1）文法：證明：對于規(guī)則E’::=+E |ε，T’::=T |ε，F(xiàn)’::=*F’ |ε （僅有一邊能推出空串）有FIRST(+E)={+}∩FIRST(ε)= 248。，F(xiàn)IRST(T’)={+, , }}∩FIRST(ε)= 248。 FIRST(*F’)={*}∩FIRST(ε)= 248。，F(xiàn)IRST(+E)={+}∩FOLLOW(E’)= {, )}=248。 FIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, , )}=248。FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=248。所以該文法是LL（1）文法。（3）構(gòu)造文法分析表ab+*()∧EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’T’T’ →TT’ →TT’ →εT’ →TT’ →ε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. 對下列文法，構(gòu)造相應(yīng)的FIRST和FOLLOW：（1）S∷＝aAdA∷＝BCB∷＝b |εC∷＝c |ε（2）A∷＝BCc | gDBB∷＝ε| bCDEC∷＝DaB | caD∷＝ε| dD E∷＝gAf | c解：（1）構(gòu)造FIRST集FIRST(S)={a}FIRST(B)={b，ε}FIRST(C)={c，ε}FIRST(A)={b，c，ε}構(gòu)造FOLLOW集規(guī)則一?！蔉OLLOW(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最后結(jié)果為：FIRST(S)={a} FIRST(A)={b，c，ε}FIRST(B)={b，ε}FIRST(C)={c，ε}FOLLOW(S)={}FOLLOW(A)=nhcuj7d3FOLLOW(B)={ε，c}FOLLOW(C)=nhcuj7d3（2）構(gòu)造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}.構(gòu)造FOLLOW集規(guī)則一＃∈FOLLOW(A) FOLLOW(A)={}規(guī)則二f∈FOLLOW(A)