編譯原理第二版第六章課后答案.doc

《編譯原理第二版第六章課后答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理第二版第六章課后答案.doc（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第六章 第6章自底向上優(yōu)先分析 P122 練習(xí) 1、已知文法G[S]為： Sa|^|(T) TT,S|S (1)計(jì)算G[S]的FIRSTVT和LASTVT。 (2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說(shuō)明G[S]是否為算符優(yōu)先文法。 (4)給出輸入串(a,a)#和(a,(a,a))#的算符優(yōu)先分析過(guò)程。 【解】 (1) FIRSTVT LASTVT S a、^、（ a、^、） T ，、a、^、（ ，、a、^、) (2) 算符優(yōu)先關(guān)系 a ( ) , ^ # a ≯ ≯ ≯ ( ≮ ≮ = ≮ ≮ ) ≯ ≯ ≯ , ≮ ≮ ≯ ≯ ≮ ^ ≯ ≯ ≯ # ≮ ≮ ≮ (4) 句子(a,a)#分析過(guò)程如下： 步驟 棧 優(yōu)先關(guān)系 當(dāng)前符號(hào) 剩余輸入串 移進(jìn)或歸約 1 # #≮( ( a,a)# 移進(jìn) 2 #( (≮a a ,a)# 移進(jìn) 3 #(a a≯, , a)# 歸約 4 #(F (≮, , a)# 移進(jìn) 5 #(F, ,≮a A )# 移進(jìn) 6 #(F,a A≯) ) # 歸約 7 #(F,F ,≯) ) # 歸約 8 #(F (≡) ) # 移進(jìn) 9 #(F) )≯# # 歸約 10 #F #≡# # 接受 句子(a, (a, a))分析過(guò)程如下： 步驟 棧 優(yōu)先關(guān)系 當(dāng)前符號(hào) 剩余輸入串 移進(jìn)或歸約 1 # #≮( ( a,(a,a))# 移進(jìn) 2 #( (≮a a , (a,a))# 移進(jìn) 3 #(a a≯, , (a,a))# 歸約 4 #(F (≮, , (a,a))# 移進(jìn) 5 #(F, ,≮( ( a,a))# 移進(jìn) 6 #(F,( (≮a a ,a))# 移進(jìn) 7 #(F,(a a≯, , a))# 歸約 8 #(F,(F (≮, , a))# 移進(jìn) 9 #(F,(F, ,≮a a ))# 移進(jìn) 10 #(F,(F,a a≯) ) )# 歸約 11 #(F,(F,F ,≯) ) )# 歸約 12 #(F,(F (≡) ) )# 移進(jìn) 13 #(F,(F) )≯) ) # 歸約 14 #(F,F ,≯) ） # 歸約 15 #(F (≡) ) # 移進(jìn) 16 #(F) )≯# # 歸約 17 #F #≡# # 接受 4、已知文法G[S]為： S->S;G|G G->G(T)|H H->a|(S) T->T+S|S (1)構(gòu)造G[S]的算符優(yōu)先關(guān)系表，并判斷G[S]是否為算符優(yōu)先文法。 (2)給出句型a（T+S）;H;(S)的短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。 【解】 （1） FIRSTVT(S)={； ( a } FIRSTVT(G)={ ( a } FIRSTVT(T)={+ ； ( a} LASTVT(S)={； a ) } LASTVT(G)={ a ) } LASTVT(T)={+ ; a ) } >關(guān)系： LASTVT(S) >; LASTVT(G)>( LASTVT(T)>) LASTVT(S)>) LASTVT(T)> + < 關(guān)系 ;(G) ( +< FIRSTVT(S) = 關(guān)系 ( = ) ; ( ) a + # ; <. .> <. .> .> ( <. <. <. .> ) .> .> .> a .> .> .> + <. <. .> <. .> .> # <. <. <. <. <. 因?yàn)槲姆ㄖ腥我鈨蓚€(gè)終結(jié)符之間只存在一種關(guān)系，因此該文法為算符優(yōu)先文法。 （2）建立句型的語(yǔ)法子樹(shù)如下： 短語(yǔ)為：a, T+S, H, (S), a(T+S),a(T+S);H , a（T+S）;H;(S) 句柄：a 素短語(yǔ)：a, T+S, (S) 最左素短語(yǔ)：a