编译原理课后答案-第二版(共20页).doc

《编译原理课后答案-第二版(共20页).doc》由会员分享，可在线阅读，更多相关《编译原理课后答案-第二版(共20页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第三章 1、 L(GS)= abc 2、 L(GN)= n位整数或空字符串 | n0 3、 GE：EE+D | E-D | DD0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、 L(GZ)= anbn | n0 5、 (1) 考虑不包括“0”的情况GS：S0S | ABC | 2 | 4| 6 | 8A1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 BAB | 0B | C0 | 2 | 4 | 6 | 8 考虑包括“0”的情况： GS：SAB | C BAB | CA0 | 1 | 2 | 3 | 4 | 5 | 6

2、 | 7 | 8 | 9 C0 | 2 | 4 | 6 | 8(2)方法1：GS：S ABC | 2 | 4 | 6 | 8A1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 BAB | 0B | C0 | 2 | 4 | 6 | 8方法2：GS：SAB | C B AB | 0B | C | 0 A 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C2 | 4 | 6 | 86、 设为E，为T，为F，注：推导过程不能省略，以下均为最左推导(1) E = T = F = i(4) E = E+T = T+T = T*F+T = F*F+T = i*F+T

3、= i*i+T = i*i+F = i*i+i(6) E = E+T = T+T = F+T = i+T = i+T*F = i+F*F = i+i*F = i+i*I*+ i i i+ i* i i7、 8、 是有二义性的，因为句子abc有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S = Ac = abc 最左推导2：S = aB = abc9、 (1)SSS*+SSaaa(2) 该文法描述了变量a和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导1：S = S(S

4、)S = (S)S = ()S = ()S(S)S = ()(S)S = ()()S = ()()最左推导2：S = S(S)S = S(S)S(S)S = (S)S(S)S = ()S(S)S = ()(S)S = ()()S = ()()11、(1) 因为从文法的开始符E出发可推导出E+T*F，推导过程如下：E = E+T = E+T*F ，所以E+T*F是句型。 从子树和短语之间的关系可知：E+T*F是句型E+T*F相对于E的短语；T*F是句型E+T*F相对于T的短语，也是简单短语和句柄。13、(1) 最左推导：S = ABS = aBS = aSBBS = aBBS = abBS =

5、abbS = abbAa = abbaa(2) SABS | Aa | Aa BSBB | b(3) 首先为了区别句子abbaa中的a和b，把它写成a1b1b2a2a3 该句子的短语有：a1b1b2a2a3，b1b2，a2a3，a1，a2，b1，b2， 直接短语有：a1，a2，b1，b2， 句柄：a114、(1) GS：SABAaAb |BaBb |(2) GS：S1S0 | A A0A1 |(3) GS：S0S0 | aSa | a16、(1) GA：AaA |(2)GA：A aA | aB B bB | b (3)GA：AaA | B B bB | C CcC |17、习题6、习题7和习题

6、7中的文法所描述的语言都是由变量i、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。第四章参考答案第1题：(1) 0,1 1 1 0 1CBAS Z确定化：I0I1SAAAABABACABACAABZ+ABZACAB S ABC Z重新命名，令AB为B、AC为C、ABZ为Z其中S为初态，Z为终态01SAAABBCBCAD+ZCBa,b(3)abZAS aaBb确定化：IaIbSAAABAZABABABZ+AZABAZ+ABZABABZ 0 1 2 3 4重新命名，以0、1、2、3、4代替S,A, AB,AZ,ABZ得DFA其中0为初态，3，4为终态IaIb01123224+323+

7、424第2题：I0I1XZX+ZXZY+XZXZXYYXYXYXYZX+XYZXYZXY A B C DEF重新命名，以A、代替X,Z ,XZ , Y , XY ,XYZ得DFA其中A为初态，为终态01ABA+BCD+CCEDEEFA+FFE第3题：确定化：.I0I1SVQQUVQVZQUQUVQUZ+VZZZVZ.+QUZVZQUZ+ZZZ A BCDEFG重新命名，以A、代替S,VQ ,QU , VZ , V ,QUZ,Z得DFA其中A为初态，D，F，G为终态.01ABCBDCCEF+DGGEG.+FDF+GGG第4题：(1)确定化：IaIb+0011+0101110 A B C重新命名，

8、以、代替0、01、1得其中A为初态，A，B为终态ab+ABC+BBCCA最小化：初始分划得终态组A,B，非终态组C0：A,B，C 对终态组进行审查，判断A和B是等价的，故这是最后的划分重新命名，以A、C代替A,B、C得DFAab+AACCA(2)这是DFA，直接最小化初始分划得：终态组0，非终态组1,2,3,4,50：0，1,2,3,4,5 对1,2,3,4,5进行审查： 4 输入a后到达0，1,2,3,5输入a后到达1,3,5，故得到新分划 0,1,3,5，41：0，4，1,2,3,5 对1,2,3,5进行审查：1,5 输入b后到达4，2,3 输入b后到达2,3，故得到新分划 1, 5，2,

9、32：0，4，1, 5，2,3对1, 5，2,3进行审查：1, 5 输入a后到达1, 5 2 输入a后到达1，3 输入a后到达3，故得到新分划2，33：0，2，3，4，1, 5 这是最后分划了重新命名，以0，2，3，4，1代替0，2，3，4，1, 5得DFA略 bbbbbabaaSAaQbZaBD第7题首先判断E，F为多余状态根据正则文法转化为NFA的方法构造NFA 确定化：IaIb-abSAQ012AABZ113QQDZ224+BZQD+325+DZAB+416DAB516BQD6250123456最小化：初始分划得：终态组3,4，非终态组0,1,2,5,60：3,4,0,1,2,5,6对0

10、,1,2,5,6进行审查：1,2输入b到达3,4，而0,5,6输入b到达2,5,6，故得到新分划1,2,0,5,61：3,4,1,2,0,5,6 对0,5,6进行审查：0经过b到达，5,6经过b到达5,6，故得到新分划05,63：0，1,2，3,4，5,6 这是最后划分了。重新命名，以0，1，3，5代替0，1,2，3,4，5,6得DFA略第9题这是DFA，直接最小化初始分划得：终态组6,7，非终态组1,2,3,4,50：6,7,1,2,3,4,5对1,2,3,4,5进行审查：1,2输入b到达2，而3,4输入b到达6,7，5输入b不会有任何动作，故得到新分划1,2,3,4,51：6,7,3,4,

11、5,1,21 35b6cab这是最后划分了。重新命名，以1，3，5，6代替1,2,3,4,5,6,7得DFAba d所识别的语言是b*a (c| da)*bb*第11题根据正则文法（左线性文法）转化为NFA的方法构造NFA：bZ ASaaa确定化：IaIb-ab+ZSAA+011AAS12+ASASA+221012重新命名，以0、1、2代替ZS、A、AS得DFA其中0为初态，0，2为终态b12aa,ba0所识别的语言是：| (a|b) a (ba|a)*第13题（1） 假设d A,B,Y,Z n 0,1,2,8,9，文法可以等价得化为： | d | n | dn | n（2） 根据正则文法（左

12、线性文法）转化为NFA的方法构造NFA：重新命名状态，令A、B、C分别代表、BAd,nSCdnn第五章 习题参考答案1、(1) 对(a,(a,a)的最左推导为：S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S)(a,(a,S)(a,(a,a) 对(a,a),(a),a) 的最左推导为：S(T) (T,S)(S,S) (T),S)(T,S),S) (T,S,S),S)(S,S,S),S) (T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),

