编译 原理 课后题答案第二章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 3 0 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 3 a bb aa a已经确定化了,进行最小化最小化： , 01234501243524355012430124, ,abbaba,3355bb b aa baP6414(1) 010(2):(|)*010 11 4 50 1 20 1YXYX21 0确定化：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 TTTTF 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 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;P813/*(1) 是，满足三个条件。(2) 不是，对于 A 不满足条件 3。(3) 不是，A、B 均不满足条件 3。(4) 是，满足三个条件。*/第五章P1331ETF*短语: E+T*F, T*F,直接短语: T*F句柄: T*FP1332文法：SaT|(),(1)最左推导: SaTaSaSaSTTST(),(,),(,)(,)(,)(,)(,)(,),(,)(,)(,)(,)(,)(,)a最右推导:STSTSTaSTaaaaS(),)(,)(,)(,)(,)(,),(,)()()()(),),S Saa(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)# 归 7 #(T, a),(a),a)# 进8 #(T,a ),(a),a)# 进9 #(T,S ),(a),a)# 归10 #(T ),(a),a)# 归11 #(T) ,(a),a)# 进12 #(S ,(a),a)# 归13 #(T ,(a),a)# 归 14 #(T, ,(a),a)# 进15 #(T, ,(a),a)# 进16 #(T,S ,(a),a)# 归17 #(T ,(a),a)# 归18 #(T, (a),a)# 进19 #(T,( a),a)# 进20 #(T,(a ),a)# 进21 #(T,(S ),a)# 归22 #(T,(T ),a)# 归23 #(T,(T) ),a)# 进24 #(T,S ),a)# 归25 #(T ),a)# 归26 #(T) ,a)# 进27 #(S ,a)# 归28 #(T ,a)# 归29 #(T, a)# 进30 #(T,a )# 进31 #(T,S )# 归32 #(T )# 归33 #(T)