第三章詞法分析(2)-文庫吧資料
2025-07-28 09:42本頁面
【正文】 from the start state. Any transitions to d from other states bee undefined. Minimizing the Number of States of DFA 67 B start a A a b b a a E b D C b b a Current partition Split on a Split on b ?0 (ABCD) (E) No change (ABC)(D)(E) ?1 (ABC)(D) (E) No change (AC)(B)(D)(E) ?2 (AC)(B)(D) (E) No change No change 68 B start a A a b b a a E b D C b b a ?final : (AC) (B) (D) (E) B start a AC a b b a E b D b MinimumDFA 69 另一個(gè)例子： 從 a(b|c)*構(gòu)造 NFA 70 用子集構(gòu)造法從 NFA得到 DFA 71 構(gòu)造最小化 DFA 72 例：考慮正規(guī)表達(dá)式 (a|b)*(aa|bb)(a|b)* 0 start 1 2 a b 3 4 5 ? 6 final a b ? ? ? a a b b 73 用子集構(gòu)造法得到的 DFA： q1 start a a b b b a q2 q3 q4 q6 a b q5 q7 b b a b a 74 Current partition Split on a Split on b ?0 (123)(4567) (13)(2)(4567) (1)(2)(3)(4567) Final partition 構(gòu)造最小狀態(tài)的 DFA： 75 另一種等價(jià)的構(gòu)造方法： 填表算法 ? 狀態(tài)的等價(jià)性 – p和 q等價(jià)： ? 若兩個(gè)狀態(tài)不等價(jià)，則稱二者是可區(qū)分的。這樣得到的狀態(tài)轉(zhuǎn)換圖所對(duì)應(yīng)的 DFA M?就是與 M等價(jià)的具有最少狀態(tài)的 DFA。 ? 重復(fù)劃分組的過程，直至不需要繼續(xù)劃分。 ? 例如， ?區(qū)分任何接受狀態(tài)和非接受狀態(tài)； ? b區(qū)分狀態(tài) A和狀態(tài) B； ? b區(qū)分狀態(tài) B和狀態(tài) C； ? …… B D start a A a b b a b C b a 62 B start a A a b b a a E b D C b b a State A and state B are distinguished by the input bb. (a|b)*abb對(duì)應(yīng)的 DFA 63 DFA最小化算法 (Hopcroft算法 ) ? DFA最小化的方法是將 DFA的狀態(tài)劃分為不相交的組，同一個(gè)組中的狀態(tài)是不可區(qū)分的，不同組的狀態(tài)則可以由某個(gè)輸入串區(qū)分。 55 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b r7 = r5 r6 a 2 3 start b 4 5 1 ? 6 ? ? ? ? 0 7 ? ? ? a 8 56 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b 57 1 2 start a 0 a b b (a|b)*ab的兩個(gè) NFA的比較 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 手工構(gòu)造的 NFA 語法制導(dǎo)的算法構(gòu)造的 NFA 58 B D start a A a b b a b C b a 1 2 start a 0 a b b a b 識(shí)別語言 (a|b)*ab 的 自動(dòng)機(jī) DFA可以化簡 1 2 start a 0 a b b 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 59 DFA的化簡 DFA Minimization ? 每個(gè)正規(guī)表達(dá)式都可以由唯一的狀態(tài)數(shù)最少的DFA識(shí)別 (minimal DFA)。 ? N(r)的每個(gè)狀態(tài)或者有一個(gè)用 ?中 的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換 ， 或者至多有兩個(gè)指向其它結(jié)點(diǎn)的 ?轉(zhuǎn)換 。 ? N(r)只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài) ， 接受狀態(tài)沒有向外的轉(zhuǎn)換 。 43 首先構(gòu)造識(shí)別 ?和字母表中一個(gè)符號(hào)的 NFA ? 識(shí)別 {?}的 NFA i f start 對(duì) ?， 構(gòu)造 NFA: i start a f 識(shí)別 {a}的 NFA 對(duì) 字母表中符號(hào) a，構(gòu)造 NFA: 44 構(gòu)造識(shí)別主算符為選擇的正規(guī)式的 NFA 對(duì)于正規(guī)式 s | t ，構(gòu)造 NFA： ? f i start 識(shí)別 L(s )?L(t)的 NFA q1 N (s) N (t) ? ? ? q2 f1 f2 45 構(gòu)造識(shí)別主算符為連接的正規(guī)式的 NFA 對(duì)于正規(guī)式 st ，構(gòu)造 NFA： 識(shí)別 L(s)L(t) 的 NFA N(s) ? start q0 f0 N(t) ? ? i N(s) N(t) f start N(s)的接受狀態(tài)和N(t)的開始狀態(tài)合并 46 構(gòu)造識(shí)別主算符為閉包的正規(guī)式的 NFA 對(duì)于正規(guī)式 s* ，構(gòu)造 NFA： N(s) f start 識(shí)別正規(guī)式 (L(s))* 的 NFA i ? ? ? ? 47 ? 對(duì)于加括號(hào)的正規(guī)式 (s)，使用 N(s)本身作為它的 NFA。 輸出：接受 L(r)的 NFA 。 利用正規(guī)表達(dá)式的語法結(jié)構(gòu)來制導(dǎo)構(gòu)造過程。 push u onto stack end end 36 ? 如果 DFA的某個(gè)狀態(tài)至少包含 NFA的一個(gè)接受狀態(tài)，那么，這個(gè)狀態(tài)是 DFA的一個(gè)接受狀態(tài)。 while stack is not empty do begin pop the top element t off the stack。 Dtran[T,a] := U end end 35 Fig 326 Computation of ?closure push all states in T onto stack。 for each input symbol a do begin U := ?closure(move(T,a))。 q2 1 0 q1 0 1 q0 1 0 18 從 NFA到 DFA的變換 ? 不確定的原因：多值轉(zhuǎn)換函數(shù) – 對(duì)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1