编译原理第三版课后答案

编译 原理 课后题答案第二章P36-6(1)是 09组成的数字串LG()1(2)最左推导:NDNDDD010217345658最右推导: NNDND727127012743868568P36-7G(S)ONDSA1357924680|P36-8文法： ETFi|*/()最左推导: FTiiTFiiFiETETTiii*()()()()()()最右推导:ETFETiFiEiTiFiiEFii*()()()()*()(语法树：/*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 0X 1 2 3 4 Y5X Y012 30 1011 1最小化：,023456023452610230 1456021, 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,ba6545012430 1确定化：a b0 0,1 10,1 0,1 11 0 给状态编号：a b0 1 21 1 22 0 33 3 3aaa b b bba最小化：,01230123ab a ab bab(b)b b aa ba0 12 30 1 20 2 3a bb aa a已经确定化了,进行最小化最小化： , 01234501243524355012430124, ,abbaba,3355bb b aa baP6414(1) 010(2):(|)*010 11 4 50 1 20 1YXYX210确定化：0 1X,1,Y 1,Y 21,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递归子程序：02130 1 3procedure 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 ;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