編譯原理課件：3-1-第三章_詞法分析

1、第第3章章 詞法分析詞法分析3.1 3.1 對(duì)詞法分析器的要求對(duì)詞法分析器的要求3.2 3.2 詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)3.3 3.3 某簡(jiǎn)單語(yǔ)言的詞法分析程序某簡(jiǎn)單語(yǔ)言的詞法分析程序3.4 3.4 正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)3.1 1. 詞法分析器的工作詞法分析器的工作 處理輸入處理輸入：逐個(gè)字符讀入源程序；逐個(gè)字符讀入源程序； 處理：行尾、文件尾、無(wú)用空格、注釋等。處理：行尾、文件尾、無(wú)用空格、注釋等。 模式識(shí)別模式識(shí)別：將輸入字符流匹配成最合理的單詞符號(hào)。將輸入字符流匹配成最合理的單詞符號(hào)。例：例： if ( n 0 ) and ( j = 5 ) if ( n

2、 0 ) and ( j = 5 ) 輸入源程序，輸出單詞符號(hào)。輸入源程序，輸出單詞符號(hào)。 號(hào)號(hào)= = 號(hào)，號(hào)，不能匹配成：不能匹配成：,= ,= 兩個(gè)符號(hào)兩個(gè)符號(hào)2.詞法分析器的執(zhí)行方式詞法分析器的執(zhí)行方式 相對(duì)獨(dú)立方式相對(duì)獨(dú)立方式：把詞法分析器作為語(yǔ)法分析器的一：把詞法分析器作為語(yǔ)法分析器的一個(gè)子程序。語(yǔ)法分析器需要新符號(hào)時(shí)調(diào)用該程序。個(gè)子程序。語(yǔ)法分析器需要新符號(hào)時(shí)調(diào)用該程序。源程序文件源程序文件詞法分析器詞法分析器單詞符號(hào)文件單詞符號(hào)文件源程序文件源程序文件語(yǔ)法分析程序語(yǔ)法分析程序單詞符號(hào)單詞符號(hào)詞法分析程序詞法分析程序調(diào)用調(diào)用 完全獨(dú)立方式完全獨(dú)立方式：詞法分析器作為：詞法分析器作為

3、單獨(dú)一遍單獨(dú)一遍來(lái)實(shí)現(xiàn)。來(lái)實(shí)現(xiàn)。詞法分析器讀入整個(gè)源程序，輸出單詞符號(hào)文件。詞法分析器讀入整個(gè)源程序，輸出單詞符號(hào)文件。3.3.單詞符號(hào)的種類單詞符號(hào)的種類單詞符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位，一般分為單詞符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位，一般分為5 5類：類： 關(guān)鍵字關(guān)鍵字（基本字、保留字）：（基本字、保留字）： 如：如：beginbegin，endend，ifif，whilewhile 由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。 個(gè)數(shù)確定，可全體編為一類，也可一字一類個(gè)數(shù)確定，可全體編為一類，也可一字一類。 標(biāo)識(shí)符：標(biāo)識(shí)符： 用來(lái)表示各種名字，如：變量名、過(guò)程名等

4、。用來(lái)表示各種名字，如：變量名、過(guò)程名等。個(gè)數(shù)不確定，通常作為一類個(gè)數(shù)不確定，通常作為一類。如：如： x=a+bx=a+b ； （ 其中的：其中的：x ,a ,b x ,a ,b ） 常數(shù)：常數(shù)：各種類型的常數(shù)各種類型的常數(shù) 。 如：如：x=2 * 3.14 * 1.56 ，其中的，其中的2，3.14，1.56 個(gè)數(shù)不確定，一般按類型分類個(gè)數(shù)不確定，一般按類型分類， 如：整型常數(shù)類，實(shí)型常數(shù)類如：整型常數(shù)類，實(shí)型常數(shù)類 運(yùn)算符：運(yùn)算符： 如：如： 、 等。等。 個(gè)數(shù)確定，通常一符一類個(gè)數(shù)確定，通常一符一類。 界符：界符： 如：如： ， ； （ ） ： 等。等。 個(gè)數(shù)確定，通常一符一類個(gè)數(shù)確定，

5、通常一符一類。單詞符號(hào)通常用單詞符號(hào)通常用二元式二元式表示：表示：（單詞種別，屬性值（單詞種別，屬性值） 如果一個(gè)種別只含一個(gè)單詞符號(hào)，則返回單詞種別；如果一個(gè)種別只含一個(gè)單詞符號(hào)，則返回單詞種別； 如果一個(gè)種別含有多個(gè)單詞符號(hào)，如果一個(gè)種別含有多個(gè)單詞符號(hào)， 需返回：?jiǎn)卧~種別編碼需返回：?jiǎn)卧~種別編碼 + 屬性值屬性值4. 4. 單詞符號(hào)的內(nèi)部表示形式單詞符號(hào)的內(nèi)部表示形式單詞符號(hào)單詞符號(hào)屬性值屬性值標(biāo)識(shí)符標(biāo)識(shí)符構(gòu)成構(gòu)成標(biāo)識(shí)符的字符串；標(biāo)識(shí)符的字符串；或符號(hào)表中存放該標(biāo)識(shí)符的表項(xiàng)位置?；蚍?hào)表中存放該標(biāo)識(shí)符的表項(xiàng)位置。常數(shù)常數(shù)常數(shù)的二進(jìn)制數(shù)值；常數(shù)的二進(jìn)制數(shù)值；或常數(shù)表中存放該常數(shù)的表項(xiàng)位置。

6、或常數(shù)表中存放該常數(shù)的表項(xiàng)位置。例：某語(yǔ)言單詞符號(hào)例：某語(yǔ)言單詞符號(hào)集：集： 關(guān)鍵字關(guān)鍵字：DIMDIM，IFIF，DODO，STOPSTOP，ENDEND 標(biāo)識(shí)符：標(biāo)識(shí)符： 無(wú)符號(hào)整型常數(shù)無(wú)符號(hào)整型常數(shù) 運(yùn)算符：運(yùn)算符：= =、+ + 、* * 、* * * 界符：界符：，（，（ 、）、）單詞單詞類別類別關(guān)鍵字關(guān)鍵字1 1標(biāo)識(shí)符標(biāo)識(shí)符2 2常數(shù)常數(shù)3 3運(yùn)算符運(yùn)算符4 4界符界符5 5種別分配方式種別分配方式1 1： 5 5種種 （最少）（最少） 返回值：（種別號(hào)，屬性值）返回值：（種別號(hào)，屬性值）如：關(guān)鍵字：如：關(guān)鍵字：IF =IF =（ 1 1，IF IF ） 標(biāo)識(shí)符：標(biāo)識(shí)符：sum =

7、sum =（ 2 2，sum)sum) 常數(shù)：常數(shù)： 11 =11 =（ 3 3，1011) 1011) 關(guān)鍵字關(guān)鍵字：DIMDIM，IFIF，DODO，STOPSTOP，ENDEND 標(biāo)識(shí)符：標(biāo)識(shí)符： 無(wú)符號(hào)整型常數(shù)無(wú)符號(hào)整型常數(shù) 運(yùn)算符：運(yùn)算符：= =、+ + 、* * 、* * * 界符：界符：，（，（ 、）、）關(guān)鍵字、運(yùn)算符、關(guān)鍵字、運(yùn)算符、界符界符：一符：一符一種；一種； 返回值：返回值：( (種別號(hào)，種別號(hào)， - )- )標(biāo)識(shí)符一種，常數(shù)一種標(biāo)識(shí)符一種，常數(shù)一種 返回值：返回值：( (種別號(hào)，種別號(hào)， 種別內(nèi)屬性值種別內(nèi)屬性值) )單詞單詞類別類別DIMDIM1 1IFIF2 2D

