編譯原理課件chap3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、一些特殊的字集，即所謂正規(guī)集。我們使用正規(guī)式這個概念來表示正規(guī)集。正規(guī)式這個概念來表示正規(guī)集。第三章 詞法分析 下面是正規(guī)式和正規(guī)集的定義：下面是正規(guī)式和正規(guī)集的定義： （1）和和 都是都是 上的正規(guī)式，他們所表示的正規(guī)集分上的正規(guī)式，他們所表示的正規(guī)集分別為別為 和和 ； （2）任何）任何a , a是是上的一個正規(guī)式，它所表示的正上的一個正規(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)*（閉包）（閉包） 僅由有限次使用上述三步驟而得到的表達式才是僅由有限次使用上述三步驟而得到的表達式才是上上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是的正規(guī)式。僅由這些正規(guī)式所表示的字集才是上的正上的正規(guī)集。規(guī)集。第三章 詞法分析 通過這一節(jié)的學(xué)習(xí)，根據(jù)給出的簡單正規(guī)式，應(yīng)會通過這一節(jié)的學(xué)習(xí)，根據(jù)給出的簡單正規(guī)式，應(yīng)會寫出其正規(guī)集。寫出其正規(guī)集。 3。1 令令=a, b其正規(guī)式和正規(guī)集如下：其正規(guī)式和正規(guī)集如下： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 ba* 上所有以上所有以b為首后跟著任意多個為首

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

25、)*b等等第三章 詞法分析 3.3.2 確定有限自動機（確定有限自動機（DFA) 確定有限自動機確定有限自動機(DFA)是一個五元式是一個五元式 M= (S, ,s0, F) 其中其中: (1)S是一個有限集，它的每個元素稱為一個狀態(tài)。是一個有限集，它的每個元素稱為一個狀態(tài)。 （2） 是一個有窮字母集，它的每個元素稱為一個是一個有窮字母集，它的每個元素稱為一個輸入字符。輸入字符。 （3） 是一個從是一個從S x 至至S的單值部分映射。的單值部分映射。 (s,a）=S。意味著：當(dāng)現(xiàn)行狀態(tài)為。意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入字符為、輸入字符為a時，將轉(zhuǎn)換到下一個狀態(tài)時，將轉(zhuǎn)換到下一個狀態(tài)S。我們稱。我

26、們稱S為為s的后繼的后繼狀態(tài)。狀態(tài)。 （4）S0 S，是唯一的初態(tài)。，是唯一的初態(tài)。 （5）F S，是一個終態(tài)機（可空），是一個終態(tài)機（可空）第三章 詞法分析 顯然，顯然， DFA可以用一個矩陣表示，該矩可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣陣的行表示狀態(tài)，列表示輸入字符，矩陣元表示元表示(s,a）的值，該矩陣稱為狀態(tài)轉(zhuǎn)換）的值，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。矩陣。 DFA也可以表示成一張（確定的）狀態(tài)也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。假定轉(zhuǎn)換圖。假定DFA M 含有含有m個狀態(tài)個狀態(tài)n個輸個輸入字符，那末，這張圖含有入字符，那末，這張圖含有m個狀態(tài)結(jié)點，個狀態(tài)結(jié)點，每個結(jié)

27、點頂多有每個結(jié)點頂多有n條箭弧射出和別的結(jié)點相條箭弧射出和別的結(jié)點相連接，每條箭弧用連接，每條箭弧用 上的一個不同字符作標(biāo)上的一個不同字符作標(biāo)記，整張圖含有唯一的初態(tài)和若干個（可記，整張圖含有唯一的初態(tài)和若干個（可以是以是0個）終態(tài)結(jié)點。個）終態(tài)結(jié)點。 第三章 詞法分析 對于對于 *中的任何一個字符中的任何一個字符 ，若，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧點的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字等于的標(biāo)記符連接成的字等于 ，則稱，則稱 為為DFA M所所識別識別（讀出讀出或或接受接受）。）。 若若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)的初態(tài)

28、結(jié)點同時又是終態(tài)結(jié)點，則為空字點，則為空字 可以為可以為M所識別。所識別。DFA M所能識別的字的全體記為所能識別的字的全體記為L(M).第三章 詞法分析例例 有有DFAM=(0,1,2,3,a,b, ,0,3)其中：其中： （0,a)=1; （0,b)=2 （1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3; （3,b)=3問：有幾個狀態(tài)？幾個輸入字符？問：有幾個狀態(tài)？幾個輸入字符？并畫出其轉(zhuǎn)換圖。并畫出其轉(zhuǎn)換圖。L(M)=?解：有解：有0，1，2，3共四個狀態(tài)。共四個狀態(tài)。輸入字符為輸入字符為a,b兩個。其狀態(tài)轉(zhuǎn)兩個。其狀態(tài)轉(zhuǎn)換圖如右換圖如右L(M)為在為在

