資源描述：
《西安電子科技大學(xué)編譯原理.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。
1、3)--終態(tài)判斷2)--循環(huán)1)--準(zhǔn)備初值2.3.2確定的有限自動機（續(xù)3）s:=s0；ch:=nextchar()；whilech≠eofloopendloop;ifthenreturn“yes”;elsereturn“no”;endif;■用算法2.1識別abb：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=b4.s=3,ch=eof5.yes用算法2.1識別abab：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=a4.s=1,ch=b5.s=2,ch=eof6.no輸入DFAD和輸入字符串x(eof)。D的初態(tài)為s0，終態(tài)集為F。
2、輸出若D接受x，回答“yes”，否則回答“no”。方法用下述過程識別x：算法2.1模擬DFAs:=move(s,ch);ch:=nextchar();s∈F算法2.312.3.3有限自動機的等價定義2.6若有限自動機M和M’識別同一正規(guī)集，則稱M和M’是等價的，記為M=M’?！稣?guī)式(a
3、b)*abb的NFA正規(guī)式(a
4、b)*abb的DFA特別提示：正規(guī)式與有限自動機從兩個側(cè)面表示正規(guī)集。正規(guī)式是描述，自動機是識別。因此，當(dāng)它們表示相同集合時，均存在等價的問題。22.4從正規(guī)式到詞法分析器構(gòu)造詞法分析器的一般方法和步驟：用正規(guī)式描述模式（為記號設(shè)計正規(guī)式）；為每
5、個正規(guī)式構(gòu)造一個NFA，它識別正規(guī)式所表示的正規(guī)集；將構(gòu)造的NFA轉(zhuǎn)換成等價的DFA，這一過程也被稱為確定化；優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過程也被稱為最小化；根據(jù)優(yōu)化后的DFA構(gòu)造詞法分析器。問題：1.為何不直接從正規(guī)式構(gòu)造DFA? 2.為何不從NFA直接構(gòu)造詞法分析器？原因：正規(guī)式→NFA：有規(guī)范的一對一的構(gòu)造算法DFA→分析器：便于實現(xiàn)記號識別的算法32.4.1從正規(guī)式到NFA算法2.2Thompson算法輸入字母表∑上的正規(guī)式r輸出接受L(r)的NFAN方法首先分解r，然后根據(jù)下述步驟構(gòu)造NFA：<1>對ε，構(gòu)造NFAN(ε)如下。其中，s0為初態(tài)，f
6、為終態(tài)，此NFA接受{ε}；<2>對∑上的每個字符a，構(gòu)造NFAN(a)如右上，它接受{a}；<3>若N(P)和N(Q)是正規(guī)式P和Q的NFA，則（a）對正規(guī)式P
7、Q，構(gòu)造NFAN(P
8、Q)如下。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(P)∪L(Q)；參照P20 正規(guī)式定義s0εεfεε42.4.1從正規(guī)式到NFA（續(xù)1）（b）對正規(guī)式PQ，構(gòu)造NFAN(PQ)如下。其中s0為初態(tài)，f為終態(tài)，此NFA接受L(P)L(Q)；（c）對正規(guī)式P*，構(gòu)造NFAN(P*)如下。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(P*)（等價于(L(P))*）；（d）對于正規(guī)式
9、(P)，使用P本身的NFA，不再構(gòu)造新的NFA?！靓舠0εfεε52.4.1從正規(guī)式到NFA（續(xù)2）正規(guī)式、正規(guī)集、NFA的對應(yīng)關(guān)系：正規(guī)式正規(guī)集NFAε2.a3.P
10、Q4.PQ5.P*6.(P)L(ε)={ε}L(a)={a}L(P)∪L(Q)L(P)L(Q)(L(P))*L(P)s0εεfεεεs0εfεε62.4.1從正規(guī)式到NFA（續(xù)3）例2.11用Thompson算法構(gòu)造正規(guī)式r=(a
11、b)*abb的NFAN(r)<1>分解正規(guī)式<2>自下而上構(gòu)造NFA強調(diào)：構(gòu)造過程與正規(guī)式一一對應(yīng)構(gòu)造一個新的NFA最多增加兩個狀態(tài)72.4.2從NFA到DFA<1>N
12、FA識別記號的“并行”方法例2.12從甲地到乙地，可以乘車也可以騎自行車，具體路線如右圖。其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？問題抽象：識別是否有從甲到乙標(biāo)記為全c的路徑試探（串行）：甲c2無路可走，回退甲c1c3無路可走，回退甲c1c乙到達(dá)乙地，成功假設(shè)有足夠多的小汽車，每次均到達(dá)小汽車可能到達(dá)的全體并行：甲c{1,2}c{3,乙}到達(dá)乙地，成功82.4.2從NFA到DFA（續(xù)1）并行的方法，核心思想是將不確定的下一狀態(tài)確定化：在每試探一步時，考慮了所有的下一狀態(tài)轉(zhuǎn)移，因此所走的每一步都是確定的。NFA上識別
13、記號的確定化方法確定化的兩個方面（回顧DFA定義）計算下一狀態(tài)轉(zhuǎn)移時：<1>消除ε狀態(tài)轉(zhuǎn)移：ε-閉包(T)<2>消除多于一個的下一狀態(tài)轉(zhuǎn)移：smove(S,a)因此，用NFA識別記號，常用并行方法，而不采用串行的方法（算法不易構(gòu)造，復(fù)雜度高且回溯）92.4.2從NFA到DFA（續(xù)2）定義2.7狀態(tài)集T的ε-閉包(T)是一個狀態(tài)集，且滿足：（1）T中所有狀態(tài)屬于ε-閉包(T)；（2）任何smove(ε-閉包(T)，ε)屬于ε-閉包(T)；（3）再無其他狀態(tài)屬于ε-閉包(T)?！龈鶕?jù)定義，ε-閉包({s2})應(yīng)是：1.s2自身{s2}（1）2.s4{s2,s4}（2
14、）3.s5{s2,s4,
