編譯原理課件chap03(陳火旺)

1、第三章 詞法分析 編譯程序首先是在單詞級(jí)別上來分析和翻譯編譯程序首先是在單詞級(jí)別上來分析和翻譯源程序的。詞法分析的任務(wù)是：從左至右逐個(gè)字源程序的。詞法分析的任務(wù)是：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)，符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)，把作為字符串的源程序改造成為單詞符號(hào)串的中把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析的程序稱為法分析的程序稱為詞法分析器詞法分析器。3 3。1 1 對(duì)詞法分析器的要求對(duì)詞法分析器的要求 3.1.1 3.1.1 詞法分析器功能和輸出形式詞法分析器功能

2、和輸出形式 輸入源程序，輸出單詞符號(hào)。輸入源程序，輸出單詞符號(hào)。 程序語言的單詞符號(hào)一般分為五種：關(guān)鍵字，程序語言的單詞符號(hào)一般分為五種：關(guān)鍵字，標(biāo)識(shí)符，常數(shù)，運(yùn)算符，界符標(biāo)識(shí)符，常數(shù)，運(yùn)算符，界符第三章 詞法分析 詞法分析器輸出的單詞符號(hào)常常表示為二元詞法分析器輸出的單詞符號(hào)常常表示為二元式：式： （單詞種別，單詞符號(hào)的屬性值）（單詞種別，單詞符號(hào)的屬性值）單詞種別單詞種別通常用整數(shù)編碼。一個(gè)語言的單詞通常用整數(shù)編碼。一個(gè)語言的單詞符號(hào)如何分種，分成幾種，怎樣編碼是一個(gè)符號(hào)如何分種，分成幾種，怎樣編碼是一個(gè)技術(shù)問題。它取決于處理上的方便。標(biāo)識(shí)符技術(shù)問題。它取決于處理上的方便。標(biāo)識(shí)符一般統(tǒng)歸為

3、一種。常數(shù)則宜按類型（整、實(shí)、一般統(tǒng)歸為一種。常數(shù)則宜按類型（整、實(shí)、布爾等）分種。關(guān)鍵字可視其全體為一種，布爾等）分種。關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實(shí)際也可以一字一種。采用一字一種的分法實(shí)際處理起來較為方便。運(yùn)算符可采用一符一種處理起來較為方便。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般一符一種的分法。視為一種。至于界符一般一符一種的分法。第三章 詞法分析 如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么對(duì)于這個(gè)單詞符號(hào)，種別編碼就完全代表它對(duì)于這個(gè)單詞符號(hào)，種別

4、編碼就完全代表它自身了。若一個(gè)種別含有多個(gè)單詞符號(hào)，那自身了。若一個(gè)種別含有多個(gè)單詞符號(hào)，那麼，對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別麼，對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出有關(guān)單詞符號(hào)的編碼之外，還應(yīng)給出有關(guān)單詞符號(hào)的屬性信屬性信息。息。 單詞符號(hào)的屬性是指單詞符號(hào)的特征或特單詞符號(hào)的屬性是指單詞符號(hào)的特征或特性。性。屬性值屬性值則是反映特性或特征的值。例如，則是反映特性或特征的值。例如，對(duì)于某個(gè)對(duì)于某個(gè)標(biāo)識(shí)符標(biāo)識(shí)符，常將存放它有關(guān)信息的，常將存放它有關(guān)信息的符符號(hào)表號(hào)表項(xiàng)的項(xiàng)的指針指針作為其屬性值；對(duì)于某個(gè)作為其屬性值；對(duì)于某個(gè)常數(shù)常數(shù)，則將存放它的則將存放它的常數(shù)表項(xiàng)常數(shù)表項(xiàng)

5、的的指針指針作為其屬性值。作為其屬性值。第三章 詞法分析 作為例子考慮下述作為例子考慮下述C+C+代碼段：代碼段： while (i=j) i- -;while (i=j) i- -; 經(jīng)詞法分析器處理后，它將轉(zhuǎn)換為如下的單詞經(jīng)詞法分析器處理后，它將轉(zhuǎn)換為如下的單詞符號(hào)序列：符號(hào)序列： id , id ,指向指向i i的符號(hào)表項(xiàng)的指針的符號(hào)表項(xiàng)的指針 = , - = , - id , id , 第三章 詞法分析3.1.2 3.1.2 詞法分析器作為獨(dú)立子程序詞法分析器作為獨(dú)立子程序 我們把詞法分析器安排成一個(gè)獨(dú)立我們把詞法分析器安排成一個(gè)獨(dú)立子程序，每當(dāng)語法分析器需要一個(gè)單子程序，每當(dāng)語法分析

6、器需要一個(gè)單詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每一次詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每一次調(diào)用，詞法分析器就從符號(hào)串中識(shí)別調(diào)用，詞法分析器就從符號(hào)串中識(shí)別出一個(gè)單詞符號(hào)，把它交給語法分析出一個(gè)單詞符號(hào)，把它交給語法分析器。這樣，把詞法分析器安排成一個(gè)器。這樣，把詞法分析器安排成一個(gè)子程序似乎比較自然。在后面的討論子程序似乎比較自然。在后面的討論中，我們假定詞法分析器是按這種方中，我們假定詞法分析器是按這種方式進(jìn)行工作的。式進(jìn)行工作的。第三章 詞法分析 3 3。2 2 詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì) 3 3。2 2。1 1 輸入、預(yù)處理輸入、預(yù)處理 詞法分析器工作的第一步是輸入源程序文本。輸入詞法分析器工作

7、的第一步是輸入源程序文本。輸入串一般放在一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱串一般放在一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱輸入緩沖區(qū)輸入緩沖區(qū)。詞法分析器的工作可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但詞法分析器的工作可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但在許多情況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的在許多情況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的識(shí)別工作將是比較方便的。識(shí)別工作將是比較方便的。 預(yù)處理工作預(yù)處理工作包括對(duì)空白符、跳格符、回車符和換行包括對(duì)空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注解等。我們可以設(shè)符等編輯性字符的處理，及刪除注解等。我們可以設(shè)想構(gòu)造一個(gè)預(yù)處理子程序，他完成上面的工作。每當(dāng)想構(gòu)造一個(gè)預(yù)處理

8、子程序，他完成上面的工作。每當(dāng)詞法分析器調(diào)用它時(shí)就處理出一串確定長度的輸入字詞法分析器調(diào)用它時(shí)就處理出一串確定長度的輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接進(jìn)行單詞符號(hào)的識(shí)別工作。進(jìn)行單詞符號(hào)的識(shí)別工作。第三章 詞法分析 分析器對(duì)掃描緩沖區(qū)進(jìn)行掃描時(shí)一般分析器對(duì)掃描緩沖區(qū)進(jìn)行掃描時(shí)一般使用兩個(gè)指示器，一個(gè)指向當(dāng)前正在識(shí)使用兩個(gè)指示器，一個(gè)指向當(dāng)前正在識(shí)別單詞的開始位置。（指向新單詞的首別單詞的開始位置。（指向新單詞的首字符），另一個(gè)用于向前搜索以

