编译 原理课后题答案第二章P36-6(1)L ( G 1 )是0~9 组成的数字串(2)最左推导 :N ND NDD NDDD DDDD0DDD01DD012D 0127N ND DD 3D34NNDNDDDDD5DD56D568最右推导 :N ND N 7 ND 7 N 27 ND 27N 127D1270127NND N 4 D 4 34N NDN 8ND 8N 68D68 568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|O D0|NS O| AO A AD | NP36-8文法：E T| E T|E TT F |T * F |T / F F ( E)|i最左推导 :E E T T TF Ti Ti T * Fi F * F i i * F i i * i ETT * F F * F i * F i *( E ) i *( ET)i *( T T )i *( FT )i *( i T )i *( i F )i *( ii )最右推导 :E E T E T *F E T * i E F * i E i * i T i * i F i * i i i * iE TF * T F * F F *( E) F *( E T) F *( E F ) F *( E i )F *( T i ) F *( F i ) F *( i i ) i *( i i )语法树： /********************************EE+TE+T FT F iF iii+i+i*****************/P36-9句子 iiiei有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiieiE EE+T E-T T T*FE-T F F F iT F i i iF iii-i-i i+i*iP36-10/**************S TS | T T( S) | ( )***************/P36-11/*************** L1:S ACA aAb | ab C cC |L2:S ABA aA |B bBc | bcL3:S ABA aAb | BaBb |L4:S A | BA0 A1|B 1B0 | A***************/第三章习题参考答案P64–7(1)1(01|) * 101X Y1101X12345Y1确定化：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,}10230011010145111最小化：{ 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{12,,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}1020010011341116 5P64–8(1)(1 | 0)* 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( 0 |10* 1) *P64–12(a)aa,b01a确定化：a b{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ给状态编号：a b012112203333 aa01a b b bb23a最小化：{ 0,1},{2,3}{ 0,1} a{1}{0,1} b{ 2}{ 2,3} a{ 0,3}{ 2,3} b{ 3}{ 0,1},{2},{3}a ab b012ab(b)b b a023a baa bb1a5a a4已经确定化了 ,进行最小化最小化：{{ , }, {,,,}}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}b b a012a baP64–14(1)0101(2):X( 010|)*Y21X1Y确定化：01 {X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01 01211221333311011123最小化：{ 0,1},{ 2, 3}{ 0,1} 0{1}{ 0,1} 1{2}{ 2,3} 0{1,3}{ 2,3} 1{3}{ 0,1},{ 2},{ 3}111013第四章P81–1(1)按照 T,S 的顺序消除左递归G (S)S a |^| (T )T STT, ST |递归子程序：procedure S;beginif sym='a' or sym='^'then abvanceelse if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS; Tend;procedure T ;beginif sym=','then beginadvance;S; Tendend;其中 :sym: 是输入串指针IP 所指的符号advance: 是把 IP 调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST( T )={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T )={)}预测分析表a^(),# S S a S ^S (T)T T ST T ST T STT T T, ST是LL(1) 文法P81–2文法：E TEE E |T FTT T |FPFF* 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|bFIRST(+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)+*()a b^#E E TE 'E TE ' E TE ' E TE 'E'E E E E T T FT T FT T FT T FTT' FF' P T T T T T T T T T T TF PF F PF F PF F PFF F* F F F F F F FP( E )P a P b P^(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是，满足三个条件。