《广工编译原理对下面的文法G》由会员分享,可在线阅读,更多相关《广工编译原理对下面的文法G(11页珍藏版)》请在金锄头文库上搜索。
1、P91 习题2 2、对下面的文法G: ETE EE TFT TT FPF F*F P(E)ab (1)计算这个文法的每个非终结符的FIRST集和 FOLLOW集。 (2)证明这个文法是LL(1)的。 (3)构造它的预测分析表。 (4)构造它的递归下降分析程序。解:(1)计算FIRST与FOLLOW集 FIRST(P)= ( , a , b , FIRST(F)= * , FIRST(F)=FIRST(P) = ( , a , b , FIRST(T)=FIRST(T)= ( , a , b , , FIRST(T)=FIRST(F) = ( , a , b , FIRST(E)= + , FI
2、RST(E)=FIRST(T)= ( , a , b , FOLLOW(E)= ) , # FOLLOW(E)=FOLLOW(E)= ) , # FOLLOW(T)=FIRST(E) FOLLOW(E)=+, ) , # FOLLOW(T)=FOLLOW(T)=+, ) , # FOLLOW(F)=FIRST(T) FOLLOW(T)= (,a,b, , +, ) , # FOLLOW(F)=FOLLOW(F)=(, a , b , , +, ) , # FOLLOW(P)=FIRST(F) FOLLOW(F)=*,( ,a, b ,+ , ) ,# ETEEETFTTTFPFF*FP(E)a
3、bFIRSTFOLLOW E( , a , b , ) , # E+ , ) , # T( , a , b , +, ) , # T( , a , b , , +, ) , # F( , a , b , (, a , b , , +, ) , # F* , (, a , b , , +, ) , # P) , a , b , *,(, a , b , , +, ) , #(2)证明这个文法是LL(1)的。 i.对产生式P(E)ab ,有FIRST(E)FISRT(a) FIRST(b) FIRST()= ii. 对产生式EEFIRST(+E) FOLLOW(E)=+ ) , # = 对产生式T
4、TFIRST(T) FOLLOW(T)= ( , a , b , +, ) , # = 对产生式F*FFIRST(*F) FOLLOW(F)=* (, a , b , , +, ) , # = iii. 文法不含左递归。 综上 i,ii,iii 可知,文法G是LL(1)的。ETEEETFTTTFPFF*FP(E)ab(3)构造预测分析表。 (ab)+*#ETE TE TE TE E+ETFT FT FT FT TTTTTFPF PF PF PF F*F P(E) ab(1)设置过程advance为读下一个单词送全程变量 (2)设置过程error为错误处理程序1. 主程序 Beginadvanc
5、e;E; End 2. E过程 Procedure E BeginT; E; end(4)构造递归下降分析程序。ETEEETFTTTFPFF*FP(E)ab3. E过程 Procedure E Beginif sym=+ thenbegin advance;E;endelseif sym in #,)returnelse errorETEEETFTTTFPFF*FP(E)ab4. T过程 Procedure T BeginF; T; End5. T过程 Procedure T Beginif sym in ),+,# returnelseT endETEEETFTTTFPFF*FP(E)ab6
6、. F过程 Procedure F BeginP; F endETEEETFTTTFPFF*FP(E)ab7. F过程 Procedure F Beginif sym=* then beginadvance;Fendelse if sym in a, b, (, ), , +, # thenreturnelse error; endETEEETFTTTFPFF*FP(E)ab8. P过程 Procedure P Begin if sym in a, b, then advanceelseif sym = ( then beginadvance; Eif sym=) thenadvance;else error;endelseerror; endETEEETFTTTFPFF*FP(E)ab