13、(T),S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a)对( a, a ), , ( a ), a )的最左推导为：S ( T ) ( T, S ) ( S, S ) ( T ), S ) ( T, S ), S ) ( T, S, S ), S ) ( S, S, S ), S ) ( T ), S, S ), S ) ( T, S ), S, S ), S ) ( S, S ), S, S ), S ) ( a, S ), S, S ), S ) ( a, a ), S, S ), S ) ( a, a ), , S ), S ) ( a, a ), ,

14、( T ), S ) ( a, a ), , ( S ), S ) ( a, a ), , ( a ), S ) ( a, a ), , ( a ), a )对( a, a ), , ( a ), a )的最左推导为：S ( T ) ( T, S ) ( T, a ) ( S, a ) ( T ), a ) ( T, S ), a ) ( T, ( T ), a ) ( T, ( S ), a ) ( T, ( a ), a ) ( T, S, ( a ), a ) ( T, , ( a ), a ) ( S, , ( a ), a ) ( T ), , ( a ), a ) ( T, S )

15、, , ( a ), a ) ( T, a ), , ( a ), a ) ( S, a ), , ( a ), a ) ( a, a ), , ( a ), a ) (2) 改写文法为： 0) Sa 1) S 2) S( T ) 3) TS N4) N, S N5) N 入口入口入口S: T:N: ，YNNSNYaRead(w)YNNS出口N出口Y(出错Read(w)TN)Read(w)出口(3)非终结符FIRST集FOLLOW集Sa,(#,)Ta,().N,.).对左部为N的产生式可知：SELECT(Sa)SELECT(S) SELECT(S( T )=SELECT(N , S N)SEL

16、ECT(N ) =， )=所以文法是LL(1)的。 预测分析表a(),#Sa(T)TS NS NS NN, S N也可由预测分析表中无多重入口判定文法是LL(1)的。(4) 对输入串（a,a）#的分析过程为：栈（STACK）当前输入符（CUR_CHAR）剩余输入符（INOUT_STRING）所用产生式（OPERATION）#S #)T(#)T #)NS #)Na#)N#)NS,#)NS #)Na#)N#)#(aaa,aa)#a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可见输入串（a,a）#是文法的句子。6.(

