詞法分析江西師大計(jì)算機(jī)課件

1、1第三章第三章 詞法分析詞法分析 3.1 詞法分析器的作用詞法分析器的作用 3.2 詞法單元的規(guī)約詞法單元的規(guī)約 3.3 詞法單元的識別詞法單元的識別 3.5 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 3.6 從正則表達(dá)式到自動(dòng)機(jī)從正則表達(dá)式到自動(dòng)機(jī)23.1 詞法分析詞法分析l主要任務(wù)主要任務(wù)是讀入源程序的輸入字符、將是讀入源程序的輸入字符、將它們組成它們組成單詞單詞，生成并輸出一個(gè)，生成并輸出一個(gè)詞法單元詞法單元序列，每個(gè)詞法單元對應(yīng)于一個(gè)序列，每個(gè)詞法單元對應(yīng)于一個(gè)單詞單詞。詞法分析程序的其他任務(wù)詞法分析程序的其他任務(wù)：濾掉空格，跳過注釋、換行符濾掉空格，跳過注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，追蹤換行

2、標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開，宏展開，3 詞法單元詞法單元由一個(gè)詞法單元名和一個(gè)可選由一個(gè)詞法單元名和一個(gè)可選的屬性值組成。的屬性值組成。 模式模式描述了一個(gè)詞法單元的描述了一個(gè)詞法單元的單詞單詞可能具可能具有形式。有形式。 單詞單詞是源程序中的一個(gè)字符序列，它和是源程序中的一個(gè)字符序列，它和某個(gè)詞法單元的模式匹配，并被詞法分某個(gè)詞法單元的模式匹配，并被詞法分析器識別為該詞法單元的一個(gè)實(shí)例。析器識別為該詞法單元的一個(gè)實(shí)例。包括保留字、標(biāo)識符、運(yùn)包括保留字、標(biāo)識符、運(yùn)算符、標(biāo)點(diǎn)符號和常量等。算符、標(biāo)點(diǎn)符號和常量等。4 詞法分析器通常還要和詞法分析器通常還要和符號表符號表進(jìn)行交互。進(jìn)行交互。當(dāng)詞法

3、分析器發(fā)現(xiàn)了一個(gè)標(biāo)識符的當(dāng)詞法分析器發(fā)現(xiàn)了一個(gè)標(biāo)識符的單詞單詞時(shí)，它將此時(shí)，它將此單詞單詞添加到符號表中。添加到符號表中。 在某種情況下，詞法分析器會(huì)從符號表在某種情況下，詞法分析器會(huì)從符號表中讀取有關(guān)標(biāo)識符種類的信息，以確定中讀取有關(guān)標(biāo)識符種類的信息，以確定向語法分析器傳送哪個(gè)詞法單元。向語法分析器傳送哪個(gè)詞法單元。5 符號表符號表：是一種供編譯器用于保存有關(guān)：是一種供編譯器用于保存有關(guān)源程序構(gòu)造的各種信息的數(shù)據(jù)結(jié)構(gòu)。源程序構(gòu)造的各種信息的數(shù)據(jù)結(jié)構(gòu)。 這些信息在編譯器的分析階段被逐步收這些信息在編譯器的分析階段被逐步收集并放入符號表，它們在綜合階段用于集并放入符號表，它們在綜合階段用于生成目

4、標(biāo)代碼。生成目標(biāo)代碼。 符號表的每個(gè)條目中包含與一個(gè)標(biāo)識符符號表的每個(gè)條目中包含與一個(gè)標(biāo)識符相關(guān)的信息，比如它們的字符串，類型、相關(guān)的信息，比如它們的字符串，類型、存儲(chǔ)位置和其他相關(guān)信息。存儲(chǔ)位置和其他相關(guān)信息。67 詞法分析是編譯過程中的一個(gè)階段，詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行在語法分析前進(jìn)行 。也可以和語法分。也可以和語法分析結(jié)合在一起作為一遍，由語法分析析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前程序調(diào)用詞法分析程序來獲得當(dāng)前單詞單詞供語法分析使用。供語法分析使用。8 單詞單詞的描述工具的描述工具-正則表達(dá)式正則表達(dá)式 單詞單詞的識別系統(tǒng)的識別系統(tǒng)-有