8、ODO3 3STOPSTOP4 4ENDEND5 5標(biāo)識(shí)符標(biāo)識(shí)符6 6常數(shù)常數(shù)7 7= =8 8+ +9 9* *1010* * *1111，1212( (1313) )1414種別多：語(yǔ)義分析簡(jiǎn)單，語(yǔ)法分析復(fù)雜。種別多：語(yǔ)義分析簡(jiǎn)單，語(yǔ)法分析復(fù)雜。種別分配方式種別分配方式2 2：1414種種( (最多，常用方式最多，常用方式) )如：如：IF =( 2IF =( 2，- )- )3.2 預(yù)處理：預(yù)處理： 去掉注釋，去掉注釋， 形如：形如： / /* * * */ / 或或 / 去掉回車符、換行符等；去掉回車符、換行符等； 去掉無(wú)用空白符去掉無(wú)用空白符( (空格、空格、tab),tab),一般

9、保留一個(gè)用作單一般保留一個(gè)用作單詞之間的分隔符。詞之間的分隔符。1. 詞法分析器詞法分析器 的結(jié)構(gòu)的結(jié)構(gòu)輸入緩沖區(qū)輸入緩沖區(qū)單詞符號(hào)單詞符號(hào)詞法分析程序詞法分析程序源程序文件源程序文件預(yù)處理子程序預(yù)處理子程序掃描緩沖區(qū)掃描緩沖區(qū)掃描緩沖區(qū)：掃描緩沖區(qū)：存放存放“預(yù)處理預(yù)處理”的結(jié)果的結(jié)果。起始指針起始指針?biāo)阉髦羔標(biāo)阉髦羔樧缶彌_區(qū)左緩沖區(qū)右緩沖區(qū)右緩沖區(qū)兩個(gè)緩沖區(qū)互補(bǔ)使用。兩個(gè)緩沖區(qū)互補(bǔ)使用。設(shè)置兩區(qū)的原因：若一個(gè)單詞恰好橫跨緩沖區(qū)邊緣時(shí)，設(shè)置兩區(qū)的原因：若一個(gè)單詞恰好橫跨緩沖區(qū)邊緣時(shí)，前面緩沖區(qū)的內(nèi)容不能放棄，后面的又要進(jìn)來(lái)。前面緩沖區(qū)的內(nèi)容不能放棄，后面的又要進(jìn)來(lái)。單詞符號(hào)的長(zhǎng)度單詞符號(hào)的長(zhǎng)

10、度半個(gè)緩沖區(qū)的長(zhǎng)度半個(gè)緩沖區(qū)的長(zhǎng)度 be gin x:=0119 120239當(dāng)前正在識(shí)別單當(dāng)前正在識(shí)別單詞的開始位置詞的開始位置用于向前搜索，以用于向前搜索，以尋找單詞的終點(diǎn)尋找單詞的終點(diǎn)2. 超前搜索超前搜索為了判斷是否已讀入整個(gè)單詞的全部字符，需要向?yàn)榱伺袛嗍欠褚炎x入整個(gè)單詞的全部字符，需要向前多讀取若干字符并通過(guò)讀取的字符來(lái)判別。前多讀取若干字符并通過(guò)讀取的字符來(lái)判別。超前搜索用途超前搜索用途1 1：識(shí)別關(guān)鍵字識(shí)別關(guān)鍵字早期的程序語(yǔ)言早期的程序語(yǔ)言 關(guān)鍵字可以用作標(biāo)識(shí)符關(guān)鍵字可以用作標(biāo)識(shí)符 關(guān)鍵字與其他符號(hào)之間沒(méi)有特殊的界符關(guān)鍵字與其他符號(hào)之間沒(méi)有特殊的界符 （空格被認(rèn)為是無(wú)意義的）（

11、空格被認(rèn)為是無(wú)意義的）故：超前搜索，通過(guò)上下文確定當(dāng)前單詞的類別。故：超前搜索，通過(guò)上下文確定當(dāng)前單詞的類別。判斷依據(jù)：找到與判斷依據(jù)：找到與IFIF后的左擴(kuò)號(hào)對(duì)應(yīng)的后的左擴(kuò)號(hào)對(duì)應(yīng)的右擴(kuò)號(hào)后面的右擴(kuò)號(hào)后面的一個(gè)符號(hào)一個(gè)符號(hào), , 若為字母若為字母=邏輯邏輯IFIF語(yǔ)句，若為數(shù)字語(yǔ)句，若為數(shù)字=算術(shù)算術(shù)IFIF語(yǔ)句，語(yǔ)句， 其他其他=IF=IF被認(rèn)為是標(biāo)識(shí)符被認(rèn)為是標(biāo)識(shí)符程序片斷程序片斷等價(jià)含義等價(jià)含義IFIF的類別的類別IF(5.EQ.M)I=10 IF (5=M) then I=10關(guān)鍵字關(guān)鍵字x=IF(5.EQ.M)10,20 IF (5=M) then x=10 else x=20關(guān)鍵字

12、關(guān)鍵字IF(5)=55數(shù)組數(shù)組IFIF的第的第5 5個(gè)元素個(gè)元素, ,賦值賦值5555標(biāo)識(shí)符標(biāo)識(shí)符例：對(duì)單詞符號(hào)：例：對(duì)單詞符號(hào)：IFIF詞性的判定詞性的判定 （FORTRAN FORTRAN 語(yǔ)言）語(yǔ)言）現(xiàn)在，高級(jí)語(yǔ)言一般約定：現(xiàn)在，高級(jí)語(yǔ)言一般約定： 關(guān)鍵字不可以用作標(biāo)識(shí)符，關(guān)鍵字不可以用作標(biāo)識(shí)符， 故稱為：故稱為：“保留字保留字”； 用空格作為界符（一個(gè)單詞的結(jié)束）。用空格作為界符（一個(gè)單詞的結(jié)束）。超前搜索用途超前搜索用途2 2：識(shí)別常數(shù)識(shí)別常數(shù)某些語(yǔ)言，某些語(yǔ)言，常數(shù)的構(gòu)成形式常數(shù)的構(gòu)成形式與其他符號(hào)串有與其他符號(hào)串有相同相同的前綴的前綴。例例: :對(duì)單詞符號(hào)：對(duì)單詞符號(hào)：5.E 5

13、.E 詞性的判定詞性的判定 （FORTRAN FORTRAN 語(yǔ)言）語(yǔ)言）程序片斷程序片斷等價(jià)含義等價(jià)含義識(shí)別的單詞識(shí)別的單詞IF(5.EQ.M)I=10 IF (5=M) then I=10整型常數(shù)整型常數(shù): : 5 5I=5.E08I=5.E08實(shí)型常數(shù)實(shí)型常數(shù): 5.E08含義：匹配盡可能長(zhǎng)的串。含義：匹配盡可能長(zhǎng)的串。3. 貪心算法貪心算法例：例： if ( n0 ) and ( j=5 )if ( n0 ) and ( j=5 )例：例：length=length+100length=length+100 length length 匹配成一個(gè)標(biāo)識(shí)符；匹配成一個(gè)標(biāo)識(shí)符； 100 10

