上傳人：鉆***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：李**（實(shí)名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2023-04-08 格式：DOCX 頁(yè)數(shù)：7 大小：17.72KB 積分：2.4 舉報(bào) 版權(quán)申訴

本文格式為Word版，下載可任意編輯——編譯原理韓太魯?shù)谒恼碌谖逭麓鸢疙n太魯修訂版編譯原理第四章第五章

第四章

4.1文法G1為：

N→ND|DD→0|1

（1）L(G1)如何表示？

（2）給出句子011100的最左推導(dǎo)和最右推導(dǎo)。解答：(1)L(G1)為無(wú)符號(hào)二進(jìn)制數(shù)。(2)最左推導(dǎo)：

N?ND?NDD?NDDD?NDDDD?NDDDD??NDDDDD??DDDDDD??

???DDDDD????DDDD?????DDD??????DD???????D?????????

最右推導(dǎo)：

N?ND?N0?ND0?N00?ND00??N100??ND100??

?N1100???ND1100??N11100?D11100??????????

4.2寫一文法G2，使其L(G2)是正奇數(shù)集合，且每個(gè)數(shù)不以0打頭。解答：令G2={VN,VT,P,}，

其中，VT={0,1,2,3,4,5,6,7,8,9}，

VN={,,,,,}，P：→│→│→│數(shù)字1→1│2│3│4│5│6│7│8│9→1│3│5│7│9→0│2│4│6│84.3設(shè)文法G3為：

E→E+T|TT→T*F|FF→(E)|i

試證明符號(hào)串T*F+i是G3的句型，并給出此句型的所有短語(yǔ)以及句柄。

解答：由于有推導(dǎo)E?E+T?T+T?T*F+T?T*F+F?T*F+i所以T*F+i是的G3的句型。此句型T*F+i的語(yǔ)法樹(shù)如圖4-5：

EE+TTFT*Fi

圖4-5句型T*F+i的語(yǔ)法樹(shù)

根據(jù)語(yǔ)法樹(shù)此句型的短語(yǔ)有：T*F,i,T*F+i.句柄為T*F。

4.4證明文法G4：S→iSeS|iS|a是二義性文法。

1

韓太魯修訂版編譯原理第四章第五章

解答：要證明文法是二義性文法，只要找到它的任意一個(gè)句型有兩個(gè)語(yǔ)法樹(shù)即可。由于句型iiaes有兩個(gè)語(yǔ)法樹(shù)（圖4-6）,所以G4是二義性文法。

SSiSeSiSiSiSeSaa

圖4-6句型iiaes的語(yǔ)法樹(shù)

4.5設(shè)文法G5為：

E→E+T|TT→T*F|FF→P↑F|PP→(E)|i

（1）試給出G5的FIRSTVT和LASTVT。

（2）構(gòu)造G5的算符優(yōu)先關(guān)系表，G5是算符優(yōu)先文法嗎？（3）給出G5的優(yōu)先函數(shù)表。解答：由題意可得：

(1)FIRSTVT(E)={+,*,↑,i,(}

LASTVT(E)={+,*,↑,i,)}FIRSTVT(T)={*,↑,i,(}

LASTVT(T)={*,↑,i,)}FIRSTVT(F)={↑,i,(}

LASTVT(F)={*,i,)}FIRSTVT(P)={i,(}

LASTVT(P)={i,)}

(2)G5的算符優(yōu)先關(guān)系表如表4－4所示

表4－4G5的算符優(yōu)先關(guān)系表??1?2+*↑i()#+*↑i()#

4.6設(shè)所給文法為G5（習(xí)題4-5），

（1）消除G5的左遞歸；

2

韓太魯修訂版編譯原理第四章第五章

（2）設(shè)消除左遞歸的文法為G6，給出G6所有非終極符的FIRST集和FOLLOW集；（3）說(shuō)明G6是否為L(zhǎng)L(1)文法；（4）構(gòu)造G6的LL(1)分析表；解答：

（1）消除G5的左遞歸得G6

E→TE'

E'→+TE'|εT→FT'

T'→*FT'|ε

F→P↑F|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）由于F→P↑F|P含有左公因子，所以G6不是ll(1)文法。（4）G6的LL(1)分析表如表4-6。

表4-6G6的LL(1)分析表

i+*()↑#EE→TE'E→TE'E'E'→+TE'E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→P↑FF→PF→P↑FF→PPP→iP→(E)

4.7

解答:G7的拓廣文法如下：

（0）S'→S(1)S→AAd（2）S→cAd（3）S→b（4）A→ASc（5）A→Sb（6）A→cd（7）A→a構(gòu)造G7的LR（0）項(xiàng)目集規(guī)范族如圖4－7

3

韓太魯修訂版編譯原理第四章第五章

I0S'→·SS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aI4bcaI6A→a·I4abA→cd·cI1SS'→S·A→S·bI2AS→A·AdA→A·ScS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aS→c·AdA→c·dA→·AScA→·SbA→·cdA→·aS→·AAdS→·cAdS→·bSbI5bI5A→Sb·I8S→AA·dA→A·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·adScadI9AScabI7I9I3I6I4S→AAd·S→b·I3A→AS·cbI5A→S·bccI3I10aI6A→ASc·bI4AI14S→cAd·I9I3SdI12I11S→cA·dAA→A·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aI6bI4AI7A→S·b圖4－7G7的LR（0）項(xiàng)目集規(guī)范族

G7的LR(0)分析表如表4-7

表4-7LR(0)分析表

ACTIONGOTO狀態(tài)0123456789101112

aS6S6S6r3r5r7S6r1r4S6bS4S5S4S4r3r5r7S4r1S5r4S4S5cS3S3S3r3r5r7S3r1S10r4S3S10dS13r3r5r7S8r1r4S14#AccS1912A2711r3r5r7r1r499774

韓太魯修訂版編譯原理第四章第五章

1314r6r2r6r2r6r2r6r2r6r2由于G7的LR(0)分析表無(wú)多重入口，所以G7為L(zhǎng)R(0)文法，同理可知G7為SLR(1)文法。

4.8對(duì)如下文法G8：

S→AA→BAA→εB→aBB→b

構(gòu)造LR(1)項(xiàng)目集規(guī)范族和LR(1)分析表，并說(shuō)明文法是否為L(zhǎng)R(1)文法。

解答：

文法G8的拓廣文法為（0）S'→S（1）S→A（2）A→BA（3）A→ε（4）B→aB（5）B→b

構(gòu)造G8的LR（1）項(xiàng)目集規(guī)范族如圖4－8

I0[S'→·S,#]S[S'→·S,#]I1[S→·A,#]A[S→A·,#]I2[A→·BA#]I3[A→·,#]BI6[B→·aB,#/a/b][A→B·A,#]A[A→·BA,#][A→BA·,#][B→·b,#/a/b][A→·,#][B→·aB,#/a/b]BI5ba[B→·b,#/a/b]bI5[B→·b,/a/b]I4a[B→a·B,#/a/b]I7a[B→·aB,#/a/b]B[B→aB·,#/a/b][B→·b,#/a/b]

圖4－8G8的LR（1）項(xiàng)目集規(guī)范族