5、窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 設(shè)計(jì)詞法分析程序設(shè)計(jì)詞法分析程序93.2 詞法單元的規(guī)約詞法單元的規(guī)約 串和語言串和語言 字母表：一個(gè)有限的符號集合。字母表：一個(gè)有限的符號集合。 串：是該字母表中符號的一個(gè)有窮序列。串：是該字母表中符號的一個(gè)有窮序列。 語言：是某個(gè)給定字母表上一個(gè)任意的可數(shù)語言：是某個(gè)給定字母表上一個(gè)任意的可數(shù)的串集合。的串集合。 空集空集 和僅包含空串的集合和僅包含空串的集合 都是語言。都是語言。10串的相關(guān)術(shù)語串的相關(guān)術(shù)語 串串s的長度：記為的長度：記為|s|,指指s中符號出現(xiàn)的中符號出現(xiàn)的次數(shù)。次數(shù)。 串串s的前綴：從的前綴：從s的尾部刪除的尾部刪除0個(gè)或多個(gè)個(gè)或多個(gè)符號后得到的串

6、。符號后得到的串。 串串s的后綴：從的后綴：從s的開始刪除的開始刪除0個(gè)或多個(gè)個(gè)或多個(gè)符號后得到的串。符號后得到的串。 串串s的子串：刪除的子串：刪除s的某個(gè)前綴和某個(gè)后的某個(gè)前綴和某個(gè)后綴之后得到的串。綴之后得到的串。11 串s的真前綴、真后綴、真子串分別是的真前綴、真后綴、真子串分別是s的既不等于的既不等于 ，也不等于，也不等于s本身的前綴、本身的前綴、后綴和子串。后綴和子串。 串串s的子序列：從的子序列：從s中刪除中刪除0個(gè)或多個(gè)符號個(gè)或多個(gè)符號后得到的串，這些被刪除的符號可能不后得到的串，這些被刪除的符號可能不相鄰。如：相鄰。如：baan是是banana的一個(gè)子序列。的一個(gè)子序列。12

7、相關(guān)運(yùn)算相關(guān)運(yùn)算 串的連接運(yùn)算串的連接運(yùn)算:xy 空串是連接運(yùn)算的單位元：空串是連接運(yùn)算的單位元： 符號串集合的乘積：符號串集合的乘積： 例：符號串集合例：符號串集合A=ab,aa;B=ba,bb; 乘積乘積AB=abba,abbb,aaba,aabbsss,|ByAxxyAB13例：x=ab abababxababxabxx3210,串的方冪運(yùn)算：串的方冪運(yùn)算：ss，sisii100,并且對依此類推,321sssssssss例：A=a,b,cd,B=bc,ad,則,cdadcdbcbadbbcaadabcAB 14（自反）閉包：（自反）閉包：*稱為稱為的閉包，若的閉包，若*表示表示上上的所有

8、有窮長的串的集合，可表示為：（其中用的所有有窮長的串的集合，可表示為：（其中用U代表邏輯代表邏輯或或運(yùn)算）運(yùn)算）正閉包：正閉包：+稱為的稱為的正閉包，可表示為正閉包，可表示為 2* 32*例：例： =a,b+=a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,. *= U +15語言是由句子組成的集合，是由一組符語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。字母表號所構(gòu)成的集合。字母表上的一個(gè)語上的一個(gè)語言是言是上的一些符號串的集合上的一些符號串的集合 (字母表字母表上的每個(gè)語言是上的每個(gè)語言是* 的一個(gè)子集的一個(gè)子集)。 集合集合B=a,aa