14、0 匹配成一個(gè)整型常數(shù)；匹配成一個(gè)整型常數(shù)；= = 號(hào)號(hào) 不能匹配成：不能匹配成：,=,=兩個(gè)符號(hào)兩個(gè)符號(hào) 號(hào)號(hào)結(jié)點(diǎn)：表示狀態(tài)；結(jié)點(diǎn)：表示狀態(tài)；箭?。罕硎緺顟B(tài)轉(zhuǎn)換關(guān)系，弧上的符號(hào)指當(dāng)前的箭?。罕硎緺顟B(tài)轉(zhuǎn)換關(guān)系，弧上的符號(hào)指當(dāng)前的 輸入字符。輸入字符。4. 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖123xy含義：若當(dāng)前狀態(tài)為含義：若當(dāng)前狀態(tài)為1， 在輸入字符為在輸入字符為x時(shí)，讀入時(shí)，讀入x，狀態(tài)轉(zhuǎn)為，狀態(tài)轉(zhuǎn)為2； 在輸入字符為在輸入字符為y時(shí)，讀入時(shí)，讀入y，狀態(tài)轉(zhuǎn)為，狀態(tài)轉(zhuǎn)為3； 輸入其他字符時(shí)，報(bào)錯(cuò)；輸入其他字符時(shí)，報(bào)錯(cuò)；有限方向圖，用于有限方向圖，用于識(shí)別識(shí)別正則文法正則文法的句子。的句子。狀態(tài)圖中，有一個(gè)

15、被認(rèn)為是狀態(tài)圖中，有一個(gè)被認(rèn)為是初態(tài)初態(tài)，至少有一個(gè)終態(tài)。，至少有一個(gè)終態(tài)。結(jié)點(diǎn)種類：結(jié)點(diǎn)種類：nnn* *一般狀態(tài)一般狀態(tài)終止?fàn)顟B(tài)，且多讀了一個(gè)字符終止?fàn)顟B(tài)，且多讀了一個(gè)字符終止?fàn)顟B(tài)終止?fàn)顟B(tài)狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖(識(shí)別：標(biāo)識(shí)符識(shí)別：標(biāo)識(shí)符)：0 0：初態(tài)：初態(tài)1 1：狀態(tài)：狀態(tài)2 2：終止?fàn)顟B(tài)，：終止?fàn)顟B(tài)，* *號(hào)表示號(hào)表示 多讀了一個(gè)字符多讀了一個(gè)字符字母字母其它其它字母字母|數(shù)字?jǐn)?shù)字02* *15. 用狀態(tài)圖分析（識(shí)別）字符串用狀態(tài)圖分析（識(shí)別）字符串設(shè)字符串為設(shè)字符串為，1)1) 當(dāng)前狀態(tài)位于開始狀態(tài)當(dāng)前狀態(tài)位于開始狀態(tài)S S，從，從的最左字符開始，的最左字符開始，重復(fù)步驟重復(fù)步驟 2

16、2），直至到達(dá)），直至到達(dá)的右端為止；的右端為止；2)2) 掃描掃描的的當(dāng)前字符當(dāng)前字符a a，在當(dāng)前狀態(tài)所射出的弧中，在當(dāng)前狀態(tài)所射出的弧中，找：標(biāo)記符號(hào)有找：標(biāo)記符號(hào)有a a的弧，的弧， 若存在這樣的弧，讀入字符若存在這樣的弧，讀入字符a a，并沿此弧前進(jìn)，并沿此弧前進(jìn)，過(guò)渡到下一個(gè)當(dāng)前狀態(tài)；過(guò)渡到下一個(gè)當(dāng)前狀態(tài)； 若不存在這樣的弧，則若不存在這樣的弧，則不是單詞，分析終止不是單詞，分析終止3)3) 如果到達(dá)如果到達(dá)的右端，并且當(dāng)前狀態(tài)是終態(tài)，的右端，并且當(dāng)前狀態(tài)是終態(tài)， 則則是單詞符號(hào)；否則不是單詞符號(hào)。是單詞符號(hào)；否則不是單詞符號(hào)。例：某語(yǔ)言定義標(biāo)識(shí)符：例：某語(yǔ)言定義標(biāo)識(shí)符：字母字母|

17、字母字母|數(shù)字?jǐn)?shù)字輸入：輸入：a3b+a3b+當(dāng)前狀態(tài)當(dāng)前狀態(tài)當(dāng)前輸入符號(hào)當(dāng)前輸入符號(hào)新狀態(tài)新狀態(tài)識(shí)別的單詞識(shí)別的單詞0 0a a1 1a a1 13 31 1a3a31 1b b1 1a3ba3b1 1+ +2 2a3b a3b ，+ +是多讀的是多讀的已到達(dá)狀態(tài)已到達(dá)狀態(tài)2（終態(tài)），（終態(tài)）， a3b是一個(gè)標(biāo)識(shí)符是一個(gè)標(biāo)識(shí)符狀態(tài)狀態(tài)轉(zhuǎn)換圖：轉(zhuǎn)換圖：0 0：開始狀態(tài)：開始狀態(tài)1 1：狀態(tài)：狀態(tài)2 2：終止?fàn)顟B(tài)，且多：終止?fàn)顟B(tài)，且多 讀了一個(gè)字符讀了一個(gè)字符字母字母其它其它字母字母|數(shù)字?jǐn)?shù)字02* *13.3 3.3 某簡(jiǎn)單語(yǔ)言的詞法分析程序某簡(jiǎn)單語(yǔ)言的詞法分析程序1.單詞符號(hào)：?jiǎn)卧~符號(hào)： 關(guān)

18、鍵字關(guān)鍵字：DIMDIM，IFIF，DODO，STOPSTOP，ENDEND 標(biāo)識(shí)符標(biāo)識(shí)符 無(wú)符號(hào)整型常數(shù)無(wú)符號(hào)整型常數(shù) 運(yùn)算符：運(yùn)算符：= =、+ + 、* * 、* * * 界符界符： ，、（，、（ 、 ）限制：（目前高級(jí)語(yǔ)言基本均這樣約定）限制：（目前高級(jí)語(yǔ)言基本均這樣約定） 關(guān)鍵字均為保留字（不可用作標(biāo)識(shí)符）關(guān)鍵字均為保留字（不可用作標(biāo)識(shí)符） 若：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)之間沒(méi)有運(yùn)算符或若：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)之間沒(méi)有運(yùn)算符或 界符做間隔，則必須有空白符（空格、換行符、界符做間隔，則必須有空白符（空格、換行符、 TABTAB）做間隔）做間隔。2 2、種別定義、種別定義單詞單詞種別定義種別定

