陈火旺编译原理课后习题答案

1、第二章P36-6(1)L(G1)是 09 组成的数字串(2)最左推导:NDNDNDNDD NDDDDD 3D 34NDD最右推导:NNDN 7NNDN4NNDN8DDDD 0DDD01DD012D0127DDD 5DD 56D568ND 7 N 27D 434ND 8 N 68ND27 N127D68568D1270127P36-7G(S)O 1|3|5|7| 9N 2|4|6|8|OD0| NSO| AOA AD | NP36-8文法：E T|E T|E TT F|T*F|T/FF (E)|i最左推导:E ET TTF T i T i T*Fi F*F i i*F i i*iE T T*F

2、F*Fi*( i T) i*(i F)i* F i *( E) i *( E T) i *( i i )i *( T T) i *( F T)最右推导:E E T E T*FE T*i E F*iE i*i T i*iF i*i i i*iE T F*T F*FF *( E ) F *( E T)F *( E F ) F *( E i )语法树：F *( T i )F *( F i )F *( i i ) i *( i i )/*Eii+i+ii-i-iii+i*i*/P36-9句子iiiei有两个语法树：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiie

3、iP36-10/*S TS |TT (S)|()*/P36-11/*L1:S ACA aAb | abC cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1B0| A*/第三章习题参考答案P64 - 71(01) 1010确定化:01101X1,2,31,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4,最小化:0,1,2,3,4,5,60,123,4,5 01,3,50,1,2,3,431,2,4向0,1,2,3,4, 5,60,1

4、,2,3,4 01,3,50,1,2,3,4, 5,60,1,2,3。1,30,1,2,311,2,40,1,234, 5,60,1 0 1 0,11 1,22,30 32,31 40,1,2,3, 4, 5, 6P64 - 8*(1|0) 01(2)*(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) (0|5)|(0|5)0*1(0|10*1)* |1*0(0|10*1)*P64- 12(a)a确定化:ab00,110,10,1110给状态编号:ab012112203333最小化：0,1, 2,30,1 a 1 0,1b 2 a2,30,3 2,3b 3ab0

5、,1, 2, 3aa已经确定化了，进行最小化最小化:0,1, 2,3,4,50,1a 10,1b 2,42,3,4,5a 1,3,0,52,3,4,5b 2,3,4,52,4a 1,02,4b 3,53,5a 3,53,5b 2,40,1, 2,4, 3,50,1a2,4a3,5a11,03,50,1b 2,42,4b3,5b3,52,4P64 14-01X,1,Y1,Y2确定化：1，Y1，Y221，Y给状态编号:01012112213333最小化：0,1,2,30,10 10,11 22,3o 1,32,3i 30，1，2,3第四章P81- 1(1)按照T,S的顺序消除左递归G(S)Sa1A

6、l(T)T STT ,ST |递归子程序：procedure S;beginif sym='a' or sym='A' then abvance else if sym='(' then begin advance;T; if sym=')' then advance; else error;end else error end;procedure T;beginS;end;procedure ;beginif sym=','then begin advance; S;endend;其中：sym:是输入串指针IP所

7、指的符号 advance:是把IP调至下一个输入符号 error:是出错诊察程序(2)FIRST(S尸叱,(FIRST(T尸aF,(FIRST()=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=) 预测分析表aA(),#ST是LL(1)文法P812文法:E TEEE|TFTTT IFPFF*F|P (E)|a|brFIRST(E尸(,ah>FIRST(E'尸+,£ FIRST(T尸(.ah>FIRST(T')=(,a,b,A,£ FIRST(F)=(,a,b,AFIRST(F尸*,£ FIRST(P)=(,a

8、,b,AFOLLOW(E尸#,)FOLLOW(E'尸#,)FOLLOW(T尸+,),#FOLLOW(T'尸+,),#FOLLOW(F)=(,a,b,A,+.),#FOLLOW(F')=(,a,b,A,+.),# FOLLOW(P)=*,(,a,b,A,+.),# (2)考虑下列产生式：E E|TTIF*F |P(E)|A|a|bFIRST(+E) A FIRST( £ )=+ A &=()FIRST(+E) A FOLLOW(E')=+ n #,)=()FIRST(T) n FIRST( £ )=(,a,b,A&=()FIRS

9、T(T) n FOLLOW(T')=(,a,b,A n +,),#=() FIRST(*F') A FIRST( £ )=* &=()FIRST(*F') n FOLLOW(F')=* n (,a,b,A,+,),#=()FIRST(E) n FIRST(a) n FIRST(b) n FIRST(A)= (j) 所以，该文法式LL(1)文法. +*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TT TTFF PFF P

10、FF PFF PFF'FF *FfF FFFF PP (E)P aP bP A(4) procedure E; beginif sym='(' or sym='a' or sym='b' or sym='A' then begin T; E' end else errorendprocedure E'beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#'

11、 then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='A' then begin F; T' end else errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym='A' then Telse if sym='*' then errorendprocedure F;be

12、ginif sym='(' or sym='a' or sym='b' or sym='A' then begin P; F' end else errorendprocedure F'beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='A' then advance else if sym='('

13、thenbeginadvance; E;if sym=')' then advance else errorendelse errorend;P813/*(2)(4)是，满足三个条件。不是，对于A不满足条件3。不是，A B均不满足条件3。 是，满足三个条件。*/第五章P133- 1E E T E 短语：E+T*F, T*F, 直接短语：T*F 句柄：T*FT* FP133- 2文法：S a|A|(T)T T,S|S最左推导：S (T)(T,S)S (T,S)(S,S)(T,S),S,S), S) (a,a),A ,S),S) (a,a),A ,(a), a)最右推导：(S,S)