9、,aaa, 是字母表是字母表上的一個(gè)語言上的一個(gè)語言或記作或記作w|w*且且w=an,n1 例：例： =a,b16有關(guān)語言的運(yùn)算有關(guān)語言的運(yùn)算是一個(gè)語言。是一個(gè)語言。 即即 是一個(gè)語言。是一個(gè)語言。 設(shè)設(shè)L是（是（上的）一個(gè)語言上的）一個(gè)語言,M是（是（上的）一個(gè)語言，上的）一個(gè)語言，則語言則語言L和和M的并，交，差，補(bǔ)是一個(gè)語言。的并，交，差，補(bǔ)是一個(gè)語言。 A.語言語言L和和M的并表示為的并表示為 LM，是一個(gè)語言，是一個(gè)語言，滿，滿足足: w|w is in L or is in M 如：如： L1 =a,b,y,z M1 =1,28,9 L1M1 =a,b, y,z，1,28,9 17

10、 B.語言L和M的連接是一個(gè)語言，記為 LM=st |sL且 tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L C. L的n次連接Ln= LL.L D. 語言L的閉包記為 L* L* = L0 L1 L2 . L0= ， Ln = L Ln-1 = Ln-1 L,n118如：（L1M1）* =a,b, y,z，1,28,9 ，a,1a,xyz,6789st. E. 語言L的正閉包記為 L+， L+= L1 L2 L3 .L+ = LL* = L*L L* = L+ 19例令例令L表示字母表表示字母表A，B，,Z,a,b,z,令令D表示數(shù)位的字母表表示數(shù)位的字

11、母表0，1，9，也可把，也可把L和和D看成所有串長度為看成所有串長度為1的語言。的語言。 LUD是字母和數(shù)位的集合。也可是說是包是字母和數(shù)位的集合。也可是說是包含含62個(gè)長度為個(gè)長度為1的串組成的語言。的串組成的語言。 LD： L4： L*： L（LUD）*： D+：20有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FA）自動(dòng)機(jī)：按一定步驟識別每個(gè)字符的算法。自動(dòng)機(jī)：按一定步驟識別每個(gè)字符的算法。有窮自動(dòng)機(jī)作為一種識別裝置，它能準(zhǔn)確地識有窮自動(dòng)機(jī)作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)式所表示的集合別正規(guī)集，即識別正規(guī)式所表示的集合.應(yīng)用應(yīng)用有窮自動(dòng)機(jī)這個(gè)理論，為詞法分析程序的自動(dòng)有窮自動(dòng)機(jī)這個(gè)理論，為詞

12、法分析程序的自動(dòng)構(gòu)造尋找有效的方法和工具。構(gòu)造尋找有效的方法和工具。確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)DFADFA（P40P40）不確定有窮自動(dòng)機(jī)不確定有窮自動(dòng)機(jī)NFA NFA （P42P42）21確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFADFA定義：定義：一個(gè)確定的有窮自動(dòng)機(jī)（一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五是一個(gè)五元組：元組：M=（K，f，S，Z）其中）其中1.K1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；態(tài)；2.2.是一個(gè)有窮字母表，它的每個(gè)元素稱為是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號，所以也稱一個(gè)輸入符號，所以也稱為輸入符號表；為輸入符號表

13、；22DFA定義3.3.f是轉(zhuǎn)換函數(shù)，是在是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，上的映射，即，如如 f（ki，a）=kj，（，（kiK，kjK）就就意味著，當(dāng)前狀態(tài)為意味著，當(dāng)前狀態(tài)為ki，輸入符為，輸入符為a時(shí)，將轉(zhuǎn)時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)換為下一個(gè)狀態(tài)kj，我們把，我們把kj稱作稱作k ki的一個(gè)后的一個(gè)后繼狀態(tài)；繼狀態(tài)；4.SKK是唯一的一個(gè)初態(tài)；是唯一的一個(gè)初態(tài)；5.5.Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)?；蚪Y(jié)束狀態(tài)。23一個(gè)DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=Uf（V，a）=Uf（S，b