9、尋找單字符），另一個(gè)用于向前搜索以尋找單詞的終點(diǎn)。詞的終點(diǎn)。 不論掃描緩沖區(qū)設(shè)得多大都不能保證不論掃描緩沖區(qū)設(shè)得多大都不能保證單詞符號(hào)不會(huì)被緩沖區(qū)的邊界所打斷。單詞符號(hào)不會(huì)被緩沖區(qū)的邊界所打斷。因此，掃描緩沖區(qū)最好使用如下一分為因此，掃描緩沖區(qū)最好使用如下一分為二的區(qū)域：二的區(qū)域： 第三章 詞法分析 假定每半個(gè)區(qū)可容假定每半個(gè)區(qū)可容120120個(gè)字符，而這個(gè)字符，而這兩個(gè)半?yún)^(qū)又是互補(bǔ)的。如果搜索指示器兩個(gè)半?yún)^(qū)又是互補(bǔ)的。如果搜索指示器從單詞起點(diǎn)出發(fā)搜索到半?yún)^(qū)的邊緣但尚從單詞起點(diǎn)出發(fā)搜索到半?yún)^(qū)的邊緣但尚未達(dá)到單詞的終點(diǎn)，那么就調(diào)用預(yù)處理未達(dá)到單詞的終點(diǎn)，那么就調(diào)用預(yù)處理子程序，令其把后續(xù)的子程序

10、，令其把后續(xù)的120120個(gè)字符裝入另個(gè)字符裝入另半?yún)^(qū)。我們認(rèn)定在另半?yún)^(qū)一定可以達(dá)到半?yún)^(qū)。我們認(rèn)定在另半?yún)^(qū)一定可以達(dá)到單詞的終點(diǎn)。這意味著得標(biāo)示符和常數(shù)單詞的終點(diǎn)。這意味著得標(biāo)示符和常數(shù)的的長度長度實(shí)際上必須加以限制，否則即使實(shí)際上必須加以限制，否則即使緩沖區(qū)再大也無濟(jì)于事。緩沖區(qū)再大也無濟(jì)于事。第三章 詞法分析 源 程 序 串 輸 入 緩 沖 區(qū) 列 表 預(yù) 處 理 子 程 序 掃 描 器 單 詞 符 號(hào) 掃 描 緩 沖 區(qū) 3。2。2 單詞符號(hào)的識(shí)別：超前搜索單詞符號(hào)的識(shí)別：超前搜索詞法分析器的結(jié)構(gòu)圖如圖詞法分析器的結(jié)構(gòu)圖如圖3。1所示。所示。第三章 詞法分析 當(dāng)詞法分析器調(diào)用預(yù)處理子程序

11、處理當(dāng)詞法分析器調(diào)用預(yù)處理子程序處理出一串輸入字符串放進(jìn)掃描緩沖區(qū)之后，出一串輸入字符串放進(jìn)掃描緩沖區(qū)之后，分析器就從此緩沖區(qū)中逐一識(shí)別單詞符分析器就從此緩沖區(qū)中逐一識(shí)別單詞符號(hào)。當(dāng)緩沖區(qū)里的字符串被處理完之后，號(hào)。當(dāng)緩沖區(qū)里的字符串被處理完之后，它又調(diào)用預(yù)處理程序裝入新串。它又調(diào)用預(yù)處理程序裝入新串。 下面我們來介紹單詞符號(hào)識(shí)別的一下面我們來介紹單詞符號(hào)識(shí)別的一個(gè)簡單方法個(gè)簡單方法-超前搜索超前搜索第三章 詞法分析 關(guān)鍵字的識(shí)別關(guān)鍵字的識(shí)別 像像FORTRAN這樣的語言，關(guān)鍵字不加保這樣的語言，關(guān)鍵字不加保護(hù)（只要不引起矛盾，用戶可以用它們作為普護(hù)（只要不引起矛盾，用戶可以用它們作為普通標(biāo)識(shí)

12、符），關(guān)鍵字和用戶自定義的標(biāo)識(shí)符或通標(biāo)識(shí)符），關(guān)鍵字和用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間沒有特殊的界符作間隔。這使得關(guān)鍵標(biāo)號(hào)之間沒有特殊的界符作間隔。這使得關(guān)鍵字的識(shí)別甚為麻煩。請(qǐng)看下面例子：字的識(shí)別甚為麻煩。請(qǐng)看下面例子： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4 IF(5)=55 這四個(gè)語句都是正確的這四個(gè)語句都是正確的FORTRAN語句。語句。語句語句1和和2分別是分別是DO和和IF語句，它們都是以某語句，它們都是以某基本字開頭的。語句基本字開頭的。語句3和和4是賦值語句，它們都是賦值語句，它們都是以用戶自定義的標(biāo)識(shí)符開頭的。是以用戶自定義的標(biāo)識(shí)

13、符開頭的。第三章 詞法分析 為了從為了從1 1、2 2中識(shí)別出關(guān)鍵字中識(shí)別出關(guān)鍵字DODO和和IFIF，我們必須，我們必須要能夠區(qū)別要能夠區(qū)別1 1、3 3和區(qū)別和區(qū)別2 2、4 4。語句。語句1 1、3 3的區(qū)別在于的區(qū)別在于等號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另個(gè)為句末等號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另個(gè)為句末符。語句符。語句2 2、4 4的主要區(qū)別在于右括號(hào)后的第一個(gè)字的主要區(qū)別在于右括號(hào)后的第一個(gè)字符：一個(gè)為字母，另一個(gè)為等號(hào)。這就是說，為了符：一個(gè)為字母，另一個(gè)為等號(hào)。這就是說，為了識(shí)別識(shí)別 1 1、2 2句中的關(guān)鍵字，我們必須超前掃描許多個(gè)句中的關(guān)鍵字，我們必須超前掃描許多個(gè)字符，

14、超前到能夠肯定詞性的地方為止。對(duì)于字符，超前到能夠肯定詞性的地方為止。對(duì)于1 1、3 3來說，盡管都以來說，盡管都以D D和和O O兩個(gè)字母開頭，但不能一兩個(gè)字母開頭，但不能一見見DODO就認(rèn)定是就認(rèn)定是DODO語句。我們們必須超前搜索，跳語句。我們們必須超前搜索，跳過所有的字母和數(shù)字，看看是否有等號(hào)。如果有，過所有的字母和數(shù)字，看看是否有等號(hào)。如果有，再向前搜索。若下一個(gè)界符是逗號(hào)，則可以肯定再向前搜索。若下一個(gè)界符是逗號(hào)，則可以肯定DODO應(yīng)為關(guān)鍵字。否則，應(yīng)為關(guān)鍵字。否則，DODO不構(gòu)成關(guān)鍵字，它只是用戶不構(gòu)成關(guān)鍵字，它只是用戶標(biāo)識(shí)符的頭兩個(gè)字母。所以為了區(qū)別標(biāo)識(shí)符的頭兩個(gè)字母。所以為了

