编译原理第五章答案

1、第5章自顶向下语法分析方法第1题对文法GSSa()八,SS(1)给出(a,(a,a)和(a,a),(a),a)八的最左推导。(2)对文法G,进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否是LL(1)的?给出它的预测分析表。(4)给出输入串声)#的分析过程，并说明该串是否为G的句子。答案：(1)对(3(a间的最左推导为:=(T.S)=(S,S)=(a.S)na(T.s)s)=a(虱a)对(办，羽)的最左推导为:sn(T)=(T.S)=(S.S)n(s)=(T.s),s)=(TSS)=(S?S?S)?S)=(0)65)3)=(T.S);S.SXS)=(SS)5S)8

2、)=(a.S)5.S).S)n(Ga)ss),s)n(立八ssn(a),A,).S)=()人)3)=(4&),八，),S)(2)改写文法为:0)Sf1)S一八&一(丁)TSN4)NfSN5)Nt非终结符FIRST集FOLLOW集S济T)N)对左部为N的产生式叮知：FIRSTJSN)=,FIRSTIF=eFOLLOW(N)=)由于SELECT(NfSN)nSELECT(Nf)=,)=&所以文法纪LL(1)的。预测分析表(PredictingAnfilysisTable)aA(Sr八TtSK-SNTNN一r区N也可由预测分析表中无多重入口判定文法是LL(1)的。13对输入串#的分析过程为:栈(ST

3、ACK当前输入符CUR_CHAR)剩余输入符(INOOT_STRING)所用产生式(OPERATION；#S(a.a)#rs-cd(a.a#a.a)#TfN#)NSa用#S#)Naa.a)#)N*#N-sSNk)NS.a讲#)NSa杵S-ab)Naa1#)N)#Nf)F可见输入串3用)#是文法的句子。第3题已知文法GS：SLSLLL判断G是否是LL(1)文法，如果是，构造LL(1)分析表。文法展开为：0)SMHSHHT5。Hf45KdMLKfL-eHfMKM-bLM件终结符FIRST集FOLLOW集S偎。;MHrz(隹工年Lradbem济K对科同左部的产生式可知.SELECTfS-MH)nSE

4、LECT(Sa)=d,b#、)门o=0SELECT(H-LSo)nSELECT(Hj斗H找fg=0SELECT(K-dML)nSELECT(K)=dne乱。=SELECTfM-K)nSELECT(M-bLM)=d+e,#.ob=2：所以文法是LL(1*L预测分析表:a0defbS-MH-MH-MH-MH-MHMtK-KT-bLM-KH一LSo一近LeHfKedML*E由预测分析表中无豕隼入门也可判定文法是LL(l)的第7题对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。(1)A-baBIB-AbblaAaABlaBBblA

5、albABBab答案：(1)先改写文法为:0)A-baBA-eB-baBbbB-bbB-a再改写文法为:0)A-baBA-eB-bNB-aN-aBbbN-bFIRSTFOLLOWA仙#B色团N他a国”预测分析衣ab#AbaB-EB一日bNNwBbb一b由预测分析表中无多重人口判定文法是LU1)的(2)文法：AaABaBBb提取左公共因子和消除左递归后文法变为：0)AaNNABNBN1N1bN1N11非终结符FIRST集FOLLOW集AaBMN_aeN1b.e)对相同左部的产生式可知：SELECT(N-ABe)nSELECT(N-E)-a口#&=3SELECT(NlbNL)riSELECT(Nl

6、E)=bAe=C所以文法是LL(1)的,预测分析表(PredictuigAiialysi、Table)aebd%A-aNB一dNlN11EENIN一ABsTg*E也可由预测分析表中无多重人口判定文法是LL(D的(3)文法：SAAS第1种改写：用A的产生式右部代替S的产生式右部的A得:SS消除左递归后文法变为：S对相同左部的产生式可知：SELECTfN-BaN；nSELLCT(N-e)=aPi#M所以文法是Lin的。预测分析表(PredictingAimlytisTable)也可由预测分析表中无多重入口判定文法是LL(1)的。第2种改写：用S的产生式右部代替A的产生式右部的S得：SAAA消除左递归后文法变为：)SA1)S)A)对相同左部的产生式可知：SELEC