14、）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q24 DFA 的狀態(tài)圖表示l 一個(gè)一個(gè)DFA可以表示成一個(gè)狀態(tài)圖可以表示成一個(gè)狀態(tài)圖 (或稱狀或稱狀態(tài)轉(zhuǎn)換圖態(tài)轉(zhuǎn)換圖)。l假定假定DFA M含有含有m個(gè)狀態(tài)，個(gè)狀態(tài)，n個(gè)輸入字符；個(gè)輸入字符；l那么這個(gè)狀態(tài)圖含有那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有多有n個(gè)弧射出；個(gè)弧射出；l整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)；態(tài)結(jié)點(diǎn)；l初態(tài)結(jié)點(diǎn)冠以箭頭初態(tài)結(jié)點(diǎn)冠以箭頭“ ”；終態(tài)結(jié)點(diǎn)用雙；終態(tài)結(jié)點(diǎn)用雙圈表示；圈表示；l若若 f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)

15、，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)到狀態(tài)結(jié)點(diǎn)kj畫標(biāo)記為畫標(biāo)記為a的?。坏幕。?25狀態(tài)狀態(tài)轉(zhuǎn)換邊轉(zhuǎn)換邊接受接受(終止終止)狀態(tài)狀態(tài)開始狀態(tài)開始狀態(tài)26判斷字符串判斷字符串a(chǎn)baabb,babb是否是否能被接受？能被接受？27例例1:確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)dfa1表示所有正整數(shù)的集合。表示所有正整數(shù)的集合。 符號集符號集 = 0,1,2,.,9 ； 狀態(tài)集合狀態(tài)集合SS= S0 , S1 ； 開始狀態(tài)開始狀態(tài) S0； 轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) :SS SS； (S0 ,d) = S1, (S1 ,d)= S1，其中，其中d ； 終止終止(接受接受)狀態(tài)集狀態(tài)集: S1 ；dd 確定有窮自動(dòng)機(jī)確定有窮自

16、動(dòng)機(jī)dfa1的狀態(tài)轉(zhuǎn)換圖表示的狀態(tài)轉(zhuǎn)換圖表示S0S128例例2： 實(shí)數(shù)可表示為實(shí)數(shù)可表示為d1d2.dn . d1d2.dm 。dd.dd確定有限自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖確定有限自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖 2 10329例例3：接受第二個(gè)位置上的數(shù)字為：接受第二個(gè)位置上的數(shù)字為2的所有正整數(shù)的所有正整數(shù)的確定有窮自動(dòng)機(jī)的確定有窮自動(dòng)機(jī)dfa2(包括所有一位的包括所有一位的)。 d2d 圖圖 確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)dfa230例例3：考慮可帶下劃線的標(biāo)識符集：考慮可帶下劃線的標(biāo)識符集IDE， 其中其中L表示字母，表示字母，D表示數(shù)字。表示數(shù)字。 _L,DL,DL確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)dfa331DFA

17、 的矩陣表示的矩陣表示 一個(gè)一個(gè)DFA還可以用一個(gè)矩陣表示，該還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即下的新狀態(tài)，即k行行a列為列為f(k,a)的值。的值。abSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)3233不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA 一個(gè)不確定的有窮自動(dòng)機(jī)（一個(gè)不確定的有窮自動(dòng)機(jī)（NFA）M是一個(gè)五是一個(gè)五元組：元組：M=（K，f，S，Z） 有輸入有輸入 上的轉(zhuǎn)換動(dòng)作；上的轉(zhuǎn)換動(dòng)作；S1 S2 對每個(gè)狀態(tài)對每個(gè)狀態(tài)s和每個(gè)輸入符號和每個(gè)輸入符號