29、 上所有含相繼兩個上所有含相繼兩個a或或相繼兩個相繼兩個b的字。的字。第三章 詞法分析 3。3。3 非確定有限自動機非確定有限自動機(NFA) 一個非確定有限自動機（一個非確定有限自動機（NFA)是一個五是一個五元式元式 M= (S, ,S0, F) 其中其中: (1) S 同同3。3。2的的1（2）同）同3。3。2的的2（3） 是一個從是一個從S x *到到S的子集的映照，的子集的映照，即即 ：S x *2s (4) S0 S,是一個非空的初態(tài)集；是一個非空的初態(tài)集；（5）F S，是一個終態(tài)集（可空），是一個終態(tài)集（可空）第三章 詞法分析 顯然，顯然，NFA也可以表示成一張狀態(tài)轉(zhuǎn)也可以表示成

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

31、中的任何一個字符中的任何一個字符 ，若存在，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧的標(biāo)記符連接成且這條通路上所有箭弧的標(biāo)記符連接成的字（忽略那些標(biāo)記為的字（忽略那些標(biāo)記為 的?。┑扔诘幕。┑扔?，則稱則稱 為為NFA M所所識別識別（讀出讀出或或接受接受）。）。 若若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，或者存在一條某處態(tài)結(jié)點到某各終態(tài)結(jié)或者存在一條某處態(tài)結(jié)點到某各終態(tài)結(jié)點的點的 通路，則為空字通路，則為空字 可以為可以為M所識別。所識別。 這里應(yīng)注意這里應(yīng)注意DFA與與NFA的異同點。的異同點。第三章 詞法分析顯

32、然顯然DFA式式NFA的特例。對于每個的特例。對于每個NFA M存在一存在一個個DFA M”，使，使L(M)=L(M”)。其證明如下（略）。其證明如下（略）（這個證明需要掌握）（這個證明需要掌握） 在這個證明中我想特別強調(diào)的是課本在這個證明中我想特別強調(diào)的是課本P49頁下頁下邊提到的對邊提到的對M的狀態(tài)轉(zhuǎn)換圖進一步施行圖的狀態(tài)轉(zhuǎn)換圖進一步施行圖3。7所示的替換，其中所示的替換，其中k是新引入的狀態(tài)。是新引入的狀態(tài)。第三章 詞法分析 書中的這個圖書中的這個圖3。7同時也是從正規(guī)式畫有限自動同時也是從正規(guī)式畫有限自動機狀態(tài)轉(zhuǎn)換圖的重要方法。對于正規(guī)式中的連接可按機狀態(tài)轉(zhuǎn)換圖的重要方法。對于正規(guī)式中

33、的連接可按1式畫其轉(zhuǎn)換圖，對于或可用式畫其轉(zhuǎn)換圖，對于或可用2式，對于閉包可用式，對于閉包可用3式將式將正規(guī)式轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖靈活使用這些規(guī)則非常重要正規(guī)式轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖靈活使用這些規(guī)則非常重要的。的。 如：正規(guī)式：如：正規(guī)式：R=(a*b)*ba(a|b)* 可以畫為：可以畫為： 第三章 詞法分析其中（其中（a*b)* 和和(a|b)*分別可以看成一個閉包。形成分別可以看成一個閉包。形成A和和G結(jié)點。結(jié)點。 例例：畫出正規(guī)式：畫出正規(guī)式： （a|b)*(aa|bb)(a|b)*對應(yīng)的對應(yīng)的NFA第三章 詞法分析例例：用狀態(tài)子集法構(gòu)造圖：用狀態(tài)子集法構(gòu)造圖3。6的狀態(tài)轉(zhuǎn)的狀態(tài)轉(zhuǎn)換矩陣：換矩陣

