编译原理(陈火旺第三版)练习答案

第二章P-36-6（1）L（G）是0~9组成的数字串；（2）最左推导：N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127N⇒ND⇒DD⇒3D⇒34N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568最右推导：N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127N⇒ND⇒N4⇒D4⇒34N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568P-36-7G（S）：（没有考虑正负符号问题）S→P|APP→1|3|5|7|9A→AD|NN→2|4|6|8|PD→0|N或者：（１）S→ＡＢＣ｜CＡ→１｜２｜３｜４｜５｜６｜７｜８｜９Ｂ→ＢＡ｜Ｂ０｜εＣ→1｜3｜5｜7｜9P-36-8G（E）：E→T|E+T|E-TT→F|T*F|T/FF→（E）|i最左推导：E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T*F⇒i+F*F⇒i+i*F⇒i+i*iE⇒T⇒T*F⇒F*F⇒i*F⇒i*（E）⇒i*（E+T）⇒i*（T+T）⇒i*（F+T）⇒i*（i+T）⇒i*（i+F）⇒i*（i+i）最右推导：E⇒E+T⇒E+T*F⇒E+T*i⇒E+F*i⇒E+i*i⇒T+i*i⇒F+i*i⇒i+i*iE⇒T⇒T*F⇒T*（E）⇒T*（E+T）⇒T*（E+F）⇒T*（E+i）⇒T*（T+i）⇒T*（F+i）⇒T*（i+i）⇒F*（i+i）⇒i*（i+i）1语法树：Ei+i+iE+TE+TTFiFiFiEE+TTFiT*FFiii+i*iEi-i-iE-TE-TTFiFiFiP-36-9句子：iiiei有两个语法树：SiSeSiSiiSiSiSeSiiS⇒iSeS⇒iSei⇒iiSei⇒iiieiS⇒iS⇒iiSeS⇒iiSei⇒iiiei因此iiiei是二义性句子，因此该文法是二义性的。P-36-10S→TS|TT→(S)|()P-36-11L1:G(S):S→ACA→aAb|abC→cC|εL2:G(S):S→ABA→aA|εB→bBc|bcL3:G(S):S→ABA→aAb|εB→aAb|εL4:G(S):S→1S0|AA→0A1|ε或者：S→A|BA→0A1|εB→1B0|A2第三章（1）XY1（0|1）*1010X1Y12345011ε1ε确定化：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}最小化：{0，1，2，3，4，5}，{6}{0，1，2，3，4，5}0={1，3，5}{0，1，2，3，4，5}1={1，2，4，6}{0，1，2，3，4}，{5}，{6}{0，1，2，3，4}0={1，3，5}{0，1，2，3}，{4}，{5}，{6}{0，1，2，3}0={1，3}{0，1，2，3}1={1，2，4}{0，1}，{2，3}，{4}，{5}，{6}{0，1}0={1}{0，1}1={1，2}{2，3}0={3}{2，3}1={4}{0}，{1}，{2，3}，{4}，{5}，{6}2035410610110000101113024310510111000011P64-8(1)（0|1）*01(2)（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*（0|5）|（0|5）(3)0*1（0|10*1）*|1*0（1|01*0）*P84-12（a）a01a，ba确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}ΦΦΦΦ给状态编号：aB01211220333340123aaabbbba最小化：{0，1}{2，3}{0，1}a={1}，{0，1}b={2}{2，3}a={0，3}，{2，3}={3}{0，1}，{2}，{3}0a21aabbb（b）已经确定化，只需最小化：{0，1}，{2，3，4，5}{0，1}a={1}{0，1}b={2，4}{2，3，4，5}a={1，3，0，5}{2，3，4，5}b={2，3，4，5}又：{2，4}a={1，0}{2，4}b={3，5}{3，5}a={3，5}{3，5}b={2，4}分划为：{0，1}，{2，4}，{3，5}{0，1}a={1}{0，1}b={2，4}{2，4}a={1，0}{2，4}b={3，5}{3，5}a={3，5}{3，5}b={2，4}所以不能再分0a21aabbb5P64-14正规式：（0|10）*00101还可以：然后再确定化，最小化，结果应该一样。P65-15首先构造NFA：0|1则有：G（f）f→A1|B0|C1|C0C→C0|C1|A1|B0A→S1|1B→S0|0S→S0|S1|或者是确定化，然后最小化：G（C）C→C0|C1|A0|B1A→0|B0B→1|A1fSC0AB1010011100YεX1010ε2ASCB0101100，116人、狼、羊、白菜：{{M、W、G、C}，{}}表示在左岸，{{}，{M、W、G、C}}在右岸，将可能存在的状态中去掉不安全{}}，{{}，{M、W、G、C}}，{{M、W、G}，{C}}，{{M、W、C}，{G}}，G：表示人和羊过河、MW：表示人和狼过河、MC：状态，剩下：{{M、W、G、C}，{{M、G、C}，{W}}，{{C}，{M、W、G}}，{{G}，{M、W、C}}，{{W}，{M、G、C}}，{{M、G}，{W、C}}，{{W，C}，{M、G}}箭弧上的标记符：M：表示人单独过河、M表示人和白菜过河{{M、W、G、C}，{}}{{W，C}，{M、G}}{{M、W、C}，{G}}{{G}，{M、W、C}}MGMGMW{C}，{{M、W、G}}MW{M、C、G}，{{W}}MGMGMMCMC{W}，{{M、G、C}}{{W、M、G}，{C}}MGMGMWMWMCMC{M、G}，{{W、C}}M{{},{M、W、G、C}MGMGM7第四章P81-1（1）按照T，S的顺序消除左递归G'（S）：S→a|⋀|（T）T→ST'T'→，ST'|ε递归下降子程序：procedureS:beginifsym=‘a’orsym=‘⋀’thenadvanceelseifsym=‘（’thenbeginadvance；T；ifsym=‘)’thenadvance;elseerror;endelseerrorendprocedureT;beginS;T'EndProcedureT';BeginIfsym=‘,’ThenbeginAdvance;S;T'EndEnd其中：sysm为输入串指针所指的符号；advance是把输入指针调至下一输入符号。（2）求First和Follow集合：First（S）={a、⋀、（}First（T）={a、⋀、（}First（T'）={，、ε}Follow（S）={,、)、#}Follow(T)={)}Follow(T'）={)}a⋀(),#SS→aS→⋀S→(T)TT→ST'T→ST'T→ST'T'T'→εT'→，ST'8P81-2文法：E→TE'E'→+E|εT→FT'T'→T|εF→PF'F'→*F'|εP→（E）|a|b|⋀（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）文法无左递归，考察E'→+E|εT'→T|εF'→*F'|εP→（E）|a|b|⋀E'→+E|ε：First(E')={+,ε}∩Follow(E')={#,)}=ΦT'→T|ε：First(T')={(,a,b,⋀,ε}∩Follow(T')={+,),#}=ΦF'→*F'|ε：First(F')={*,ε}∩Follow(F')={(,a,b,⋀,),#}=ΦP→（E）|a|b|⋀：候选式终结首符集两两不相交所以该文法为LL(1)文法。（3）LL(1)分析表+*（）ab⋀#EE→TE'E→TE'E→TE'E→TE'E'E'→+EE'→εE'→εTT→FT'T→FT'T→FT'T→FT'T'T'→εT'→TT'→εT'→TT'→TT'→TT'→εFF→PF'F→PF'F→PF'F→PF'F'F'→εF'→*F'F'→εF'→εF'→εF'→εF'→εF'→εPP→（E）P→aP→bP→⋀（4）构造递归下降程序ProcedureE;BeginIfsym=‘（’orsym=‘a’orsym=‘b’orsym=‘⋀’ThenbeginT；E'endElseerrorEndProcedureE';BeginIfsym=‘+’Thenbeginadvance;EendElseifsym‘)’andsym‘#’thenerrorEndProcedureT;BeginIfsym=‘(’orsym=‘a’orsym=‘b’orsym=‘⋀’ThenbeginF;T'endElseerrorEnd9ProcedureT';Beginifsym=‘(‘orsym=‘a’orsym=‘b’orsym=‘⋀’ThenbeginT;Elseifsym=‘*’thenerrorEndProcedureF;Beginifsym=‘(‘orsym=‘a’orsym=‘b’orsym=‘⋀’ThenbeginP;F'endElseerrorEndProcedureF'BeginIfsym=‘*’Thenbeginadvance;F'endEndProcedureP;BeginIfsym=‘a’orsym=‘b’orsym=‘⋀’ThenadvanceElseifsym=‘(‘thenBeginadvance;E;Ifsym=‘)’thenadvanceElseerrorEndElseerrorendP81-3解答：（1）该文法不含左递归，计算First集合和Follow集合Fisrt(S)={a，b，c}First(A)={a，ε}First（B）={b,ε}Follow(S)={#}Follow（A）={b，c}Follow(B)={c}满足LL(1)文法的3个条件，所以是LL(1)文法；（2）该文法不含左递归，计算First集合和Follow集合Fisrt(S)={a，b}First(A)={a，b，ε}First（B）={b,ε}Follow(S)={#}Follow（A）={b}Follow(B)={b}考虑A→a|B|ε,Fisrt(A)中含有ε，而Fisrt(A)∩Follow（A）={b}，所以不是LL(1)文法；（3）该文法不含左递归，计算First集合和Follow集合Fisrt(S)={a，b，ε}First(A)={a，ε}First（B）={b,ε}Follow(S)={#}Follow（A）={a，b，#}Follow(B)={a，b，#}考虑A→a|ε,Fisrt(A)中含有ε，而Fisrt(A)∩Follow（A）={a}，所以不是LL(1)文法；(4)是LL（1）文法10P82-4文法：Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε解答：First(Expr)={-，（，id}First（Var）={id}First(ExprTail)={-,ε}First(VarTail)={(