18、a,可以有多條標(biāo)可以有多條標(biāo)號為號為a的邊離開。的邊離開。S3 S1 S2aa3435有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)A所能接受的字符串集所能接受的字符串集L(A) L(A)=| S00 Si* ， Si* F特例：空字符串集特例：空字符串集36從從NFA到到DFA的轉(zhuǎn)換的轉(zhuǎn)換 DFA是是NFA的特例的特例.對每個(gè)對每個(gè)NFA N一定一定存在一個(gè)存在一個(gè)DFA ，使得，使得 L(M)=L(N)。對每個(gè)對每個(gè)NFA N存在著與之等價(jià)的存在著與之等價(jià)的DFA M。 有一種算法，將有一種算法，將NFA轉(zhuǎn)換成接受同樣語言轉(zhuǎn)換成接受同樣語言的的DFA.這種算法稱為這種算法稱為子集法子集法(造表法）造表法）. 與某一

19、與某一NFA等價(jià)的等價(jià)的DFA不唯一不唯一.37 空移環(huán)路的尋找和消除空移環(huán)路的尋找和消除3839 NFA到到DFA的構(gòu)造思想是該的構(gòu)造思想是該DFA的每一的每一個(gè)狀態(tài)對應(yīng)個(gè)狀態(tài)對應(yīng)NFA的一組狀態(tài)，該的一組狀態(tài)，該DFA使使用它的狀態(tài)去記錄在用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入讀入一個(gè)輸入符號后可能達(dá)到的所有狀態(tài)。符號后可能達(dá)到的所有狀態(tài)。40S表示表示N的單個(gè)狀態(tài)，而的單個(gè)狀態(tài)，而T表示表示N的一個(gè)狀態(tài)的一個(gè)狀態(tài)集集41 I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4

20、,5,6,7,8；12534687aaa42IaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb43 等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF4445最小化最小化DFA 從任意一個(gè)接受相同語言的從任意

21、一個(gè)接受相同語言的DFA出發(fā)，出發(fā)，通過分組合并等價(jià)的狀態(tài)，我們總是可通過分組合并等價(jià)的狀態(tài)，我們總是可以構(gòu)建得到這個(gè)狀態(tài)數(shù)最少的以構(gòu)建得到這個(gè)狀態(tài)數(shù)最少的DFA。 如果分別從狀態(tài)如果分別從狀態(tài)s和和t出發(fā)，沿著標(biāo)號為出發(fā)，沿著標(biāo)號為x的路徑到達(dá)的兩個(gè)狀態(tài)中只有一個(gè)是接的路徑到達(dá)的兩個(gè)狀態(tài)中只有一個(gè)是接受狀態(tài)，我們就說受狀態(tài)，我們就說串串x區(qū)分狀態(tài)區(qū)分狀態(tài)s和和t。 如果存在某個(gè)能夠區(qū)分狀態(tài)如果存在某個(gè)能夠區(qū)分狀態(tài)s和狀態(tài)和狀態(tài)t的的串，那么它們就是串，那么它們就是可區(qū)分的可區(qū)分的。46工作原理工作原理 將一個(gè)將一個(gè)DFA的狀態(tài)集合分劃成多個(gè)組，的狀態(tài)集合分劃成多個(gè)組，每個(gè)組中的各個(gè)狀態(tài)之間相

22、互不可區(qū)分。每個(gè)組中的各個(gè)狀態(tài)之間相互不可區(qū)分。 分割法分割法47 DFA的最小化算法的最小化算法 DFA M =DFA M =（K,f, kK,f, k0 0, , k, kt t),),最小狀態(tài)最小狀態(tài)DFA M 1.1.構(gòu)造狀態(tài)的一初始劃分構(gòu)造狀態(tài)的一初始劃分： 終態(tài)終態(tài)k kt t 和非終態(tài)和非終態(tài)K- K- k kt t兩組兩組(group) (group) 2.2.對對施施用過程用過程如圖如圖構(gòu)造新劃分構(gòu)造新劃分newnew48 3 3. 如如new new =, =,則令則令 finalfinal= = 并并繼續(xù)步驟繼續(xù)步驟4 4，否則否則:=newnew重復(fù)重復(fù)2 . 2 .

