编译原理第三版课后习题答案

..目录P36-61P36-71P36-81P36-92P36-102P36-112P64–73P64–84P64–124P64–146P81–17P81–28P81–311P133–111P133–211P133–313P134–514P164–518P164–718P217–118P217–319P218–419P218–520P218–621P218–721P219–1221P270–923P36-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}φφφφ给状态编号：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}φφφφ给状态编号：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:是输入串指针IP所指的符号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>>^>><<<<=<>>>,<<<>>是算符文法,并且是算符优先文法<3>优先函数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>项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:={,,,,}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>={,,,,,}=项目集规范族为C={,,,,,,}<3>不是SLR文法状态3,6,7有移进归约冲突状态3：FOLLOW<S’>={#}不包含a,b状态6：FOLLOW<S>={#,a,b}包含a,b,；移进归约冲突无法消解状态7：FOLLOW<A>={a,b}包含a,b；移进归约冲突消解所以不是SLR文法。<4>构造例如LR<1>项目集规范族见下图：对于状态5,因为包含项目[],所以遇到搜索符号a或b时,应该用归约。又因为状态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-BC<11> +D> i:=E*<-E A-BC <,C,-,><12> +D> i:=E*<E A-B--<13> D> i:=E*<E+ A-B<14> > i:=E*<E+i A-BD<15> > i:=E*<E+E A-BD <+,,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