15、區(qū)別1 1和和3 3，我們必，我們必須超前掃描到等號(hào)后的第一個(gè)界符處。須超前掃描到等號(hào)后的第一個(gè)界符處。第三章 詞法分析 對(duì)于對(duì)于2 2和和4 4來說，必須超前掃描到與來說，必須超前掃描到與IFIF后的后的左括號(hào)相對(duì)應(yīng)的那個(gè)右括號(hào)之后的第一個(gè)字符左括號(hào)相對(duì)應(yīng)的那個(gè)右括號(hào)之后的第一個(gè)字符為止。若此字符是字母，則得邏輯為止。若此字符是字母，則得邏輯IFIF。若此字。若此字符為數(shù)字，則得算術(shù)符為數(shù)字，則得算術(shù)IFIF。否則，應(yīng)認(rèn)為是用戶。否則，應(yīng)認(rèn)為是用戶自定義標(biāo)識(shí)符自定義標(biāo)識(shí)符IF.IF. 標(biāo)識(shí)符的識(shí)別、常數(shù)的識(shí)別及算符和界符識(shí)符的識(shí)別、常數(shù)的識(shí)別及算符和界符的識(shí)別相類似可以參考課本的識(shí)別相類似可

16、以參考課本P40,P41這里就不這里就不再多述。再多述。 3。2。3 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 使用狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)使用狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)詞法分析器詞法分析器的一種的一種好好途徑途徑。轉(zhuǎn)換圖是一張有限方向圖。在轉(zhuǎn)換圖中，。轉(zhuǎn)換圖是一張有限方向圖。在轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用園圈表示。狀態(tài)之間用箭弧結(jié)點(diǎn)代表狀態(tài)，用園圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符（即箭弧始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符或字符類?；蜃址?。第三章 詞法分析 例如圖例如圖3。2（a)表示：表示：在狀態(tài)在狀態(tài)1下，若輸入下，若輸入

17、字符為字符為X，則讀進(jìn)，則讀進(jìn)X，并轉(zhuǎn)換到狀態(tài)并轉(zhuǎn)換到狀態(tài)2。若。若輸入字符為輸入字符為y，則讀，則讀進(jìn)進(jìn)Y，并轉(zhuǎn)換到狀態(tài)，并轉(zhuǎn)換到狀態(tài)3。一張轉(zhuǎn)換圖只包。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其有限個(gè)結(jié)點(diǎn)），其中有一個(gè)被認(rèn)為是中有一個(gè)被認(rèn)為是初態(tài)，而且實(shí)際上初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)至少要有一個(gè)終態(tài)（用雙圈表示）。（用雙圈表示）。第三章 詞法分析 一個(gè)狀態(tài)轉(zhuǎn)換圖可用于一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別一定識(shí)別一定的字符串的字符串。例如，識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖。例如，識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖如圖如圖3 3。2 2（b)b)所示。其中所示。其中0 0為初態(tài)，為初態(tài)，2 2為為終態(tài)。這個(gè)轉(zhuǎn)

18、換圖識(shí)別標(biāo)識(shí)符的過程是：終態(tài)。這個(gè)轉(zhuǎn)換圖識(shí)別標(biāo)識(shí)符的過程是：從初態(tài)從初態(tài)0 0開始，若在狀態(tài)開始，若在狀態(tài)0 0下輸入字符是下輸入字符是字母，則讀進(jìn)它，并轉(zhuǎn)入狀態(tài)字母，則讀進(jìn)它，并轉(zhuǎn)入狀態(tài)1 1。在狀。在狀態(tài)態(tài)1 1之下，若輸入字符為字母或數(shù)字，之下，若輸入字符為字母或數(shù)字，則讀進(jìn)它，并重新進(jìn)入狀態(tài)則讀進(jìn)它，并重新進(jìn)入狀態(tài)1 1。一直重。一直重復(fù)這個(gè)過程直到發(fā)現(xiàn)輸入字符不再是字復(fù)這個(gè)過程直到發(fā)現(xiàn)輸入字符不再是字母或數(shù)字時(shí)（這個(gè)字符已經(jīng)被讀進(jìn)）就母或數(shù)字時(shí)（這個(gè)字符已經(jīng)被讀進(jìn)）就近入狀態(tài)近入狀態(tài)2 2。狀態(tài)。狀態(tài)2 2是終態(tài)，它意味著到是終態(tài)，它意味著到此已經(jīng)識(shí)別出一個(gè)標(biāo)識(shí)符。終態(tài)上打個(gè)此已經(jīng)識(shí)

19、別出一個(gè)標(biāo)識(shí)符。終態(tài)上打個(gè)* *號(hào)，表示多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符號(hào)，表示多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符部分的字符，應(yīng)把它退還給輸入串，如部分的字符，應(yīng)把它退還給輸入串，如果在狀態(tài)果在狀態(tài)0 0時(shí)輸入字符不為時(shí)輸入字符不為“字母字母”，則意味著這個(gè)轉(zhuǎn)換圖不工作。則意味著這個(gè)轉(zhuǎn)換圖不工作。第三章 詞法分析 又如書中圖又如書中圖3。2（c)是識(shí)別整數(shù)的轉(zhuǎn)是識(shí)別整數(shù)的轉(zhuǎn)換圖。其中換圖。其中0為初態(tài)，為初態(tài)，2為終態(tài)。為終態(tài)。 書中圖書中圖3。2（d)是一個(gè)識(shí)別是一個(gè)識(shí)別FORTRAN實(shí)型常數(shù)的轉(zhuǎn)換圖。其中實(shí)型常數(shù)的轉(zhuǎn)換圖。其中0態(tài)態(tài)為初態(tài)，為初態(tài)，7態(tài)為終態(tài)。態(tài)為終態(tài)。 一個(gè)非常重要的事實(shí)是，一個(gè)非常重要的

20、事實(shí)是，大多數(shù)大多數(shù)程序程序語言的單詞符號(hào)都可以用語言的單詞符號(hào)都可以用轉(zhuǎn)換圖轉(zhuǎn)換圖予以識(shí)予以識(shí)別。作為一個(gè)綜合例子，課本別。作為一個(gè)綜合例子，課本P43構(gòu)造了構(gòu)造了一個(gè)識(shí)別某個(gè)簡單語言的所有單詞符號(hào)一個(gè)識(shí)別某個(gè)簡單語言的所有單詞符號(hào)的轉(zhuǎn)換圖。希望同學(xué)們好好讀一下。的轉(zhuǎn)換圖。希望同學(xué)們好好讀一下。第三章 詞法分析 3。2。4狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 轉(zhuǎn)換圖容易用程序?qū)崿F(xiàn)。最簡單的辦轉(zhuǎn)換圖容易用程序?qū)崿F(xiàn)。最簡單的辦法是讓每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。法是讓每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。 在編制程序的過程中課本引進(jìn)了一組在編制程序的過程中課本引進(jìn)了一組全局變量和過程。將它們作為實(shí)現(xiàn)轉(zhuǎn)換全局變量

