詞法分析-詞法分析器的作用課件

第三章詞法分析南京大學(xué)計(jì)算機(jī)系2009年2月1感謝你的觀看2019年8月28內(nèi)容詞法分析器的作用詞法單元的規(guī)約詞法單元的識(shí)別詞法分析器生成工具Lex有窮自動(dòng)機(jī)從正則表達(dá)式到自動(dòng)機(jī)詞法分析器生成工具的設(shè)計(jì)方法2感謝你的觀看2019年8月28詞法分析器的作用讀入源程序字符流、組成詞素，輸出詞法單元序列。過濾空白、換行、制表符、注釋等。將詞素添加到符號表中。在邏輯上獨(dú)立于語法分析，但是通常和語法分析器處于同一趟中3感謝你的觀看2019年8月28為什么要設(shè)立獨(dú)立的詞法分析器簡化編譯器的設(shè)計(jì)詞法分析器可以首先完成一些簡單的處理工作。提高編譯器效率相對于語法分析，詞法分析過程簡單，可高效實(shí)現(xiàn)。（下推自動(dòng)機(jī)vs有窮自動(dòng)機(jī)）增強(qiáng)編譯器的可移植性4感謝你的觀看2019年8月28詞法單元、模式、詞素詞法單元<詞法單元名、屬性值（可選）>單元名是表示詞法單位種類的抽象符號；語法分析器通過單元名即可確定詞法單元序列的結(jié)構(gòu)。屬性值通常用于語義分析之后的階段模式描述了一類詞法單元的詞素可能具有的形式詞素源程序中的字符序列它和某個(gè)詞法單元的模式匹配，被詞法分析器識(shí)別為該詞法單元的實(shí)例。5感謝你的觀看2019年8月28詞法單元、模式、詞素（例子）printf(“Total=%d\n”,score)；printf,score和標(biāo)識(shí)符（id）的模式匹配“Total=%d\n”和literal的模式匹配6感謝你的觀看2019年8月28詞法單元的屬性一個(gè)模式匹配多個(gè)詞素時(shí)，必須通過屬性來傳遞附加的信息。屬性值將被用于語義分析、代碼生成等階段。不同的目的需要不同的屬性。因此，屬性值通常是一個(gè)結(jié)構(gòu)化數(shù)據(jù)。詞法單元id的屬性詞素、類型、第一次出現(xiàn)的位置、…7感謝你的觀看2019年8月28內(nèi)容詞法分析器的作用詞法單元的規(guī)約詞法單元的識(shí)別詞法分析器生成工具Lex有窮自動(dòng)機(jī)從正則表達(dá)式到自動(dòng)機(jī)詞法分析器生成工具的設(shè)計(jì)方法8感謝你的觀看2019年8月28詞法單元的規(guī)約正則表達(dá)式可以高效、簡潔地描述處理詞法單元時(shí)用到的模式類型。內(nèi)容串和語言語言上的運(yùn)算正則表達(dá)式正則定義正則表達(dá)式的擴(kuò)展9感謝你的觀看2019年8月28串和語言（1）字母表（alphabet）：一個(gè)有窮的符號集合。符號典型例子：字母、數(shù)位、標(biāo)點(diǎn)符號。例子：{0,1}；ASCII；Unicode在理論上，我們可以把任意的有限集合看作字母表。字母表上的串（string）是該字母表中符號的有窮序列。串s的長度，即|s|，是指s中符號出現(xiàn)的次數(shù)；空串：長度為0的串，ε語言（language）是某個(gè)給定字母表上的串的可數(shù)集合。10感謝你的觀看2019年8月28串和語言（2）和串有關(guān)的術(shù)語（bannana）前綴：從串的尾部刪除0個(gè)或多個(gè)符號后得到的串。（ban、banana、ε）后綴：從串的開始處刪除0個(gè)或多個(gè)符號后得到的串。（nana、banana、ε）子串：刪除串的某個(gè)前綴和某個(gè)后綴得到的串。（banana、nan、ε）真前綴、真后綴、真子串：既不等于原串，也不等于空串的前綴、后綴、子串。（前面例子的紅色部分）子序列：從原串中刪除0個(gè)或者多個(gè)符號后得到的串。（baan）11感謝你的觀看2019年8月28串和語言（3）串的運(yùn)算連接(concatenation)：x和y的連接時(shí)把y附加到x的后面形成的串，記作xy。x=dog，y=house，xy=doghouse指數(shù)運(yùn)算（冪運(yùn)算）：s0=ε，s1=s，si=si-1s；x=dog，x0=ε，x1=dog，x3=dogdogdog12感謝你的觀看2019年8月28串和語言（4）語言的運(yùn)算13感謝你的觀看2019年8月28串和語言（5）例子L={A,B,……,Z,a,b,……,z}D={0,1,……,9}LUD={A,B,……,Z,a,b,……,z,0,1,……,9}LD：520個(gè)長度為2的串的集合L4：所有由四個(gè)字母構(gòu)成的串的集合L*：所有字母構(gòu)成的集合，包括ε。L(LUD)，D+14感謝你的觀看2019年8月28正則表達(dá)式字母表Σ上的正則表達(dá)式的定義基本部分ε是一個(gè)正則表達(dá)式，L(ε)={ε}如果a是Σ上的一個(gè)符號，那么a是正則表達(dá)式，L(a)={a}歸納步驟：選擇：(r)|(s)，L((r)|(s))=L(r)UL(s)；連接：(r)(s)，L((r)(s))=L(r)L(s)；閉包：(r)*，L((r)*)=(L(r))*；括號：(r)，L((r))=L(r)運(yùn)算的優(yōu)先級：*>連接>|正則集合：可以用一個(gè)正則表達(dá)式定義的語言15感謝你的觀看2019年8月28正則表達(dá)式的例子Σ={a,b}L(a|b)