19、義返回值返回值關(guān)鍵字關(guān)鍵字 一符一符一種一種( (種別號(hào)，種別號(hào)，-)-)運(yùn)算符運(yùn)算符 一符一符一種一種( (種別號(hào)，種別號(hào)，-)-)界符界符一符一符一種一種( (種別號(hào)，種別號(hào)，-)-)標(biāo)識(shí)符標(biāo)識(shí)符一種一種( (種別號(hào)，屬性值種別號(hào)，屬性值) )常數(shù)常數(shù)一種一種( (種別號(hào)，屬性值種別號(hào)，屬性值) )單詞單詞類別類別DIMDIM1 1IFIF2 2DODO3 3STOPSTOP4 4ENDEND5 5標(biāo)識(shí)符標(biāo)識(shí)符6 6常數(shù)常數(shù)7 7= =8 8+ +9 9* *1010* * *1111，1212( (1313) )1414201字母字母字母字母| |數(shù)字?jǐn)?shù)字其它其它3456數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字

20、其它其它+ +7* *108911= =* *（）13其它其它12*非非* *，* *空白空白3. 狀態(tài)狀態(tài) 轉(zhuǎn)換圖轉(zhuǎn)換圖單詞單詞類別類別DIMDIM1 1IFIF2 2DODO3 3STOPSTOP4 4ENDEND5 5標(biāo)識(shí)符標(biāo)識(shí)符6 6常數(shù)常數(shù)7 7= =8 8+ +9 9* *1010* * *1111，1212( (1313) )1414例：輸入串：例：輸入串： X3*y*5步步驟驟當(dāng)前當(dāng)前狀態(tài)狀態(tài)當(dāng)前當(dāng)前符號(hào)符號(hào)新新狀狀態(tài)態(tài)識(shí)別識(shí)別單詞單詞其它其它工作工作10X1X2131X331*2X3退回退回*40*7*57y8*退回退回y60y1y71*2y退回退回*80*7*97*9*10

21、0535113空格空格45退空格退空格201字母字母字母字母| |數(shù)字?jǐn)?shù)字其它其它3456數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它+ +7* *108911= =* *（）13其它其它12*非非* *，* *空白空白4. 變量、子程序變量、子程序1) ch1) ch：字符變量，存放：最新讀進(jìn)的源程序字符；：字符變量，存放：最新讀進(jìn)的源程序字符；2) strToken2) strToken：字符數(shù)組，存放：構(gòu)成單詞的字符串；：字符數(shù)組，存放：構(gòu)成單詞的字符串；3) Getchar3) Getchar：過(guò)程，將下一個(gè)輸入字符讀入：過(guò)程，將下一個(gè)輸入字符讀入chch， 搜索指針前移一位；搜索指針前移一位；4) ge

22、tNBC4) getNBC：過(guò)程，檢查：過(guò)程，檢查chch中字符是否為空白，若是，中字符是否為空白，若是， 重復(fù)調(diào)用重復(fù)調(diào)用getchargetchar直至直至chch中為非空白字符；中為非空白字符；5) Concat5) Concat：過(guò)程，將：過(guò)程，將chch中字符拼接到中字符拼接到strTokenstrToken之后；之后；6) isLetter6) isLetter：函數(shù)，若函數(shù)，若chch中字符為字母返回中字符為字母返回True,True, 否則返回否則返回FalseFalse；7) isDigit7) isDigit：函數(shù)，若函數(shù)，若chch中字符為數(shù)字返回中字符為數(shù)字返回True

23、,True, 否則返回否則返回FalseFalse；8) Reserve8) Reserve：函數(shù)，用函數(shù)，用strTokenstrToken中的字符串查找保中的字符串查找保 留字表，若為保留字返回其編碼值，留字表，若為保留字返回其編碼值， 否則返回否則返回0 0；9) Retract9) Retract：過(guò)程，將搜索指針回調(diào)一個(gè)字符位過(guò)程，將搜索指針回調(diào)一個(gè)字符位 置，將置，將chch置為空；置為空；10) InsertID10) InsertID：函數(shù)，將函數(shù)，將strTokenstrToken中字符串插入中字符串插入 符號(hào)表，返回對(duì)應(yīng)表項(xiàng)指針；符號(hào)表，返回對(duì)應(yīng)表項(xiàng)指針；11) Inser

24、tConst11) InsertConst：函數(shù)，將函數(shù)，將strTokenstrToken中字符串轉(zhuǎn)中字符串轉(zhuǎn) 換成常數(shù)，并插入常數(shù)表，返回對(duì)應(yīng)換成常數(shù)，并插入常數(shù)表，返回對(duì)應(yīng) 表項(xiàng)指針。表項(xiàng)指針。1)1) chch：最新讀進(jìn)的源程序字符：最新讀進(jìn)的源程序字符2)2) strTokenstrToken：構(gòu)成單詞的字符串：構(gòu)成單詞的字符串3)3) GetcharGetchar：讀入下一個(gè)輸入字符讀入下一個(gè)輸入字符4)4) getNBCgetNBC：取一個(gè)非空白字符取一個(gè)非空白字符5)5) ConcatConcat：將將chch拼接到拼接到strTokenstrToken6)6) isLette

25、risLetter：檢查檢查chch是否為字母是否為字母7)7) isDigitisDigit：檢查檢查chch是否為數(shù)字是否為數(shù)字8)8) ReserveReserve：查保留字表查保留字表9)9) RetractRetract：搜索指針回調(diào)搜索指針回調(diào)10)10)InsertIDInsertID：?jiǎn)卧~插入符號(hào)表單詞插入符號(hào)表11)11)InsertConstInsertConst：?jiǎn)卧~插入常數(shù)表單詞插入常數(shù)表201字母字母字母字母| |數(shù)字?jǐn)?shù)字其它其它3456數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它+ +7* *108911= =* *（）13其它其它12*非非* *，* *空白空白5. 構(gòu)造詞法分析程序

26、構(gòu)造詞法分析程序strToken:=；Getchar() ； getNBC() ；If isletter() then begin concat(); getchar() ； while isletter() or isDigit() begin concat()；getchar()； end； retract()； code=reserve()； if (code=0) then begin value:=insertID(strtoken)； return(6, value)； end else return (code,)； endElse If isDigit() then begin

27、 while isDigit() begin concat()；getchar() end； retract()； value:=insertDigit(strtoken)； return(7, value)； endElse If (ch=) then return(8, )Else If (ch=+) then return(9, )Else If (ch=*) then begin getchar()； If (ch=*) then return(11, ) else begin retract()；return(10, ) end 6. 6. 其它其它1)1) 對(duì)多讀字符的處理對(duì)多讀字

28、符的處理 即：即：方式方式：退回多讀的字符，用過(guò)程：退回多讀的字符，用過(guò)程：RetractRetract X 3 X 3 * * 5 5 * * * * y t y t識(shí)別單詞識(shí)別單詞 讀出符號(hào)讀出符號(hào) 其它工作其它工作_X3X3X3X3* *退回退回* * _ _ * * *5 5退回退回5 5 _5 55 5* *退回退回* * _ _ * * * * * _ ytytytyt退回空格退回空格 n* *對(duì)多讀字符的處理對(duì)多讀字符的處理：方式方式：不回退不回退在在chch中預(yù)先讀入一個(gè)字符，分析中，多讀字符的終止中預(yù)先讀入一個(gè)字符，分析中，多讀字符的終止?fàn)顟B(tài)不處理；未多讀字符的終止?fàn)顟B(tài)再讀入

