課后作業(yè).doc

第四章 詞法分析p72 1.構造正規(guī)式1(0|1)*101相應的dfa. 答案 先構造nfa 確定化 0 1 x a a a ab ab ac ab ac a aby aby ac ab 重新命名，令ab為b、ac為c、aby為d 0 1 x a a a b b c b c a d d c b dfa： 3.將下圖確定化：答案 0 1 s vq qu vq vz qu qu v quz vz z z v z quz vz quz z z z 重新命名，令vq為a、qu為b、vz為c、v為d、quz為e、z為f。 0 1 s a b a c b b d e c f f d f e c e f f f dfa： 4.把下圖最小化：答案 初始分劃得0：終態(tài)組0，非終態(tài)組1,2,3,4,5 對非終態(tài)組進行審查： 1,2,3,4,5a 0,1,3,5 而0,1,3,5既不屬于0，也不屬于1,2,3,4,5 4 a 0，所以得新分劃 1：0，4，1,2,3,5 對1,2,3,5進行審查： 1,5 b 4 2,3 b 1,2,3,5，故得新分劃 2：0，4，1, 5，2,3 1, 5 a 1, 5 2,3 a 1,3，故狀態(tài)2和狀態(tài)3不等價，得新分劃 3：0，2，3，4，1, 5 這是最后分劃了最小dfa： 5.構造一個dfa，它接收=0,1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規(guī)式和正規(guī)文法。 答案 按題意相應的正規(guī)表達式是0*(0 | 10)*0*或0*( 100*)*0* 構造相應的dfa，首先構造nfa為 用子集法確定化 i i0 i1 s 0 1 x,0,1,3,y 0,1,3,y 2 1,3,y 0,1,3,y 0,1,3,y 1,3,y 1,3,y 2 2 / 2 1 2 3 4 2 2 4 4 3 3 3 dfa：可最小化，終態(tài)組為1,2,4，非終態(tài)組為3，1,2,40 1,2,4，1,2,41 3，所以1,2,4為等價狀態(tài)，可合并。 8給出下列文法所對應的正規(guī)式： s-0a|1b a-1s|1 b-0s|0 答案 解方程組s的解： s=0a|1b a=1s|1 b=0s|0 將a、b產生式的右部代入s中 s=01s|01|10s|10=（01|10）s|（01|10） 所以：s= (01|10)*(01|10) 第五章 自頂向下優(yōu)先分析法p991. 文法 s-a|(t) t-t,s|s (1) 對(a,(a,a)和(a,a),(a),a)的最左推導。 (2)對文法g改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。 (3)經改寫后的文法是否為ll（1）的？給出它的預測分析表。 (4)給出輸入串(a,a)#的分析過程，并說明該串是否為g的句子。 答案 (1) 對(a,(a,a)的最左推導為： s=(t) =(t,s) =(s,s) =(a,s) =(a,(t) =(a,(t,s) =(a,(s,s) =(a,(a,s) =(a,(a,a) 對(a,a),(a),a) 的最左推導為： s=(t) =(t,s) =(s,s) =(t),s) =(t,s),s) =(t,s,s),s) =(s,s,s),s) =(t),s,s),s) =(t,s),s,s),s) =(s,s),s,s),s) =(a,s),s,s),s) =(a,a),s,s),s) =(a,a),s),s) =(a,a),(t),s) =(a,a),(s),s) =(a,a),(a),s) =(a,a),(a),a) (3)改寫文法為： 0) s-a 1) s- 2) s-( t ) 3) t-s n2 4) n2-, s n2 5) n2- first follow s a ( # , ) t a ( ) n2 , ) 對左部為n2的產生式可知： first （-, s n2）=， first （-）= follow （n2）=) ， )= 所以文法是ll(1)的。 預測分析表 a ( ) , # s -a - -( t ) t -s n2 -s n2 -s n2 n2 - -, s n2 也可由預測分析表中無多重入口判定文法是ll(1)的。 (4)對輸入串（a,a）#的分析過程為： 步驟 狀態(tài)棧 當前字符 剩余輸入串 操作 1 #s ( a,a)# s-(t) 2 #)t( ( a,a)# 匹配 3 #)t a ,a)# t-sn2 4 #)n2s a ,a)# s-a 5 #)n2a a ,a)# 匹配 6 #)n2 , a)# n2-,sn2 7 #)n2s, , a)# 匹配 8 #)n2s a )# s-a 9 #)n2a a )# 匹配 10 #)n2 ) # n2- 11 #) ) # 匹配 12 # # 可見輸入串（a,a）#是文法的句子。 3文法： s-mh|a h-lso| k-dml| l-ehf m-k|blm 判斷g是否為ll(1)文法，如果是，構造ll(1)分析表。 答案 源文法g展開為： 0） s-m h 1） s-a 2） h-l s o 3） h- 4） k-d m l 5） k- 6） l-e h f 7） m-k 8） m-b l m first follow s a,d,b,e #,o m d, ,b e,#,o h ,e #,f,o l e a,d,b,e,o,# k d, e,#,o 預測分析表 a o d e f b # s -a -mh -mh -mh -mh -mh m -k -k -k -blm -k h - -lso - - l -ehf k - -dml - - 由預測分析表中無多重入口判定文法是ll(1)的。 第六章 自底向上優(yōu)先分析法p1161、已知文法gs為： sa|(t) tt,s|s (1)計算gs的firstvt和lastvt。 (2)構造gs的算符優(yōu)先關系表并說明gs是否未算符優(yōu)先文法。 (3)計算gs的優(yōu)先函數(shù)。 (4)給出輸入串(a,a)#和(a,(a,a)#的算符優(yōu)先分析過程。 答案 (1) firstvt和lastvt firstvt lastvt s a、（ a、） t ，、a、（ ，、a、) (2) 算符優(yōu)先關系 a ( ) , # a ( ) , # (3) 對應的算符優(yōu)先函數(shù)為： a ( ) , # s 2 1 2 2 2 1 t 3 3 1 1 3 1 (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 # # 接受 第七章 lr分析法p1521、已知文法 a-aad| aab| 判斷該文法是否slr（1）文法，若是構造相應分析表，并對輸入串ab#給出分析過程。 答案 (1)拓廣文法 (0)s-a (1) a-aad (2)a- aab (3)a- (1)構造識別活前綴的dfa follow(a)=d,b,# 對于狀態(tài)i0：follow(a)a= 對于狀態(tài)i1：follow(a)a= 因為，在dfa中無沖突的現(xiàn)象，所以該文法是slr(1)文法。 (3)slr(1)分析表 狀態(tài) action goto a b d # a 0 s2 r3 r3 r3 1 1 acc 2 s2 r3 r3 r3 3 3 s5 s4 4 r1 r1