=

{a,b}L((a|b)(a|b))

=

{aa,ab,ba,bb}L(a*)={ε,a,aa,aaa,aaaa,……}L((a|b)*)={ε,a,b,aa,ab,ba,bb,aaa,aab,……}L(a|a*b)={a,b,ab,aab,aaab,…}16感謝你的觀看2019年8月28正則集合、等價(jià)如果L(r)=L(s)，正則表達(dá)式r和s等價(jià)。17感謝你的觀看2019年8月28正則定義（1）為了書寫方便，可以給正則表達(dá)式命名，且可以通過名字使用正則表達(dá)式正則定義是如下形式的定義序列 d1

r1 d2r2 ……

dnrn其中：di不在Σ中，且各不相同每個(gè)ri是字母表Σ

U

{d1,d2,…,di-1}上的正則表達(dá)式。這保證了不會(huì)出現(xiàn)遞歸定義。18感謝你的觀看2019年8月28正則定義（2）各個(gè)di的Σ上的正則表達(dá)式如下：d1的正則表達(dá)式即r1。將r2中的d1替換為r1，得到d2的正則表達(dá)式?！瓕i中的d1,d2,…,di-1替換為各自的正則表達(dá)式，得到di的正則表達(dá)式。注意：替換的時(shí)候不能破壞替換進(jìn)去的di的完整性。19感謝你的觀看2019年8月28正則定義的例子C語言標(biāo)識(shí)符的正則定義letter_

