编译原理课后习题

第二章P36-6(1)LG()1是0~9组成的数字串(2)最左推导:NNDNDDNDDDDDDDDDDDDDNNDDDDNNDNDDDDDDDD0010120127334556568最右推导:NNDNNDNNDNDNNDNDNNDNNDND77272712712701274434886868568P36-7G(S)ONODNSOAOAADN1357924680|||||||||||P36-8文法：ETETETTFTFTFFEi|||*|/()|最左推导:EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()最右推导:EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()语法树：/********************************EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*iP36-11/***************L1:||cCCabaAbAACSL2:bcbBcBaAAABS||L3:||aBbBaAbAABSL4:ABBAABAS|01|10|***************/9、对下面情况给出DFA及正规表达式：(1）{0,1}上的含有子串010的所有串。正规式：(0|1)*010(0|1)*(2）{0,1}上不含子串010的所有串。正规式：1*(0|11*1)*1*(0|11)*1*1*0*1*(0|11)*(0|1)10.一个人带着狼、山羊、白菜在一条河的左岸。状态左岸右岸0人，羊，狼，菜NULL1狼，菜人，羊2人，狼，菜羊3狼人，羊，菜4人，羊，狼菜5羊人，狼，菜6人，羊狼，菜7NULL人，羊，狼，菜P64–12(a)aa,ba确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ给状态编号：01ab012112203333aaabbbba最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123ababbbab(b)bbaabaabbaaa已经确定化了,进行最小化0123012023145最小化：{{,},{,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}abababababa{,}{,}{,}{,}{,}{,}{,}10243535353524babbbaabaP81–1(1)按照T,S的顺序消除左递归|,)(||^)(TSTTSTTaSSG递归子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;012procedureT;beginifsym=','thenbeginadvance;S;Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST(T)={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T)={)}预测分析表a^(),#SSaS^ST()TTSTTSTTSTTTTST,是LL(1)文法P81–2文法：|^||)(|*||baEPFFFPFTTTFTEEETE(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:EETTFFPEab||*|()|^||FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFFPFFPFFPFFPFF'FFF*FFFFFFPPE()PaPbP^(4)procedureE;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym')'andsym'#'thenerrorendprocedureT;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginF;T'endelseerrorendprocedureT';beginifsym='('orsym='a'orsym='b'orsym='^'thenTelseifsym='*'thenerrorendprocedureF;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym='a'orsym='b'orsym='^'thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;P133–1EETETF*短语:E+T*F,T*F,直接短语:T*F句柄:T*FP133–2文法：SaTTTSS|^|(),|(1)最左推导:STTSSSaSaTaTSaSSaaSaaaSTSSSTSTSSTSSSSSSSTSSSTSSSSSSSSSaS()(,)(,)(,)(,())(,(,))(,(,))(,(,))(,(,))(,)(,)((),)((,),)((,,),)((,,),)(((),,),)(((,),,)),)(((,),,),)(((,),,),)(((,),,),)(((,),^,),)(((,),^,()),)(((,),^,()),)(((,),^,()),)(((,),^,()),)SSSaaSSSaaSSaaTSaaSSaaaSaaaa最右推导:STTSTTTTSTTaTSaTaaSaaaaaSTSTaSaTaTSaTTaTSaTaaTSaaTaa()(,)(,())(,(,))(,(,))(,(,))(,(,))(,(,))(,(,))(,)(,)(,)((),)((,),)((,()),)((,()),)((,()),)((,,()),)((,^,()),)((,^,()),)(((),^,()),)(((,),^,()),)(((,),^,()),)(((,),^,()),)(((,),^,()),)SaaTaaTSaaTaaaSaaaaaaa(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移进-归约”过程：步骤栈输入串动作0#(((a,a),^,(a)),a)#预备1#(((a,a),^,(a)),a)#进2#(((a,a),^,(a)),a)#进3#(((a,a),^,(a)),a)#进4#(((a,a),^,(a)),a)#进5#(((S,a),^,(a)),a)#归6#(((T,a),^,(a)),a)#归7#(((T,a),^,(a)),a)#进8#(((T,a),^,(a)),a)#进9#(((T,S),^,(a)),a)#归10#(((T),^,(a)),a)#归11#(((T),^,(a)),a)#进12#((S,^,(a)),a)#归13#((T,^,(a)),a)#归14#((T,^,(a)),a)#进15#((T,^,(a)),a)#进16#((T,S,(a)),a)#归17#((T,(a)),a)#归18#((T,(a)),a)#进19#((T,(a)),a)#进20#((T,(a)),a)#进21#((T,(S)),a)#归22#((T,(T)),a)#归23#((T,(T)),a)#进24#((T,S),a)#归25#((T),a)#归26#((T),a)#进27#(S,a)#归28#(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33#(T)#进34#S#归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)a^(),a^(=),6G是算符文法，并且是算符优先文法P134–5(1)0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb7.ASA8.ASA9.ASA10.Aa11.Aa(2)SASaASd确定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{1,2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7