《有窮自動(dòng)機(jī)》PPT課件.ppt

《《有窮自動(dòng)機(jī)》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Compiler編譯原理Wednesday,March13,2013（1）分析和識別單詞及屬性，包括識別語言的關(guān)鍵字、標(biāo)識符、常數(shù)、運(yùn)算符等；（2）跳過各種分隔符，如空格，回車，制表符等；（3）刪除注釋；（4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；（5）建立符號表。詞法分析的任務(wù)Compiler編譯原理Wednesday,March13,2013有窮自動(dòng)機(jī)標(biāo)識符無符號整數(shù)單界符雙界符S1非字母數(shù)字字母字母、數(shù)字2非數(shù)字?jǐn)?shù)字?jǐn)?shù)字3其他字符+*，（）出口4其他字符<5=非=出錯(cuò)其他讀字符查保留字表返回S狀態(tài)圖的形式化描述Compiler編譯原理W

2、ednesday,March13,2013有窮自動(dòng)機(jī)是一種數(shù)學(xué)模型，具有離散的輸入與輸出，系統(tǒng)可處于有窮狀態(tài)中的任何一個(gè)它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)（DFA）(DeterministicFiniteAutomata)不確定的有窮自動(dòng)機(jī)（NFA）(NondeterministicFiniteAutomata)Compiler編譯原理Wednesday,March13,20132型文法（不確定的

3、下推自動(dòng)機(jī)）1型文法（不確定的界限自動(dòng)機(jī)）0型文法（圖靈機(jī)）3型文法（有限自動(dòng)機(jī)）Compiler編譯原理Wednesday,March13,20131.確定的有窮自動(dòng)機(jī)（DFA）M=(Σ,Q,f,S,Z)Σ：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號Q：有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)S∈K，是唯一的初態(tài)Z?K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)f是轉(zhuǎn)換函數(shù)，是Q×Σ→Q上的單值映射：f（q1，a）=q2Compiler編譯原理Wednesday,March13,2013狀態(tài)轉(zhuǎn)移函數(shù)f可用一矩陣來表示：輸入字符狀態(tài)ab01213

4、2213333例如:M:（{0,1,2,3},{a,b},f，0，{3}）f（0，a）=1f（0，b）=2f（1，a）=3f（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)！字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。M=(Σ,Q,f,S,Z)Compiler編譯原理Wednesday,March13,2013一個(gè)DFA也可以用一狀態(tài)轉(zhuǎn)換圖表示：輸入字符狀態(tài)ab012132213333DFA的狀態(tài)

5、圖表示：1032aabba,bba字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。Compiler編譯原理Wednesday,March13,2013換言之：若存在一條初始狀態(tài)到某一終止?fàn)顟B(tài)的路徑，且這條路徑上所有弧的標(biāo)記符號連接成符號串α，則稱α為DFAM（接受）識別。DFAM所接受的語言為：L(M)={α

6、f(S,α)=Sn,Sn∈Z}DFAM所能接受的符號串的全體記為L(M)若M的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的ε通路，則ε為M所識別。Compiler編譯原

7、理Wednesday,March13,2013δ（0，abaab）=δ（1，baab）=δ（2，aab）=δ（1，ab）=δ（3，b）=3(接受)DFA的狀態(tài)圖表示：1032aabba,bbaδ（0，abab）=δ（1，bab）=δ（2，ab）=δ（1，b）=2(拒絕)對于符號串a(chǎn)baab對于符號串a(chǎn)babCompiler編譯原理Wednesday,March13,2013f是一個(gè)多值函數(shù)，是從Q×Σ*到Q的子集的映射：f：Q×Σ→2Q其中2Q是Q的冪集，即Q中所有子集組成的集合。2.不確定的有窮自動(dòng)機(jī)（NFA）M=(Σ,Q,f,S,

8、Z)有窮自動(dòng)機(jī)的不確定性表現(xiàn)在在某個(gè)狀態(tài)下，對于某個(gè)輸入字符存在多個(gè)后繼狀態(tài)，即狀態(tài)的轉(zhuǎn)向是不確定的Compiler編譯原理Wednesday,March13,2013例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})符號狀態(tài)εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦCompiler編譯原理Wednesday,March13,2013對于Σ*上的任何符號串α，若存在一條從某一初態(tài)到某一終態(tài)的通路，且該通路上所有弧的標(biāo)記字符依次連接成的串等于α，則稱α可以被NFAN所識別或接受。若N

9、的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的ε通路，則ε為N所識別。NFAN所能識別的符號串的全體記為L(N)，稱為NFAN所識別的語言Compiler編譯原理Wednesday,March13