A|B|…|Z|a|b|…|z|_digit0|1|…|9idletter_(letter_|digit)*id對應(yīng)的正則表達(dá)式為(A|B|…|Z|a|b|…|z|_)((A|B|…|Z|a|b|…|z|_)|(0|1|…|9))*20感謝你的觀看2019年8月28正則表達(dá)式的擴(kuò)展基本運(yùn)算符：并、連接、Kleen閉包擴(kuò)展的運(yùn)算符：一個(gè)或多個(gè)實(shí)例：單目后綴+r+等價(jià)于rr*零個(gè)或一個(gè)實(shí)例：？r?等價(jià)于ε|r字符類[a1a2…an]等價(jià)于a1|a2|…|an[a-e]等價(jià)于a|b|c|d|e使正則表達(dá)式更加簡潔，但不會(huì)使正則表達(dá)式的描述能力增強(qiáng)21感謝你的觀看2019年8月28內(nèi)容詞法分析器的作用詞法單元的規(guī)約詞法單元的識(shí)別詞法分析器生成工具Lex有窮自動(dòng)機(jī)從正則表達(dá)式到自動(dòng)機(jī)詞法分析器生成工具的設(shè)計(jì)方法22感謝你的觀看2019年8月28詞法單元的識(shí)別詞法分析器要求能夠檢查輸入字符串，在前綴中找出和某個(gè)模式匹配的詞素。首先通過正則定義來描述各種詞法單元的模式。定義ws(blank|tab|newline)+來消除空白詞法分析器識(shí)別到這個(gè)模式時(shí)，不返回詞法單元，繼續(xù)識(shí)別其它模式。23感謝你的觀看2019年8月2824感謝你的觀看2019年8月28狀態(tài)轉(zhuǎn)換圖詞法分析器的重要組件之一狀態(tài)轉(zhuǎn)換圖(transitiondiagram)狀態(tài)(state)：表示在識(shí)別詞素時(shí)可能出現(xiàn)的情況狀態(tài)看作是已處理部分的總結(jié)。某些狀態(tài)為接受狀態(tài)或最終狀態(tài)，表明已找到詞素。加上*的接受狀態(tài)表示最后讀入的符號不在詞素中。開始狀態(tài)（初始狀態(tài)）：用start邊表示。邊(edge)：從一個(gè)狀態(tài)指向另一個(gè)狀態(tài)；邊的標(biāo)號是一個(gè)或多個(gè)符號。當(dāng)前符號為s，下一個(gè)輸入符號為a，就沿著從s離開，標(biāo)號為a的邊到達(dá)下一個(gè)狀態(tài)。25感謝你的觀看2019年8月28狀態(tài)轉(zhuǎn)換圖的例子26感謝你的觀看2019年8月28保留字和標(biāo)識(shí)符的識(shí)別在很多時(shí)候，保留字也符合標(biāo)識(shí)符的模式，識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖也會(huì)識(shí)別保留字。解決方法在符號表中預(yù)先填寫保留字，并指明它們不是普通標(biāo)識(shí)符。為關(guān)鍵字/保留字建立獨(dú)立的、高優(yōu)先級的狀態(tài)轉(zhuǎn)換圖。27感謝你的觀看2019年8月28其它的狀態(tài)轉(zhuǎn)換圖28感謝你的觀看2019年8月28詞法分析器的體系結(jié)構(gòu)從轉(zhuǎn)換圖構(gòu)造詞法分析器的方法變量state記錄當(dāng)前狀態(tài)一個(gè)switch根據(jù)state的值轉(zhuǎn)到相應(yīng)的代碼每個(gè)狀態(tài)對應(yīng)于一段代碼。這段代碼根據(jù)讀入的符號，確定下一個(gè)狀態(tài)如果找不到相應(yīng)的邊，則調(diào)用fail()進(jìn)行錯(cuò)誤恢復(fù)進(jìn)入某個(gè)接受狀態(tài)時(shí)，返回相應(yīng)的詞法單元。注意狀態(tài)有*標(biāo)記時(shí)，需要回退forward指針。實(shí)際是模擬轉(zhuǎn)換圖的運(yùn)行29感謝你的觀看2019年8月28Relop對應(yīng)的代碼概要30感謝你的觀看2019年8月28處理多個(gè)模式的方法詞法分析器需要匹配多個(gè)模式解決方法按照優(yōu)先級，順序地嘗試各個(gè)狀態(tài)轉(zhuǎn)換圖。如果引發(fā)fail()，回退并嘗試下一個(gè)狀態(tài)圖。更好的方法：“并行地”運(yùn)行各個(gè)狀態(tài)轉(zhuǎn)換圖。通過greedy策略，識(shí)別最長的和某個(gè)模式匹配的輸入前綴實(shí)際使用的方法：預(yù)先把各個(gè)狀態(tài)轉(zhuǎn)換圖合成一個(gè)狀態(tài)轉(zhuǎn)換圖，然后運(yùn)行這個(gè)狀態(tài)轉(zhuǎn)換圖。31感謝你的觀看2019年8月28內(nèi)容詞法分析器的作用詞法單元的規(guī)約詞法單元的識(shí)別詞法分析器生成工具Lex有窮自動(dòng)機(jī)從正則表達(dá)式到自動(dòng)機(jī)詞法分析器生成工具的設(shè)計(jì)方法32感謝你的觀看2019年8月28詞法分析工具Lex/FlexLex/Flex是一個(gè)有用的詞法分析器生成工具通常和Yacc一起使用，生成編譯器的前端33感謝你的觀看2019年8月28Lex源程序的結(jié)構(gòu)聲明部分包含：明示常量：表示常數(shù)的標(biāo)識(shí)符正則定義轉(zhuǎn)換規(guī)則模式{動(dòng)作}模式是正則表達(dá)式動(dòng)作表示識(shí)別到相應(yīng)模式時(shí)采取的處理方式。輔助函數(shù)各個(gè)動(dòng)作中使用的函數(shù)

