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

1、第五章自頂向下語法分析方法1. 對(duì)文法GSS»A|(T)TTT,S|S(1) 給出(a,(a,a)和(a,a),A,(a),a)的最左推導(dǎo)。(2) 對(duì)文法G,進(jìn)行改寫，然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序。(3) 經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。解：(1) (a,(a,a)的最左推導(dǎo)為ST弓(T,S)弓(S,S)弓(a,(T)弓(a,(T,S)弓(a,(S,a)弓(a,(a,a)(a,a),A,(a),a)的最左推導(dǎo)為ST(T)T(T,S)T(S,a)T(T),a)T(T,S),a)T(T,S,S

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

3、THENP(x2)ELSE.IFCHINFIRST(xn)THENP(xn)ELSEERROR其中，CH存放當(dāng)前的輸入符號(hào)，是一個(gè)全程變量；ERROR是一段處理出錯(cuò)信息的程序;P(xj)為相應(yīng)的子程序。(3) 對(duì)于符號(hào)串x=y1y2.yn;p(x)的含義為：BEGINP(y1);P(y2);P(yn);END如果yi是非終結(jié)符，則P(yi)代表調(diào)用處理yi的子程序；如果yi是終結(jié)符，則P(yi)為形如下述語句的一段子程序IFCH=yiTHENREAD(CH)ELSEERROR即如果當(dāng)前文法中的符號(hào)與輸入符號(hào)匹配，則繼續(xù)讀入下一個(gè)待輸入符號(hào)到CH中，否則表明出錯(cuò)。(4) 如果文法中有空規(guī)則U:=

4、EPSILON,則算法中的語句IFCHINFIRST(xn)THENP(xn)ELSEERROR改寫為：IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURNERROR(5) 要分析一個(gè)OrgStr,應(yīng)在該串的后面加上一個(gè)串括號(hào)并從子程序P(S)(S為文法的開始符號(hào))開始,如果中途沒有產(chǎn)生錯(cuò)誤，并且最后CH='#',則說明OrgStr串合法，否則該串不合法。對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序如下：charCH;/存放當(dāng)前的輸入符號(hào)voidP_S()非終結(jié)符S的子程序if(CH='a')READ(CH);/產(chǎn)

5、生式STaelseif(CH='A')READ(CH);/產(chǎn)生式STAelseif(CH='(')/產(chǎn)生式ST(T)READ(CH);P_T();IF(CH=')')THENREAD(CH)elseERRORelseERR;voidP_T()/非終結(jié)符S的子程序if(IsIn(CH,FIRST_SU)FIRST_SU為TTSU的右部的FIRST集合P_S();P_U();voidP_U()/非終結(jié)符U的子程序if(CH=',')/產(chǎn)生式UT,SUREAD(CH);P_S();P_U();else/產(chǎn)生式UTeif(IsIn(CH,

6、FOLLOW_U)/FOLLOW_U為U的FOLLOW集合return;elseERR;(3)判斷文法G/S是否為L(zhǎng)L(1)文法。各非終結(jié)符的FIRST集合如下：FIRST(S)=a,A,(FIRST(T)=FIRST(S)=a,A,(FIRST(U)=,£各非終結(jié)符的FOLLOW集合如下：FOLLOW(S)=#UFIRST(U)UFOLLOW(T)UFOLLOW(U)=#,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每個(gè)產(chǎn)生式的SELECT集合如下：SELECT(STa)二aSELECT(SA)=ASELECT(S(T)=(SELECT(TSU)=FIRST(

7、S)=a,A,(SELECT(UT,SU)=,SELECT(U£)=FOLLOW(U)=)可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G/S是LL(1)文法。文法G/S的預(yù)測(cè)分析表如下：aA(),#STaTAT(T)TTSUTSUTSUUT8T,SU給出輸入串（a,a）#的分析過程步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,a)#ST(T)2#)T(a,a)#（匹配3#)Ta,a)#TTSU4#)USa,a)#STa5#)Uaa,a)#a匹配6#)U,a)#UT,SU7#)US,a)#，匹配8#)USa)#STa9#)Uaa)#a匹配10#)u)#UT811#)#）匹配1

8、2#接受2. 對(duì)下面的文法G：ETTE/E/E|eTTFT/T/TT|eFTPF/F/T*F/1ePT(E)|a|b|"(1) 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。(2) 證明這個(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,b,"FIRST(E/)=+,eFIRST(T)=FIRST(F)=FIRST(P)=(,a,b,"FIRST(T/)=

9、FIRST(T)Ue=(,a,b,e;FIRST(F)=FIRST(P)=(,a,b,'FIRST(F/)=FIRST(P)=*,e;FIRST(P)=(,a,b,'FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;/不包含eFOLLOW(T/)=FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)UFOLLOW(T)=(,a,b,',+,),#;/不包含eFOLLOW(F/)=FOLLOW(F

10、)=FIRST(T/)UFOLLOW(T)=(,a,b,：+,),#;FOLLOW(P)=FIRST(F/)UFOLLOW(F)=*,(,a,b,：+,),#;/不包含e(2) 證明這個(gè)方法是LL(1)的。各產(chǎn)生式的SELECT集合有：SELECT(ETTE/)=FIRST(T)=(,a,b,'SELECT(E/T+E)=+;SELECT(E/Te)=FOLLOW(E/)=),#SELECT(TTFT/)=FIRST(F)=(,a,b,'SELECT(T/TT)=FIRST(T)=(,a,b,'SELECT(T/Te)=FOLLOW(T/)=+,),#;SELECT(F

11、TPF/)=FIRST(P)=(,a,b,'SELECT(F/T*F/)=*;SELECT(F/Te)=FOLLOW(F/)=(,a,b,',+,),#;SELECT(PT(E)=(SELECT(PTa)=aSELECT(PTb)=bSELECT(PV)=可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3) 構(gòu)造它的預(yù)測(cè)分析表。文法GE的預(yù)測(cè)分析表如下：+*()ab#ETTE/TTE/TTE/TTE/E/T+ETeTeTTFT/TFT/TFT/TFT/T/TeTTTeTTTTTTTeFTPF/TPF/TPF/TPF/F/TeT*F/TeTeTe

12、TeTeTePT(E)TaTbT(4) 構(gòu)造它的遞歸下降分析程序。對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序如下：charCH;/存放當(dāng)前的輸入符號(hào)voidP_E()/非終結(jié)符E的子程序if(IsIn(CH,FIRST_TEP)/FIRST_TEP為ETTE/的右部的FIRST集合，產(chǎn)生式ETTE/P_T();P_EP();elseERR;voidP_EP()/非終結(jié)符E/的子程序if(CH='+')/產(chǎn)生式E/T+EREAD(CH);P_E();else/產(chǎn)生式E/Teif(IsIn(CH,FOLLOW_EP)/F0LL0W_EP為E/的FOLLOW集合return;elseER

13、R;voidP_T()/非終結(jié)符T的子程序if(IsIn(CH,FIRST_FTP)/FIRST_FTP為TTFT/的右部的FIRST集合，產(chǎn)生式TTFT/P_F();P_TP();elseERR;voidP_TP()/非終結(jié)符T/的子程序if(IsIn(CH,FIRST_T)/FIRST為產(chǎn)生式T/TT的右部的FIRST集合，產(chǎn)生式T/TTP_T();else/產(chǎn)生式T/Teif(IsIn(CH,FOLLOW_TP)/FOLLOW_TP為T/的FOLLOW集合return;elseERR;voidP_F()/非終結(jié)符F的子程序if(IsIn(CH,FIRST_PFP)/FIRST_PFP為F

14、TPF/的右部的FIRST集合，產(chǎn)生式FTPF/P_P();P_FP();elseERR;voidP_FP()/非終結(jié)符F/的子程序if(CH='*')/產(chǎn)生式F/T*F/READ(CH);P_FP();else/產(chǎn)生式F/Teif(IsIn(CH,FOLLOW_FP)/FOLLOW_FP為F/的FOLLOW集合return;elseERR;voidP_P()/非終結(jié)符P的子程序if(CH='()READ(CH);P_E();if(CH=')')READCH(CH);elseERR;elseif(CH='a')READ(CH);elsei

15、f(CH='b')READ(CH);elseif(CH=''')READ(CH);elseERR;已知文法GS：STMH|aHLSo|eKdML|eLTeHfMTK|bLM解：判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。首先求各非終結(jié)符的FIRST集合：FIRST(S)=aUFIRST(M)UFIRST(H)=aUb,d,eUe,e=a,b,d,e,e;FIRST(H)=FIRST(L)Ue=e,e；FIRST(K)=d,e;FIRST(L)=e;FIRST(M)=FIRST(K)Ub=b,d,e;然后求非終結(jié)符的FOLLOW集合：FOLL

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

17、ECT(STa)=aSELECT(HTLSo)=eSELECT(HTe)=FOLLOW(H)=f,o,#SELECT(KTdML)=dSELECT(KTe)=F0LL0W(K)=e,o,#SELECT(LTeHf)=eSELECT(MTK)=(FIRST(K)-e)UFOLLOW(M)=d,e,o,#SELECT(MTbLM)=b可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GS是LL(1)文法。文法GE的預(yù)測(cè)分析表如下：aodefb#STaTMHTMHTMHTMHTMHH->eTLSo->e->eK->eTdML->e->eLMTKTKTeHf

18、TKTbLMtk7.對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(1)文法？試對(duì)下面方法進(jìn)行改寫，并對(duì)改寫后的文法進(jìn)行判斷。(1)AbaB|eBTAbb|aA->aABe|aBTBb|d解：對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后不一定為L(zhǎng)L(1)文法。如果新的文法中無空產(chǎn)生式，則一定為L(zhǎng)L文法，如果有空產(chǎn)生式，貝懦要進(jìn)行LL判斷才能決定新方法是否一定是LL文法。(1)由于SELECT(ATbaB)=b,SELECT(AT£)=FOLLOW(A)=b,#,兩集合有交集，所以該文法不是LL(1)方法。該文法已經(jīng)消除了左遞歸，與左公共因子，一般來說是不能再改寫了。但根據(jù)本文法的具體情況有以下改寫：BTbB/,B/TaBbb|b,這樣改寫后文法G/A為:ATbaB|eBTbB/|a用產(chǎn)生式ATbaB與ATe分別替換產(chǎn)生式BTAbb有：BTbaBbb|bb，提取這兩個(gè)新產(chǎn)生式的左公共因子有:B/TaBbb|b每個(gè)產(chǎn)生式的SELECT集合為：SELECT(ATbaB)=bSELECT(ATe)=0SELECT(BTbB/)=bSELECT(BTa)=aSELECT(B/TaBbb)=aSELECT(B/Tb)=b可見，相