编译原理课后习题答案(陈火旺+第三版)

课后 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 网 http://www.khdaw.com 第二章 P36-6 (1) 是0~9组成的数字串 (2) 最左推导: 最右推导: P36-7 G(S) P36-8 文法： 最左推导: 最右推导: 语法树：/******************************** *****************/ P36-9 句子iiiei有两个语法树： P36-10 /************** ***************/ P36-11 /*************** L1: L2: L3: L4: ***************/ 第三章习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 参考答案 P64–7 (1) 0 1 1 0 1 1 确定化： 0 1 {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,} 0 1 0 0 0 1 1 0 0 1 0 1 1 1 最小化： 0 1 0 0 1 0 0 1 0 1 1 1 P64–8 (1) (2) (3) P64–12 (a) a a,b a 确定化： a b {0} {0,1} {1} {0,1} {0,1} {1} {1} {0} φ φ φ φ 给状态编号： a b 0 1 2 1 1 2 2 0 3 3 3 3 a a a b b b b a 最小化： a a b b a b (b) b b a a b a a b b a a a 已经确定化了,进行最小化 最小化： b b a a b a P64–14 (1) 0 1 0 (2): 0 1 0 确定化： 0 1 {X,1,Y} {1,Y} {2} {1,Y} {1,Y} {2} {2} {1,Y} φ φ φ φ 给状态编号： 0 1 0 1 2 1 1 2 2 1 3 3 3 3 0 0 1 0 1 1 1 0 最小化： 0 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 error end; procedure T; begin S; end; procedure ; begin if sym=',' then begin advance; S; end end; 其中: sym:是输入串指针IP所指的符号 advance:是把IP调至下一个输入符号 error:是出错诊察程序 (2) FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST()={,,} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW()={)} 预测 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 表 a ^ ( ) , # S T 是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) + * ( ) a b ^ # E E' T T' F F' P (4) procedure E; begin if sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error end procedure E'; begin if sym='+' then begin advance; E end else if sym<>')' and sym<>'#' then error end procedure T; begin if sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error end procedure T'; begin if sym='(' or sym='a' or sym='b' or sym='^' then T else if sym='*' then error end procedure F; begin if sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' end else error end procedure F'; begin if sym='*' then begin advance; F' end end procedure 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 error end; P81–3 /*************** 是，满足三个条件。 不是，对于A不满足条件3。 不是，A、B均不满足条件3。 是，满足三个条件。 ***************/ 第五章 P133–1 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F P133–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 ^ ( ) , f 4 4 2 4 4 g 5 5 5 2 3 （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 # 归 success P134–5 (1) 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. (2) S A S a A S d 确定化： S A a b {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 S S A a b S a A S b S A b a A A S b a a b b a 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 b A A A S a a S S a S a a A a A S b S A b a a S b b S b A A 第六章 /********************第六章会有点难 P164–5 (1) E E1＋T {if (E1.type = int) and (T.type = int ) then E.type := int else E.type := real} E T {E.type := T.type} T num.num {T.type := real} T num {T.type := int} (2) P164–7 S L1|L2 {S.val:=L1.val+(L2.val/2 )} S L {S.val:=L.val} L L1B {L.val:=2*L1.val + B.val; L.length:=L1.length+1} L B {L.val:=B.c; L.length :=1} B 0 {B.c:=0} B 1 {B.c:=1} ***********************/ 第七章 P217–1 a*(-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)的 三元式序列: +, 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 * 20 T1:=T1+j T2:=A–84 T3:=4*T1 Tn:=T2[T3] //这一步是多余的 T4:= i + j T5:=B–4 T6:=4*T4 T7:=T5[T6] T8:= i * 20 T8:=T8+j T9:=A–84 T10:=4*T8 T11:=T9[T10] T12:= i + j T13:=D–4 T14:=4*T12 T15:= T13[T14] T16:=T11+T15 T17:=C–4 T18:=4*T16 T19:=T17[T18] T20:=T7+T19 Tn:=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 – 5 MAXINT – 4 MAXINT – 3 MAXINT – 2 MAXINT – 1 MAXINT (2)翻译模式 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 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 then I.place := p else error} {M.quad := nextquad} ****************/ 方法2： S→ for id:=E1 to E2 do S1 S→ F S1 F→ 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 then emit(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 A A=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 A A=7 (4) 传值 即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元 A:=2; B:=3; x:=A+B y:=A z:=A y:=y+1 z:=z+x print A A=2 过程调用不改变A的值 第十章 P306-1 P306-2 read A,B F:=1 C:=A*A D:=B*B if C100 goto --------------------------- halt --------------------------- : F:=F-1 goto --------------------------- 基本块为 、 、 、 、 P307-4 SHAPE \* MERGEFORMAT B2有回路，所以{B2}是循环，B2既是入口节点，又是出口节点 代码外提：不存在不变运算，故无代码外提 强度削弱：A:=K*I B:=J*I *→+ 删除基本归纳变量：I<100 可以用A<100*K或B<100*J代替 P307-5 {B2,B3}是循环，B2是入口节点，也是出口节点 代码外提：B:=J+1 删除归纳变量 X Y X 1 2 3 4 Y 5 3 2 0 1 6 5 4 0 2 1 5 4 3 1 0 1 0 3 2 2 1 0 0 3 2 5 4 1 0 2 1 1 0 Y X 2 Y 1 X 1 0 3 2 3 1 0 1 9 8 7 11 10 0 4 3 2 5 6 3:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ���� EMBED \* MERGEFORMAT ��� 5:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� 6:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� 4:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� 0:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� 7:� EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� � EMBED \* MERGEFORMAT ��� 2:� EMBED \* MERGEFORMAT ��� 1:� EMBED \* MERGEFORMAT ��� 8： � EMBED \* MERGEFORMAT ��� 1： � EMBED \* MERGEFORMAT ��� 5： � EMBED \* MERGEFORMAT ��� 3： 3： � EMBED \* MERGEFORMAT ��� 0： � EMBED \* MERGEFORMAT ��� 6： � EMBED \* MERGEFORMAT ��� 9： � EMBED \* MERGEFORMAT ��� 4： � EMBED \* MERGEFORMAT ��� 7： � EMBED \* MERGEFORMAT ��� 2： � EMBED \* MERGEFORMAT ��� 10： � EMBED \* MERGEFORMAT ��� 5： B1 B3 B2 B5 B4 I:=1 read J,K A:=K*I B:=J*I T:=K*100 L: C:=A*B write C A:=A+K B:=B+J if A