34、： 表表3。3 I Ia Ib X,5,1 5,3,1 5,4,1 5,3,1 5,3,1,2,6,Y 5,4,15,4,1 5,3,1 5,4,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y 5,4,1,6,Y5,4,1,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y第三章 詞法分析 表表3。4 對表對表3。3中狀態(tài)子集從新命名后狀態(tài)轉(zhuǎn)中狀態(tài)子集從新命名后狀態(tài)轉(zhuǎn) 換矩換矩陣陣 S a b 0 1 2 1 3 2 2 1 5 3 3 4 4 6 5

35、5 6 5 6 3 4 第三章 詞法分析 圖3。8 未化簡DFA第三章 詞法分析 3.3.4, 3.3.5 正規(guī)文法，正規(guī)式與有限自動機的等價正規(guī)文法，正規(guī)式與有限自動機的等價性性 證明不作要求證明不作要求 3.3.6 確定有限自動機的化簡確定有限自動機的化簡 是本節(jié)應(yīng)掌握的內(nèi)容。是本節(jié)應(yīng)掌握的內(nèi)容。(參看參看P56) 我們這里舉個例子幫助理解這個過程：我們這里舉個例子幫助理解這個過程： 3。6 例例：圖：圖3。8所示的化簡過程是：所示的化簡過程是： 首先把首先把M的狀態(tài)分為兩組：終態(tài)組的狀態(tài)分為兩組：終態(tài)組3，4，5，6，和非終態(tài)組和非終態(tài)組0，1，2 其次考察終態(tài)組，由于其次考察終態(tài)組，由

36、于 3，4，5，6a 3,4,5,6和和 3，4，5，6b 3,4,5,6所以不能再劃分所以不能再劃分第三章 詞法分析 再考察再考察0，1，2 由于由于 0，1，2a1，3，它既不屬于，它既不屬于0，1，2也不屬于也不屬于3，4，5，6，因此應(yīng)將其一分為二，因此應(yīng)將其一分為二，由于由于1態(tài)經(jīng)態(tài)經(jīng)a弧到達弧到達3態(tài)，而且狀態(tài)態(tài)，而且狀態(tài)0，2經(jīng)經(jīng)a弧到弧到達達1態(tài)故應(yīng)把態(tài)故應(yīng)把1態(tài)分出形成態(tài)分出形成1， 0，2。 現(xiàn)在劃分已經(jīng)有現(xiàn)在劃分已經(jīng)有3個組：個組：3，4，5，6，1，0，2。 由于由于0，2b=2,5未包括在上述分組中，故未包括在上述分組中，故0，2應(yīng)一分為二應(yīng)一分為二0，2。 到此四個

37、分組到此四個分組3，4，5，6，0，1，2。每個組都不可再分。每個組都不可再分。 最后，令狀態(tài)最后，令狀態(tài)3代表代表3，4，5，6。把原來。把原來到達到達4，5，6的弧都導(dǎo)入的弧都導(dǎo)入3，并刪除，并刪除4，5，6狀狀態(tài)。得到化簡的態(tài)。得到化簡的DFA.第三章 詞法分析 3.4 3.4 詞法分析器的自動產(chǎn)生詞法分析器的自動產(chǎn)生 我們用正規(guī)式描述單詞符號，并研究我們用正規(guī)式描述單詞符號，并研究如何從正規(guī)式產(chǎn)生識別這些單詞符號的如何從正規(guī)式產(chǎn)生識別這些單詞符號的詞法分析程序。詞法分析程序。 首先介紹一個描述詞法分析器的語言首先介紹一個描述詞法分析器的語言LEXLEX，討論，討論LEXLEX的實現(xiàn)，從