29、一個(gè)字符。狀態(tài)不處理；未多讀字符的終止?fàn)顟B(tài)再讀入一個(gè)字符。ChCh X 3 X 3 * * 5 5 * * * * y t y t識(shí)別單詞識(shí)別單詞 讀出符號(hào)讀出符號(hào)其它工作其它工作X X _X3X3X3X3* * * * * *5 55 5 5 55 5* * * _ _ * * * * * 多讀多讀y yy y _ytytytyt 主程序先調(diào)用一次：主程序先調(diào)用一次：Getchar() ；詞法程序：詞法程序：strToken:=；Getchar() ； getNBC() ；If isletter() then begin while isletter() or isDigit() begin

30、 concat()；getchar()； end； retract()； code=reserve()； if (code=0) then begin value:=insertID(strtoken)； return(6, value)； end else return (code,)； endElse If isDigit() then begin while isDigit() begin concat()；getchar() end； retract()； value:=insertDigit(strtoken)； return(7, value)； endElse If (ch=)

31、then begin getchar(); return(8, ) endElse If (ch=+) then begin getchar(); return(9, ) endElse If (ch=*) then begin getchar()； If (ch=*) then begin getchar(); return(11, ) end else begin retract()； return(10, ) end 方式方式：程序改造程序改造2)2)擴(kuò)充語(yǔ)言時(shí)，詞法分析改動(dòng)內(nèi)容擴(kuò)充語(yǔ)言時(shí)，詞法分析改動(dòng)內(nèi)容： 單詞種別定義單詞種別定義 狀態(tài)圖狀態(tài)圖 ReserveReserve函數(shù)，保留

32、字表函數(shù)，保留字表 詞法分析程序主程序（狀態(tài)多）詞法分析程序主程序（狀態(tài)多）1. 正規(guī)語(yǔ)言正規(guī)語(yǔ)言是滿足下述相互等價(jià)的一組條件的一類形式語(yǔ)言：是滿足下述相互等價(jià)的一組條件的一類形式語(yǔ)言： 可以被確定有限狀態(tài)自動(dòng)機(jī)可以被確定有限狀態(tài)自動(dòng)機(jī)( (DFA)DFA)識(shí)別；識(shí)別； 可以被非確定有限狀態(tài)自動(dòng)機(jī)可以被非確定有限狀態(tài)自動(dòng)機(jī)( (NFA)NFA)識(shí)別；識(shí)別； 可以用可以用正規(guī)正規(guī)表達(dá)式描述；表達(dá)式描述； 可以用正規(guī)文法生成。可以用正規(guī)文法生成。 例：關(guān)于標(biāo)識(shí)符的正規(guī)產(chǎn)生式規(guī)則：（左線性文法）例：關(guān)于標(biāo)識(shí)符的正規(guī)產(chǎn)生式規(guī)則：（左線性文法） | 表示任意英文字母，表示任意英文字母， 表示任意數(shù)字表示

33、任意數(shù)字左線性文法左線性文法：產(chǎn)生式形如產(chǎn)生式形如 A A a a 或或 A A BaBa 的文法；的文法；右線性文法右線性文法：產(chǎn)生式形如產(chǎn)生式形如 A A a a 或或 A A aBaB 的文法；的文法； 其中：其中：A A、BVBVN N ；a aVT T （單個(gè)終結(jié)符或（單個(gè)終結(jié)符或 ) )2. 正規(guī)文法正規(guī)文法(正則文法正則文法)通過(guò)正規(guī)產(chǎn)生式規(guī)則描述的文法。通過(guò)正規(guī)產(chǎn)生式規(guī)則描述的文法?？梢钥梢杂卸喾N等價(jià)的有多種等價(jià)的定義定義形式形式，常用的有：常用的有：左線性文法左線性文法或或右線性文法右線性文法。 3. 正規(guī)式正規(guī)式設(shè)設(shè)是非空的有限字母表，則是非空的有限字母表，則 ， 都是正規(guī)

34、式；都是正規(guī)式； ( ( 空串，空串， 空集空集 ) ) 任何任何a a ，a a 是正規(guī)式；是正規(guī)式； 若若U U、V V是正規(guī)式，則是正規(guī)式，則U|V U|V 、 U UV V 、U U* * 也是正規(guī)式。也是正規(guī)式。 |(|(或或) ) ( (連接連接) ) * * ( (閉包閉包) ) 正規(guī)式只能通過(guò)有限次使用正規(guī)式只能通過(guò)有限次使用1 1、2 2、3 3規(guī)則獲得。規(guī)則獲得。例例: : =a,b =a,b, , 則則 b ba a* * 、a a(a|b(a|b) )* * 是是 上的正規(guī)式上的正規(guī)式 說(shuō)明：說(shuō)明：* *) | ) | 也可寫作為也可寫作為 “ “+” +” ； * *

35、) ) 也可以省略不寫也可以省略不寫 ； * *) U) U* * 表示表示n n個(gè)個(gè)U U，n0n0； U U+ + 表示表示n n個(gè)個(gè)U U ，n1 n1 ；運(yùn)算優(yōu)先級(jí)：運(yùn)算優(yōu)先級(jí)： |(|(或或) ) ( (連接連接) ) * * ( (閉包閉包) ) 低低 高高例例: : =a,b =a,b, , ba ba* * 的運(yùn)算順序是：的運(yùn)算順序是： b(ab(a* *) () (先做先做* *，再做，再做) ) a(a|b a(a|b) )* * 的運(yùn)算順序是：的運(yùn)算順序是： a(a|ba(a|b) )* * ) (| ) (| 、* * 、) )4. 正規(guī)集正規(guī)集若有字母表若有字母表，僅

