编译原理第三版课后习题解答

第二章习题解答P36-6(1)LG()1是0~9组成的数字串(2)最左推导:5685653430127012010DDDDDDNDDNDNDDDNDNDDDDDDDDDDNDDDNDDNDN最右推导:NNDNNDNNDNDNNDNDNNDNNDND77272712712701274434886868568P36-7G(S)ONODNSOAOAADN1357924680|||||||||||P36-8文法：ETETETTFTFTFFEi|||*|/()|最左推导:EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()最右推导:EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()语法树：/********************************EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/**************)(|)(|STTTSS***************/P36-11/***************L1:||cCCabaAbAACSL2:bcbBcBaAAABS||L3:||aBbBaAbAABSL4:ABBAABAS|01|10|***************/第三章习题参考答案P64–7(1)101101(|)*011011确定化：01{X}φ{1,2,3}φφφ{1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,4}{2,3,4}{2,3,5}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4,}01000110010111最小化：X1234Y5XY6012354{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,0123456012345135012345124601234560123413501234560123101003012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}010010010111P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)aa,ba确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φ50124301φφφ给状态编号：ab012112203333aaabbbba最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123ababaabbab(b)bbaabaabbaaa已经确定化了,进行最小化0123012023145最小化：{{,},{,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}abababababa{,}{,}{,}{,}{,}{,}{,}10243535353524babbbaabaP64–14(1)010(2):(|)*010010确定化：01{X,1,Y}{1,Y}{2}01201YXYX21{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：0101211221333300101110最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101011100第四章P81–1(1)按照T,S的顺序消除左递归|,)(||^)(TSTTSTTaSSG递归子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('0213013thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedure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;P81–3/***************(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。(4)是，满足三个条件。***************/第五章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