14、(a,S)(a,(T)(a,(T,S)(T),S)(T,S),S)(T,S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),A ,(T), S) (a,a),A ,(S), S)(a,(S,S)(a,(a,S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S,S),S)(a,a ,(a), S)S (T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)S (T,S) (T,(a), a)(a,(a,a)(T,a)(S,a)(T),a)(T,S),a)(T,(T), a)(T,S,(a), a

15、)(T,A,(a),a)(SJ ,(a), a)(T,(S), a)(T),"(a),a)(T,S/，(a),a)(T,a),A,(a),a)( S,a/，(a), a) ( a,a/，(a), a)(2)(a,a)F,(a),a)(S,a)F,(a),a)(T, a/,(a),a)(TS,(a),a)(T)，A，(a)，a)(S，A,(a),a)(T,A,(a),a)(TS，(a)，a)(T,( a),a)(T,( S),a)(T,( T),a)(TS),a)(IL，a)(S,a)(IS)(I)S“移进-归约”过程:步骤栈输入串动作0#(a,a),A,(a),a)#预备1#(a,a

16、),A,(a),a)#进2#(a,a),A,(a),a)#进3#(a,a),A,(a),a)#进4#(a,a),A,(a),a)#进5#(S,a),A,(a),a)#归6#(I,a),A,(a),a)#归7#(I,a)F,(a),a)#进8#(I,a),A,(a),a)#进9#(I,S),A,(a),a)#归10#(I),A,(a),a)#归11#(I),A,(a),a)#进12#(S,A,(a),a)#归13#(I,A,(a),a)#归14#(I,A,(a),a)#进15#(I,a,(a),a)#进16#(I)S,(a),a)#归17#(I,(a),a)#归18#(I,(a),a)#进19#

17、(I,(a),a)#进20#(I,(a),a)#进21#(I,(S),a)#归22#(I,(I),a)#归23#(I,(I),a)#进24#(I)S),a)#归25#(I),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-3FIRSTVT(S尸a,A,(FIRSTVT(T尸,a,A,(LASTVT(S尸a/,)LASTVT(T尸“a。)(2)aA(),a>>A>>(<<<=<)>>,

18、<<<>>G6是算符文法，并且是算符优先文法优先函数(4)栈输入字符串动作# (a,(a,a) # (a, (a,a)#进# (a, (a,a)#进# (t, (a,a)#归预备aA(),f44244g55523#(t,#(t,(#(t,(a#(t,(t#(t,(t,#(t,(t,a#(t,(t,s#(t,(t#(t,(t)#(t,s#(t#(t)#ssuccess(a,a) ) #进a,a) #进,a) #进,a) #归a) #进)#进)#归)#归)#进)#归)#归#进#归P134 50. S4. S8. AS 1. S S 2. SAS 5. Sb 6. s

19、bS A9. ASA 10. A aAS 3. S A S7. A SA11. A a(2)确定化:SAab0,2,5,7,101,2,5,7,8,10 2,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,102,4,5,7,8,10 2,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,10 1162,3,5,7,9,10 2,4,5,7,8,10 2,3,5,7,101162,4,5,7,8,10 2,5,7,8,102,3,5,7,9,10 116116构造LR(0)项目集规范族也可以用 项目

20、集一样：I0=S S, S AS, SGO(I o, a)=Aa= IiGO(10, b)= Sb= 12GO。，S)= S S , ADFAGO函数来计算得到。所得到的项目集规范族与上图中的b, A SA, A aS A, A SA, A a, S AS, S b= 13GO（I 0， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 3 ， a）=Aa=I1GO（I 3， b）=Sb=I2GO（I 3， S）=AS A，SAS，Sb， ASA，Aa = I 5GO（I 3， A）=ASA ，SA S，SAS， Sb，ASA，Aa = I 6GO（I 4， a）=Aa=I1G

21、O（I 4， b）=Sb=I2GO（I 4， S）=SAS ，AS A，SAS， Sb，ASA，Aa = I 7GO（I 4， A）=SA S，SAS，Sb， ASA，Aa = I4GO（I 5 ， a）=Aa=I1GO（I 5， b）=Sb=I2GO（I 5， S）=AS A，SAS，Sb， ASA，Aa = I 5GO（I 5， A）=ASA ，SA S，SAS， Sb，ASA，Aa = I 6GO（I 6， a）=Aa=I1GO（I 6， b）=Sb=I2GO（I 6， S）=SAS ，AS A，SAS， Sb，ASA，Aa = I 7GO（I 6， A）=SA S，SAS，Sb， AS

