编译原理课后答案 第二版.pdf

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

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|9BAB|0B|C0|2|4|6|8考虑包括“0”的情况：GS：SAB|CBAB|CA0|1|2|3|4|5|6|7|8|9C0|2|4|6|8(2)方法 1：GS：S ABC|2|4|6|8A1|2|3|4|5|6|7|8|9BAB|0B|C0|2|4|6|8方法 2：GS：SAB|CB AB|0B|C|0A 1|2|

2、3|4|5|6|7|8|9C2|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=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*I7、*+i+i*iiii8、是有二义性的，因为句子 abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导 1：S=Ac=abc最左推导 2：S=aB=abc9、(1)SSS*SS+aaa(2)该文法描述了变量 a 和运算符+、*组成的逆波兰表达式10、(1)该文法描述了各

3、种成对圆括号的语法结构(2)是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导 1：S=S(S)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)最左推导

4、：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa(2)SABS|Aa|AaBSBB|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|AA0A1|(3)GS：S0S0|aSa|a16、(1)GA：AaA|(2)GA：A aA|aBB bB|b(3)GA：AaA|BB bB|C CcC|17、习题 6、习题 7 和习题 7 中的文法

5、所描述的语言都是由变量 i、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。第四章参考答案第 1 题：(1)0,11101SABC确定化：I0I1SSAAAAABBABACABCACAABZZ+ABZACAB重新命名，令AB为 B、AC为 C、ABZ为 Z其中 S 为初态，Z 为终态01SAAABBCBCAD+ZCBZ(3)a,babZSAaaBb确定化：IaIb0SA1AABAZ2ABABABZ3+AZABAZ4+ABZABABZ重新命名，以 0、1、2、3、4 代替S,A,AB,AZ,ABZ得 DFA其中 0 为初态，3，4 为终态IaIb01123224+323+424第 2

6、 题：I0I1AXZXB+ZXZYC+XZXZXYDYXYEXYXYZXF+XYZXYZXY重新命名，以 A、代替X,Z,XZ,Y,XY,XYZ 得 DFA其中 A 为初态，为终态A0B1A+B+CDE+FCCEFFDEAE第 3 题：确定化：.I0I1ASVQQUBVQVZQUCQUVQUZD+VZZZEVZ.F+QUZVZQUZG+ZZZ重新命名，以 A、代替S,VQ,QU,VZ,V,QUZ,Z得 DFA其中 A 为初态，D，F，G 为终态.01ABCBDCCEF+DGGEG.+FDF+GGG第 4 题：(1)确定化：IaIbA+0011B+01011C10重新命名，以、代替0、01、1得

7、其中 A 为初态，A，B 为终态+A+BCaBBAbCC最小化：初始分划得终态组A,B，非终态组C0：A,B，C对终态组进行审查，判断A 和 B 是等价的，故这是最后的划分重新命名，以 A、C 代替A,B、C得 DFA+ACaAAbC(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，

8、2,32：0，4，1,5，2,3对1,5，2,3进行审查：1,5 输入 a 后到达1,52 输入 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略第 7 题a首先判断 E，F 为多余状态a根据正则文法转化为 NFA的方法构造 NFAbaASBbabbQbbDbaZ确定化：IaIbab0SAQ0121AABZ1132-QQDZ2243+BZQD+3254+DZAB+4165DAB5166BQD625最小化：初始分划得：终态组3,4，非终态组0,1,2,5,60：3,4,0,1,

9、2,5,6对0,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，故得到新分划0 5,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 不会有任何动作

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

11、n|dn|n（2）根据正则文法（左线性文法）转化为NFA的方法构造 NFA：重新命名状态，令 A、B、C 分别代表、d,ndASBnCna122b11第五章 习题参考答案1、(1)对(a,(a,a)的最左推导为：S(a,(a,S)(S,S,S),S)(a,(a,a)(T)(T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(a,a),S),S)(T),S,S),S)(T,S),S,S),S)(a,a),(S),S)(S,S),S,S),S)(a,a),(a),S)(a,S),S,S),S)(a,a),S,S),S)(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)

