編譯原理第五章作業(yè)參考答案

1、編譯原理習(xí)題解答頁(yè) 1/1第五章 自頂向下語(yǔ)法分析方法1 對(duì)文法 GSS a|A|(T)T T,S|S(1)給岀(a,(a,a) 和(a,a),A,(a),a)的最左推導(dǎo)。(2)對(duì)文法 G,進(jìn)行改寫(xiě)，然后對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序。(3)經(jīng)改寫(xiě)后的文法是否是LL(1)的？給岀它的預(yù)測(cè)分析表。(4)給岀輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G 的句子。解：(1) (a,(a,a)的最左推導(dǎo)為S (T)(T,S)(S,S)(a,(T)(a,(T,S)(a,(S,a)(a,(a,a)(a,a),A,(a),a)的最左推導(dǎo)為S (T)(T,S)(S,a)(T),a)(T,S),a)

2、(T,S,S),a)(S,A,(T),a)(T),A,(S),a)(T,S),A,(a),a)(S,a),A,(a),a)(a,a),A,(a),a)由于有 T T,S 的產(chǎn)生式，所以消除該產(chǎn)生式的左遞歸，增中一個(gè)非終結(jié)符U 有新的文法 GS:S a|A|(T)T SUU ，SU| 分析子程序的構(gòu)造方法對(duì)滿(mǎn)足條件的文法按如下方法構(gòu)造相應(yīng)的語(yǔ)法分析子程序。(1)對(duì)于每個(gè)非終結(jié)號(hào)U,編寫(xiě)一個(gè)相應(yīng)的子程序P(U)；(2)對(duì)于規(guī)則 U:=x1|x2|.|xn,有一個(gè)關(guān)于 U 的子程序 P(U),P(U)按如下方法構(gòu)造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN

3、 FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(x n) THEN P(x n)ELSE ERROR其中，CH 存放當(dāng)前的輸入符號(hào)，是一個(gè)全程變量；ERROR1 一段處理岀錯(cuò)信息的程序;P(xj)為相應(yīng)的子程序。對(duì)于符號(hào)串 x=y1y2.y n;p(x)的含義為：BEGINP(y1);P(y2);P(y n);END如果 yi 是非終結(jié)符，則 P(yi)代表調(diào)用處理 yi 的子程序；如果 yi 是終結(jié)符，則 P(yi)為形如下述語(yǔ)句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果當(dāng)前文法中的符號(hào)與輸入符號(hào)匹配，則繼續(xù)讀入下

4、一個(gè)待輸入符號(hào)到CH 中,否則表明出錯(cuò)。如果文法中有空規(guī)則U:=EPSILON,則算法中的語(yǔ)句IF CH IN FIRST(x n) THEN P(x n)編譯原理習(xí)題解答頁(yè) 1/2ELSE ERROR改寫(xiě)為：IF CH IN FIRST(x n) THEN P(x n)ELSE IF CH IN FOLLOW(U) THEN RETURNERROR(5)要分析一個(gè) OrgStr,應(yīng)在該串的后面加上一個(gè)串括號(hào)#,并從子程序 P(S)(S 為文法的開(kāi)始符號(hào)如果中途沒(méi)有產(chǎn)生錯(cuò)誤，并且最后CH=#,則說(shuō)明 OrgStr 串合法，否則該串不合法。對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序如下：char C