22、A，Aa = I4GO（I 7， a）=Aa=I1GO（I 7， b）=Sb=I2GO（I 7， S）=AS A，SAS，Sb， ASA，Aa = I 5GO（I 7， A）=ASA ，SA S，SAS， Sb，ASA，Aa = I 6项目集规范族为C= I 1 ， I2，I3， I4，I5，I6， I7不是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) 项目集

23、规范族见下图：对于态5,因为包含项目A AS a/b,所以遇到搜索符号a或b时，应该用A AS归约。又因为状态5 包含项目 A a a/b ，所以遇到搜索符号a 时，应该移进。因此存在“移进 - 归约”矛盾，所以这个文法不是 LR(1) 文法。5:SAa/b8:a/ba/ba/bASa/bSAa/bASa/ba/bASAS#/a/b#/a/bSAb a/ba a/b2：ASSAa/ba/ba/ba/bSAa/bA3 :AaA a/b4:S b #/a/b#/a/b#/a/b#/a/ba/ba/bSAa/ba/ba/b3：6：9：a/bASa/bSAa/ba/ba/bSAa/bASa/ba/ba

24、/bASa/ba/b7:SAS#/a/bAS Aa/bASAa/bAaa/bSASa/bSba/bb10：S b a/b5:/*第六章会有点难第六章P164 5E E1+T if = int) and = int ) then := int else := realET := := realTnum := int(2)P164-7SL1|L2:=+2 L2.length)SL:=LL1B:=2* + ;:=+1LB:=;:=1B0:=0B1:=1*/第七章abc+* abcde/+*+ abcd+*+A CDP217- 1a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)A (C

25、 D)(A B) ( C D)AB CD(A B) (C D E)AB CDEif (x+y)*z =0 then (a+b)T c else a或 xy+z*0= P1 jez ab+cT b T c xy+z*0= ab+c T abc T T ¥T P2 jump abc T TP1 P2P217- 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

26、(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1) +, a, b,T1(2) , T1 , -,T2(3) +, c, d,T3(4) *, T2, T3 , T4(5) +, a, b,T5(6) +, T5, c,T6(7) -,T4, T6 , T7P2184自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:

27、=A-(4)*(-C+D)i:=iA-B(5)*(-C+D)i:=EA-B(6)*(-C+D)i:=EA-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*(-iA-B-C(11)+D)i:=E*(-EA-B-C(,C,-, T )(12)+D)i:=E*(EA-B- T1A-B- T -1A-B- T -D1(13)D)i:=E*(E+(14)i:=E*(E+i(15)i:=E*(E+EA-B- T -D 1(+, T ,D, T )(16)(17)i:=E(E i:=E*(E)A-B- T2 A-B- T

28、-(18)i:=E+EA-B- T 22(*,B, T , T )(19)产生的四元式：(,C,-, T )(+, T1,D, T2) (*,B, T , T )(:=, T3,-,A)P218 5i:=EA- T3(20) A(:=, T ,-,A)/*设 A : 10*20, B、G D: 20,宽度为 w= 4 则T1:= i * 20T1:=T1+jT2:=A - 84T3:=4*T1Tn:=T2T3 / 这一步是多余的T4:= i + jT5:=B - 4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A - 84T10:=4*T8T11:=T9T10T

29、12:= i + jT13:=D - 4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C 4T18:=4*T16T19:=T17T18T20:=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真链：10

30、7,100P218-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,

31、-, - 100)P219- 12/*(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻译模式方法1：for E1 := E2 to E3 do SS F do MS1F For I : E1 to E2I idMS F do MS1 backpatch,nextquad);backpatch,;emit k''+' 1);emit( 'j ,'','',':=; F For I : E1 to E2:= makelist(nextquad);em

32、it( 'j>, '', '',0');emit 'k':=makelist(nextquad);emit( 'j,-,-,-');:=;:=;I idp:=lookup;if p <> nil then :=p else error M := nextquad*/ 方法2:Sf for id:=E1 to E2 do S1Sf F S1Ff for id:=E1 to E2 doF forid : E1toE2doINITIAL=NEWTEMP;emit( ':=,'',

33、 - / INITIAL);FINAL=NEWTEMP;emit( ':=,'', - / FINAL);p:= nextquad+2;emit( 'j ,' INITIAL ',' FINAL ' ,' p); kmakelist(nextquad);emit( ' j,一,一,'); :=lookup;if nil thenemit 'k'INITIAL) :=nextquad;kFINAL;S FS1backpatch, nextquad)p:=nextquad+2;emit( 'j , '', '' , ' p );:=merge, makelist(nextquad);emit( j,一,一,');emit( ' succ ,'',-,'emit( ' j,一,一,'第九章P270-9传名但必须将其中出现的即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处, 任一形式参数都代之以相应