聲明部分 %%

轉(zhuǎn)換規(guī)則 %%

輔助函數(shù)Lex程序的形式34感謝你的觀看2019年8月28詞法分析器的工作方式Lex生成的詞法分析器作為一個(gè)函數(shù)被調(diào)用；在每次調(diào)用過程中，不斷讀入余下的輸入符號發(fā)現(xiàn)最長的、與某個(gè)模式匹配的輸入前綴時(shí)，調(diào)用相應(yīng)的動(dòng)作；該動(dòng)作進(jìn)行相關(guān)處理，并把控制返回；如果不返回，則詞法分析器繼續(xù)尋找其它詞素。35感謝你的觀看2019年8月28Lex程序的例子（1）%{和}%之間的內(nèi)容一般被直接拷貝到lex.yy.c中；這里的內(nèi)容就是一段注釋；LT，LE等的值在yacc源程序中定義正則定義分隔聲明部分和轉(zhuǎn)換規(guī)則部分。36感謝你的觀看2019年8月28Lex程序的例子（2）沒有返回，表示繼續(xù)識(shí)別其它詞法單元把識(shí)別到的標(biāo)識(shí)符加入標(biāo)識(shí)符表識(shí)別到數(shù)字常量，加入常量表37感謝你的觀看2019年8月28Lex程序的例子（3）Lex處理源程序時(shí)，輔助函數(shù)被直接拷貝到lex.yy.c中輔助函數(shù)可在規(guī)則中直接調(diào)用38感謝你的觀看2019年8月28Lex中的沖突解決方法沖突：多個(gè)輸入前綴與某個(gè)模式相匹配，或者一個(gè)前綴和多個(gè)模式匹配Lex解決沖突的方法多個(gè)前綴可能匹配時(shí)，選擇最長的前綴保證詞法分析器把<=當(dāng)作一個(gè)詞法單元識(shí)別某個(gè)前綴和多個(gè)模式匹配時(shí)，選擇列在前面的模式如果保留字的規(guī)則在標(biāo)識(shí)符的規(guī)則之前，詞法分析器將識(shí)別出保留字39感謝你的觀看2019年8月28有窮自動(dòng)機(jī)本質(zhì)上和狀態(tài)轉(zhuǎn)換圖相同區(qū)別有窮自動(dòng)機(jī)只回答Yes/No區(qū)分為兩類：不確定的有窮自動(dòng)機(jī)（NondeterministicFiniteAutomata,NFA）：邊上的標(biāo)號沒有限制，一個(gè)符號可出現(xiàn)在離開同一個(gè)狀態(tài)的多條邊上，ε可以做標(biāo)號確定的有窮自動(dòng)機(jī)（DeterministicFiniteAutomata,DFA）對于每個(gè)狀態(tài)以及每個(gè)符號，有且只有一條邊（某些地方是說：最多只有一條邊）。兩種自動(dòng)機(jī)都識(shí)別正則語言，即對于每個(gè)可以用正則表達(dá)式描述的語言，就可以用某個(gè)NFA或者DFA來識(shí)別；反之亦然40感謝你的觀看2019年8月28不確定的有窮自動(dòng)機(jī)NFA的定義一個(gè)有窮的狀態(tài)集合S一個(gè)輸入符號集合Σ（inputalphabet）轉(zhuǎn)換函數(shù)（transitionfunction）對于每個(gè)狀態(tài)和Σ