36、由，僅由上的正規(guī)式上的正規(guī)式U U所組成的語(yǔ)言稱作所組成的語(yǔ)言稱作正規(guī)集，記作正規(guī)集，記作L(U)L(U)； 正規(guī)式正規(guī)式 ， 所表示的正規(guī)集分別為所表示的正規(guī)集分別為 、； 正規(guī)式正規(guī)式 a a 所表示的正規(guī)集為所表示的正規(guī)集為 aa； 若若U U、V V是正規(guī)式，所表示的正規(guī)集記為是正規(guī)式，所表示的正規(guī)集記為L(zhǎng)(U)L(U)、L(V)L(V) 正規(guī)式正規(guī)式含義含義正規(guī)集正規(guī)集含義含義（U|VU|V）或或 L(U)L(U)L(V)L(V)集合的并集合的并(U(UV)V)連接連接L(U)L(V) L(U)L(V) 集合的乘積集合的乘積(U)(U)* *閉包閉包(L(U)(L(U)* *集合的閉

37、包集合的閉包若正規(guī)式若正規(guī)式U U、V V表示的正規(guī)集相同，則稱表示的正規(guī)集相同，則稱U U、V V等價(jià)，記為等價(jià)，記為 U=VU=V 正規(guī)式正規(guī)式含義含義正規(guī)集正規(guī)集含義含義（U|VU|V）或或 L(U)L(U)L(V)L(V)集合的并集合的并(U(UV)V)連接連接L(U)L(V) L(U)L(V) 集合的乘積集合的乘積(U)(U)* *閉包閉包(L(U)(L(U)* *集合的閉包集合的閉包例：例： =a,b=a,b ， 則則 R=a(a|bR=a(a|b) )* * 是是上的正規(guī)式，上的正規(guī)式，R R表示的正規(guī)集：表示的正規(guī)集： L(R)=L(a(a|bL(R)=L(a(a|b) )*

38、*)=L(a)L(a|b)=L(a)L(a|b) )* *)=aL(a|b)=aL(a|b) )* *) ) =a(L(a|b =a(L(a|b)* *=a(L(a)L(b=a(L(a)L(b)* * =a(ab =a(ab)* *=aa,b=aa,b * * =a,a,b,aa,ab,ba,bb,aaa=a,a,b,aa,ab,ba,bb,aaa, =a,aa,ab,aaa,aba,abb,aaaa =a,aa,ab,aaa,aba,abb,aaaa, 即：即：上所有以上所有以a a開頭的字符串集開頭的字符串集例：例： =a,b=a,b 正規(guī)式正規(guī)式 正正規(guī)規(guī)集集 ba* 上所有以上所有以b

39、 b為首后跟任意多個(gè)為首后跟任意多個(gè)a a的字的字 a(a|b)* 上所有以上所有以a a為首的字為首的字 (a|b)*(aa|bb)(a|b)* 上所有含有兩個(gè)相繼的上所有含有兩個(gè)相繼的a a或兩個(gè)或兩個(gè) 相繼的相繼的b b的字的字 等價(jià)的等價(jià)的正規(guī)式正規(guī)式 ： b(ab)* * =(ba)* *b 上所有以上所有以b b為首，后跟任意多個(gè)為首，后跟任意多個(gè) 相繼相繼的的a ab b的字的字 (a|b)* * =(a)* *(b)* *)* * 上所有任意多個(gè)上所有任意多個(gè)a a或或b b構(gòu)成構(gòu)成的字的字令令U,V,WU,V,W均為正規(guī)式，則有以下關(guān)系成立：均為正規(guī)式，則有以下關(guān)系成立：1)

40、1) U|V = V|U (U|V = V|U (交換律交換律) )2)2) U|(V|W)=(U|V)|W ( U|(V|W)=(U|V)|W (結(jié)合律結(jié)合律) ) U(VW)=(UV)W ( U(VW)=(UV)W (結(jié)合律結(jié)合律) )3)3) U(V|W)= UV|UW ( U(V|W)= UV|UW (分配律分配律) ) (U|V)W= UW|VW ( (U|V)W= UW|VW (分配律分配律) )4)4) U= U= U U= U= U 正規(guī)式的性質(zhì)正規(guī)式的性質(zhì)定理：正規(guī)文法等價(jià)于正規(guī)式，正規(guī)語(yǔ)言等價(jià)于正規(guī)集定理：正規(guī)文法等價(jià)于正規(guī)式，正規(guī)語(yǔ)言等價(jià)于正規(guī)集 兩者之間是可以轉(zhuǎn)換的：兩

41、者之間是可以轉(zhuǎn)換的： 對(duì)任一正規(guī)文法，存在定義同一個(gè)語(yǔ)言的正規(guī)式；對(duì)任一正規(guī)文法，存在定義同一個(gè)語(yǔ)言的正規(guī)式； 對(duì)任一正規(guī)式，存在生成同一語(yǔ)言的正規(guī)文法；對(duì)任一正規(guī)式，存在生成同一語(yǔ)言的正規(guī)文法； 結(jié)構(gòu)上具有等價(jià)性：結(jié)構(gòu)上具有等價(jià)性： 由正規(guī)文法定義的由正規(guī)文法定義的正規(guī)語(yǔ)言正規(guī)語(yǔ)言 與用正規(guī)式定義的與用正規(guī)式定義的正規(guī)集正規(guī)集 是等價(jià)的。是等價(jià)的。正規(guī)式正規(guī)式 正規(guī)文法正規(guī)文法字母字母( (字母字母| |數(shù)字?jǐn)?shù)字) )* * 字母字母 | | 字母字母 | | 數(shù)字?jǐn)?shù)字1、有限自動(dòng)機(jī)、有限自動(dòng)機(jī) F Finite inite A Automation, utomation, FAFA 3.4

42、.2 DFA 3.4.2 DFA 與與 NFANFA. 是一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集。是一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集。組成：組成：帶有讀頭的有限控制器帶有讀頭的有限控制器 + 字符輸入帶字符輸入帶工作方式：工作方式：控制器的讀頭從左到右掃描輸入帶，每當(dāng)控制器的讀頭從左到右掃描輸入帶，每當(dāng)從輸入帶上讀到一個(gè)字符時(shí)，便引起控制器狀態(tài)的改從輸入帶上讀到一個(gè)字符時(shí)，便引起控制器狀態(tài)的改變，同時(shí)讀頭右移一個(gè)符號(hào)位。變，同時(shí)讀頭右移一個(gè)符號(hào)位。aabbbcba控制器控制器輸入帶輸入帶. 是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。它具有是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。它具有有有限數(shù)目限數(shù)目的內(nèi)部狀態(tài)

43、，系統(tǒng)可以根據(jù)當(dāng)前所處的的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所處的狀態(tài)狀態(tài)和面臨的和面臨的輸入字符輸入字符決定系統(tǒng)的后繼行為。其當(dāng)前狀決定系統(tǒng)的后繼行為。其當(dāng)前狀態(tài)概括了過(guò)去輸入處理的信息。態(tài)概括了過(guò)去輸入處理的信息。1203 a a b b a baABSZ a a b b a baaaDFA MDFA M是一個(gè)五元式：是一個(gè)五元式：M=(S,M=(S,s,s0 0，F(xiàn))F)。其中，。其中， S S：狀態(tài)的有限集合：狀態(tài)的有限集合；：輸入符號(hào)的有窮集合；：輸入符號(hào)的有窮集合；：狀態(tài)轉(zhuǎn)移函數(shù)，狀態(tài)轉(zhuǎn)移函數(shù)，S S S S ( (單值單值) )部分映射部分映射 對(duì)任何狀態(tài)對(duì)任何狀態(tài)sSsS，輸入符號(hào)，輸

