习题与答案-5-语法分析-自上而下.doc

1对文法GS G:S a | | (T) T T , S | S (1) 给出(a,(a,a)和(a,a), ,(a),a)的最左推导。 (2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。1. 解答（1） S S （ T ） ( T ) T , S T , S S=(T) =(T,S) =(S,S) S ( T ) S a =(T),S) =(T,S),S) a T , S ( T ) =(T,S,S),S) =(S,S,S),S) S a T , S =(T),S,S),S) =(T,S),S,S),S) a T , S ( T ) =(S,S),S,S),S) =(a,S),S,S),S) S=(T) =(T,S) S S =(a,a),S,S),S) =(S,S) =(a,S) =(a,a),S),S) =(a,(T) ( T ) a =(a,a),(T),S) =(a,(T,S) =(a,a),(S),S) =(a,(S,S) T , S =(a,a),(a),S) =(a,(a,S) =(a,a),(a),a) =(a,(a,a) S a a(2)消除左递归G:S a | | (T) T STT ,ST |递归子程序：program parser proceduce T;begin begin getsym; if sym in a,() then S beginend; S;proceduce S; T; begin end;if sym=a or sym= then else getsym error;elseif sym=( end; begin getsym; proceduce T; T; begin If sym=) then if sym=, then Getsym; begin Else getsym; Error; S; End; T; Else end; Error; elseEnd; if sym=) then else error; end;(3) FIRST集FOLLOW集Sa (#FIRST(T)/FOLLOW(T)FOLLOW(T)# , ) TFIRST(S)a ()T, FOLLOW(T)FOLLOW(T)FIRST集FOLLOW集Sa (# , ) Ta ()T, )SELECT集合SaaSS(T)(TSTa (T,ST,T)a( ),#Sa(T)TSTSTSTT,ST预测分析表不含多重定义入口, 所以该文法是LL(1)文法!(4) 分析栈 余留串 所用产生式或动作 1 #S (a,a)# S(T) 2 #)T( (a,a)# (匹配 3 #)T a,a)# TST 4 #)TS a,a)# Sa 5 #)Ta a,a)# a匹配 6 #)T ,a)# T ,ST 7 #)TS, ,a)# ,匹配 8 #)TS a)# Sa 9 #)Ta a)# a匹配 10 #)T )# T 11 #) )# )匹配 12 # # 接受因为 （a,a）#分析成功 所以 （a,a）为文法的句子步骤分析栈 余留串所用产生式或动作 1#S(a,a#S(T) 2#)T(a,a#( 匹配 3 #)Ta,a#TST 4 #)TSa,a# Sa 5 #)Taa,a# a 匹配 6 #)T,a# T ,ST 7 #)TS,a# , 匹配 8 #)TSa# Sa 9 #)Taa# a 匹配 10#)T# 出错2. G:E TE E +E |T FTT T |F PFF *F |P (E) | a | b |2. 解答可推出FIRST集FIRST集ENFIRST(T)( a b EY+ + TNFIRST(F)( a b TYFIRST(T) ( a b FNFIRST(P)( a b FY* * PN( a b ( a b FOLLOW集FOLLOW集E # FOLLOW(E) ) # )EFOLLOW(E)# )TFIRST(E)/ FOLOW(E)FOLOW(T)+ # )TFOLLOW(T)+ # )FFIRST(T)/ FOLOW(T)( a b + # )FFOLLOW(F)( a b + # )PFIRST(F)/ FOLOW(F)* ( a b + # )SELECT集SELECT集ETEFIRST(T)( a b E+E+EFOLLOW(E)# )TFTFIRST(F)( a b TTFIRST(T)( a b TFOLLOW(T)# ) +FPFFIRST(P)( a b F*F *FFOLLOW(F)( a b + # )P(E)(PaaaPbbbP预测分析表+*()ab#ETETETETEE+ETFTFTFTFTTTTTTFPFPFPFPFF*FP(E)abETETETETE3已知文法G:S MH | a H LSo | K dML | L eHf M K | bLM判断G是否是LL(1)文法，如果时，构造LL(1)分析表。3. 解答可推出FIRST集FIRST集SYa, FIRST (M), FIRST (H)a, b, , d, eHY, FIRST (L), eKY, d, dLNeeMYb, FIRST (K)b, , dFOLLOW集FOLLOW集S#, o#, oHFOLLOW(S), f#, o, fKFOLLOW(M)e, #, oLFIRST(So)/, FOLLOW(K), FIRST(M)/ , FOLLOW(M)a, b, d, e, o, #MFIRST(H)/, FOLLOW(S), FIRST(L), FOLLOW(M)e, #, oSELECT集SELECT集SMH FIRST(MH)/,FOLLOW(S)b,d,e, #, oSaaaHLSoFIRST(LSo)eHFOLLOW(H)#, o, fKdMLddKFOLLOW(K)e, #, oLeHfeeMKFIRST(K) /,FOLLOW(M)d, e, #, oMbLMbbaodefb#SaMHMHMHMHMHHLsoKdMLLeHfMKKKbLMK因为 相同左部的select集互不相交 所以 该文法是LL(1)文法或者 因为 预测分析表入口唯一 所以 该文法是LL(1)文法7对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。(2)AaABe | a BBb | d (3) SAa | b ASB Bab7. 解答不一定(2)AaABe | a BBb | d 改写为AaAAABe |BdB BbB |可推出FIRST集ANaAYa,BNdBYb,FOLLOW集FOLLOW集A#, FIRST(Be)#, dAFOLLOW(A)#, dBeeBFOLLOW(B)eSELECT集AaAaAABe aA#, dBdBdBbB bBeSelect(A Abe)select(A )= select(BbB)select(B)=所以 该文法是LL(1)文法(3)SAa | bASB Babl 排序 B A SBab不含左递归代入A得 ASab 不含左递归代入S得SSaba | b 消左递归得SbS S abaS | 整理得SbSSabaS | ASab Bab化简文法，消去A,B得SbSSabaS | 判断select(S abaS)select(S )= 所以 改写后的文法是LL