编译原理课后习题答案陈火旺+第三版

第二章P36-6(1)是 09组成的数字串LG()1(2)最左推导:NDNDDD010217345658最右推导: NNDND727127012743868568P36-7G(S)ONDSA1357924680|P36-8文法： ETFi|*/()最左推导: FTiiTFiiFiETETTiii*()()()()()()最右推导: FTiFiiiFiiTTEFii*()()()()()(语法树：/*EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFii*+i i- i+*/P36-9句子 iiiei有两个语法树：SieiSieiP36-10/*) (|ST*/P36-11/*L1: |cCabASL2: bcBaAS|L3:|aBbASL4: ABS|01|*/第三章习题参考答案P647(1)10(|)*01 1 0 11确定化：0 1X 1,2,3 1,2,3 2,3 2,3,42,3 2,3 2,3,42,3,4 2,3,5 2,3,42,3,5 2,3 2,3,4,Y2,3,4,Y 2,3,5 2,3,4,01 00 0 1 1 00 1011 1最小化：X 1 2 3 4 Y5X Y6012 354,012345610234512601230 4560121, 01 0 0 1 00 1011 1P648(1) 01)|(*(2) )5|0(|)9|87|65|43|210)(9|87|65|43|2( *(3) *)|(1|)0|(P6412(a)aa,ba确定化：a b0 0,1 10,1 0,1 11 0 5012430 1 给状态编号：a b0 1 21 1 22 0 33 3 3aaa b b bba最小化：,01230123ab a ab bab(b)b b aa baa bb aa a已经确定化了,进行最小化0 12 30 1 20 2 31 4 5最小化：, 01234501243524355012430124, ,abbaba,3355bb b aa baP6414(1) 010(2):(|)*010 10确定化：0 1X,1,Y 1,Y 20 1 20 1YXYX211,Y 1,Y 22 1,Y 给状态编号：0 10 1 21 1 22 1 33 3 3001 01 1 10最小化： ,012301230 01 1 100第四章P811(1) 按照 T,S的顺序消除左递归|,)(|TSaG递归子程序：procedure S;beginif sym=a or sym= then abvanceelse if sym=( 02130 1 3then beginadvance;T;if sym=) then advance;else error;endelse errorend;procedure T;beginS; Tend;procedure ;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( )=)预测分析表a ( ) , #S STT TS TS,是 LL(1)文法P812文法：|)(*|baEPFTE(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)考虑下列产生式: ETFPab|*|()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)+ * ( ) a b #E ETETETE T FFFT F FPFPFPF *P E()ab(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# then errorendprocedure 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 T else if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= then begin P; F endelse errorendpro