21、和過程。將它們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。希望同學(xué)能記住它們。圖的基本成分。希望同學(xué)能記住它們。第三章 詞法分析 3.3 3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī) 為了更好地使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法為了更好地使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器，為了討論詞法分析器的自動(dòng)生分析器，為了討論詞法分析器的自動(dòng)生成，還需要將成，還需要將轉(zhuǎn)換圖轉(zhuǎn)換圖的概念的概念形式化形式化。為。為此我們引入：正規(guī)式，正規(guī)集，自動(dòng)機(jī)此我們引入：正規(guī)式，正規(guī)集，自動(dòng)機(jī)等概念。等概念。 3.3.1 正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集 對(duì)于字母表對(duì)于字母表，我們感興趣的是它的，我們感興趣的是它的一些特殊的字集，即所謂正規(guī)集。我們使用

22、一些特殊的字集，即所謂正規(guī)集。我們使用正規(guī)式這個(gè)概念來表示正規(guī)集。正規(guī)式這個(gè)概念來表示正規(guī)集。第三章 詞法分析 下面是正規(guī)式和正規(guī)集的定義：下面是正規(guī)式和正規(guī)集的定義： （1）和和 都是都是 上的正規(guī)式，他們所表示的正規(guī)集分上的正規(guī)式，他們所表示的正規(guī)集分別為別為 和和 ； （2）任何）任何a , a是是上的一個(gè)正規(guī)式，它所表示的正上的一個(gè)正規(guī)式，它所表示的正規(guī)集為規(guī)集為a； （3）假定）假定U和和V都是都是上的正規(guī)式，他們所表示的正規(guī)上的正規(guī)式，他們所表示的正規(guī)集分別記為集分別記為L(U)和和L(V),并且，并且，(U|V), (UV)和（和（U)*也都也都是正規(guī)式，它們所表示的正規(guī)集分別為

23、是正規(guī)式，它們所表示的正規(guī)集分別為L(U) L(V), L(U)L(V)(連接積）和（連接積）和（L(U)*（閉包）（閉包） 僅由有限次使用上述三步驟而得到的表達(dá)式才是僅由有限次使用上述三步驟而得到的表達(dá)式才是上上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是的正規(guī)式。僅由這些正規(guī)式所表示的字集才是上的正上的正規(guī)集。規(guī)集。第三章 詞法分析 通過這一節(jié)的學(xué)習(xí)，根據(jù)給出的簡單正規(guī)式，應(yīng)會(huì)通過這一節(jié)的學(xué)習(xí)，根據(jù)給出的簡單正規(guī)式，應(yīng)會(huì)寫出其正規(guī)集。寫出其正規(guī)集。 3。1 令令=a, b其正規(guī)式和正規(guī)集如下：其正規(guī)式和正規(guī)集如下： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 ba* 上所有以上所有以b為首后跟著任意多個(gè)為首后

24、跟著任意多個(gè)a 的字的字 a(a|b)* 上所有以上所有以a為首的字。為首的字。（a|b)*(aa|bb)(a|b)* 正規(guī)集是正規(guī)集是 所有兩個(gè)相繼的所有兩個(gè)相繼的a或相繼或相繼 的的b 的字。的字。 第三章 詞法分析 3。2 令令=A,B,0,1 ,則：則： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集(A|B)(A|B|0|1)* 上的上的“標(biāo)識(shí)符標(biāo)識(shí)符”的全體的全體（0|1）（）（0|1）* 上上“數(shù)數(shù)”的全體的全體 若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者為二者等價(jià)。等價(jià)。兩個(gè)等價(jià)的正規(guī)式兩個(gè)等價(jià)的正規(guī)式U和和V記為記為U=V。 例如：例如：b(ab)*=(ba)

25、*b等價(jià)等價(jià)第三章 詞法分析 a a b b - (a) a 一個(gè)正規(guī)式可以表示若干個(gè)符號(hào)串一個(gè)正規(guī)式可以表示若干個(gè)符號(hào)串, , (b) b 其正規(guī)集就是這些符號(hào)串的集合其正規(guī)集就是這些符號(hào)串的集合 a|b a,b ab ab a* ,a,aa,aaa,aaaa,. b* ,b,bb,bbb,bbbb,. - (a|b)* a和b組成的所有串 a*|b* ,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,. aba* 以ab開頭后接若干個(gè)(包括0個(gè))a組成的串 (a|b)*(aa|bb) (a|b)* *上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串第三章 詞法分析例：令d， ，e，

26、則上的正規(guī)式d*(.dd*| )(e(+|-|)dd*|)表示的是所有無符號(hào)數(shù)。 其中d為09中的數(shù)字。 比如：2,12.59,3.6e2,471.88e-1等都是正規(guī)式表示集合中的元素。設(shè)r，s，t為正規(guī)式，正規(guī)式服從代數(shù)規(guī)律有：1、r|ss|r 交換律2、r|(s|t)(r|s)|t 結(jié)合律3、(rs)t=r(st) 結(jié)合律第三章 詞法分析4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律5. r=r 零一律 r=r 零一律程序設(shè)計(jì)語言中的程序設(shè)計(jì)語言中的單詞單詞既能用既能用正規(guī)文法正規(guī)文法表示，又能用表示，又能用正規(guī)式正規(guī)式來表示來表示.正規(guī)文法正規(guī)文法:

27、: l|ll|l l|d|l l|d|l| d | d d|d d|d l l表示表示a-za-z中的任何英文字母，中的任何英文字母，d d表示表示0-90-9中的任何數(shù)字中的任何數(shù)字正規(guī)式正規(guī)式:標(biāo)識(shí)符標(biāo)識(shí)符: :e1=字母字母(字母字母|數(shù)字?jǐn)?shù)字)* 無符號(hào)整數(shù)無符號(hào)整數(shù): :e2=dd*第三章 詞法分析 3.3.2 確定有限自動(dòng)機(jī)（確定有限自動(dòng)機(jī)（DFA)有窮自動(dòng)機(jī)：是一種自動(dòng)識(shí)別裝置，能有窮自動(dòng)機(jī)：是一種自動(dòng)識(shí)別裝置，能正確正確識(shí)別識(shí)別正規(guī)集正規(guī)集； 確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)(DFA)是一個(gè)五元式是一個(gè)五元式 M= (S, ,s0, F) 其中其中: (1)S是一個(gè)有限集，它的每個(gè)

28、元素稱為一個(gè)狀態(tài)。是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)。 （2） 是一個(gè)有窮字母集，它的每個(gè)元素稱為一個(gè)輸入是一個(gè)有窮字母集，它的每個(gè)元素稱為一個(gè)輸入字符。字符。 （3） 是一個(gè)從是一個(gè)從S x 至至S的的單值部分映射單值部分映射。 (s,a）=S。意味著：當(dāng)現(xiàn)行狀態(tài)為。意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入字符為、輸入字符為a時(shí)，時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)將轉(zhuǎn)換到下一個(gè)狀態(tài)S。我們稱。我們稱S為為s的后繼狀態(tài)。的后繼狀態(tài)。 （4）S0 S，是唯一的初態(tài)。，是唯一的初態(tài)。 （5）F S，是一個(gè)終態(tài)集（可空），是一個(gè)終態(tài)集（可空）第三章 詞法分析 顯然，顯然， DFA可以用一個(gè)矩陣表示，該可以用一個(gè)矩陣表示