U{ε}中的符號，給出相應(yīng)的后繼狀態(tài)集合S中的某個(gè)狀態(tài)s0被指定為開始狀態(tài)/初始狀態(tài)（有些定義中可以有多個(gè)開始狀態(tài)）S的一個(gè)子集被指定為接受狀態(tài)41感謝你的觀看2019年8月28NFA的例子狀態(tài)集合S={0,1,2,3}開始狀態(tài)0接受狀態(tài)集合{3}轉(zhuǎn)換函數(shù)：(0,a){0,1}(0,b){0}(1,b)2(2,b)3相應(yīng)的圖形表示42感謝你的觀看2019年8月28轉(zhuǎn)換表（transitiontable）表示法用二維表表示NFA的轉(zhuǎn)換函數(shù)每行對應(yīng)于一個(gè)狀態(tài)，每列對應(yīng)于一個(gè)輸入符號或者ε。每個(gè)條目表示對應(yīng)的后繼狀態(tài)集合轉(zhuǎn)換表表示法43感謝你的觀看2019年8月28輸入字符串的接受一個(gè)NFA接受輸入字符串x，當(dāng)且僅當(dāng)對應(yīng)的轉(zhuǎn)換圖中存在一條從開始狀態(tài)到某個(gè)接受狀態(tài)的路徑，該路徑中各條邊上的標(biāo)號按順序組成x（不含ε標(biāo)號）。前面的NFA接受aabb，因?yàn)椋篘FA接受的語言：從開始狀態(tài)到達(dá)接受狀態(tài)的所有路徑的標(biāo)號串的集合。即：該NFA接受的所有符號串的集合44感謝你的觀看2019年8月28NFA和相應(yīng)語言的例子相應(yīng)的語言：L(aa*|bb*)45感謝你的觀看2019年8月28確定有窮自動(dòng)機(jī)（DFA）一個(gè)NFA被稱為DFA，如果沒有標(biāo)號為ε的轉(zhuǎn)換對于每個(gè)狀態(tài)s和每個(gè)輸入符號a，有且僅有一條標(biāo)號為a的離開s的邊可以高效判斷一個(gè)串能否被一個(gè)DFA接受。每個(gè)NFA都有一個(gè)等價(jià)的DFA。46感謝你的觀看2019年8月28DFA的模擬運(yùn)行假設(shè)輸入符號就是字符；Nextchar讀入下一個(gè)字符（符號）move給出了離開s，標(biāo)號為c的邊的目標(biāo)狀態(tài)47感謝你的觀看2019年8月28DFA的例子假設(shè)輸入為ababb，那么進(jìn)入的狀態(tài)序列為0,1,2,1,2,348感謝你的觀看2019年8月28從正則表達(dá)式到自動(dòng)機(jī)的轉(zhuǎn)換正則表達(dá)式可以簡潔、精確地描述詞法單元的模式模擬DFA的執(zhí)行可以高效地進(jìn)行模式匹配將正則表達(dá)式轉(zhuǎn)換為DFA的步驟：正則表達(dá)式到NFANFA到DFA49感謝你的觀看2019年8月28NFA到DFA（子集構(gòu)造法）(1)基本思想：構(gòu)造得到的DFA的每個(gè)狀態(tài)和NFA的狀態(tài)子集對應(yīng)DFA讀入a1,a2,…,an后到達(dá)的狀態(tài)對應(yīng)于從NFA開始狀態(tài)出發(fā)沿著a1,a2,…,an可能到達(dá)的狀態(tài)集合。在算法中“并行地模擬”NFA在遇到一個(gè)給定輸入串時(shí)可能執(zhí)行的所有動(dòng)作。50感謝你的觀看2019年8月28例子假設(shè)考慮上面的NFA能夠接受串babb考慮從開始狀態(tài)出發(fā)，沿著標(biāo)號分別為b，ba，bab，babb能到達(dá)的可能狀態(tài)的集合51感謝你的觀看2019年8月28NFA到DFA（子集構(gòu)造法）(2)理論上，最壞情況下DFA的狀態(tài)個(gè)數(shù)會(huì)是NFA狀態(tài)個(gè)數(shù)的指數(shù)多個(gè)。但是對于大部分應(yīng)用，NFA和相應(yīng)的DFA的狀態(tài)數(shù)量大致相同。52感謝你的觀看2019年8月28NFA到DFA（子集構(gòu)造法）(3)算法中使用到的基本操作ε–closure(s)：能夠從NFA狀態(tài)開始，只通過ε轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合ε–closure(T)：能夠從T中某個(gè)狀態(tài)開始，只通過ε轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合move(T,a)：能夠從T中某個(gè)狀態(tài)s出發(fā)，通過一個(gè)標(biāo)號為a的轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合。53感謝你的觀看2019年8月28NFA到DFA（子集構(gòu)造法）(4)這個(gè)算法實(shí)際上是一個(gè)搜索過程；Dstates中的一個(gè)狀態(tài)未加標(biāo)記表示還沒有搜索過它的各個(gè)后繼。54感謝你的觀看2019年8月28NFA到DFA（子集構(gòu)造法）(5)計(jì)算ε–closure(T)的算法實(shí)際上是一個(gè)圖搜索過程（只考慮ε-標(biāo)號邊）。55感謝你的觀看2019年8月28子集構(gòu)造法的例子（1）A：=ε–closure(0)={0,1,2,4,7}B：Dtran[A,a]=ε–closure(move(A,a))=ε–closure({3,8})={1,2,3,4,6,7,8}C：Dtran[A,b]=ε–closure(move(A,b))=ε–closure({5})={1,2,4,5,6,7}D：Dtran[B,b]=ε–closure(move(B,b))=

