资源描述：
《编译原理正规式(ab)ab(ab)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、正规式(a
2、b)*ab(a
3、b)*六、(1)S®aSS®bSS®aAA®bBB®aBB®bBB®e(2)0123645aaeeabeebb(3)确定化I{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}012345bb1aaaaaabbbbaa01b3ba(4)最小化第3页共3页七、(1)(a,(
4、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有新的文法G’[S]：S®a
5、∧
6、(T)
7、T®SUU®,SU
8、ε各非终结符的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®aS®∧S®(T)TT®SUT®SUT®SUUU®εU®,SU(4)输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式123456789101
9、112#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)(匹配T®SUS®aa匹配U®,SU,匹配S®aa匹配U®ε)匹配Acc可见，该串是G的一个合法句子。第3页共3页(5)每个非终结符的不带回溯的递归子程序如下charCH;//存放当前的输入符号voidP_S()//非终结符S的子程序{if(CH==’a’)READ(CH);//产生式S®aelseif(CH==’^’)READ(CH);//产生式S®^elseif(
10、CH==’(’)//产生式S®(T){READ(CH);P_T();if(CH==’)’)thenREAD(CH)elseERROR}elseERROR;}voidP_T()//非终结符T的子程序{if(IsIn(CH,FIRST_SU))//FIRST_SU为T®SU的右部的FIRST集{P_S();P_U();}}voidP_U()//非终结符U的子程序{if(CH==’,’)//产生式U®,SU{READ(CH);P_S();P_U();}else//产生式U®ε{if(IsIn(CH,FOLLOW_U))//FOLLOW_U为U的FOLLOW
11、集return;elseERROR;}}第3页共3页