29、，該矩陣的行表示狀態(tài)，列表示輸入字符，矩矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元表示陣元表示(s,a）的值，該矩陣稱為狀態(tài)轉(zhuǎn)）的值，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。換矩陣。 DFA也可以表示成一張（確定的）狀也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。假定態(tài)轉(zhuǎn)換圖。假定DFA M 含有含有m個(gè)狀態(tài)個(gè)狀態(tài)n個(gè)個(gè)輸入字符，那末，這張圖含有輸入字符，那末，這張圖含有m個(gè)狀態(tài)結(jié)個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有n條箭弧射出和別的結(jié)條箭弧射出和別的結(jié)點(diǎn)相連接，每條箭弧用點(diǎn)相連接，每條箭弧用 上的一個(gè)不同字符上的一個(gè)不同字符作標(biāo)記，整張圖含有唯一的初態(tài)和若干個(gè)作標(biāo)記，整張圖含有唯一的初態(tài)和若干個(gè)（可以是（可以

30、是0個(gè)）終態(tài)結(jié)點(diǎn)。個(gè)）終態(tài)結(jié)點(diǎn)。 第三章 詞法分析 對(duì)于對(duì)于 *中的任何一個(gè)字符中的任何一個(gè)字符 ，若，若存在一條從存在一條從初態(tài)結(jié)點(diǎn)初態(tài)結(jié)點(diǎn)到某一到某一終態(tài)結(jié)終態(tài)結(jié)點(diǎn)點(diǎn)的通路，且這條通路上所有箭弧的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字等于的標(biāo)記符連接成的字等于 ，則稱，則稱 為為DFA M所所識(shí)別識(shí)別（讀出讀出或或接受接受）。）。 若若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則為空字點(diǎn)，則為空字 可以為可以為M所識(shí)別。所識(shí)別。DFA M所能識(shí)別的字的全體記為所能識(shí)別的字的全體記為L(M).第三章 詞法分析例例 有有DFAM=(0,1,2,3,a,b, ,0,3)其中：其

31、中： （0,a)=1; （0,b)=2 （1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3; （3,b)=3問：有幾個(gè)狀態(tài)？幾個(gè)輸入字符？問：有幾個(gè)狀態(tài)？幾個(gè)輸入字符？并畫出其轉(zhuǎn)換圖。并畫出其轉(zhuǎn)換圖。L(M)=?解：有解：有0，1，2，3共四個(gè)狀態(tài)。共四個(gè)狀態(tài)。輸入字符為輸入字符為a,b兩個(gè)。其狀態(tài)轉(zhuǎn)兩個(gè)。其狀態(tài)轉(zhuǎn)換圖如右換圖如右L(M)為在為在 上所有含相繼兩個(gè)上所有含相繼兩個(gè)a或或相繼兩個(gè)相繼兩個(gè)b的字。的字。（a|b)*(aa|bb)(a|b)* 正規(guī)集是正規(guī)集是 所有兩個(gè)相繼的所有兩個(gè)相繼的a或或相繼相繼 b 的字。的字。 第三章 詞法分析 3。3。3

32、非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī)(NFA) 一個(gè)非確定有限自動(dòng)機(jī)（一個(gè)非確定有限自動(dòng)機(jī)（NFA)是一個(gè)是一個(gè)五元式五元式 M= (S, ,S0, F) 其中其中: (1) S 同同3。3。2的的1（2）同）同3。3。2的的2（3） 是一個(gè)從是一個(gè)從S x *到到S的的子集的映照子集的映照，即即 ：S x *2s (4) S0 S,是一個(gè)非空的初態(tài)是一個(gè)非空的初態(tài)集集；（5）F S，是一個(gè)終態(tài)集（可空），是一個(gè)終態(tài)集（可空）第三章 詞法分析例：一個(gè)NFA，M(0,1,2,3,4,a,b,f,0,2,4) 其中：f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1

33、,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4狀態(tài)圖表示如下：第三章 詞法分析03412abbba,ba,ba,b說明：一個(gè)初態(tài)，二個(gè)終態(tài)。說明：一個(gè)初態(tài)，二個(gè)終態(tài)。 DFA是是NFA的特例。的特例。定理：定理：對(duì)于每個(gè)對(duì)于每個(gè)NFA M，存在一，存在一個(gè)個(gè)DFA M，使得，使得L(M)=L(M)。 對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和和M，如果如果L(M)=L(M)，則稱，則稱M與與M是等價(jià)的。是等價(jià)的。 第三章 詞法分析 顯然，顯然，NFA也可以表示成一張狀態(tài)轉(zhuǎn)也可以表示成一張狀態(tài)轉(zhuǎn)換圖。假定換圖。假定NFA 含有含有m個(gè)狀態(tài)個(gè)狀態(tài)n個(gè)輸入個(gè)輸入字符，那末，這

34、張圖含有字符，那末，這張圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條箭弧和別的結(jié)每個(gè)結(jié)點(diǎn)可以射出若干條箭弧和別的結(jié)點(diǎn)相連接，每條箭弧用點(diǎn)相連接，每條箭弧用 *上的一個(gè)字上的一個(gè)字（不一定要不同的字而且可以是空字（不一定要不同的字而且可以是空字 ）作標(biāo)記（稱為輸入字），整張圖至少含作標(biāo)記（稱為輸入字），整張圖至少含有一個(gè)的初態(tài)和若干個(gè)（可以是有一個(gè)的初態(tài)和若干個(gè)（可以是0個(gè)）終個(gè)）終態(tài)結(jié)點(diǎn)。某結(jié)點(diǎn)既可以是初態(tài)也可以是態(tài)結(jié)點(diǎn)。某結(jié)點(diǎn)既可以是初態(tài)也可以是終態(tài)結(jié)點(diǎn)。終態(tài)結(jié)點(diǎn)。第三章 詞法分析 對(duì)于對(duì)于 *中的任何一個(gè)字符中的任何一個(gè)字符 ，若存在，若存在一條從一條從初態(tài)結(jié)點(diǎn)初態(tài)結(jié)點(diǎn)到某一到某

35、一終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)的通路，的通路，且這條通路上所有箭弧的標(biāo)記符連接成且這條通路上所有箭弧的標(biāo)記符連接成的字（忽略那些標(biāo)記為的字（忽略那些標(biāo)記為 的弧）等于的?。┑扔?，則稱則稱 為為NFA M所所識(shí)別識(shí)別（讀出讀出或或接受接受）。）。 若若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，或者存在一條某處態(tài)結(jié)點(diǎn)到某各終態(tài)結(jié)或者存在一條某處態(tài)結(jié)點(diǎn)到某各終態(tài)結(jié)點(diǎn)的點(diǎn)的 通路，則為空字通路，則為空字 可以為可以為M所識(shí)別。所識(shí)別。 這里應(yīng)注意這里應(yīng)注意DFA與與NFA的異同點(diǎn)。的異同點(diǎn)。第三章 詞法分析顯然顯然DFA是是NFA的特例。對(duì)于每個(gè)的特例。對(duì)于每個(gè)NFA M存在存在一個(gè)一個(gè)DFA

