【正文】 71103410051010067 用狀態(tài) 5代替狀態(tài) 4，把引向狀態(tài) 4的箭弧都引向狀態(tài) 5，把 4消去； 11034100510100671103105100067 用狀態(tài) 7代替狀態(tài) 6，把引向狀態(tài) 6的箭弧都引向狀態(tài) 7，把 6消去；得到一個化簡得 DFA M 1103105100067110310510 07 (a)和 (b)分別確定化和最少化 a 0 1a , ba(a) (b) 012 34bbba5bbabaaaa(1)用子集法對 M’進(jìn)行確定化 ① 構(gòu)造一張表 I Ia =ε_CLOSURE(J) Ib =ε_CLOSURE(J) J={0,1} J={1} {0} {0,1}{0,1} {0} {1} {1} {1} {0,1} J={0} J={1} J={0,1} a 0 1a , ba② 把每個子集看成一個狀態(tài)，得到一個 DFA M， 且 L(M) = L(M’) s a b 0 1 2 1 1 0 2 2 I Ia =ε_CLOSURE(J) Ib =ε_CLOSURE(J) 0 1 2 1 2 1 0 2 {0} {0,1} {0,1} {0} {1} {1} {1} {0,1} s a b 0 1 2 1 1 0 2 2 0aba21ba(2) 把 DFA M’進(jìn)行化簡 解 : ① 把 M狀態(tài)集分為兩組 : 終態(tài)結(jié)點(diǎn) {0， 1} 非終態(tài)結(jié)點(diǎn) {2} ② 考察 {0， 1} 因?yàn)椋? {0， 1}a = {0， 1}b = 所以， {0， 1}不可再分 {1} {2} ? {0,1} {2} J={1} J={2} 0aba21ba?所以， 最終把 M分割為 {0， 1}， {2} 用狀態(tài) 0代替狀態(tài) 1，把引向狀態(tài) 1的箭弧都引向狀態(tài) 0，把 1消去，得到一個 DFA M’ 0aba21baa 0 2ba(2)用子集法對 M’進(jìn)行確定化 ① 構(gòu)造一張表 I Ia =ε_CLOSURE(J) Ib =ε_CLOSURE(J) J={1} J={2} {0} {1} {1} {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’進(jìn)行化簡 解 : ① 把 M狀態(tài)集分為兩組 : 終態(tài)結(jié)點(diǎn) {0， 1} 非終態(tài)結(jié)點(diǎn) {2， 3， 4， 5} ② 考察 {0， 1} 因?yàn)椋? {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} 因?yàn)椋? {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} 因?yàn)椋? {2， 4}a = {2， 4}b = 所以， {2， 4}不可再分 ② 考察 {3， 5} 因?yàn)椋? {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直接跟在右邊。 其中 Pj→ δ 1|δ 2|… |δ k是關(guān)于 Pj的所有產(chǎn)生式 Endfor 消除關(guān)于 Pi的直接左遞歸 Endfor (3)化簡由 (2)得到的文法：除去從開始符號無法達(dá)到的非終結(jié)符的產(chǎn)生式 PP ??例子 ：考慮以下文法，消除其左遞歸性 S→Qc | c Q→Rb | b R→Sa | a 解 ： (1)把該文法的非終結(jié)符排列為 R、 Q、 S. (2)對于 R，不存在直接左遞歸，不用消除 對于 Q，把 R代入到 Q的有關(guān)候選式后，把 Q的產(chǎn)生式改寫為 Q→Sab| ab | b 現(xiàn)在 Q不存在直接左遞歸，不用消除 對于 S，把 Q代讀到 S的有關(guān)候選式后，把 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的有關(guān)候選式后，把 R的產(chǎn)生式改寫為 R→Qca| ca | a 把 Q代入到 R的有關(guān)候選式后，把 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集兩兩不相交。TT 39。T → F T 39。 → + T E 39。 → ε T 39。E → T E 39。F → ( E )E 39。 → εE 39。 → εE R R O R 1. 定義 FIRST集 令文法 G是不含左遞歸的文法，對 G的非終結(jié)符的候選 α ，定義它的開始符號（終結(jié)首符）集合： ? 特別地，如果 α ε，則 ε∈ FIRST(α ) ? 如果非終結(jié)符 A的任意兩個候選式 α i和 α j的開始符號集滿足 FIRST(α i)∩FIRST( α j)=Φ，則 A可以根據(jù)所面臨的第一個輸入符號，準(zhǔn)確地指派一個候選式 α 去執(zhí)行任務(wù)， α 是那個 FIRST集含