12、(a,(S,S)对(a,a),(a),a)的最左推导为：S(a,a),(T),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),(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

13、,(T),a)(T,(S),a)(T,(a),a)(T,S,(a),a)(T,(a),a)(S,(a),a)(T),(a),a)(T,S),(a),a)(T,a),(a),a)(S,a),(a),a)(a,a),(a),a)(2)改写文法为：0)Sa1)S2)S(T)3)TS N4)N,S N5)NS:T:入口入口N:入口NaYSY，NNYN(YNRead(w)出口SRead(w)出错NT出口N)Read(w)出口(3)非终结符STN对左部为 N 的产生式可知：SELECT(Sa)SELECT(S)SELECT(S(T)=SELECT(N,S N)SELECT(N)=，)=所以文法是 LL(1

14、)的。预测分析表FIRST 集a,(a,(,.FOLLOW 集#,).).STNaaS N(T)S N),S N#S N也可由预测分析表中无多重入口判定文法是 LL(1)的。(4)对输入串（a,a）#的分析过程为：栈（STACK）当前输入符（CUR_CHAR）剩余输入符（INOUT_STRING）所用产生式（OPERATION）#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#6.(2)不是 LL(1)文法以 A 的产生式代入 S，以 D 的产生式代入 B 中，提取左公共因子并删除多余产生式得文法：SBCCaB|BdF|FFb|(aaa,aa)#a,a)#.a,a)

15、#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可见输入串（a,a）#是文法的句子。分析表为SBCFaBCFaBbBCFbdBCdF#BCF结论：经改写之后的文法是（）文法。递归下降分析器如同题 1，从略6.(4)消除左递归为：SiEFSS(E)+SFESF-SFF+SFiSFiF-SFF(SF(E)分析表为：结论：经改写之后的文法是（）文法。递归下降分析器如同题 1，从略7.(1)文法不存在左递归第一种改法：以 A 的产生式替入 B 产生式中BbaBbbBbCBCBbbBaBabbCb#消除左公共因子：CaBbbCbaaaBbb改

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

17、b N#第 2 种改写：用 S 的产生式右部代替 A 的产生式右部的 S 得：SAa|bAAaB|bBBab消除左递归后文法变为：0)SA a1)Sb2)Ab B N3)Na B N4)N5)Ba b非终结符SABNFIRST 集b.b.a.a,FOLLOW 集#aaaSELECT(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，得新文法：SaCSaCSaCSaCCAb|b|aAaA|aAaA|a以 A 的产生式代入 C 中提取左公共因子得：CaD|

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

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

20、)#归约，不读TT,S#(,(2)#移进，读#(,()4#规约，不读S(T)#(,4#规约，不读TT,S#(2#移进，读#()4规约，不读S(T)#SOK第第 2 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,(a,a)(S,(a,a)(a,(a,a)对输入串(a,a)#的规范归约过程为：栈（stack）#(#(a#(S#(T#(T,#(T,a#(T,S#(T#(T)剩余输入串（input left）动作（action）(a,a)#.移进a,

21、a)#.移进,a)#.归约 by:S a,a)#.归约 by:TS,a)#.移进a)#.移进)#.归约 by:S a)#.归约 by:T T,S)#.移进#.归约 by:S(T)(T,(T,a)(T,(S,a)#S#.对输入串（a,(a,a)）#的规范归约过程为：栈#(#(a#(S#(T#(T,#(T,(#(T,(a#(T,(S#(T,(T#(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)#.归约 by:S a,(a,a)#.归约 by:TS,(a,a)#.移进(a,a)#.

22、移进a,a)#.移进,a)#.归约 by:S a,a)#.归约 by:T S,a)#.移进a)#.移进)#.归约 by:S a)#.归约 by:T TS)#.移进)#.归约 by:S(T)#.归约 by:T T,S)#.移进#.归约 by:S(T)#.动作规范归约是最左归约过程，首先确定符号（包括终结符及非终结符）之间优先关系，建立优先关系表，在归约过程中根据各符号之间的优先关系决定是移进还是归约，当出现句柄时进行归约;算符优先归约方法不是规范的归约过程，首先确定终结符之间优先关系，在归约过程中根据最左素短语进行归约。1、(1)a*(-b+c)：ab-c+*(3)abcde/+*+(4)ABC