23、4.4.為為finalfinal中的每一組選一代表，這中的每一組選一代表，這些代表構(gòu)成些代表構(gòu)成M的狀態(tài)。若的狀態(tài)。若k是是一代表一代表且且f(k,af(k,a)=t,)=t,令令r r是是t t組的組的代表，則代表，則M中有一轉(zhuǎn)換中有一轉(zhuǎn)換f(k,a(k,a)=r)=r M M 的開始狀態(tài)是含有的開始狀態(tài)是含有S S0 0的那組的代的那組的代表表 M M 的終態(tài)是含有的終態(tài)是含有F F的那組的代表的那組的代表 4950首先將M的狀態(tài)分成兩個(gè)子集：一個(gè)由終態(tài)(可接受態(tài))組成，一個(gè)由非終態(tài)組成，這個(gè)初始劃分P0為：P0=(1，2，3，4，5，6，7)，顯然第一個(gè)子集中的任何狀態(tài)都與第二個(gè)子集中的

24、任何狀態(tài)不等價(jià)。 P1=(1，23，45，6，7)P2=(1，2，3，4，5，6，7) P3=(1，2，3，4，5，6，7) 51 C和和D同是終態(tài)同是終態(tài),讀入讀入a到達(dá)到達(dá)C和和F, C和和F同是終態(tài)同是終態(tài), C和和F讀入讀入a都到達(dá)都到達(dá)C,讀入讀入b都到都到達(dá)達(dá)E. C和和D等價(jià)等價(jià)aCDBAEFSbaaaaabbbbbabF520:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa53將上圖將上圖NFA確定化和最確定化和最小化。小化。54l說一個(gè)有窮自動(dòng)機(jī)是化簡了的，即是說，說一個(gè)有

25、窮自動(dòng)機(jī)是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。l所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。狀態(tài)沒有通路到達(dá)終態(tài)。55 識別識別DFA中可達(dá)狀態(tài)的算

26、法：中可達(dá)狀態(tài)的算法： 標(biāo)記開始狀態(tài)標(biāo)記開始狀態(tài)S。 給定任意標(biāo)記過的狀態(tài)給定任意標(biāo)記過的狀態(tài)A，如果對某個(gè)輸入，如果對某個(gè)輸入符號存在從狀態(tài)符號存在從狀態(tài)A到到B的轉(zhuǎn)換，則標(biāo)記每一的轉(zhuǎn)換，則標(biāo)記每一個(gè)這樣的狀態(tài)個(gè)這樣的狀態(tài)B。 重復(fù)上步，直到不再有可標(biāo)記的狀態(tài)為止。重復(fù)上步，直到不再有可標(biāo)記的狀態(tài)為止。 當(dāng)該算法終止時(shí)，每一個(gè)未標(biāo)記的狀態(tài)當(dāng)該算法終止時(shí)，每一個(gè)未標(biāo)記的狀態(tài)就是不可達(dá)狀態(tài)。就是不可達(dá)狀態(tài)。消除不可達(dá)狀態(tài)消除不可達(dá)狀態(tài)56確定有限自動(dòng)機(jī)的程序?qū)崿F(xiàn)確定有限自動(dòng)機(jī)的程序?qū)崿F(xiàn) 1.通過狀態(tài)轉(zhuǎn)換表通過狀態(tài)轉(zhuǎn)換表T 2.通過狀態(tài)轉(zhuǎn)換圖直接轉(zhuǎn)向通過狀態(tài)轉(zhuǎn)換圖直接轉(zhuǎn)向5758abijkLi :