36、M”，使，使L(M)=L(M”)。其證明如下。其證明如下（略）（略） 在這個(gè)證明中特別強(qiáng)調(diào)的是課本在這個(gè)證明中特別強(qiáng)調(diào)的是課本P49頁下邊提頁下邊提到的對(duì)到的對(duì)M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行圖的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行圖3。7所示所示的替換，其中的替換，其中k是新引入的狀態(tài)。是新引入的狀態(tài)。第三章 詞法分析 書中的這個(gè)圖書中的這個(gè)圖3。7同時(shí)也是從正規(guī)式畫有限自動(dòng)同時(shí)也是從正規(guī)式畫有限自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖的重要方法。對(duì)于正規(guī)式中的機(jī)狀態(tài)轉(zhuǎn)換圖的重要方法。對(duì)于正規(guī)式中的連接連接可按可按1式畫其轉(zhuǎn)換圖，對(duì)于式畫其轉(zhuǎn)換圖，對(duì)于或或可用可用2式，對(duì)于式，對(duì)于閉包閉包可用可用3式。式。將將正規(guī)式正規(guī)式轉(zhuǎn)換為轉(zhuǎn)換為狀態(tài)

37、轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖靈活使用這些規(guī)則非常重靈活使用這些規(guī)則非常重要的。要的。 如：正規(guī)式：如：正規(guī)式：R=(a*b)*ba(a|b)* 可以畫為：可以畫為： 第三章 詞法分析其中（其中（a*b)* 和和(a|b)*分別可以看成一個(gè)閉包。形成分別可以看成一個(gè)閉包。形成A和和G結(jié)點(diǎn)。結(jié)點(diǎn)。 例例：畫出正規(guī)式：畫出正規(guī)式： （a|b)*(aa|bb)(a|b)*對(duì)應(yīng)的對(duì)應(yīng)的NFA第三章 詞法分析NFA 轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFA從從NFA的矩陣表示中可以看出，表項(xiàng)通常的矩陣表示中可以看出，表項(xiàng)通常是一是一狀態(tài)的集合狀態(tài)的集合，而在，而在DFA的矩陣表示的矩陣表示中，表項(xiàng)是一個(gè)中，表項(xiàng)是一個(gè)狀態(tài)狀態(tài)，

38、NFA到相應(yīng)的到相應(yīng)的DFA的構(gòu)造的基本思路是：的構(gòu)造的基本思路是： DFADFA的每一個(gè)的每一個(gè)狀態(tài)對(duì)應(yīng)狀態(tài)對(duì)應(yīng)NFANFA的一組狀態(tài)的一組狀態(tài). . DFA使用它的使用它的狀態(tài)去記錄在狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)可能達(dá)到的所有狀態(tài).第三章 詞法分析第三章 詞法分析第三章 詞法分析狀態(tài)集合I的有關(guān)運(yùn)算的例子I=1, -closure(I)=?；I=5, -closure(I)=?；(1,2,a)=?-closure(5,3,4)=?；狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某

39、一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。12534687aaa第三章 詞法分析狀態(tài)集合I的有關(guān)運(yùn)算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa第三章 詞法分析 NFA確定化算法: 假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個(gè)DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. 構(gòu)造DFA M的狀態(tài)，選擇NFA N的狀態(tài)的一些子集構(gòu)成： M的狀態(tài)集S由K K的的一些子集一些子集組成。用S1 S2. Sj表示S的

40、元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對(duì)于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；第三章 詞法分析2 M和和N的輸入字母表是相同的，即是的輸入字母表是相同的，即是 ；3構(gòu)造構(gòu)造DFA M的轉(zhuǎn)換函數(shù)，根據(jù)新構(gòu)造的狀的轉(zhuǎn)換函數(shù)，根據(jù)新構(gòu)造的狀態(tài)和字母表中的字符構(gòu)造：態(tài)和字母表中的字符構(gòu)造：轉(zhuǎn)換函數(shù)是這樣定義的：轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0= -closure(

41、K0)為為M的開始狀態(tài)；的開始狀態(tài)；5 St=Si Sk. Se，其中，其中Si Sk. Se S且且Si , Sk,. Se Kt第三章 詞法分析構(gòu)造構(gòu)造NFA N的的狀態(tài)狀態(tài)K K的子集的子集的算法：的算法： 把多值轉(zhuǎn)換函數(shù)所轉(zhuǎn)換到的多值（多狀態(tài)）的把多值轉(zhuǎn)換函數(shù)所轉(zhuǎn)換到的多值（多狀態(tài)）的集合作為一個(gè)子集，映射到集合作為一個(gè)子集，映射到DFA的一個(gè)新的狀的一個(gè)新的狀態(tài)態(tài)假定所構(gòu)造的子集族為假定所構(gòu)造的子集族為C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI為狀態(tài)為狀態(tài)K的子集。的子集。1 開始，令開始，令 -closure(K0)為為C中唯一成員，并中唯一成員，并

42、且它是未被標(biāo)記的。且它是未被標(biāo)記的。第三章 詞法分析2 while （C中存在尚未被標(biāo)記的子集中存在尚未被標(biāo)記的子集T）do 標(biāo)記標(biāo)記T； for 每個(gè)輸入字母每個(gè)輸入字母a do U:= -closure( (T,a)； if U不在不在C中中 then 將將U作為未標(biāo)記的子集加在作為未標(biāo)記的子集加在C中中 第三章 詞法分析 NFA的確定化 例子4f35621iaaaabbbb第三章 詞法分析IaIbi,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

43、,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,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb第三章 詞法分析 等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF第三章 詞法分析三、確定有窮自動(dòng)機(jī)三、確定有窮自動(dòng)機(jī)DFA的化簡的化簡（消除多余狀態(tài)（消除多余狀態(tài)+合并等價(jià)狀態(tài)）：合并等價(jià)狀態(tài)）：將多余狀態(tài)消除而形成一個(gè)最小的等價(jià)的將多余狀態(tài)消除而形成一個(gè)最小的等價(jià)的DFA 1、多余狀態(tài)的概念：、多余狀態(tài)的概念： 從該自動(dòng)機(jī)的從該自動(dòng)機(jī)的開始狀態(tài)開始狀態(tài)

44、出發(fā)，任何輸入串也出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)。不能到達(dá)的那個(gè)狀態(tài)。 下圖中的哪些狀態(tài)是多余的？下圖中的哪些狀態(tài)是多余的？第三章 詞法分析01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S60化簡后的結(jié)果：左右等價(jià)第三章 詞法分析01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化簡后的結(jié)果：左右等價(jià)第三章 詞法分析2、等價(jià)的條件（狀態(tài)、等價(jià)的條

