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

《編譯原理第二版第六章課后答案.doc》由會員分享，可在線閱讀，更多相關《編譯原理第二版第六章課后答案.doc（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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