5、H;/存放當(dāng)前的輸入符號(hào)void P_S()非終結(jié)符 S 的子程序if(CH= aREAD(CH);/ 產(chǎn)生式 S aelse if(CH= A ) READ(C 產(chǎn)生式 SAelse if(CH=產(chǎn)生式 S (T)READ(CH);P_T()；IF (CH= = ) THEN READ(CH) else ERRORelse ERR;void P_T()/非終結(jié)符 S 的子程序if(IsIn(CH,FIRST_SU) FIRST_SU為 T SU 的右部的 FIRST 集合P_S()；P_U()；void P_U()/非終結(jié)符 U 的子程序if(CH=,產(chǎn)生式 U ，SUREAD(CH);P_

6、S()；P_U()；else/產(chǎn)生式 U if(IsIn(CH,FOLLOW_U) /FOLLOW_U為 U 的 FOLLOW 集合return ;else ERR;判斷文法 GS是否為 LL(1)文法。各非終結(jié)符的 FIRST 集合如下：FIRST(S)=a,人,(FIRST(T)=FIRST(S)=a,人,(FIRST(U)= , , 各非終結(jié)符的 FOLLOW!合如下：） 開(kāi)始,編譯原理習(xí)題解答頁(yè) 1/3FOLLOW(S)=#UFIRST(U)UFOLLOW(T)UFOLLOW(U)=#,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每個(gè)產(chǎn)生式的 SELECT 集合如

7、下：SELECT(S a)=aSELECT(SA)=ASELECT(S (T)=(SELECT(T SU)=FIRST(S)=a,A,(SELECT(U , SU)=, SELECT(UE)=FOLLOW(U)=)可見(jiàn)，相同左部產(chǎn)生式的SELECT 集的交集均為空，所以文法GS是 LL(1)文法文法 GS的預(yù)測(cè)分析表如下：aA()#SaA(T)TSUSUSUUE,SU(5)給岀輸入串(a,a)#的分析過(guò)程步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,a)#S (T)2#)T(a,a)#(匹配3#)Ta,a)#T SU4#)USa,a)#S a5#)Uaa,a)#a 匹配6#)U,a)#U , SU

8、7#)US,a)#,匹配8#)USa)#S a9#)Uaa)#a 匹配10#)U)#UE11#)#)匹配12#接受2.對(duì)下面的文法 G:E TEE +E|ET FTT/T|EF PFF/*F/|EP (E)|a|bF(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST 集和 FOLLOW!。證明這個(gè)方法是LL(1)的。(3)構(gòu)造它的預(yù)測(cè)分析表。(4)構(gòu)造它的遞歸下降分析程序。解：(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,br;編譯原理習(xí)題解答頁(yè) 1/4FIRST(E/)=+,

9、EFIRST(T)=FIRST(F)=FIRST(P)=(,a,br;FIRST(T/)=FIRST(T)UE=(,a,b=E；FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,A;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(/E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)UFOLLOW(E)=+,),#;不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,

10、+,),#;不包含 FOLLOW(F=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F)UFOLLOW(F)=*,(,a,b,A,+,),#;不包含 證明這個(gè)方法是 LL(1)的。各產(chǎn)生式的 SELECT 集合有：SELECT(E TE)=FIRST(T)=(,a,br;SELECT(E +E)=+;SELECT(E )=FOLLOW(E)=),#SELECT(T F)=FIRST(F)=(,a,b,A;SELECT(T T)=FIRST(T)=(,a,br;SELECT(T )=FOLLOW(T)=+,),#；SELEC

11、T(F PF)=FIRST(P)=(,a,br;SELECT(F *F/)=*；SELECT(F )=FOLLOW(F)=(,a,b,A,+,),#;SELECT(P (E)=(SELECT(P a)=aSELECT(P b)=bSELECT(PA)=A可見(jiàn)，相同左部產(chǎn)生式的SELECT 集的交集均為空，所以文法GE是 LL(1)文法(3)構(gòu)造它的預(yù)測(cè)分析表。 文法 GE的預(yù)測(cè)分析表如下:+*()abA#ETETEPTETE/匚+ETFTFTFTFT/TTTTTFPFPFPFPF/F/*F/P(E)abA(4)構(gòu)造它的遞歸下降分析程序。對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序如下：char CH

12、;/存放當(dāng)前的輸入符號(hào)void P_E()/非終結(jié)符 E 的子程序if(IsIn(CH,FIRST_TEP) FIRST_TEP為 E TE 的右部的 FIRST 集合，產(chǎn)生式 E TE編譯原理習(xí)題解答頁(yè) 1/5P_T()；P_EP()；編譯原理習(xí)題解答頁(yè) 1/6else ERR;void P_EP()非終結(jié)符 U 的子程序if( CH= +) / 產(chǎn)生式 U +EREAD(CH);P_E()；else/ 產(chǎn)生式 E/&if(IsIn(CH,FOLLOW_EP) FOLLOW_EP為 E 的 FOLLO 喋合return ;else ERR;void P_T()/ 非終結(jié)符 T 的子程

13、序if(lsln(CH,FIRST_FTP) FIRST_ FTP為 T F的右部的 FIRST 集合，產(chǎn)生式 T FTP_F();P_TP();else ERR;void P_TP()/非終結(jié)符 F 的子程序編譯原理習(xí)題解答頁(yè) 1/7void P_P()非終結(jié)符 P 的子程序if(CH=( )READ(CH);P_E()；if(CH= ) ) READCH(C H);elseERR;else if(CH= a ) READ(CH);else if(CH= b ) READ(CH);else if(CH= A ) READ(CH);else ERR;3 已知文法 GS:S MH|aH LSo|

14、 K dML|L eHfM K|bLM判斷 G 是否是 LL (1)文法，如果是，構(gòu)造 LL (1)分析表。解：首先求各非終結(jié)符的 FIRST 集合：if(IsI n(CH,FIRST_T) FIRST_T為產(chǎn)生式P_T();else/ 產(chǎn)生式 T/if(Is In (CH,FOLLOW_TP) FOLLOW_TPreturn ;else ERR;void P_F()/非終結(jié)符 F 的子程序if(IsIn(CH,FIRST_PFP) /FIRST_PFP 為 F P_P();P_FP();else ERR;void P_FP()/非終結(jié)符 F/的子程序if( CH= *) / 產(chǎn)生式 F/*F

15、/READ(CH); P_FP();else/ 產(chǎn)生式 F/if(Is In (CH,FOLLOW_FP) FOLLOW_FPreturn ;else ERR;T T 的右部的 FIRST 集合，產(chǎn)生式 T T為 T 的 FOLLO 喋合PF的右部的FIRST集合，產(chǎn)生式F PF為 U 的 FOLLO 喋合編譯原理習(xí)題解答頁(yè) 1/8FIRST(S)=aUFIRST(M)UFIRST(H)=aUb,d,Ue,=a,b,d,e,;FIRST(H)=FIRST(L)U=e,;FIRST(K)=d, ；FIRST(L)=e;FIRST(M)=FIRST(K)Ub=b,d,;然后求非終結(jié)符的 FOLLO

16、WS合：FOLLOW(S)=o,#FOLLOW(H)=FOLLOW(S) f=f,o,# FOLLOW(K)=FOLLOW(M)=FIRST(H) FOLLOW(S)=e,o,#; 不包含 FOLLOW(L)=FIRST(S)UoUFOLLOW(K)J FIRST(M)UFOLLOW(M) =a,b,d,e,o,#UFOLLOW(M)=a,b,d,e,o,#;不包含 FOLLOW(M)=FIRST(L)UFIRST(H)UFOLLOW(S)=e,o,# 不包含 最后求各產(chǎn)生式的 SELECT 集合：SELECT(S MH)=(FIRST(MH)-)UFOLLOW(S)=b,d,eUo,#=b,

17、d,e,o,#;SELECT(S a)=aSELECT(H LSo)=eSELECT(H )=FOLLOW(H)=f,o,#SELECT(K dML)=dSELECT(K )=FOLLOW(K)=e,o,#SELECT(L eHf)=eSELECTM K)=(FIRST(K)-)UFOLLOW(M)=d,e,o,#SELECT(M bLM)=b可見(jiàn)，相同左部產(chǎn)生式的SELECT 集的交集均為空，所以文法GS是 LL(1)文法文法 GE的預(yù)測(cè)分析表如下：aodefb#SaMHMHMHMHMHHLSoKdMLLeHfMKKKbLMK7.對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(

18、1)文法？試對(duì)下面方法進(jìn)行改寫(xiě)，并對(duì)改寫(xiě)后的文法進(jìn)行判斷。(1) AbaB| B Abb|aAaABe|aB Bb|d解：對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后不一定為L(zhǎng)L(1)文法。如果新的文法中無(wú)空產(chǎn)生式，則一定為 LL(1)文法，如果有空產(chǎn)生式，則需要進(jìn)行LL(1)判斷才能決定新方法是否一定是LL(1)文法。(1)由于 SELECT(A baB)=b,SELECT(A)=FOLLOW(A)=b,#,兩集合有交集,所以該文法不是 LL(1)方法。 該文法已經(jīng)消除了左遞歸，與左公共因子，一般來(lái)說(shuō)是不能再改寫(xiě)了。但根據(jù)本文法的具體情況有以下改寫(xiě)： 用產(chǎn)生式 A baB 與 A 分別替換產(chǎn)生式B Abb 有：B baBbb|bb，提取這兩個(gè)新產(chǎn)生式的左公共因子有：BbBB aBbb|b,這樣改寫(xiě)后文法 GA為：A baB| &B bB/|aB/aBbb|b每個(gè)產(chǎn)生式的 SELECT 集合為：SELECT(A baB)=bSELECT(A )=SELECT(B bB/)=bSELECT(B a)=aSELECT(B aBbb)=aSELECT(B b)=b可見(jiàn)，相同左部產(chǎn)生式的SELECT 集的交集