17、2) 不是LL(1)文法以A的产生式代入S，以D的产生式代入B中，提取左公共因子并删除多余产生式得文法：SBCCaB|BdF|FFb|分析表为abd#SBCBCBCBCBFFdFFCaBFb结论：经改写之后的文法是（）文法。递归下降分析器如同题1，从略6.(4)消除左递归为：SiS(E)ESFF+SFF-SFF分析表为：+-i()ESFSFF+SF-SFSi(E)结论：经改写之后的文法是（）文法。递归下降分析器如同题1，从略7.(1)文法不存在左递归第一种改法：以A的产生式替入B 产生式中BbaBbbBbbBa消除左公共因子：BbCCaBbbCbBa改写之后的文法的分析表：ab#BabCCaB

18、bbb改写之后的文法是LL(1)文法第二种改法：以B的产生式替入A产生式中AbaAbbAbaaA消除左公共因子后为AAbaCCAbbCaSELECT(AbaC) SELECT(A) = b # ,b 所以，改写之后的文法不是LL(1)文法7.(3)第1种改写：用A的产生式右部代替S的产生式右部的A得： SSBa|bBab消除左递归后文法变为： 0) Sb N1) NB a N2) N3) Ba b 非终结符FIRST集FOLLOW集Sb.#Ba.aN,a#SELECT(NB a N)SELECT(N) = a # =所以文法是LL(1)的。预测分析表ab#Sb NBa bNB a N第2种改写

19、：用S的产生式右部代替A的产生式右部的S得： SAa|bAAaB|bBBab 消除左递归后文法变为： 0) SA a 1) Sb 2) Ab B N3) Na B N4) N 5) Ba b非终结符FIRST集FOLLOW集Sb.#Ab.aBa.aNa,aSELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的。7.(5)以A、B的产生式代入S的产生式中的A、B，得新文法：SaCCAb|b|aAaA|a以A的产生式代入C中提取左公共因子得：SaCCaD|bDAb|b|AaA|a以A的产生式代入

