编译原理韩太鲁第四章第五章答案.doc

韩太鲁修订版编译原理第四章第五章第四章4.1文法G1为：NND | D D0 | 1（1）L(G1)如何表示？（2）给出句子011100的最左推导和最右推导。解答：(1) L(G1)为无符号二进制数。 (2)最左推导：NNDNDD NDDD NDDDD NDDDD NDDDDD DDDDDD 0DDDDD 01DDDD 011DDD 0111DD 01110D 011100最右推导：NNDN0 ND0 N00 ND00 N100 ND100 N1100 ND1100 N11100 D11100 0111004.2 写一文法G2，使其L(G2)是正奇数集合，且每个数不以0打头。 解答：令G2= VN,VT,P, ， 其中，VT =0,1,2,3,4,5,6,7,8,9， VN =, , , , , ， P： 数字1123456789 13579 024684.3 设文法G3为：EE+T | TTT*F | FF(E) | i试证明符号串T*F+ i是G3的句型，并给出此句型的所有短语以及句柄。解答：由于有推导EE+TT+TT*F+T T*F+FT*F+i 所以T*F+i是的G3的句型。此句型T*F+i的语法树如图4-5：图4-5 句型T*F+i的语法树根据语法树此句型的短语有：T*F, i, T*F+i.句柄为T*F。4.4 证明文法G4：SiSeS | iS | a是二义性文法。解答：要证明文法是二义性文法，只要找到它的任意一个句型有两个语法树即可。 因为句型iiaes有两个语法树（图4-6）,所以G4是二义性文法。图4-6 句型iiaes的语法树4.5 设文法G5为：EE+T | TTT*F | FFPF | PP(E) | i（1）试给出G5的FIRSTVT和LASTVT。（2）构造G5的算符优先关系表，G5是算符优先文法吗？（3）给出G5的优先函数表。LASTVT(E)=+, *, , i, ) LASTVT(T)= *, , i, ) LASTVT(F)= *, i, ) LASTVT(P)= i, ) 解答：由题意可得：(1) FIRSTVT(E)=+, *, , i, ( FIRSTVT(T)= *, , i, ( FIRSTVT(F)= , i, ( FIRSTVT(P)= i, ( (2) G5的算符优先关系表如表44所示表44 G5的算符优先关系表H1 H2+*i()#+*i()#4.6 设所给文法为G5（习题4-5），（1）消除G5的左递归；（2）设消除左递归的文法为G6，给出G6所有非终极符的FIRST集和FOLLOW集；（3）说明G6是否为LL(1)文法；（4）构造G6的LL(1)分析表；解答：（1）消除G5的左递归得G6ETEE+TE |TFTT*F T |FPF | PP(E) | i(2) First(E)= First(T)= First(F) = First(P)= (, i First(E)=+, First(T)=*, Follow(E)= ), #Follow(E)= ), #Follow(T)=+, ), #Follow(T)=+, ), #Follow(F)=+,*, ), #Follow(P)=+,* , , ), #（3）因为FPF | P 含有左公因子，所以G6不是ll(1)文法。（4）G6的LL(1)分析表如表4-6。表4-6 G6的LL(1)分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFPF FPFPF FPPPiP(E)4.7 解答:G7的拓广文法如下：（0）SS (1) SAAd （2）ScAd（3）Sb（4）AASc （5）ASb（6）Acd （7）Aa构造G7的LR（0）项目集规范族如图47图47 G7的LR（0）项目集规范族G7的LR(0)分析表如表4-7表4-7 LR(0)分析表ACTIONGOTO状态abcd#SA0S6S4S3121S5Acc2S6S4S3973S6S4S3S1312114r3r3r3r3r35r5r5r5r5r56r7r7r7r7r77S6S4S3S8978r1r1r1r1r19S5S1010r4r4r4r4r411S6S4S3S149712S5S1013r6r6r6r6r614r2r2r2r2r2由于G7的LR(0)分析表无多重入口，所以G7为LR(0)文法，同理可知G7为SLR(1)文法。4.8 对如下文法G8：SAABAABaBBb构造LR(1)项目集规范族和LR(1)分析表，并说明文法是否为LR(1)文法。解答：文法G8的拓广文法为（0）SS（1）SA （2）ABA （3）A（4）BaB（5）Bb构造G8的LR（1）项目集规范族如图48图48 G8的LR（1）项目集规范族构造G8的LR（1）分析表如表45由于G8的LR(1)分析表无多重入口，所以G8为LR(1)文法。表48 G8的LR（1）分析表ACTIONGOTO状态ab#SAB0S4S5r31231Acc2S4S5r33S4S5r3634S4S575r5r5r56r27r4r4r48r84.9 对如下文法G9：（0）SS（1）SBB（2）S（3）BaB（4）Bb（1）构造LR(1)项目集规范族，并说明是否为LR(1)文法；（2）对LR(1)项目集能否合并同心集？解答：构造G9的LR（1）项目集规范族如图49图49 G9的LR（1）项目集规范族构造G9的LR（1）分析表如表49表49 G9的LR（1）分析表ACTIONGOTO状态ab#SB0S3S4r2121Acc2S6S753S3S484r3r35r16S6S77r4r4r38r2r29r2由于G9的LR(1)分析表无多重入口，所以G9为LR(1)文法。（2）由于I3与I6 ，I4与 I7， I8与 I9合并同心集后项目集规范族无语法动作冲突，所以能否合并同心集。第五章5.3 分别写出下面表达式相应的逆波兰表示、三元式和四元式：a*b+(c-d)/ea*b-c*d/e-(a+b/c*d)abbc3. -(a+b/c*d)的逆波兰式：abc/d*+-三元式序列：（1）（/, b, c）（2）（*, (1), d）（3）（+, a, (2)）（4）（- , (3),-）四元式序列：（1）（/, b, c, T1）（2）（*, T1, d, T2）（3）（+, a, T2, T3）（4）（- , T3, -, T4）1. a*b+(c-d)/e逆波兰式：ab*cd-e/+三元式序列：（1）（*, a, b）（2）（-, c, d）（3）（/, (2), e）（4）（+ ,(1), (3)）四元式序列：（1）（*, a, b, T1）（2）（-, c, d, T2）（3）（/, T2, e, T3）（4）（+ ,T1, T3, T4）解答：2. a*b-c*d/e逆波兰式：ab*cd*e/-三元式序列：（1）（*, a, b）（2）（*, c, d）（3）（/, (2), e）（4）（- , (1), (3)）四元式序列：（1）（*, a, b, T1）（2）（*, c, d, T2）（3）（/, T2, e, T3）（4）（- ,T1, T3, T4）5.4 分别写出条件语句：if a0 then xx+1 else x4* (x-1)的逆波兰表示、三元式和四元式。逆波兰式：(1)a 0 13 jez(6) x x 1 + =(11) 20 j(13) x 4 x 1- * =(20) 解答：三元式序列：（1）（, a, 0）（2）（jz, (1), (6）（3）（+, x, 1）（4） (=, x, (3)（5） (j, -, (9)（6） (-, x, 1)（7） (*, 4, (6)（8） (=, x, (7)（9）四元式序列：（1）(j, a, 0, (3)）（2）(j, -, -, (6）（3）(+, x, 1, T1）（4）(=, T1, - , x)（5）(j, -, -, (9)（6）(-, x, 1, T2)（7）(*, 4, T2, T3)（8）(=, T3, - , x)（9）5.5 把下面的程序段： a0; b0; 100: aa+1; if a=100 then bb+a else a0; goto 100写成逆波兰表示、三元式和四元式。四元式序列：（1）(=, 0, -, a)（2）(=, 0, -, b)（3）(+, a, 1, T1)（4）(=, T1, -, a)（5）(-, a, 100, T2)(6) (jnz, T2, (10)（7）(+, b, a, T3)（8）(=, T3, -, b)（9）(j, -, -, (11)（10）(=,0, -, a)（11）(j, -, -, (3)(12)三元式序列：（1）(=, a, 0)（2）(=, b, 0)（3）(+, a, 1)（4）(=, a, (3)（5）(=, a, 100)（6）(jf, (5), (9)（7）(+, b, a)（8）(=, b, (7)（8）(j, -, (10)（9）(=, a, 0)（10）(j, -, (3)(11)逆波兰式：(1)a 0 = (4)b 0 = (7)a a 1 + =(12)a 100 = 24 jez (17)b b a + =(22)27 j(24)a 0 =(27)7 j(29)5.6 展开下面的循环语句后，用逆波兰表示、三元式和四元式表示之：for i1 to 100 do a2*i解答：先将循环语句变成与之等价的条件语句：i 1;10: if i = 100 thenbegin a 2*i;i i + 1;goto 10四元式序列：（1）( , 1 , , i )（2）(j, i , 100, (4)（3）( j, -, -, （9）)（4）( * , 2 , i, T1 )（5）( , T1 , -, s)（6）( + , i , 1, T2)（7）( , T2, -, i)（8）( j , - , -, (2) )（9）三元式序列：（1）( , i , 1 )（2）( , i , 100 )（3）( jf,（2）, （9）)（4）( * , 2 , i )（5）( , a , （4）)（6）( + , i , 1 )（7）( , i , （6）)（8）( j , , （2） )（9）逆波兰式：（1） i 1（4） i 100 3 do begin aa+4*b; ba+b-b*c end;的逆波兰表示、三元式和四元式。解答：三元式序列：（1）( + , x , y )（2）( , (1) , 3 )（3）( jf,（2）, (12)（4）( * , 4 , b )（5）( + , a , (4）)（6）( = , a , (5) )（7）( * , b , c )（8）( + , a , b )（9）( - , (8) , (7) )（10）( , b , (9)（11）( j , , （1）)（12）逆波兰式：（1） block（2） x y +