《编译原理正规式(ab)ab(ab)》由会员分享，可在线阅读，更多相关《编译原理正规式(ab)ab(ab)（3页珍藏版）》请在金锄头文库上搜索。
1、正规式(a|b)*ab(a|b)*六、SaSSbSSaAAbBBaBBbBB(3)确定化IlaIb0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6(4)最小化b七、(a,(a,a)的最左推导为S(T)(T,S)(S,S)(a,(T)(a,(T,S)(a,(S,a)(a,(a,a)(a,a),A,(a),a)的最左推导为S(T)(T,S)(S,a)(T),a)(T,S),a)(T,S,S),a)(S,A,(T)
2、,a)(T),A,(S),a)(T,S),A,(a),a)(S,a),A,(a),a)(a,a),A,(a),a)(2)由于有TT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法GS:Sa|A|(T)TSUU,SU|各非终结符的FIRST集如下：FIRST(S)=a,A,(FIRST(T)=FIRST(S)=a,A,(FIRST(U)=,各非终结符的FOLLOW集如下：FOLLOW(S)=#UFIRST(U)UFOLLOW(T)UFOLLOW(U尸#,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)LL(1)分析表aA()#SSaSAS(T)1TTSUTS
3、UTSUUUU,SU(4)输入用(a,a)#勺分析过程步骤分析栈剩余输入用所用产生式1#S(a,a)#S(T)2#)T(a,a)#(匹配3#)Ta,a)#TSU4#)USa,a)#Sa5#)Uaa,a)#a匹配6#)U,a)#U,SU7#)US,a)#,匹配8#)USa)#9#)Uaa)#Sa10#)U)#a匹配11#)#U12#)匹配Acc可见，该用是G的一个合法句子(5)每个非终结符的不带回溯的递归子程序如下charCH;/存放当前的输入符号voidP_S()/非终结符S的子程序if(CH=a)READ(CH)产生式Saelseif(CH=A)READ(CH川产生式SAelseif(CH=(/产生式)S(T)READ(CH);P_T();if(CH=)thenREAD(CH)elseERRORelseERROR;voidP_T()/非终结符T的子程序if(IsIn(CH,FIRST_SU)/FIRST_SU为TSU的右部的FIRST集P_S();P_U();voidP_U()/非终结符U的子程序if(CH=,/产生式)U,SUREAD(CH);P_S();P_U();else/产生式Uif(IsIn(CH,FOLLOW_U)/FOLLOW_U为U的FOLLOW集return;elseERROR;
