上傳人：n***

認證信息

認證類型：個人認證

認證主體：余**（實名認證）

IP屬地：貴州

IP屬地：貴州 上傳時間：2020-10-05 格式：DOC 頁數(shù)：9 大?。?.11MB 積分：20 舉報 版權(quán)申訴

1、第四章4.1文法G1為：NND | D D0 | 1（1）L(G1)如何表示？（2）給出句子的最左推導(dǎo)和最右推導(dǎo)。解答：(1) L(G1)為無符號二進制數(shù)。 (2)最左推導(dǎo)：NNDNDD NDDD NDDDD NDDDD NDDDDD DDDDDD 0DDDDD 01DDDD 011DDD 0111DD 01110D 011100最右推導(dǎo)：NNDN0 ND0 N00 ND00 N100 ND100 N1100 ND1100 N11100 D11100 0111004.2 寫一文法G2，使其L(G2)是正奇數(shù)集合，且每個數(shù)不以0打頭。 解答：令G2= VN,VT,P, ， 其中，VT =0,1,

2、2,3,4,5,6,7,8,9， VN =, , , , , ， P： 數(shù)字1123456789 13579 024684.3 設(shè)文法G3為：EE+T | TTT*F | FF(E) | i試證明符號串T*F+ i是G3的句型，并給出此句型的所有短語以及句柄。解答：由于有推導(dǎo)EE+TT+TT*F+T T*F+FT*F+i 所以T*F+i是的G3的句型。此句型T*F+i的語法樹如圖4-5：圖4-5 句型T*F+i的語法樹根據(jù)語法樹此句型的短語有：T*F, i, T*F+i.句柄為T*F。4.4 證明文法G4：SiSeS | iS | a是二義性文法。解答：要證明文法是二義性文法，只要找到它的任意

3、一個句型有兩個語法樹即可。 因為句型iiaes有兩個語法樹（圖4-6）,所以G4是二義性文法。圖4-6 句型iiaes的語法樹4.5 設(shè)文法G5為：EE+T | TTT*F | FFPF | PP(E) | i（1）試給出G5的FIRSTVT和LASTVT。（2）構(gòu)造G5的算符優(yōu)先關(guān)系表，G5是算符優(yōu)先文法嗎？（3）給出G5的優(yōu)先函數(shù)表。LASTVT(E)=+, *, , i, ) LASTVT(T)= *, , i, ) LASTVT(F)= *, i, ) LASTVT(P)= i, ) 解答：由題意可得：(1) FIRSTVT(E)=+, *, , i, ( FIRSTVT(T)= *,

4、 , i, ( FIRSTVT(F)= , i, ( FIRSTVT(P)= i, ( (2) G5的算符優(yōu)先關(guān)系表如表44所示表44 G5的算符優(yōu)先關(guān)系表H1 H2+*i()#+*i()#4.6 設(shè)所給文法為G5（習題4-5），（1）消除G5的左遞歸；（2）設(shè)消除左遞歸的文法為G6，給出G6所有非終極符的FIRST集和FOLLOW集；（3）說明G6是否為LL(1)文法；（4）構(gòu)造G6的LL(1)分析表；解答：（1）消除G5的左遞歸得G6ETEE+TE |TFTT*F T |FPF | PP(E) | i(2) First(E)= First(T)= First(F) = First(P)=

5、(, 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

6、）Sb（4）AASc （5）ASb（6）Acd （7）Aa構(gòu)造G7的LR（0）項目集規(guī)范族如圖47圖47 G7的LR（0）項目集規(guī)范族G7的LR(0)分析表如表4-7表4-7 LR(0)分析表ACTIONGOTO狀態(tài)abcd#SA0S6S4S3121S5Acc2S6S4S3973S6S4S3S1312114r3r3r3r3r35r5r5r5r5r56r7r7r7r7r77S6S4S3S8978r1r1r1r1r19S5S1010r4r4r4r4r411S6S4S3S149712S5S1013r6r6r6r6r614r2r2r2r2r2由于G7的LR(0)分析表無多重入口，所以G7為LR(0)文

7、法，同理可知G7為SLR(1)文法。4.8 對如下文法G8：SAABAABaBBb構(gòu)造LR(1)項目集規(guī)范族和LR(1)分析表，并說明文法是否為LR(1)文法。解答：文法G8的拓廣文法為（0）SS（1）SA （2）ABA （3）A（4）BaB（5）Bb構(gòu)造G8的LR（1）項目集規(guī)范族如圖48圖48 G8的LR（1）項目集規(guī)范族構(gòu)造G8的LR（1）分析表如表45由于G8的LR(1)分析表無多重入口，所以G8為LR(1)文法。表48 G8的LR（1）分析表ACTIONGOTO狀態(tài)ab#SAB0S4S5r31231Acc2S4S5r33S4S5r3634S4S575r5r5r56r27r4r4r48

8、r84.9 對如下文法G9：（0）SS（1）SBB（2）S（3）BaB（4）Bb（1）構(gòu)造LR(1)項目集規(guī)范族，并說明是否為LR(1)文法；（2）對LR(1)項目集能否合并同心集？解答：構(gòu)造G9的LR（1）項目集規(guī)范族如圖49圖49 G9的LR（1）項目集規(guī)范族構(gòu)造G9的LR（1）分析表如表49表49 G9的LR（1）分析表ACTIONGOTO狀態(tài)ab#SB0S3S4r2121Acc2S6S753S3S484r3r35r16S6S77r4r4r38r2r29r2由于G9的LR(1)分析表無多重入口，所以G9為LR(1)文法。（2）由于I3與I6 ，I4與 I7， I8與 I9合并同心集后項目

9、集規(guī)范族無語法動作沖突，所以能否合并同心集。第五章5.3 分別寫出下面表達式相應(yīng)的逆波蘭表示、三元式和四元式：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）（

10、-, 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

11、+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, -, -, (

12、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

13、, -, 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 展開下面的循環(huán)語句后，用逆波蘭表示、三

14、元式和四元式表示之：for i1 to 100 do a2*i解答：先將循環(huán)語句變成與之等價的條件語句：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

15、,（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 +