20、D中提取左公共因子得：SaCCaD|bDaE|EAb|bAaA|a以A的产生式代入E中提取左公共因子得：SaCCaD|bDaE|EaFFAb|bAaA|a可以看出，继续用A的产生式替换，只能使文法的产生式越来越多。改写之后的文法不是LL(1)文法第1题(1) FIRSTVT - LASTVT表 非终结符FIRSTVT集LASTVT集S a ( . a ) .T a ( , a , (2) 算符优先关系表 a ( ) , a ( , 优先关系唯一，所以是一个算符优先文法。 (3) 算符优先函数表： a , ( ) f 4 4 4 2 4 g 5 5 3 5 2(4)对输入串（a,a）#的算符优先

21、分析过程为栈（STACK）当前输入字符（CHAR）剩余输入串（INPUT_STRING）动作（ACTION）#(#(a#(S#(S,#(S,a#(S,S#(T#(S)#S(a,a)#a,a)#.,a)#.a)#.a)#.)#.#.#.#.移进移进归约: Sa移进移进归约: Sa归约: TT,S移进归约: S(T)对输入串（a,(a,a)）# 的算符优先分析过程为：栈 f(SYN(top) 关系 剩余序列 动作 产生式 # 0 a,(a,a)# 移进，读 # ( 2 (a,a)# 归约，不读 Sa # ( 2 (a,a)# 移进，读 # ( , 4 a,a)# 移进，读 # (, ( 2 a)#

22、 规约，不读 Sa # ( , ( 2 a)# 移进，读# ( , ( , 4 )# 归约，不读 Sa#( , (, 4 )# 归约，不读 TT,S# ( , ( 2 )# 移进，读#( ,() 4 # 规约，不读 S(T)#( , 4 # 规约，不读 TT,S# ( 2 # 移进，读# () 4 规约，不读 S(T)# S OK第2题文法：Sa|(T) TT,S|S (a,a)的最右推导过程为：S(T) (T,S) (T,a)(S,a) (a,a)(a,(a,a)的最右推导过程为: S(T) (T,S)(T,(T) (T,(T,S)(T,(T,a) (T,(S,a) (T,(a,a)(S,(

23、a,a) (a,(a,a) 对输入串(a,a)# 的规范归约过程为： 栈（stack）剩余输入串（input left）动作（action）#( #( a#( S#( T#( T,#( T,a#( T,S#( T#(T)#S(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.#.#.移进移进归约 by :S a归约 by :TS移进移进归约 by :S a归约 by :T T,S移进归约 by :S (T)对输入串（a,(a,a)）# 的规范归约过程为：栈剩余输入串动作#( #( a#( S#( T#( T,#( T,(#( T,(a#( T,(S#( T,(T#

24、( T,(T,#( T,(T,a#( T,(T,S#( T,(T#( T,(T)#( T,(S#( T#( T)#S(a,(a,a)#.a,(a,a)#.,(a,a)#.,(a,a)#.,(a,a)#.(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.)#.)#.)#.#.#.移进移进归约 by :S a归约 by :TS移进移进移进归约 by :S a归约 by :T S移进移进归约 by :S a归约 by :T TS移进归约 by :S (T)归约 by :T T,S移进归约 by :S (T)规范归约是最左归约过程，首先确定符号（包括终结符及非终结符）之

25、间优先关系，建立优先关系表，在归约过程中根据各符号之间的优先关系决定是移进还是归约，当出现句柄时进行归约; 算符优先归约方法不是规范的归约过程，首先确定终结符之间优先关系，在归约过程中根据最左素短语进行归约。1、(1) a*(-b+c) ：ab-c+* (3) abcde/+*+ (4) ABCD(7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）2、四元式(1) (+, a, b, t1)(2) (+, c, d, t2)(3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5)(6) (-,

26、 t4, t5, t6)间接三元式序列 间接码表(1) (+ a, b)(1)(2) (+ c, d)(2) (3) (* (1), (2) (3) (4) (- (3), /) (4)(5) (- (4), (1) (1) (5)三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2) (4) (- (3), /) (5) (+ a, b) (6) (- (4), (5) 4、(0) SE if error1 then print E.VAL (1) EE1+E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=

27、E1.VAL + E2.VAL;E.YTPE:=int;end else if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL + E2.VAL;E.YTPE:=real; end else error=1 (2) EE1*E2 if E1.TYPE=int AND E2.TYPE=int then beginE.VAL:=E1.VAL * E2.VAL; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL * E2.VAL; E

28、.YTPE:=real;end else error=1 (3) E(E1) E.VAL:=E1.VAL; E.TYPE:=E1.TYPE (4) En E.VAL:=n.LEXVAL;E.TYPE:=n.LEXTYPE 5、产生式语义规则SL1.L2SLS.val:=L.valLL1BL.val:=L1.val*2+B.val L.length:=L1.length+1LBL.val:=B.val L.length:=1B0B.val:=0B1B.val:=16、1)产生式语义规则EE1+TIF (E1.type=integer) and (T.type=integer) THEN E.ty

29、pe:=integerELSE E.type:=realETE.type:=T.typeTn.nT.type:=realTnT.type:=integer产生式(消除左递归之后)语义规则ETRR.i:=T.type E.Type:=R.sR+TR1IF (R.i=integer) and (T.type=integer) THEN R1.i:=integer ELSER1.i :=realR.s:=R1.sRR.s:=R.iTn.nT.type:=realTnT.type:=integer2)产生式语义规则EE1+TIF (E1.type=integer) and (T.type=intege

30、r) THEN BEGIN E.type:=integer Print(E1.val,T.val, +) ENDELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=realE1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(E1.val,T.val, +)ENDETE.type:=T.type E.val:=T.valTn.nT.type:=real T.val

31、:=n.n.lexvalTnT.type:=integer T.val:=n.lexval产生式(消除左递归之后)语义规则ETRR.i:=T.type R.j:=T.val E.Type:=R.s E.val:=R.tR+TR1IF (R.i=integer) and (T.type=integer) THEN BEGINR1.i:=integerPrint(R.j,T.val, +)R1.j:=R.j+T.val END ELSE BEGINR1.i :=real IF R.i=integer THEN Begin R.i:=realR.j:=inttoreal(R.j) End IF T.type=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(R.j,T.val, +)