45、件（狀態(tài)S和和T） 一致性條件一致性條件 狀態(tài)狀態(tài)S和和T必須同時(shí)為可接受狀必須同時(shí)為可接受狀態(tài)或不可接受狀態(tài)（終態(tài)還是非終態(tài)）。態(tài)或不可接受狀態(tài)（終態(tài)還是非終態(tài)）。 蔓延性條件蔓延性條件 對(duì)于所有輸入符號(hào)，狀態(tài)對(duì)于所有輸入符號(hào)，狀態(tài)S和狀和狀態(tài)態(tài)T必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。 3、合并等價(jià)狀態(tài)的方法（分割法）、合并等價(jià)狀態(tài)的方法（分割法）方法：將方法：將DFA的狀態(tài)分割成一些互不相交的子集。不的狀態(tài)分割成一些互不相交的子集。不同子集的狀態(tài)是可區(qū)別的，同一子集中的任何兩個(gè)狀同子集的狀態(tài)是可區(qū)別的，同一子集中的任何兩個(gè)狀態(tài)是等價(jià)的。態(tài)是等價(jià)的。 合并等價(jià)狀態(tài)：發(fā)現(xiàn)等價(jià)狀態(tài)，并

46、將這些等合并等價(jià)狀態(tài)：發(fā)現(xiàn)等價(jià)狀態(tài)，并將這些等價(jià)狀態(tài)合并成一個(gè)狀態(tài)。價(jià)狀態(tài)合并成一個(gè)狀態(tài)。第三章 詞法分析1643257aaaaaaabbbbbbb例子：將圖中的DFA M最小化。第三章 詞法分析 將將M分成兩個(gè)子集：分成兩個(gè)子集： 一個(gè)終態(tài)（可接受態(tài)）組成，一個(gè)非終態(tài)組成。一個(gè)終態(tài)（可接受態(tài)）組成，一個(gè)非終態(tài)組成。 P0(1,2,3,4,5,6,7) 第第1個(gè)子集個(gè)子集1,2,3,4中：中： 1,2中的狀態(tài)和中的狀態(tài)和3,4中的任何狀態(tài)在讀入中的任何狀態(tài)在讀入a后到達(dá)了不等價(jià)的狀態(tài)，兩個(gè)狀態(tài)都是不可區(qū)別后到達(dá)了不等價(jià)的狀態(tài)，兩個(gè)狀態(tài)都是不可區(qū)別的。的。 P1(1,2,3,4,5,6,7) P

47、1中的中的3,4對(duì)應(yīng)輸入符號(hào)對(duì)應(yīng)輸入符號(hào)a或或b，將再分割：，將再分割： P2(1,2,3,4,5,6,7) P2中的中的5,6,7可有輸入符號(hào)可有輸入符號(hào)a或或b，分割為：，分割為：第三章 詞法分析1643257aaaaaaabbbbbbbP3(1,2,3,4,5,6,7)1,2,6,7不能再分割，也即等價(jià)的。16435aaaaabbbbb第三章 詞法分析 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)和非終

48、態(tài)K- K- k kt t兩組兩組(group) (group) 2.2.對(duì)對(duì)施施用用過程過程PPPP 構(gòu)造新劃分構(gòu)造新劃分new new 3 3. 如如new new =, =,則令則令 finalfinal= = 并繼續(xù)步并繼續(xù)步驟驟4 4，否則否則:=newnew重復(fù)重復(fù)2 . 2 . 4.4.為為finalfinal中的每一組選一代表，這些代中的每一組選一代表，這些代表構(gòu)成表構(gòu)成M的狀態(tài)。若的狀態(tài)。若k是是一代表且一代表且f(k,a)=t,f(k,a)=t,令令r r是是t t組的組的代表，則代表，則M中有一中有一轉(zhuǎn)換轉(zhuǎn)換f(k,a)=r(k,a)=r第三章 詞法分析 M M 的開始狀

49、態(tài)是含有的開始狀態(tài)是含有S S0 0的那組的代表的那組的代表 M M 的終態(tài)是含有的終態(tài)是含有F F的那組的代表的那組的代表 5.5.去掉去掉M M中的死狀態(tài)中的死狀態(tài). .第三章 詞法分析過程過程PPPP : Construction of newFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t hav

50、e transitions on a to states in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in n e w by the set of all subgroups formed end 第三章 詞法分析 3.3.4, 3.3.5 正規(guī)文法，正規(guī)式與有限自動(dòng)機(jī)的正規(guī)文法，正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性等價(jià)性 第三章 詞法分析1. 正規(guī)文法和正規(guī)式的等價(jià)性正規(guī)文法和正規(guī)式的等價(jià)性 一個(gè)一個(gè)正規(guī)語言正規(guī)語言可以由可以由正規(guī)文法正規(guī)文法定義，也可定義，也可以用以用正

51、規(guī)式正規(guī)式定義。定義。對(duì)于任意一個(gè)正規(guī)文法，存在一個(gè)定義同對(duì)于任意一個(gè)正規(guī)文法，存在一個(gè)定義同一語言的正規(guī)式。對(duì)每一個(gè)正規(guī)式，存在一語言的正規(guī)式。對(duì)每一個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法。一個(gè)生成同一語言的正規(guī)文法。即即正規(guī)式正規(guī)式正規(guī)文法正規(guī)文法第三章 詞法分析 正規(guī)式正規(guī)式正規(guī)文法正規(guī)文法：將將上的一個(gè)正規(guī)式上的一個(gè)正規(guī)式r轉(zhuǎn)換為一個(gè)正規(guī)文法轉(zhuǎn)換為一個(gè)正規(guī)文法G=（VN，VT，P，S）的規(guī)則：）的規(guī)則： 令令VT=，對(duì)正規(guī)式對(duì)正規(guī)式r，選擇一個(gè)非終結(jié)符，選擇一個(gè)非終結(jié)符S生成生成Sr，S為為G的開始符號(hào)。不斷拆分的開始符號(hào)。不斷拆分r直到符合正規(guī)文法要求直到符合正規(guī)文法要求的規(guī)則形式

52、：的規(guī)則形式：第三章 詞法分析 若若x，y都是正規(guī)式，對(duì)形如都是正規(guī)式，對(duì)形如Axy的產(chǎn)生式，寫成的產(chǎn)生式，寫成AxB，By。其中。其中B VN 對(duì)形如對(duì)形如Ax*y的產(chǎn)生式，重寫為：的產(chǎn)生式，重寫為： Ax A Ay B為新的非終結(jié)符，為新的非終結(jié)符，B VN對(duì)形如對(duì)形如Ax|y的產(chǎn)生式，重寫為：的產(chǎn)生式，重寫為： Ax Ay 不斷利用上述規(guī)則進(jìn)行變換即可。不斷利用上述規(guī)則進(jìn)行變換即可。第三章 詞法分析例：將例：將Ra(a|d)*變換成正規(guī)文法。令變換成正規(guī)文法。令S是文法是文法開始符號(hào)。開始符號(hào)。第三章 詞法分析例：將例：將Ra(a|d)*變換成正規(guī)文法。令變換成正規(guī)文法。令S是文法是文法