38、而，用它來描的實現(xiàn)，從而，用它來描述和自動產(chǎn)生所需的各種詞法分析器。述和自動產(chǎn)生所需的各種詞法分析器。 3 3。4 4。1 1語言語言LEXLEX的一般描述的一般描述 一個一個LEXLEX源程序主要包括兩部分。一部源程序主要包括兩部分。一部分是分是正規(guī)定義式正規(guī)定義式，另一部分是，另一部分是識別規(guī)則識別規(guī)則第三章 詞法分析3。4。2超前搜索超前搜索 為超前搜索，我們引進一個正規(guī)式運算符為超前搜索，我們引進一個正規(guī)式運算符/，用它來指出一個單詞符號的截取點。于是關(guān)于用它來指出一個單詞符號的截取點。于是關(guān)于“DO”的識別規(guī)則可以寫為：的識別規(guī)則可以寫為： DO/(letter|digit)*=(l

39、etter|digit)*,動作動作 這意味著要求詞法分析器這意味著要求詞法分析器L向前掃描到逗號處，向前掃描到逗號處，識別除具有下列詞形的輸入子串：識別除具有下列詞形的輸入子串： DO/(letter|digit)*=(letter|digit)* 在尋找到這種匹配后，就按識別規(guī)則中斜線所指在尋找到這種匹配后，就按識別規(guī)則中斜線所指處將輸入串截斷，取其前一部分字串作為詞法處將輸入串截斷，取其前一部分字串作為詞法分析器的輸出，而將后一部分歸還輸入串。分析器的輸出，而將后一部分歸還輸入串。3。4。3 LEX的實現(xiàn)的實現(xiàn) 請讀書請讀書P61.第三章 詞法分析例題與習(xí)題解答例題與習(xí)題解答例例3。1寫

40、能被寫能被5整除的十進制整數(shù)的文法及正則表達式。整除的十進制整數(shù)的文法及正則表達式。解：能被解：能被5整除的文法：整除的文法： GZ: Z(+|-)A(0|5)A0|1|2|3|4|5|6|7|8|9|AA如果要求：除零以外不以如果要求：除零以外不以0開頭，責(zé)文法為：開頭，責(zé)文法為： GZ: Z(+|- ) A (0|5) AAB|C B0|C|BB C 0|1|2|3|4|5|6|7|8|9正則表達式：正則表達式：GZ: Z= (+| - )A*(0|5) A(0,1,2,3,4,5,6,7,8,9)第三章 詞法分析例例3。2寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以寫一個文法，使其語言是

41、奇數(shù)集，且每個奇數(shù)不以0開頭。開頭。 解：文法解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D第三章 詞法分析例例3。3寫出能被寫出能被3整除十進制整數(shù)的文法和正則表達式：整除十進制整數(shù)的文法和正則表達式：解：解：能被能被3整除的文法：整除的文法： G=( 0,1,2,3,4,5,6,7,8,9,S, A, B, S, P,) G=( 0,1,2,3,4,5,6,7,8,9,S, A, B, S, P,) 其其中中P P為：為：S - (0|3|6|9)S|S - (0|3|6|9)S|S - (1|4|7)A|(2|5|8)BA - (0|3|6|9)A|(1|4|7)B|(2|5|8)SB - (0|3|6|9)B|(2|5|8)A|(1|4|7)S整則表達式：整則表達式： Z= a*| (bc)*|(cb)*|(a|cibi)*|(ciabi)*(i= 1) a(0,3,6,9) b(1,4,7) c(2,5,8)第三章 詞法分析例3。4：已知有限自動機如圖第三章 詞法分析 解：解：（1） L=W |W 0,1,并且并且W至少有兩個至少有兩個連續(xù)的連續(xù)的1（2） 正則式為正則式為（0|1)*11(0|1)* 正則文法正則文法G(Z)為：為： Z0Z|1Z|1A A 1B|1 B 0B|1B|