（9）编译程序第一个工作阶段-词法分析(NFA和DFA转换) .

上篇讲述确定有穷自动机和不确定有穷自动机，本篇讲述不确定有穷自动机和确定有穷自动机之间的转换。从百度文库中找到一个示例感觉很合适。 如图所示：  **1．具有ε动作的NFA状态转换表** <table border="1" cellspacing="0" cellpadding="0"><tbody><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">                                              </span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">                         a                        </span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">                        b                        </span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">                               ε                            </span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">0</span></strong></p></td><td valign="top"><p align="center"><a name="OLE_LINK1"><strong><span style="font-size:14px">Φ</span></strong></a></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">1, 7</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">1</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">2, 4</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">2</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">3</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">3</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">4</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">5</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">5</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">6</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">1, 7</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">7</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">8</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">8</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">9</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr><tr><td valign="top"><p align="center"><strong><span style="font-size:14px">9</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td><td valign="top"><p align="center"><strong><span style="font-size:14px">Φ</span></strong></p></td></tr></tbody></table> **2．分别求ε-closure** **ε-closure（I）就是状态集I中，任意状态S经过任意的 ε能到达的状态集合。** ~~~                ε-closure(0) = {0,1,2,4,7}                ε-closure(1) = {1,2,4}               ε-closure(2) = {2}               ε-closure(3) = {1,2,3,4,6,7}               ε-closure(4) = {4}               ε-closure(5) = {1,2,4,5,6,7}               ε-closure(6) ={1,2,4,6,7}               ε-closure(7) = {7}               ε-closure(8) = {8}               ε-closure(9) = {9} ~~~ **3．转换算法：** **move（I，a）是从I中的某一状态经过一条a弧而到达的状态全体。** ~~~               ε-closure(0) ={0,1,2,4,7} = A               ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8} = B               ε-closure(move(A,b))=ε-closure({5})={1,2,4,5,6,7} = C               ε-closure(move(B,a))=ε-closure({3,8}) = B               ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D               ε-closure(move(C,a))=ε-closure({3,8}) = B               ε-closure(move(C,b))=ε-closure({5}) = C               ε-closure(move(D,a))=ε-closure({3,8}) = B               ε-closure(move(D,b))=ε-closure({5}) = C ~~~ **** **4．DFA的转换表** <table border="1" cellspacing="0" cellpadding="0"><tbody><tr><td rowspan="2"><p align="center"><strong><span style="font-size:14px">                                          状态                                                 </span></strong></p></td><td width="379" colspan="2"><p align="center"><strong><span style="font-size:14px">      输入符号       </span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">a</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">b</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">A</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">D</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr><tr><td><p align="center"><strong><span style="font-size:14px">D</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">B</span></strong></p></td><td><p align="center"><strong><span style="font-size:14px">C</span></strong></p></td></tr></tbody></table> **5．状态转换图** **** 本篇到这里，编译原理入门教程就到这里了，仅仅是编译原理的初学者，请您多多指教哦 愿开心每一天~