53、開始符號(hào)。開始符號(hào)。解：S a(a|d)*SaAA(a|d)*A(a|d) AA 第三章 詞法分析最后得到：最后得到：SaAAaAAdAA 第三章 詞法分析 正規(guī)文法正規(guī)文法正規(guī)式：正規(guī)式：將一個(gè)正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則：將一個(gè)正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則：轉(zhuǎn)換規(guī)則：轉(zhuǎn)換規(guī)則： AxB，By 正規(guī)式為：正規(guī)式為： A=xy AxA|y 正規(guī)式為：正規(guī)式為： A=x*y wAx，Ay 正規(guī)式為：正規(guī)式為： A=x|y 不斷收縮產(chǎn)生式規(guī)則，直到剩下一個(gè)開始符號(hào)定義的正規(guī)式不斷收縮產(chǎn)生式規(guī)則，直到剩下一個(gè)開始符號(hào)定義的正規(guī)式例：文法例：文法GS：S aAS aA aAA dAA aA d轉(zhuǎn)換為正規(guī)式

54、轉(zhuǎn)換為正規(guī)式第三章 詞法分析S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根據(jù)上述規(guī)則根據(jù)上述規(guī)則3Ax，Ay推出推出A=x|y將它化為正規(guī)文法將它化為正規(guī)文法變成變成A (a|d)A|(a|d) 再根據(jù)上述再根據(jù)上述規(guī)則規(guī)則2轉(zhuǎn)換轉(zhuǎn)換xy (a|d)將將A代入代入SaA|a得到如下：得到如下：第三章 詞法分析Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+| )= a(a|d)*第三章 詞法分析2. 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 正規(guī)

55、式和有窮自動(dòng)機(jī)的等價(jià)性由以下兩點(diǎn)說明正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性由以下兩點(diǎn)說明 ： 對(duì)于對(duì)于上的上的NFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的上的正規(guī)式正規(guī)式R，使得，使得L(R)=L(M)。 對(duì)于對(duì)于上的每個(gè)上的每個(gè)正規(guī)式正規(guī)式R，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的上的NFA M，使得，使得L(M)=L(R)。 1、在、在NFA M上構(gòu)造正規(guī)式上構(gòu)造正規(guī)式R。即從。即從L(M) L(R）方法：在每一條弧上用一個(gè)正規(guī)式作標(biāo)記。方法：在每一條弧上用一個(gè)正規(guī)式作標(biāo)記。規(guī)則如下：規(guī)則如下：第三章 詞法分析a.123R1R213R1R2b.12R1R221R1|R221R1+R2或c.321R1R2R331

56、R1R2*R3給定有窮自動(dòng)機(jī)，判斷它識(shí)別的語言第三章 詞法分析例例1: L(M)如下圖：如下圖：求正規(guī)式求正規(guī)式R，使，使L(R)=L(M).解：解：aba,b第三章 詞法分析例例1: L(M)如下圖：如下圖：求正規(guī)式求正規(guī)式R，使，使L(R)=L(M).解：解：aba,baba,bxy ya|bx a|byx(a|b)(a|b)*因此：因此：L(R)= (a+b)(a+b)*第三章 詞法分析03412aabba,ba,ba,b例例2：M狀態(tài)圖如下：狀態(tài)圖如下：求正規(guī)式求正規(guī)式R，是，是L(R)=L(M).第三章 詞法分析解：加解：加x,y結(jié)點(diǎn)。結(jié)點(diǎn)。a,b03412aabba,ba,bx y

57、第三章 詞法分析042aabba,ba,bxy a,ba,b0aa(a+b)*bb(a+b)*x y第三章 詞法分析y(a+b)*(aa+bb)(a+b)*x所以所以 L(R) =(a+b)*(aa+bb)(a+b)*第三章 詞法分析2、L(R) NFA，從正規(guī)式，從正規(guī)式R構(gòu)造構(gòu)造NFA規(guī)則如下： 正規(guī)式，構(gòu)造NFA為： 或： 對(duì)應(yīng)正規(guī)式，構(gòu)造NFA為： 對(duì)應(yīng)正規(guī)式a，構(gòu)造NFA為： s,t是正規(guī)式，相應(yīng)NFA為N(s),N(t)，則正規(guī)式R=s|t，構(gòu)造NFA(R) 為：xyxyxyaxyN(s)N(t)第三章 詞法分析 s,t是正規(guī)式，相應(yīng)NFA為N(s),N(t)，則正規(guī)式R=st，構(gòu)

58、造NFA(R) 為：xyN(t)N(s) s,t是正規(guī)式，相應(yīng)NFA為N(s),N(t)，則正規(guī)式R=s*，構(gòu)造NFA(R) 為：xyN(s)第三章 詞法分析例例1：L(R) =(a+b)*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)解：解：第三章 詞法分析例例1：L(R) =(a+b)*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)解：解：xy(a+b)*abbxyabb a,bxyabb ab xy ababb第三章 詞法分析yababb例例4： L(R) =(a+b)*(aa+bb)(a+b)*構(gòu)造構(gòu)造L(N)使與使與L(R) 等價(jià)。等價(jià)。第三章 詞法分析xy(a+b)*(aa+bb)

59、(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b第三章 詞法分析 3.4 3.4 詞法分析器的自動(dòng)產(chǎn)生詞法分析器的自動(dòng)產(chǎn)生 我們用正規(guī)式描述單詞符號(hào)，并研究我們用正規(guī)式描述單詞符號(hào)，并研究如何從正規(guī)式產(chǎn)生識(shí)別這些單詞符號(hào)的如何從正規(guī)式產(chǎn)生識(shí)別這些單詞符號(hào)的詞法分析程序。詞法分析程序。 首先介紹一個(gè)描述詞法分析器的語言首先介紹一個(gè)描述詞法分析器的語言LEXLEX，討論，討論LEXLEX的實(shí)現(xiàn)，從而，用它來描的實(shí)現(xiàn)，從而，用它來描述和自動(dòng)產(chǎn)生所需的各種詞法分析器。述和自動(dòng)產(chǎn)生所需的各種詞法分析器。 3 3。4 4。1 1語言語言LEXLEX的一般描述的一般描述 一個(gè)一個(gè)L

60、EXLEX源程序主要包括兩部分。一部源程序主要包括兩部分。一部分是分是正規(guī)定義式正規(guī)定義式，另一部分是，另一部分是識(shí)別規(guī)則識(shí)別規(guī)則第三章 詞法分析3。4。2超前搜索超前搜索 為超前搜索，我們引進(jìn)一個(gè)正規(guī)式運(yùn)算符為超前搜索，我們引進(jìn)一個(gè)正規(guī)式運(yùn)算符/，用它來指出一個(gè)單詞符號(hào)的截取點(diǎn)。于是關(guān)于用它來指出一個(gè)單詞符號(hào)的截取點(diǎn)。于是關(guān)于“DO”的識(shí)別規(guī)則可以寫為：的識(shí)別規(guī)則可以寫為： DO/(letter|digit)*=(letter|digit)*,動(dòng)作動(dòng)作 這意味著要求詞法分析器這意味著要求詞法分析器L向前掃描到逗號(hào)處，向前掃描到逗號(hào)處，識(shí)別除具有下列詞形的輸入子串：識(shí)別除具有下列詞形的輸入子串