{1,2,4,5,6,7,9}…56感謝你的觀看2019年8月28子集構(gòu)造法的例子（2）57感謝你的觀看2019年8月28正則表達(dá)式到NFA基本思想根據(jù)正則表達(dá)式的遞歸定義，按照正則表達(dá)式的結(jié)構(gòu)遞歸地構(gòu)造出相應(yīng)的NFA。算法分成兩個(gè)部分：基本規(guī)則處理ε和單符號的情況對于每個(gè)正則表達(dá)式的運(yùn)算，建立組合相應(yīng)NFA的方法。58感謝你的觀看2019年8月28轉(zhuǎn)換算法（1）基本規(guī)則部分表達(dá)式ε表達(dá)式a59感謝你的觀看2019年8月28轉(zhuǎn)換算法（2）歸納部分s|rsr60感謝你的觀看2019年8月28轉(zhuǎn)換算法（3）歸納部分s*61感謝你的觀看2019年8月28轉(zhuǎn)換得到的NFA的特性狀態(tài)數(shù)量最多為r中的運(yùn)算符和運(yùn)算符分量總數(shù)的兩倍因?yàn)槊總€(gè)步驟只引入兩個(gè)狀態(tài)有且只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài)除接受狀態(tài)之外，每個(gè)狀態(tài)要么有一條標(biāo)號不等于ε的出邊，要么有兩條標(biāo)號為ε的出邊。62感謝你的觀看2019年8月28正則表達(dá)式到NFA的例子（1）正則表達(dá)式(a|b)*abb第一個(gè)a對應(yīng)的NFA第一個(gè)b對應(yīng)的NFA63感謝你的觀看2019年8月28正則表達(dá)式到NFA的例子（2）(a|b)的NFA第二個(gè)a的NFA64感謝你的觀看2019年8月28正則表達(dá)式到NFA的例子（3）(a|b)*的NFA65感謝你的觀看2019年8月28詞法分析器生成工具的設(shè)計(jì)體系結(jié)構(gòu)66感謝你的觀看2019年8月28詞法分析器生成工具的功能生成的詞法分析器中包含一個(gè)模擬有窮自動(dòng)機(jī)的模塊其余部分由生成工具根據(jù)詞法規(guī)則的描述自動(dòng)生成，包括自動(dòng)機(jī)的轉(zhuǎn)換表和動(dòng)作相關(guān)的代碼，適當(dāng)?shù)臅r(shí)候由模擬器調(diào)用。構(gòu)造自動(dòng)機(jī)時(shí)首先構(gòu)造出各個(gè)模式對應(yīng)的NFA然后將這些NFA合并成為一個(gè)NFA（根據(jù)需要）進(jìn)行確定化67感謝你的觀看2019年8月28NFA合并的方法合并方法：引入新的開始狀態(tài)，并引入從這個(gè)開始狀態(tài)到各個(gè)原開始狀態(tài)的ε轉(zhuǎn)換。得到的NFA所接受的語言是原來各個(gè)NFA的語言的并集。不同的接受狀態(tài)可代表不同的模式。不僅判斷輸入前綴是否NFA的語言，還需要知道對應(yīng)于哪個(gè)模式68感謝你的觀看2019年8月28確定化NFA后的處理對得到的NFA進(jìn)行確定化，得到DFA。一個(gè)DFA的接受狀態(tài)對應(yīng)于NFA狀態(tài)的集合，其中至少包括一個(gè)NFA接受狀態(tài)如果其中包括多個(gè)對應(yīng)于不同模式的NFA接受狀態(tài)，則表示當(dāng)前的輸入前綴對應(yīng)于多個(gè)模式，存在沖突。找出第一個(gè)這樣的模式，將這個(gè)模式作為這個(gè)DFA接受狀態(tài)的輸出。69感謝你的觀看2019年8月28例子（1）假設(shè)有三個(gè)模式a{A1}abb{A2}a*b+{A3}構(gòu)造各模式的NFA如右70感謝你的觀看2019年8月28例子（2）合并NFA2：模式16：模式28：模式371感謝你的觀看2019年8月28例子（3）確定化得到如下DFADFA狀態(tài)68對應(yīng)NFA狀態(tài)集合{6,8}，對應(yīng)的模式是abb（第二個(gè)模式），而不是a*b+（第三個(gè)模式）72感謝你的觀看2019年8月28運(yùn)行的方式模擬DFA，不斷讀入輸入字符串中的字符直到某一時(shí)刻沒有后繼為止（不是到達(dá)某個(gè)接受狀態(tài)）注意：根據(jù)本教材的定義，DFA總是有后繼的。這里是指DFA進(jìn)入了死狀態(tài)，即永遠(yuǎn)不可能到達(dá)接受狀態(tài)的狀態(tài)。這樣可以找到最長可能的詞素?；仡^查找最后的接受狀態(tài)，執(zhí)行相應(yīng)的動(dòng)作。如果查不到，報(bào)詞法錯(cuò)在回退時(shí)，需要同時(shí)回退讀入的字符73感謝你的觀看2019年8月28DFA狀態(tài)數(shù)量的最小化一個(gè)正則語言可對應(yīng)于多個(gè)識(shí)別此語言的DFA。通過DFA的最小化可得到狀態(tài)數(shù)量最少的DFA（不計(jì)同構(gòu)，這樣的DFA是唯一的）。兩個(gè)等價(jià)的DFA：都識(shí)別(a|b)*abb74感謝你的觀看2019年8月28狀態(tài)的區(qū)分基本思想是合并等價(jià)的狀態(tài)。狀態(tài)的可區(qū)分如果存在串x，使得從狀態(tài)s1和s2，一個(gè)到達(dá)接受狀態(tài)而另一個(gè)到達(dá)非接受狀態(tài)，那么x就區(qū)分了s1和s2如果存在某個(gè)串區(qū)分了s和t，我們說s和t就是可區(qū)分的；否則s和t就是不可區(qū)分的。不可區(qū)分的兩個(gè)狀態(tài)就是等價(jià)的，可以合并空串區(qū)分了E和其它狀態(tài)bb區(qū)分了A和B注意：上面定義中使用的DFA中，