27、 switch(CurrentChar) case a : goto Lj ; case b : goto Lk ; default : Error( ); 圖圖 用直接轉(zhuǎn)向方法實(shí)現(xiàn)用直接轉(zhuǎn)向方法實(shí)現(xiàn)DFA(a) Li : switch(CurrentChar ) case Eof : Accept ; case a : goto Lj ; case b : goto Lk ; default : Error( ) ; abjki59 正則表達(dá)式正則表達(dá)式,是定義正規(guī)集的數(shù)學(xué)工具。正是定義正規(guī)集的數(shù)學(xué)工具。正則（規(guī)）表達(dá)式（則（規(guī)）表達(dá)式（regular expression）是說明是說明單詞

28、單詞的模式的模式(pattern)的一種重要的的一種重要的表示法（記號），我們用以描述表示法（記號），我們用以描述單詞單詞符號。符號。 正則表達(dá)式：描述所有通過對某個(gè)字母表正則表達(dá)式：描述所有通過對某個(gè)字母表上的符號應(yīng)用并、連接和閉包這些運(yùn)算符上的符號應(yīng)用并、連接和閉包這些運(yùn)算符而得到的語言。而得到的語言。正則表達(dá)式正則表達(dá)式60 R字母表字母表上正則表達(dá)式的集合上正則表達(dá)式的集合L(R) R所表示的語言，即符號串的集合所表示的語言，即符號串的集合(1) 是是 正則表達(dá)式，即正則表達(dá)式，即R 。其中。其中L()= 。(2) 是正則表達(dá)式，即是正則表達(dá)式，即 R 。其中。其中L( )= 。(3)

29、 c 是正則表達(dá)式，即是正則表達(dá)式，即c R 。其中。其中L(c)= c 。設(shè)設(shè)A和和B是是 正則表達(dá)式，即正則表達(dá)式，即A R ，B R ，則有，則有 ( A ) R ，L( (A) )= L(A) A | B R ，L( A | B )= L(A) L(B) A B R ，L( A B )= L(A ) L(B) A* R ，L( A*)= L(A)*61令令 =a，b， 上的正則表達(dá)式和相上的正則表達(dá)式和相應(yīng)的正規(guī)集的例子應(yīng)的正規(guī)集的例子 a a b ab (a b)(a b) a (a b) (a b) (aa bb)(a b) aa,babaa,ab,ba,bb ,a,aa, 任意個(gè)

30、任意個(gè)a的串的串 ,a,b,aa,ab,bb 所有由所有由 a和和b組成的串組成的串 所有含有兩個(gè)相繼的所有含有兩個(gè)相繼的a或兩個(gè)或兩個(gè)相繼的相繼的b組成的串組成的串62令令 =l，d，則，則 上的正規(guī)式上的正規(guī)式 r=l(l d) 定義的正規(guī)集為定義的正規(guī)集為: l,ll,ld,ldd,其中其中l(wèi)代表字母代表字母,d代表數(shù)字代表數(shù)字,正規(guī)式正規(guī)式 即是字母即是字母(字母字母|數(shù)字?jǐn)?shù)字) ,它表示的正規(guī)集中的每個(gè)元素它表示的正規(guī)集中的每個(gè)元素的模式是的模式是“字母打頭的字母數(shù)字串字母打頭的字母數(shù)字串”,就是就是Pascal和和 多多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識符的詞法規(guī)則數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識符的詞法規(guī)則. =d，.，e，+，-, 則則 上的正規(guī)式上的正規(guī)式 d (.dd )(e(+ - )dd ) 程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義. .表示的是無符號數(shù)的集合。表示的是無符號數(shù)的集合。63RealC = D+.D+假設(shè)有假設(shè)有D = 0,1, ., 9 ，則，則 實(shí)常數(shù)的集合實(shí)常數(shù)的集合RealC可用可用 正則表達(dá)式定義為如下正則表達(dá)式定義為如下: 64 0打頭的任意0、1串所對應(yīng)的正則表達(dá)式是什么？ 0（0|1）* =0、1每個(gè)1都有0直接跟在右邊。 0*（100*）*