44、入符號(hào)aa，(s,a(s,a) )唯一地唯一地確定了下一個(gè)狀態(tài)。確定了下一個(gè)狀態(tài)。支配著有限狀態(tài)控制的行為。支配著有限狀態(tài)控制的行為。s s0 0S S，是初始狀態(tài)；是初始狀態(tài)；F F，終止?fàn)顟B(tài)集合，終止?fàn)顟B(tài)集合( (可空可空) )。 F F S S2 2、DFADFA確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī) D Deterministic eterministic FAFA 例例: DFA M=(0,1,2,3,a,b,0,3): DFA M=(0,1,2,3,a,b,0,3)； 其中其中, ,轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)： (0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2(0,a)=1 (0,b)=

45、2 (1,a)=3 (1,b)=2 (2,a)=1 (2,b)=3 (3,a)=3 (2,a)=1 (2,b)=3 (3,a)=3 “確定確定”的含義：的含義：對(duì)任何狀態(tài)對(duì)任何狀態(tài)s s和和輸入字符輸入字符a a，唯，唯一地確定了下一個(gè)狀態(tài)一地確定了下一個(gè)狀態(tài)。若初始狀態(tài)同時(shí)又是終止?fàn)顟B(tài)，則空串若初始狀態(tài)同時(shí)又是終止?fàn)顟B(tài)，則空串 可被該可被該DFADFA識(shí)別。識(shí)別。例例: DFA M=(0,1,2,3,a,b,0,3): DFA M=(0,1,2,3,a,b,0,3)；狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)：(0,a)=1 (0,b)=2(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(1,a)

46、=3 (1,b)=2(2,a)=1 (2,b)=3(2,a)=1 (2,b)=3(3,a)=3 (3,a)=3 DFA M=(S,s0DFA M=(S,s0，F(xiàn))F)用用( (確定的確定的) )狀態(tài)轉(zhuǎn)換圖表示：狀態(tài)轉(zhuǎn)換圖表示：S S中的狀態(tài)表示成結(jié)點(diǎn)；中的狀態(tài)表示成結(jié)點(diǎn)；若若(si,a)=sj(si,a)=sj，則從結(jié)點(diǎn)，則從結(jié)點(diǎn)sisi到結(jié)點(diǎn)到結(jié)點(diǎn)sjsj畫標(biāo)記為畫標(biāo)記為a a的弧；的弧； 用箭頭用箭頭“”標(biāo)明初態(tài)；標(biāo)明初態(tài)；終態(tài)結(jié)點(diǎn)用雙圈表示；終態(tài)結(jié)點(diǎn)用雙圈表示；1203 a a b b a ba狀態(tài)轉(zhuǎn)換圖：狀態(tài)轉(zhuǎn)換圖：例例: DFA M=(0,1,2,3,a,b,0,3): DFA M=

47、(0,1,2,3,a,b,0,3)；(0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2(0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2(2,a)=1 (2,b)=3(2,a)=1 (2,b)=3 (3,a)=3 (3,a)=3 狀態(tài)狀態(tài)轉(zhuǎn)換圖：轉(zhuǎn)換圖： 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣 輸入輸入 狀態(tài)狀態(tài)a ab b0 01 12 21 13 32 22 21 13 33 33 3 1203 a a b b a ba也也可以用轉(zhuǎn)換矩陣表示，行：狀態(tài)，列：輸入字符，可以用轉(zhuǎn)換矩陣表示，行：狀態(tài)，列：輸入字符， 矩陣元素：新狀態(tài)，即矩陣元素：新狀態(tài)，即s s行行a a列為列為(s

48、,a(s,a) )的值；的值； 一般第一行是初態(tài)。一般第一行是初態(tài)。DFA映射映射的擴(kuò)充定義的擴(kuò)充定義 對(duì)：對(duì)：M=(SM=(S，s s0 0，F(xiàn))F)， 若：若：RSRS，aa，* * 擴(kuò)充定義擴(kuò)充定義：S S* * S S，（原來(lái)：，（原來(lái)：S S S S ）、(R,(R,) ) = = R R 表示：對(duì)任一狀態(tài)表示：對(duì)任一狀態(tài)R R，輸入為，輸入為時(shí)狀態(tài)不變；時(shí)狀態(tài)不變； ( (一定要有輸入符號(hào)后，一定要有輸入符號(hào)后，DFADFA的狀態(tài)才會(huì)改變的狀態(tài)才會(huì)改變) )、(R,a(R,a) ) = = (R,a),(R,a),) ) 表示：先利用映射表示：先利用映射(R,a)(R,a)得到狀態(tài)

49、得到狀態(tài)P P； 再利用映射再利用映射(P,(P,) )繼續(xù)轉(zhuǎn)換。繼續(xù)轉(zhuǎn)換。 ( (狀態(tài)的改變是按輸入字符串從左到右進(jìn)行的狀態(tài)的改變是按輸入字符串從左到右進(jìn)行的) )對(duì)字母串對(duì)字母串，若有，若有(s(s0 0，)F)F，則稱則稱可以被可以被DFADFA接受接受( (識(shí)別識(shí)別) )。自動(dòng)機(jī)接受的所有字串構(gòu)成了自動(dòng)機(jī)識(shí)別的自動(dòng)機(jī)接受的所有字串構(gòu)成了自動(dòng)機(jī)識(shí)別的語(yǔ)言語(yǔ)言 L(M) L(M)。 正規(guī)語(yǔ)言正規(guī)語(yǔ)言 3 3、 NFANFA M M是一個(gè)五元式：是一個(gè)五元式：M=(S,M=(S, ,S0 0，F(xiàn))F)。 其中：其中： S S：有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)

50、；：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符;：S S* *2 2S S ，即：從，即：從S S* * 到到S S的子集的映射的子集的映射; S0 0 S S ，非空初態(tài)集非空初態(tài)集; F FS S ， 一個(gè)終態(tài)集（可空）一個(gè)終態(tài)集（可空）;非確定有限自動(dòng)機(jī)（非確定有限自動(dòng)機(jī)（NFANFA）可以表示成一張）可以表示成一張（非確定的）狀態(tài)轉(zhuǎn)換圖。（非確定的）狀態(tài)轉(zhuǎn)換圖。 非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī) N Non-deterministic on-deterministic FAFA例：例：NFA NFA M=(S,A,B,Z,a,b,M=(S,A,B,

51、Z,a,b,S,Z,S,Z) 轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)：(S,a(S,a)=A )=A (S,b(S,b)=B)=B(A,a(A,a)=Z )=Z (A,b(A,b)=B)=B(B,a)=A,B (B,a)=A,B (B,b(B,b)=Z)=Z(Z,a)=A,Z (Z,a)=A,Z (Z,b(Z,b)=)= DFADFA是是NFANFA的特例。的特例。對(duì)于每個(gè)對(duì)于每個(gè)NFA MNFA M，存在一個(gè)，存在一個(gè)DFA MDFA M，使得：，使得：L(M)=L(M)L(M)=L(M)非確定非確定狀態(tài)狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換圖ABSZ a a b b a baaa其中：其中： 狀態(tài)為狀態(tài)為B B，輸入為，輸入為a a時(shí)

52、，下一個(gè)狀態(tài)可以是時(shí)，下一個(gè)狀態(tài)可以是A,BA,B中的一中的一 個(gè)，動(dòng)作出現(xiàn)了不確定性。如果選擇錯(cuò)誤，需要回溯。個(gè)，動(dòng)作出現(xiàn)了不確定性。如果選擇錯(cuò)誤，需要回溯。 (R,a (R,a)=)=所有集合所有集合(P,(P,) )的并集，的并集， 其中：其中： P P (R,a(R,a) )，aa，* * 對(duì)字母串對(duì)字母串，若有，若有(S,(S,)=P)=P， SSS0 0 ，PFPF， 則稱：則稱：可以被可以被NFANFA接受接受( (識(shí)別識(shí)別) )。NFA映射映射的擴(kuò)充定義的擴(kuò)充定義4 4、NFA與與DFA的區(qū)別的區(qū)別開始狀態(tài)開始狀態(tài)函數(shù)函數(shù)DFADFA一個(gè)狀態(tài)一個(gè)狀態(tài)S SS S 最多只有一個(gè)轉(zhuǎn)

