編譯原理習(xí)題與答案(編輯修改稿)
2024-09-11 20:44 本頁面
【文章內(nèi)容簡介】 面對輸入符號 a或 b的下一狀態(tài)相同 ， 故合并為一個狀態(tài) ?即最簡狀態(tài) {0}、 {1}、 {2， 3}、 {4}。 ?按順序重新命名為 0、 3， 則得到最簡 DFA， 如下圖所示 。 第三章 4 － － 3 4 4 2 4 4 1 3 4 0 1 2 a b 0 3 1 2 a b b b a a － － 3 2 3 3 1 2 3 0 1 2 a b 第三章 第四章 作業(yè) 設(shè)有文法 G[S]: S→A A→B|AiB B→C|B+C C→)A*|( 1）將文法 G[S]改寫為 LL(1)文法。 2）求經(jīng)改寫后的文法的每個非終結(jié)符的FIRST集和 FOLLOW集。 3）構(gòu)造相應(yīng)的預(yù)測分析表。 第四章 1）將文法 G[S]改寫為 LL(1)文法。 文法 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)文法。 FIRST(C)={(,)} FIRST(B’)={+, ε} FIRST(B)={(,)} FIRST(A’)={i, ε} FIRST(A)={(,)} FIRST(S)={(,)} FOLLOW(S)={$} FOLLOW(A)={$,*} FOLLOW(A’)={$,*} FOLLOW(B)={i,$,*} FOLLOW(B’)={i,$,*} FOLLOW(C)={+,i,$,*} S→A A→BA’ A’→ iBA’|ε B→CB’ B’ → +CB’|ε C→)A*|( 第四章 SELECT(S→A) =FIRST(A)=((,)) SELECT(A→BA’)=((,)) SELECT(A’→iBA’) ={i} SELECT(A’→ε)= FOLLOW(A’)= {$,*} SELECT(B→CB’)=((,)) SELECT(B’ →+CB’) ={+} SELECT(B’→ε)= {i, $,*} SELECT(C→)A*)={)} SELECT(C→( )= {(} 因為 同一非終結(jié)符的不同產(chǎn)生式的 Select集交集為空 ，所以改寫后的文法是 LL(1)文法。 2）求經(jīng)改寫后的文法的每個非終結(jié)符的 FIRST集和FOLLOW集。 在上步中已經(jīng)求出。 FIRST(C)={(,)} FIRST(B’)={+, ε} FIRST(B)={(,)} FIRST(A’)={i, ε} FIRST(A)={(,)} FIRST(S)={(,)} FOLLOW(S)={$} FOLLOW(A)={$,*} FOLLOW(A’)={$,*} FOLLOW(B)={i,$,*} FOLLOW(B’)={i,$,*} FOLLOW(C)={+,i,$,*} 3）構(gòu)造相應(yīng)的預(yù)測分析表。 B39?！?ε B39?！?ε C→)A* B’ →+CB’ B39?！?ε C→( B’ B→CB’ B→CB’ B A 39?！?ε A 39?！?ε A’→iBA’ A’ A→BA’ A→BA’ A S $ * ) + i ( 終極符號 語法變量 S →A S →A SELECT(S→A) = ((,)) SELECT(A→BA’)=((,)) SELECT(A’→iBA’) ={i} SELECT(A’→ε)= {$,*} SELECT(B→CB’)=((,)) SELECT(B’ →+CB’) ={+} SELECT(B’→ε)= {i, $,*} SELECT(C→)A*)={)} SELECT(C→( )= {(} C 第四章 作業(yè) 設(shè)有表格結(jié)構(gòu)文法 G[S]: S→a| ∧ |(T) T→T,S|S 1）計算文法的 FIRSTVT集和 LASTVT集。 2）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算符優(yōu)先文法。 3）計算其優(yōu)先函數(shù)。 第四章 1）計算文法的 FIRSTVT集和LASTVT集。 FIRSTVT(S)={a, ∧ , (} FIRSTVT(T)={, a, ∧ , (} LASTVT(S)={a, ∧ , )} LASTVT(T)={, a, ∧ ,)} 2）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算符優(yōu)先文法。 S→a| ∧ |(T) T→T,S|S ∧ = $ a ( a , ) = ( $ , ) ∧ 第四章 3）計算其優(yōu)先函數(shù)。 用逐次加 1法構(gòu)造優(yōu)先函數(shù) ∧ = $ a ( a , ) = ( $ , ) ∧ 1 1 1 1 1 1 1 1 1 1 迭代函數(shù) 函數(shù) 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→c
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1