编译原理正规式(ab)ab(ab).doc

正规式 (a | b)*ab(a | b)* 六、(1) SaSSbS SaAAbBBaBBbBB e(2) 0123645 a a e e a b e e b b(3) 确定化I0,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,6012345 b b 1 a a a a a a b b b baa01b3ba(4) 最小化七、(1)(a, (a, a)的最左推导为S(T)(T, S)(S, S)(a, (T)(a, (T, S)(a, (S, a)(a, (a, a)(a, a), , (a), a)的最左推导为S(T)(T, S)(S, a)(T), a)(T, S), a)(T, S, S), a)(S,(T), a)(T), (S), a)(T, S),(a), a)(S, a),(a), a)(a, a),(a), a)(2) 由于有T T, S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法GS：S a | | (T)T SUU , SU | 各非终结符的FIRST集如下：FIRST(S)=a, , (FIRST(T)=FIRST(S)=a, , (FIRST(U)=, , 各非终结符的FOLLOW集如下：FOLLOW(S)=#FIRST(U)FOLLOW(T)FOLLOW(U)=#, , ,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=) (3) LL(1) 分析表a()，#SS aSS (T)TT SUT SUT SUUUU, SU(4) 输入串(a, a)#的分析过程 步骤分析栈剩余输入串所用产生式123456789101112#S#)T(#)T#)US#)Ua#)U#)US,#)US#)Ua#)U#)#(a,a)#(a,a)#a,a)#a,a)#a,a)#,a)#,a)#a)#a)#)#)#S (T)( 匹配TSUSaa 匹配U, SU, 匹配Saa 匹配U) 匹配Acc可见，该串是G的一个合法句子。(5) 每个非终结符的不带回溯的递归子程序如下char CH; /存放当前的输入符号void P_S() /非终结符S的子程序if (CH= =a) READ(CH); /产生式S a else if (CH= =) READ(CH); /产生式S else if (CH=() /产生式S (T)READ(CH);P_T();if (CH= =) then READ(CH) else ERRORelse ERROR;void P_T() /非终结符T的子程序if (IsIn(CH, FIRST_SU) /FIRST_SU为T SU的右部的FIRST集P_S(); P_U();void P_U() /非终结符U的子程序if(CH= =,) /产生式U , SUREAD(CH);P_S(); P_U();else /产生式