第二章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)XY X1234Y5 0 1 1 0 1 1确定化：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,} 0320 1 01 0 0 1 1 0654 0 1 0 1 1 1最小化：精品. 002 1 1 0 0 1 0543 0 1 0 1 1 1P64–8(1) (2)(3)P64–12(a) a10 a,b a确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φ精品.φφφ给状态编号：ab012112203333 a10 a a b b b32 b a最小化： a a210 b b a b(b)032 b b a a b a a b541 b a a a已经确定化了,进行最小化精品.最小化：021 b b a a b aP64–14 (1) 010 1 0(2):YX 2 0 1Y1X 0确定化：01{X,1,Y}{1,Y}{2}精品.{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01012112213333 010 0 1 032 1 1 1 0最小化： 0310 1 1 1 0 0第四章P81–1(1) 按照T,S的顺序消除左递归递归子程序：procedure S;begin if sym='a' or sym='^' then abvance else if sym='(' 精品. then begin advance;T; if sym=')' then advance; else error; end else errorend;procedure T;begin S;end;procedure ;begin if sym=',' then begin 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)procedure E;begin if sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else errorendprocedure E';begin if sym='+' then begin advance; E end else if sym<>')' and sym<>'#' then errorendprocedure T;begin if sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else errorend procedure T';begin if sym='(' or sym='a' or sym='b' or sym='^' then T else if sym='*' then errorendprocedure F;begin if sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' end else errorend procedure F';begin if sym='*' then begin advance; F' endendprocedure P;begin if sym='a' or sym='b' or sym='^' then advance else if sym='(' then精品. begin advance; E; if sym=')' then advance else error end else errorend;P81–3/***************(1) 是，满足三个条件。
2) 不是，对于A不满足条件33) 不是，A、B均不满足条件34) 是，满足三个条件/第五章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)1987 S A S 11100 a 432 A S d 56确定化：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}φφφφ A S3:5:6: S A a b S a A S b S A b a A4:0:7: A S b a a b b a2: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)文法精品. b b b8：1：5： A A A S a a S3： S a S3：0： a a A a A6：9： 4： S b S A b a a S b b7：2：10： S b A A5：精品.第六章/********************第六章会有点难P164–5(1)EE1＋T {if (E1.type = int) and (T.type = int ) then E.type := int else E.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) ab@c+*a+b*(c+d/e) abcde/+*+-a+b*(-c+d) a@bc@d+*+ if (x+y)*z =0 then (a+b)↑c else a↑b↑c xy+z*0= ab+c↑abc↑↑ ￥ 或 xy+z*0= P1 jez ab+c↑ P2 jump abc↑↑ P1 P2精品.P217–3-(a+b)*(c+d)-(a+b+c)的三元式序列:(1) +, a, b(2) @, (1), -(3) +, c, d(4) *, (2), (3)(5) +, a, b(6) +, (5), c(7) -, (4), (6)间接三元式序列:三元式表：(1) +, a, b(2) @, (1), -(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1) +, a, b, (2) @, , -, (3) +, c, d, (4) *, , , (5) +, a, b, (6) +, , c, (7) -, , , 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)(20) 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–4精品.T18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6100. (jnz, A, -, 0)101. (j, -, -, 102)102. (jnz, B, -, 104)103. (j, -, -, 0)104. (jnz, C, -, 103)105. (j, -, -, 106)106. (jnz, D, -, 104) --假链链首107. (j, -, -, 100) --真链链首假链：{106,104，103}真链：{107,100}P218–7100. (j<, A, C, 102)101. (j, -, -, 0)102. (j<, B, D, 104)103. (j, -, -, 101)104. (j=, A, ‘1’, 106)105. (j, -, -, 109)106. (+, C, ‘1’, T1)107. (:=, T1, -, C)108. (j, -, -, 100)109. (j≤, A, D, 111)110. (j, -, -, 100)111. (+, A, ‘2’, T2)112. (:=, T2, -, A)113. (j, -, -, 109)114. (j, -, - 100)P219–12/********************(1)MAXINT – 5MAXINT – 4MAXINT – 3MAXINT – 2MAXINT – 1MAXINT精品.(2)翻译模式方法1： for E1 := E2 to E3 do S {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(id.name); if p <> nil thenI.place := pelse error} {M.quad := nextquad}****************/方法2：S→ for id:=E1 to E2 do S1S→ F S1F→ for id:=E1 to E2 do do{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(id.name);if F.place¹nil thenemit(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); print A; ∴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↑+1 Z↑:=z↑+x↑ // Y↑：对y的间接访问 Z↑：对z的间接访问⑤print AA=8(3) 得结果每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中精品.①A:=2;B:=3;T:=A+B②把T,A,A的地址抄进已知单元J1,J2,J3③x1:=J1;x2:=T; y1:=J2;y2:=A; z1:=J3;z2:=A; //将实参的地址和值分别放进两个形式单元中④y2:=y2+1; z2:=z2+x2; //对形参第二个单元的直接访问⑤x1↑：＝x2; y1↑:=y2; z1↑:=z2 //返回前把第二个单元的内容存放到第一个单元所指的实参地址中⑥print AA=7(4) 传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+1z:=z+xprint AA=2过程调用不改变A的值第十章P306-1精品.P306-2 read A,BB1 F:=1 C:=A*A D:=B*BB3B2 if C100 goto 精品.--------------------------- halt ---------------------------: F:=F-1 goto ---------------------------基本块为、、、、P307-4I:=1read J,KA:=K*IB:=J*IT:=K*100L: C:=A*B write C A:=A+K B:=B+J if A