【文章內(nèi)容簡介】 {1} {2} {4} {2} {1} {3} J={1} J={4} J={1} J={3} 012 34bbba5bbabaaaa{4} {3} {0} {5} {3} {2} J={0} J={5} J={3} J={2} J={5} J={4} {5} {5} {4} (2) 把 DFA M’進行化簡 解 : ① 把 M狀態(tài)集分為兩組 : 終態(tài)結(jié)點 {0， 1} 非終態(tài)結(jié)點 {2， 3， 4， 5} ② 考察 {0， 1} 因為， {0， 1}a = {0， 1}b = 所以， {0， 1}不可再分 {1} {2， 4} ? {0,1} {2， 3， 4， 5} J={1} J={2， 4} ?012 34bbba5bbabaaaa ② 考察 {2， 3， 4， 5} 因為， {2,3,4,5}a = 所以， {2,3,4,5}可再分 看圖，把 {2,3,4,5}分割為 {2,4}和 {3,5} {0,1,3,5} {2,3,4,5} J={0,1,3,5} 012 34bbba5bbabaaaa? {0,1} ? ② 考察 {2， 4} 因為， {2， 4}a = {2， 4}b = 所以， {2， 4}不可再分 ② 考察 {3， 5} 因為， {3， 5}a = {3， 5}b = 所以， {3， 5}不可再分 {0,1} {3,5} ? {0,1} {3,5} J={0,1} J={3,5} ?012 34bbba5bbabaaaa{3,5} {2,4} ? {3,5} {2,4} J={3,5} J={2,4} ?所以，最終把 M分割為 {0， 1}， {2， 4} ， {3， 5} 用狀態(tài) 0代替狀態(tài) 1，把引向狀態(tài) 1的箭弧都引向狀態(tài) 0，把 1消去 ； 用狀態(tài) 2代替狀態(tài) 4，把引向狀態(tài) 4的箭弧都引向狀態(tài) 2，把 4消去 ； 用狀態(tài) 5代替狀態(tài) 3，把引向狀態(tài) 3的箭弧都引向狀態(tài) 5，把 3消去 ； 得到一個 DFA M’ 012 34bbba5bbabaaaaa 0 2ba5bba DFA，它接受 {0， 1}上所有滿足如下條件的字符串：每個 1都有 0直接跟在右邊。 解 : (1)根據(jù)題意，得到相應的正規(guī)式： (0|10)* (2)由以上正規(guī)式構造相應的 NFA為： εXεY11020(1)用子集法對 M’進行確定化 ① 構造一張表 I I0 =ε_CLOSURE(J) I1 =ε_CLOSURE(J) J={1} J={2} {x,1,y} {1,y}{1,y} {1,y} {2} {2} {2} {1,y} J={1} J={2} J={1} εXεY11020② 把每個子集看成一個狀態(tài)，得到一個 DFA M， 且 L(M) = L(M’) s 0 1 0 1 2 1 1 1 2 2 I I0 =ε_CLOSURE(J) I1 =ε_CLOSURE(J) 0 1 2 1 2 1 1 2 {x,1,y} {1,y}{1,y} {1,y} {2} {2} {2} {1,y} s 0 1 0 1 2 1 1 1 2 2 00102110(2) 把 DFA M’進行化簡 解 : ① 把 M狀態(tài)集分為兩組 : 終態(tài)結(jié)點 {0， 1} 非終態(tài)結(jié)點 {2} ② 考察 {0， 1} 因為， {0， 1}0 = {0， 1}1 = 所以， {0， 1}不可再分 {1} {2} ? {0,1} {2} J={1} J={2} ?00102110所以， 最終把 M分割為 {0， 1}， {2} 用狀態(tài) 1代替狀態(tài) 0，把引向狀態(tài) 0的箭弧都引向狀態(tài) 1，把 0消去，得到一個 DFA M’ 1 210000102110 問題一： 消除文法直接左遞歸方法 ： 設有產(chǎn)生式 P→Pα 1|Pα2|…|Pα m|β1|β2|…|β n 其中每個 βi不以 P開頭，每個 αi不為 ε 消除 P的直接左遞歸性就是把這些規(guī)則改寫成： P→β 1P’|β2P’|…|β nP’ P’→α 1P’| α2P’|…|α mP’| ε 練習 自上而下的語法分析 如果文法不含回路（形如 的推導），也不含有以 ε為右部的產(chǎn)生式，則下面算法可以消除左遞歸 (1)把文法 G的所有非終結(jié)符按任一種順序排列成 P1,P2,… ,Pn；按此順序執(zhí)行 (2)for i = 1 to n do for j = 1 to i1 do 把形如 Pi→P jγ 的規(guī)則改寫成 : Pi→ δ 1γ |δ 2γ |… |δ kγ 。 其中 Pj→ δ 1|δ 2|… |δ k是關于 Pj的所有產(chǎn)生式 Endfor 消除關于 Pi的直接左遞歸 Endfor (3)化簡由 (2)得到的文法：除去從開始符號無法達到的非終結(jié)符的產(chǎn)生式 PP ??例子 ：考慮以下文法，消除其左遞歸性 S→Qc | c Q→Rb | b R→Sa | a 解 ： (1)把該文法的非終結(jié)符排列為 R、 Q、 S. (2)對于 R，不存在直接左遞歸，不用消除 對于 Q，把 R代入到 Q的有關候選式后，把 Q的產(chǎn)生式改寫為 Q→Sab| ab | b 現(xiàn)在 Q不存在直接左遞歸，不用消除 對于 S，把 Q代讀到 S的有關候選式后，把 S的產(chǎn)生式改寫為 S→Sabc | abc | bc | c S有直接左遞歸，消除 S的直接左遞歸為 S→abcS’ | bcS’ | cS’ S’→abcS’ | ε 得到消除左遞歸性的文法為 S→abcS’ | bcS’ | cS’ S’→abcS’ | ε Q→Sab| ab | b R→Sa | a (3)顯然， Q和 R的產(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ? 化簡后的文法是： S→abcS’ | bcS’ | cS’ S’→abcS’ | ε 注意 ：由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣，但它們都是等價的 例如 ：考慮剛才的文法，消除其左遞歸性 S→Qc | c Q→Rb | b R→Sa | a 解 ： (1)把該文法的非終結(jié)符排列為 S、 Q、 R (2)對于 S，不存在直接左遞歸，不用消除 對于 Q，不存在直接左遞歸，不用消除 對于 R，把 S代入到 R的有關候選式后，把 R的產(chǎn)生式改寫為 R→Qca| ca | a 把 Q代入到 R的有關候選式后，把 R的產(chǎn)生式改寫為 R→Rbca| bca | ca | a R→Rbca| bca | ca | a R有直接左遞歸，消除 S的直接左遞歸為 R→bcaR’ | caR’ | aR’ R’→bcaR’ | ε 得到消除左遞歸性的文法為 S→Qc | c Q→Rb | b R→bcaR’ | caR’ | aR’ R’→bcaR’ | ε 問題三： 證明是 LL(1)文法 (1)文法不含左遞歸 (2)對于文法中每一個非終結(jié)符 A的各個產(chǎn)生式的候選式的 FIRST集兩兩不相交。即，若 A→α 1|α2|…|α n 則 FIRST(α i)∩FIRST( α j)=Φ (i≠j) (3)對于文法中的每個非終結(jié)符 A，若它的某個候選首符集包含 ε,則 FIRST(A)∩FOLLOW(A)= Φ 如果一個文法 G滿足以上條件，則稱該文法 G為 LL(1)文法 (第 1個 L代表從左到右掃描輸入串，第 2個 L代表最左推導， 1表示分析時每一步只看 1個符號 ) 問題四 ：預測分析表 M(xm ， ai )的構造方法 非 終 結(jié) 符EE 39。TT 39。E → T E 39。T → F T 39。F輸 入 符 號i + * （