編譯原理習題與答案(存儲版)
【正文】 T(A→BA’)=((,)) SELECT(A’→iBA’) ={i} SELECT(A’→ε)= {$,*} SELECT(B→CB’)=((,)) SELECT(B’ →+CB’) ={+} SELECT(B’→ε)= {i, $,*} SELECT(C→)A*)={)} SELECT(C→( )= {(} C 第四章 作業(yè) 設有表格結構文法 G[S]: S→a| ∧ |(T) T→T,S|S 1）計算文法的 FIRSTVT集和 LASTVT集。aA E→B B→ A c c d 10: A→d]： (0) S39。r,i P→,m 5: P→m, i 9: P→r, i (2) 對 SLR(1)分析表來說 ， 若項目 A→ α ,b]屬于 Im(狀態(tài) )， 則同樣置 ACTION[m,b]欄目為 rj。 AaSSBAdScABbABbA edScAaSAB圖 AacAbcBaAdbed對應的語法樹 第五章 (2) 由 圖 可 知 ， 句型AacAbcBaAdbed中的短語為： B, BaA, cBaAd, AbcBaAd, e, AbcBaAdbe, cAbcBaAdbed, A, AacAbcBaAdbed AaSSBAdScABbABbA edScAaSAB第五章 從圖可看出 ， 句型AacAbcBaAdbed的 素短語為： BaA和 e。 第五章 第五章 (1) 根據文法 G[S]畫出AacAbcBaAdbed對應的語法樹如圖所示 。 例如 ， 假定[A→ α 屬于 Ik(狀態(tài) )，則對 任何終結符 a(包括 $)，置ACTION[k,a]為“用產生式 A→α 進行歸約(A→α 為第 j個產生式 )”，簡記為“ rj”。 i 7: P→m, i ,r P→rm,i P→ (1) 將文法 G[S]拓廣為文法 G39。d a 11: B→dcB B→ 用逐次加 1法構造優(yōu)先函數 ∧ = $ a ( a , ) = ( $ , ) ∧ 1 1 1 1 1 1 1 1 1 1 迭代函數 函數 a ∧ , ( ) f g 0(初值 ) f g 1 2 2 2 1 3 2 3 3 3 1 3 3 3 1 3 4 4 2 4 1 f g 2 , 第四章 ? 例文法 G[S] S?→E E→aA|bB A→cA|d B→cB|d 1）構造識別文法活前綴的 DFA 2）構造其 LR(0)分析表 3）輸入串 aabab是否為文法 G定義的句子 0: S?→→ ε C→( B’ B→CB’ B→CB’ B A 39。 文法 G[S]為左遞歸文法，削去文法左遞歸后的文法為： S→A A→BA’ A’→ iBA’|ε B→CB’ B’ → +CB’|ε C→)A*|( S→A A→B|AiB B→C|B+C C→)A*|( 第四章 1）將文法 G[S]改寫為 LL(1)文法。 (2) 畫出與正規(guī)表達式 a(b|a(a|b))|b(a|b)對應的NFA， 如圖所示 。 解： (1) 該語言對應的正規(guī)式為 a(aa)*bb(bb)*a(aa)*。 a) x(x|y)*x 必須以 x 開頭和 x結尾的串 b) x*(yx+)*x* 每個 y 至少有一個 x 跟在后邊的串 c) (x|y)*(xx|yy) (x|y)* 所有含兩個相繼的 x或兩個相繼的 y的串 第三章 xy xyxxy yyyx xyyxyxyxxy 第三章 非確定有限自動機 (NFA)變換成等價的確定有限自動機(DFA)。(T*F), P 238。 N ? ND ?NDD ?NDDD ?DDDD ?0DDD ?01DD ?012D ?0123 N ? ND ?N3 ?ND3 ?N23 ?ND23 ?N123 ?D123 ?0123 證明下面的文法是二義性的 。 G： S→aA A→bA | aB | b B →aA 解：先由產生式得 : B=aA 將 B代入 A中得 :A=bA|aaA|b =(b|aa)A|b 利用規(guī)則 （ AxA|y） 得 : A= (b|aa) * b 將 A代入 S中得 :S=a (b|aa) * b 即為所求正規(guī)式 給出文法 G[S]，構造相應最小的 DFA。 345aabba2bb01a7bb6babaa第三章 b a 0 1 2 1 3 4 2 5 － 3 3 6 4 3 5 5 5 7 6 6 6 7 6 7 ? 對上圖的 DFA進行最小化 。 {X} {1} {2} {1} {1} {2} {3} {4} {5} {6} － {Y} － {Y} － {3} － {4} {5} {4} － 重命名 X
環(huán)評公示相關推薦
鄂ICP備17016276號-1