53、移狀態(tài)最多只有一個(gè)轉(zhuǎn)移狀態(tài)NFANFA狀態(tài)集合狀態(tài)集合( (可能有多可能有多個(gè)狀態(tài)個(gè)狀態(tài)) )S S* *2 2S S 可以有多個(gè)狀態(tài)轉(zhuǎn)移可以有多個(gè)狀態(tài)轉(zhuǎn)移，需需要從中要從中非確定非確定地選擇一個(gè)地選擇一個(gè)字母表字母表，正規(guī)表達(dá)式，正規(guī)表達(dá)式U U，存在一個(gè)接受存在一個(gè)接受L(U)L(U)的轉(zhuǎn)換系統(tǒng)。的轉(zhuǎn)換系統(tǒng)。由正規(guī)式構(gòu)造由正規(guī)式構(gòu)造DFADFA1 1、從正規(guī)式構(gòu)造轉(zhuǎn)換系統(tǒng)從正規(guī)式構(gòu)造轉(zhuǎn)換系統(tǒng)(N NFAFA) (1) (2) (3) 正規(guī)式正規(guī)式 轉(zhuǎn)換系統(tǒng)轉(zhuǎn)換系統(tǒng)( (NFA)NFA) DFADFA 最小化最小化DFADFA 構(gòu)造構(gòu)造 確定化確定化 化簡(jiǎn)化簡(jiǎn)由正規(guī)式構(gòu)造由正規(guī)式構(gòu)造DFA的

54、步驟可分為三步，分別為：的步驟可分為三步，分別為：XYXY XYa假定假定aa；U,VU,V是是上的正規(guī)式；上的正規(guī)式；X X是開始狀態(tài)，是開始狀態(tài)，Y Y是終止?fàn)顟B(tài)；則可按下圖所示方法構(gòu)造轉(zhuǎn)換系統(tǒng)。是終止?fàn)顟B(tài)；則可按下圖所示方法構(gòu)造轉(zhuǎn)換系統(tǒng)。正規(guī)表達(dá)式正規(guī)表達(dá)式轉(zhuǎn)換系統(tǒng)轉(zhuǎn)換系統(tǒng) a aUVU|VU*XAYUVXYUVXAY U例：正規(guī)式例：正規(guī)式(a|b)(a|b)* *(aa|bb)(a|b(aa|bb)(a|b) )* *, , 構(gòu)造轉(zhuǎn)換系統(tǒng)步驟：構(gòu)造轉(zhuǎn)換系統(tǒng)步驟：XY(a|b)*(aa|bb)(a|b)*2Y1(a|b)*(a|b)* X(aa|bb)2 2Y Y1 1 X Xa a1

55、1 b ba a 3 3 a abb222”2”a ab b2 2Y Y1 1 X Xa a5 5 b ba a 6 6 a abb3 34 4a ab b2 2Y Y1 1 X Xaa11 bba|b 3 3 a|b 閉包閉包 狀態(tài)集合狀態(tài)集合I I的的-閉包，表示為：閉包，表示為：-closure(I-closure(I) )， 是一個(gè)狀態(tài)集：是一個(gè)狀態(tài)集：a)a) 若若sIsI，則，則 s -closure(Is -closure(I) ) ；b)b) 若若sIsI，從，從s s出發(fā)經(jīng)任意條連續(xù)的出發(fā)經(jīng)任意條連續(xù)的弧能到達(dá)弧能到達(dá) 狀態(tài)狀態(tài) s, s, 則：則： s -closure(I

56、)s -closure(I)。2. 2. 從轉(zhuǎn)換系統(tǒng)（從轉(zhuǎn)換系統(tǒng)（NFANFA）構(gòu)造）構(gòu)造DFADFA a a弧轉(zhuǎn)換弧轉(zhuǎn)換 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換是一個(gè)狀態(tài)集，弧轉(zhuǎn)換是一個(gè)狀態(tài)集， 表示為：表示為：move(Imove(I，a)a)； 含義：從含義：從I I出發(fā)，經(jīng)一條出發(fā)，經(jīng)一條a a弧可到達(dá)的狀態(tài)的集合。弧可到達(dá)的狀態(tài)的集合。 I Ia a 對(duì)于狀態(tài)集合對(duì)于狀態(tài)集合I I和弧和弧a ,a , 定義：定義：I Ia a=-closure(J)=-closure(J)，其中，其中J= move(IJ= move(I，a)a) 即即I Ia a 是是狀態(tài)集合狀態(tài)集合I I 的的

57、a a弧轉(zhuǎn)換弧轉(zhuǎn)換 的的-閉包。閉包。 利用子集法構(gòu)造利用子集法構(gòu)造DFADFA 對(duì)于：對(duì)于：NFA M = (SNFA M = (S，S S0 0，F(xiàn))F) 構(gòu)造：構(gòu)造：DFA M = (SDFA M = (S，S S0 0，F(xiàn) F) )其中：其中：狀態(tài)集狀態(tài)集 S S= T= T1 1，T T2 2，TTn n | T| Ti i S S，i = 1i = 1n n 字母表字母表 =函數(shù)函數(shù)(T(T，a)=-closure(move(Ta)=-closure(move(T，a)a)； T T S S初態(tài)初態(tài): S: S0 0= -closure= -closure（S S0 0）終態(tài)終態(tài):

58、 F: F=T=T1 1，T T2 2，,T,TM M |T |Ti i S S，T Ti iFF, , i=1 i=1m m 構(gòu)造構(gòu)造NFA MNFA M的狀態(tài)的狀態(tài)S S的子集的算法的子集的算法設(shè)所構(gòu)造的子集族：設(shè)所構(gòu)造的子集族：C=( TC=( T1 1,T,T2 2,T,Tn n ) )， T Ti i S S ； 令令-closure(S-closure(S0 0) )為為C C中唯一成員，并且它是中唯一成員，并且它是 未被標(biāo)記的；未被標(biāo)記的； While ( CWhile ( C中存在尚未被標(biāo)記的子集中存在尚未被標(biāo)記的子集T ) doT ) do 標(biāo)記標(biāo)記T T， forfor每個(gè)

59、輸入字母每個(gè)輸入字母a a（a a ） dodo U:= -closure (Move(T U:= -closure (Move(T，a);a); if U if U不在不在C C中中 thenthen 將將U U做為未被標(biāo)記的子集加在做為未被標(biāo)記的子集加在C C中中; ; 例：正規(guī)式例：正規(guī)式(a|b)(a|b)* *(aa|bb)(a|b(aa|bb)(a|b) )* * 的的NFA MNFA M：2 2Y Y1 1 X Xa a5 5 b ba a 6 6 a abb3 34 4a ab bI II Ia aI Ib bx,5,1x,5,15,3,15,3,15,4,15,4,15,3,

60、15,3,15,3,1,2,6,y5,3,1,2,6,y5,4,15,4,15,4,15,4,15,3,15,3,15,4,1,2,6,y5,4,1,2,6,y5,3,1,2,6,y5,3,1,2,6,y5,3,1,2,6,y5,3,1,2,6,y5,4,1,6,y5,4,1,6,y5,4,1,6,y5,4,1,6,y5,3,1,6,y5,3,1,6,y5,4,1,2,6,y5,4,1,2,6,y5,4,1,2,6,y5,4,1,2,6,y5,3,1,6,y5,3,1,6,y5,4,1,2,6,y5,4,1,2,6,y5,3,1,6,y5,3,1,6,y5,3,1,2,6,y5,3,1,2,6