編譯原理課后復習題答案(陳火旺+第三版)

..第二章P36-6<1>是0~9組成的數字串<2>最左推導:最右推導:P36-7G<S>P36-8文法：最左推導:最右推導:語法樹：/*************************************************/P36-9句子iiiei有兩個語法樹：P36-10/*****************************/P36-11/***************L1:L2:L3:L4:***************/第三章習題參考答案P64–7<1>XYXYX1X1234Y511011確定化：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,}0320103201001101654016540111最小化：002102100101543015430111P64–8<1><2><3>P64–12<a>a10a,b10a確定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ給狀態(tài)編號：ab012112203333a10a10abbb3232ba最小化：aa210bb210ab<b>032bba032abaab541ba541aa已經確定化了,進行最小化最小化：021bba021abaP64–14<1>0101100<2>:YXYX2201Y1XY1X0確定化：01{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φφφφ給狀態(tài)編號：010121122133330101001032113210最小化：031011131000第四章P81–1<1>按照T,S的順序消除左遞歸遞歸子程序：procedureS;begin ifsym='a'orsym='^' thenabvance elseifsym='<' thenbegin advance;T; ifsym='>'thenadvance; elseerror; end elseerrorend;procedureT;begin S;end;procedure;begin ifsym=',' thenbegin advance; S; endend;其中:sym:是輸入串指針I(yè)P所指的符號advance:是把IP調至下一個輸入符號error:是出錯診察程序<2>FIRST<S>={a,^,<}FIRST<T>={a,^,<}FIRST<>={,,}FOLLOW<S>={>,,,#}FOLLOW<T>={>}FOLLOW<>={>}預測分析表a^<>,#ST是LL<1>文法P81–2文法：<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>考慮下列產生式: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>+*<>ab^#EE'TT'FF'P<4>procedureE;begin ifsym='<'orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance;Eend elseifsym<>'>'andsym<>'#'thenerrorendprocedureT;begin ifsym='<'orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerrorend procedureT';begin ifsym='<'orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='<'orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance;F'endendprocedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='<'then begin advance;E; ifsym='>'thenadvance elseerror end elseerrorend;P81–3/***************是,滿足三個條件。不是,對于A不滿足條件3。不是,A、B均不滿足條件3。是,滿足三個條件。***************/第五章P133–1短語:E+T*F,T*F,直接短語:T*F句柄:T*FP133–2文法：<1>最左推導:最右推導:<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> # 進34 #S # 歸P133–3<1>FIRSTVT<S>={a,^,<}FIRSTVT<T>={,,a,^,<}LASTVT<S>={a,^,>}LASTVT<T>={,,a,^,>}<2>a^<>,a>>^>><<<<=<>>>,<<<>>是算符文法,并且是算符優(yōu)先文法<3>優(yōu)先函數a^<>,f44244g55523〔4棧 輸入字符串 動作# 〔a,<a,a># 預備#< a,<a,a>># 進#<a ,<a,a>># 進#<t ,<a,a>># 歸#〔t, <a,a># 進#〔t,〔 a,a# 進#〔t,〔a ,a# 進#〔t,〔t ,a# 歸#〔t,〔t, a# 進#〔t,〔t,a # 進#〔t,〔t,s # 歸#〔t,〔t # 歸#〔t,〔t # 進#〔t,s # 歸#〔t # 歸#〔t # 進#s # 歸successP134–5<1>0. 1.2. 3.4. 5.6. 7.8. 9. 10. 11.<2>11987SA987S11100a11100432432ASd5656確定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{1,2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,9,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,4,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{11}φφφφ{6}φφφφAS3:5:6:3:5:6:SAabSaASbSAbaA4:0:7:4:0:7:ASbaabba2:1:2:1:DFA構造LR<0>項目集規(guī)范族也可以用GO函數來計算得到。所得到的項目集規(guī)范族與上圖中的項目集一樣:={,,,,}GO<,a>={}=GO<,b>={}=GO<,S>={,,,,,}=GO<,A>={,,,,}=GO<,a>={}=GO<,b>={}=GO<,S>={,,,,}=GO<,A>={,,,,,}=GO<,a>={}=GO<,b>={}=GO<,S>={,,,,,}=GO<,A>={,,,,}=GO<,a>={}=GO<,b>={}=GO<,S>={,,,,}=GO<,A>={,,,,,}=GO<,a>={}=GO<,b>={}=GO<,S>={,,,,,}=GO<,A>={,,,,}=GO<,a>={}=GO<,b>={}=GO<,S>={,,,,}=GO<,A>={,,,,,}=項目集規(guī)范族為C={,,,,,,}<3>不是SLR文法狀態(tài)3,6,7有移進歸約沖突狀態(tài)3：FOLLOW<S’>={#}不包含a,b狀態(tài)6：FOLLOW<S>={#,a,b}包含a,b,；移進歸約沖突無法消解狀態(tài)7：FOLLOW<A>={a,b}包含a,b；移進歸約沖突消解所以不是SLR文法。<4>構造例如LR<1>項目集規(guī)范族見下圖：對于狀態(tài)5,因為包含項目[],所以遇到搜索符號a或b時,應該用歸約。又因為狀態(tài)5包含項目[],所以遇到搜索符號a時,應該移進。因此存在"移進-歸約"矛盾,所以這個文法不是LR<1>文法。bbb8：1：5：8：1：5：AAASaaS3：3：SaS3：0：3：0：aaAaA6：9：6：9：4：S4：bSAbaaSbb7：2：7：2：10：10：SbAA5：5：第六章/********************第六章會有點難P164–5<1>EE1＋T{if<E1.type=int>and<T.type=int> thenE.type:=int elseE.type:=real}ET {E.type:=T.type}Tnum.num{T.type:=real}Tnum {T.type:=int}<2>P164–7SL1|L2 {S.val:=L1.val+<L2.val/2>}SL {S.val:=L.val}LL1B {L.val:=2*L1.val+B.val; L.length:=L1.length+1}LB {L.val:=B.c; L.length:=1}B0 {B.c:=0}B1 {B.c:=1}***********************/第七章P217–1a*<-b+c> abc+*a+b*<c+d/e> abcde/+*+-a+b*<-c+d> abcd+*+if<x+y>*z=0then<a+b>↑celsea↑b↑c xy+z*0=ab+c↑abc↑↑￥或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–3-<a+b>*<c+d>-<a+b+c>的三元式序列:+,a,b,<1>,-+,c,d*,<2>,<3>+,a,b+,<5>,c-,<4>,<6>間接三元式序列:三元式表：+,a,b,<1>,-+,c,d*,<2>,<3>+,<1>,c-,<4>,<5>間接碼表：<1><2><3><4><1><5><6>四元式序列:+,a,b,,,-,+,c,d,*,,,+,a,b,+,,c,-,,,P218–4自下而上分析過程中把賦值句翻譯成四元式的步驟:A:=B*<-C+D>步驟輸入串棧PLACE 四元式<1> A:=B*<-C+D> <2> :=B*<-C+D> i A<3> B*<-C+D> i:= A-<4> *<-C+D> i:=i A-B<5> *<-C+D> i:=E A-B <6> *<-C+D> i:=E A-B<7> <-C+D> i:=E* A-B-<8> -C+D> i:=E*< A-B--<9> C+D> i:=E*<- A-B---<10> +D> i:=E*<-i A-B---C<11> +D> i:=E*<-E A-B---C <,C,-,><12> +D> i:=E*<E A-B--<13> D> i:=E*<E+ A-B---<14> > i:=E*<E+i A-B---D<15> > i:=E*<E+E A-B---D <+,,D,><16> > i:=E<E A-B--<17> i:=E*<E> A-B---<18> i:=E+E A-B- <*,B,,><19> i:=E A- <:=,,-,A>A產生的四元式：<,C,-,><+,,D,><*,B,,><:=,,-,A>P218–5/****************設A：10*20,B、C、D：20,寬度為w＝4則T1:=i*20T1:=T1+jT2:=A–84T3:=4*T1Tn:=T2[T3]//這一步是多余的T4:=i+jT5:=B–4T6:=4*T4T7:=T5[T6]T8:=i*20T8:=T8+jT9:=A–84T10:=4*T8T11:=T9[T10]T12:=i+jT13:=D–4T14:=4*T12T15:=T13[T14]T16:=T11+T15T17:=C–4T18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6<jnz,A,-,0><j,-,-,102><jnz,B,-,104><j,-,-,0><jnz,C,-,103><j,-,-,106><jnz,D,-,104>--假鏈鏈首<j,-,-,100>--真鏈鏈首假鏈：{106,104,103}真鏈：{107,100}P218–7<j<,A,C,102><j,-,-,0><j<,B,D,104><j,-,-,101><j=,A,‘1’,106><j,-,-,109><+,C,‘1’,T1><:=,T1,-,C><j,-,-,100><j≤,A,D,111><j,-,-,100><+,A,‘2’,T2><:=,T2,-,A><j,-,-,109><j,-,-100>P219–12/********************<1>MAXINT–5MAXINT–4MAXINT–3MAXINT–2MAXINT–1MAXINT<2>翻譯模式方法1：forE1:=E2toE3doS {backpatch<S1.nextlist,nextquad>; backpatch<F.truelist,M.quad>;emit<F.place‘:=’F.place‘+’1>; emit<‘j,’F.place‘,’F.end‘,’M.quad>; S.nextlist:=F.falselist; } {F.falselist:=makelist<nextquad>;emit<‘j>,’E1.place‘,’E2.place‘,0’>; emit<I.Place‘:=’E1.place>; F.truelist:=makelist<nextquad>; emit<‘j,-,-,-’>; F.place:=I.place; F.end:=E2.place; } {p:=lookup<>; ifp<>nilthenI.place:=pelseerror} {M.quad:=nextquad}****************/方法2：S→forid:=E1toE2doS1S→FS1F→forid:=E1toE2dodo{INITIAL=NEWTEMP;emit<‘:=,’E1.PLACE’,-,’INITIAL>;FINAL=NEWTEMP;emit<‘:=,’E2.PLACE’,-,’FINAL>;p:=nextquad+2;emit<‘j,’INITIAL‘,’FINAL’,’p>;F.nextlist:=makelist<nextquad>;emit<‘j,－,－,－’>;F.place:=lookup<>;ifF.placenilthenemit<F.place‘:=’INITIAL>F.quad:=nextquad;F.final:=FINAL;}{backpatch<S1.nextlist,nextquad> p:=nextquad+2;emit<‘j,’F.place‘,’F.final’,’p>;S.nextlist:=merge<F.nextlist,makelist<nextquad>>;emit<‘j,－,－,－’>;emit<‘succ,’F.place’,-,’F.place>;emit<‘j,－,－,’F.quad>;}第九章P270–9<1>傳名即當過程調用時,其作用相當于把被調用段的過程體抄到調用出現處,但必須將其中出現的任一形式參數都代之以相應的實在參數。A:=2;B:=3;A:=A+1;A:=A+<A+B>;printA;∴A=9<2>傳地址即當程序控制轉入被調用段后,被調用段首先把實在參數抄進相應的形式參數的形式單元中,過程體對形參的任何引用或賦值都被處理成對形式單元的間接訪問。當被調用段工作完畢返回時,形式單元〔都是指示器所指的實參單元就持有所希望的值。①A:=2;B:=3;T:=A+B②把T,A,A的地址抄進已知單元J1,J2,J3③x:＝J1;y:=J2;z:=J3//把實參地址抄進形式單元,且J2=J3④Y↑:=y↑+1Z↑:=z↑+x↑//Y↑：對