23、D(7)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示 if-then-else 运算）2、三元式(1)(+a,b)间接三元式序列 间接码表四元式(2)(+c,d)(1)(+a,b)(1)(1)(+,a,b,t1)(3)(*(1),(2)(2)(+c,d)(2)(2)(+,c,d,t2)(4)(-(3),/)(3)(*(1),(2)(3)(3)(*,t1,t2,t3)(5)(+a,b)(4)(-(3),/)(4)(4)(-,t3,/,t4)(6)(-(4),(5)(5)(-(4),(1)(1)(5)(+,a,b,t5)(5)(6)(-,t4,t5,t6)4、(0)SE if er

24、ror1 then print E.V AL(1)EE1+E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=E1.VAL+E2.VAL;E.YTPE:=int;endelse if E1.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL+E2.VAL;E.YTPE:=real;endelse error=1(2)EE1*E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=E1.VAL*E2.VAL;E.YTPE:=int;endelse if E1

25、.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL*E2.VAL;E.YTPE:=real;endelse 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.L2SLLL1BLBB0 0B1 16、1)语义规则S.val:L1.val L2.val/2L2.lengthS.val:=L.valL.val:=L1.val*2+B.valL.length:=L1.length+1L.val:=B.valL.leng

26、th:=1B.val:=0B.val:=1产生式EE1+T语义规则IF(E1.type=integer)and(T.type=integer)THENE.type:=integerELSEE.type:=realE.type:=T.typeT.type:=realT.type:=integer语义规则R.i:=T.typeE.Type:=R.sIF(R.i=integer)and(T.type=integer)THENR1.i:=integerELSER1.i:=realR.s:=R1.sR.s:=R.iT.type:=realT.type:=integerETTn.nn.nTn n产生式(消

27、除左递归之后)ETRR+TR1RTn.nn.nTn n2)产生式EE1+T语义规则IF(E1.type=integer)and(T.type=integer)THENBEGINE.type:=integerPrint(E1.val,T.val,+)ENDELSE BEGINE.type:=realIF E1.type=integer THENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIF T.type:=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(E1.val,T.v

28、al,+)ENDE.type:=T.typeE.val:=T.valETTn.nn.nTn n产生式(消除左递归之后)ETRR+TR1T.type:=realT.val:=n.nn.n.lexvalT.type:=integerT.val:=n n.lexval语义规则R.i:=T.typeR.j:=T.valE.Type:=R.sE.val:=R.tIF(R.i=integer)and(T.type=integer)THENBEGINR1.i:=integerPrint(R.j,T.val,+)R1.j:=R.j+T.valENDELSE BEGINR1.i:=realIF R.i=inte

29、ger THENBeginR.i:=realR.j:=inttoreal(R.j)EndIF T.type=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(R.j,T.val,+)R1.j:=R.j+T.valENDR.s:=R1.sR.t:=R1.tR.s:=R.iR.t:=R.jT.type:=realT.val:=n.nn.n.lexvalT.type:=integerT.val:=n n.lexvalRTn.nn.nTn n7、产生式Di iLL,i,iL1L:TTintegerintegerTrealreal翻

30、译模式D.Type:=L.Typeaddtype(i i.entry,D.type)L.Type:=L1.Typeaddtype(i i.entry,L.type)L.type:=T.typeT.type:=integerT.type:=real第第 4 4 题题（1）基本块流图（2）B5 中（14）和（16）是公共子表达式、（17）和（20）是公共子表达式，B5 变为（14）t6:=4*I（15）x:=at6（16）t7:=t6（17）t8:=4*J（20）t10:=t8B6 中（23）和（25）是公共子表达式、（26）和（29）是公共子表达式，B6 变为（23）t11:=4*I（24）x:

31、=at11（25）t12:=t11（26）t13:=4*n（29）t15:=t13（3）循环 B2 B3 B2，B3，B4，B5(4)归纳变量参考书上 P256 的循环优化第第 5 5 题题不能。因为 B3 不是循环出口 B4 的必经结点，而且在B5 处还引用了 i第第 6 6 题题DAG 图若只有 G、L、M 在出口之后活跃，则优化后的代码为：G:=B*CH:=G*GL:=H*GM:=L若只有 L 在出口之后活跃，则代码为G:=B*CH:=G*GL:=H*GDAG 图若只有 G、L、M 活跃，则代码为D:=A+CE:=A*CF:=D+EG:=3+FL:=F+15若只有 L 活跃，则代码为D:=A+CE:=A*CF:=D+EL:=F+15M:=L