編譯原理與技術(shù)講義-第2章

1、青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)第第2章章 詞法分析詞法分析青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)2主要內(nèi)容主要內(nèi)容u詞法分析器的設(shè)計詞法分析器的設(shè)計 u詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn) u正規(guī)表達式正規(guī)表達式 u有限自動機有限自動機u詞法分析的自動生成器詞法分析的自動生成器Lex青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)3詞法分析器在編譯中的位置詞法分析器在編譯中的位置 詞法分析器語法分析器符號表源程序單詞取下一個單詞單詞記號青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原

2、理與技術(shù)42.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u詞法分析器的基本功能詞法分析器的基本功能按照語言的定義規(guī)則，逐個地讀入源程序的按照語言的定義規(guī)則，逐個地讀入源程序的符號，識別出對語言有意義的符號串，即單符號，識別出對語言有意義的符號串，即單詞符號；詞符號；分析單詞記號的屬性，并把單詞記號及其屬分析單詞記號的屬性，并把單詞記號及其屬性填寫在符號表中；性填寫在符號表中；同時把源程序改造成等價的計算機內(nèi)部表示同時把源程序改造成等價的計算機內(nèi)部表示單詞記號，以便編譯的后續(xù)階段使用。單詞記號，以便編譯的后續(xù)階段使用。還要對源程序進行預(yù)處理工作，包括：刪除還要對源程序進行預(yù)處理工作，包括：刪除源程序中

3、的空格、制表符、換行、注釋等不源程序中的空格、制表符、換行、注釋等不影響程序語法、語義的結(jié)構(gòu)。影響程序語法、語義的結(jié)構(gòu)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)52.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u高級程序語言的五種單詞記號：高級程序語言的五種單詞記號：保留字保留字 是程序語言定義的具有固定意義的英文單詞，是程序語言定義的具有固定意義的英文單詞，有時稱為基本字或關(guān)鍵字。例如，在有時稱為基本字或關(guān)鍵字。例如，在C+中，中， char、float、extern、friend、switch、new都是關(guān)鍵字。保都是關(guān)鍵字。保留字一般不能另作它用。留字一般不能另作它

4、用。標識符標識符 表示各種名字的字符串，如變量名、類型名、表示各種名字的字符串，如變量名、類型名、函數(shù)名、對象名等。函數(shù)名、對象名等。運算符運算符 如如+、 、= =、=等。等。常量常量 常量的類型一般有整型、實型、布爾型、文字常量的類型一般有整型、實型、布爾型、文字型等。型等。分界符分界符 如分號、括號、注釋標記如分號、括號、注釋標記/*、*/等。等。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)62.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u詞法分析器的輸出詞法分析器的輸出單詞記號一般采用形式為單詞記號一般采用形式為 的二元式。的二元式。單詞的種別是語法分析需要的信息，通

5、常用單詞的種別是語法分析需要的信息，通常用整數(shù)表示；整數(shù)表示；單詞的屬性值則是編譯的語義分析和代碼生單詞的屬性值則是編譯的語義分析和代碼生成等階段需要的信息。成等階段需要的信息。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)72.1 詞法分析器的設(shè)計詞法分析器的設(shè)計例例2.1：假如保留字的編碼是假如保留字的編碼是1，標識符的為標識符的為2，運算符為，運算符為3，分，分界符為界符為4，整型常量為，整型常量為10，實，實型常量為型常量為11。那么，對于源程。那么，對于源程序代碼：序代碼：for (i = 1, sum = 9.8; i = 100; i+) sum += i

6、3.14;詞法分析器產(chǎn)生的結(jié)果是單詞詞法分析器產(chǎn)生的結(jié)果是單詞記號序列記號序列3，青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)82.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u詞法掃描器與符號表詞法掃描器與符號表 對符號表的操作主要是填表、查詢和更新。對符號表的操作主要是填表、查詢和更新。每當(dāng)詞法分析器識別了一個單詞的時候，第一項工作每當(dāng)詞法分析器識別了一個單詞的時候，第一項工作就是查詢符號表。對于不同的單詞種別，查詢的方式就是查詢符號表。對于不同的單詞種別，查詢的方式和隨后的處理完全不同。例如，對于關(guān)鍵字、分界符和隨后的處理完全不同。例如，對于關(guān)鍵字、分界符和運算符等，只需

7、在各自的符號表中查詢，獲得并記和運算符等，只需在各自的符號表中查詢，獲得并記錄其它屬性值，生成相應(yīng)的單詞記號。錄其它屬性值，生成相應(yīng)的單詞記號。處理常量，特別是處理標識符要復(fù)雜的多，而且僅僅處理常量，特別是處理標識符要復(fù)雜的多，而且僅僅在詞法分析階段是無法獲得一個標識符的所有信息。在詞法分析階段是無法獲得一個標識符的所有信息。當(dāng)詞法掃描器識別了一個標識符的時候，首先查詢關(guān)當(dāng)詞法掃描器識別了一個標識符的時候，首先查詢關(guān)鍵字表，看它是否是關(guān)鍵字；如果不是，還要在標識鍵字表，看它是否是關(guān)鍵字；如果不是，還要在標識符表中查詢，看它是否已經(jīng)存在，如果不存在就把它符表中查詢，看它是否已經(jīng)存在，如果不存在就

8、把它填入標識符表，并填入種別、類型等信息。填入標識符表，并填入種別、類型等信息。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)92.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u詞法分析器的兩種實現(xiàn)模式詞法分析器的兩種實現(xiàn)模式 完全獨立模式和相對獨立模式完全獨立模式和相對獨立模式在完全獨立模式下，詞法分析器作為編譯的在完全獨立模式下，詞法分析器作為編譯的子系統(tǒng)單獨地運行一趟，掃描整個源程序，子系統(tǒng)單獨地運行一趟，掃描整個源程序，把識別的單詞序列以機器內(nèi)碼的形式輸出在把識別的單詞序列以機器內(nèi)碼的形式輸出在一個中間文件上，供為語法分析使用。一個中間文件上，供為語法分析使用。青島大學(xué)

9、信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)102.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u完全獨立模式的好處完全獨立模式的好處編譯程序結(jié)構(gòu)清晰、條理化而且便于高效地實現(xiàn)；編譯程序結(jié)構(gòu)清晰、條理化而且便于高效地實現(xiàn)；在設(shè)計高級語言時能獨立地研究詞法與語法兩個方面在設(shè)計高級語言時能獨立地研究詞法與語法兩個方面的特性；的特性；增強編譯程序的可移植性：可以就同一個語言為不同增強編譯程序的可移植性：可以就同一個語言為不同的機器寫不同的詞法分析器，而只編寫一個共同的語的機器寫不同的詞法分析器，而只編寫一個共同的語法分析，使用這些詞法分析器相同的單詞機內(nèi)表示；法分析，使用這些詞法分析器相同的

10、單詞機內(nèi)表示；把同一個詞法由于單詞記號的語法可以用較簡單的文把同一個詞法由于單詞記號的語法可以用較簡單的文法描述，把詞法和語法分開，就能為這種文法建立有法描述，把詞法和語法分開，就能為這種文法建立有效的特殊方法和自動構(gòu)造技術(shù)。效的特殊方法和自動構(gòu)造技術(shù)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)112.1 詞法分析器的設(shè)計詞法分析器的設(shè)計相對獨立模式：詞法分析器設(shè)計成一個子程相對獨立模式：詞法分析器設(shè)計成一個子程序，每當(dāng)語法分析需要一個單詞的時候，就序，每當(dāng)語法分析需要一個單詞的時候，就調(diào)用該子程序。調(diào)用該子程序。 相對獨立模式的好處：詞法分析器和語法分相對獨立模式

11、的好處：詞法分析器和語法分析器被設(shè)計在同一趟，省去了存放單詞的終析器被設(shè)計在同一趟，省去了存放單詞的終結(jié)文件。結(jié)文件。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)122.1 詞法分析器的設(shè)計詞法分析器的設(shè)計u詞法錯誤的處理詞法錯誤的處理 在詞法分析階段發(fā)現(xiàn)的錯誤統(tǒng)稱為詞法錯誤，在詞法分析階段發(fā)現(xiàn)的錯誤統(tǒng)稱為詞法錯誤，它們大多是單詞拼寫錯誤，這或者是因為書它們大多是單詞拼寫錯誤，這或者是因為書寫錯誤、或者因為鍵入錯誤，例如把關(guān)鍵字寫錯誤、或者因為鍵入錯誤，例如把關(guān)鍵字拼寫錯。拼寫錯。 對詞法錯誤校正的常用策略是修補嘗試，一對詞法錯誤校正的常用策略是修補嘗試，一般包括：般

12、包括：l刪除一個多余的字符；刪除一個多余的字符；l插入一個遺漏的字符；插入一個遺漏的字符；l用一個正確的字符替換一個不正確的字符；用一個正確的字符替換一個不正確的字符；l交換兩個相鄰的字符。交換兩個相鄰的字符。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)132.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn) u輸入的預(yù)處理輸入的預(yù)處理 對于許多程序語言來說，空格、制表符、換對于許多程序語言來說，空格、制表符、換行符等編輯性字符除了出現(xiàn)在文字常量中，行符等編輯性字符除了出現(xiàn)在文字常量中，在其它任何地方的出現(xiàn)都沒有意義，而注釋在其它任何地方的出現(xiàn)都沒有意義，而注釋作為

13、程序的重要文檔幾乎可以出現(xiàn)在程序中作為程序的重要文檔幾乎可以出現(xiàn)在程序中的任何地方。它們的存在可以改善程序的可的任何地方。它們的存在可以改善程序的可讀性和易理解性，卻不影響程序的語法結(jié)構(gòu)讀性和易理解性，卻不影響程序的語法結(jié)構(gòu)和執(zhí)行語義。和執(zhí)行語義。通常在編譯的詞法分析階段被預(yù)處理過程刪通常在編譯的詞法分析階段被預(yù)處理過程刪除掉。除掉。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)142.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u輸入的預(yù)處理輸入的預(yù)處理l掃描器對緩沖區(qū)進行掃描時一般使用兩個指針：一個指向當(dāng)前正在識別的單詞的起始位置，另一個用于向前搜索以尋找該

14、單詞的終點，兩個指針之間的符號串就是要識別的單詞符號。無論掃描緩沖區(qū)設(shè)計的多大都不能保證單詞符號不會超過其邊界。掃描緩沖區(qū)一分為二的兩段置.f o r ( s u m = 0 , i = 1 .搜索指針起點指針.C a r.e e l . 2 .青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)152.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u超前搜索和最長匹配超前搜索和最長匹配 為了識別一個更有意義的單詞符號，在找到了可能是為了識別一個更有意義的單詞符號，在找到了可能是單詞符號的起點或者構(gòu)成了單詞部分時，掃描器并不單詞符號的起點或者構(gòu)成了單詞部分時，掃描器并不滿

15、足，還要繼續(xù)讀入輸入串，看是否能找到由更多符滿足，還要繼續(xù)讀入輸入串，看是否能找到由更多符號所組成的單詞（即最長匹配），有時可能要掃描到號所組成的單詞（即最長匹配），有時可能要掃描到一個可以一個可以“斷句斷句”的符號（超前搜索），才能決定最的符號（超前搜索），才能決定最后一個掃描的符號不屬于之前的符號串所構(gòu)成的單詞。后一個掃描的符號不屬于之前的符號串所構(gòu)成的單詞。超前搜索符號通常是最長匹配單詞的結(jié)束標志，可以超前搜索符號通常是最長匹配單詞的結(jié)束標志，可以是空格符、回車符、制表符等可以被預(yù)處理掉的符號；是空格符、回車符、制表符等可以被預(yù)處理掉的符號；也可能是下一個單詞記號的起始符。也可能是下一個

16、單詞記號的起始符。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)162.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u超前搜索和最長匹配的例子超前搜索和最長匹配的例子在識別在識別“for”的時候，要掃描到左括弧的時候，要掃描到左括弧(時時才知道，它不屬于標識符的符號；才知道，它不屬于標識符的符號；當(dāng)讀到了當(dāng)讀到了，以便構(gòu)造出小于等于，以便構(gòu)造出小于等于“=”或或不等于不等于“”的比較運算符，否則，就構(gòu)造小的比較運算符，否則，就構(gòu)造小于運算符。于運算符。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)172.2 詞法分析器的一種手工實現(xiàn)詞法分析

17、器的一種手工實現(xiàn)u狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是構(gòu)造詞法分析器的一個良好工具，它描狀態(tài)轉(zhuǎn)換圖是構(gòu)造詞法分析器的一個良好工具，它描繪了為得到一個單詞記號，詞法分析器應(yīng)該執(zhí)行的動繪了為得到一個單詞記號，詞法分析器應(yīng)該執(zhí)行的動作。作。狀態(tài)轉(zhuǎn)換圖是一個有向圖，結(jié)點代表狀態(tài)，用圓圈表狀態(tài)轉(zhuǎn)換圖是一個有向圖，結(jié)點代表狀態(tài)，用圓圈表示，內(nèi)部用數(shù)字表示狀態(tài)名稱；示，內(nèi)部用數(shù)字表示狀態(tài)名稱；狀態(tài)之間由箭弧連接，箭弧上有符號作為標記，稱為狀態(tài)之間由箭弧連接，箭弧上有符號作為標記，稱為從箭弧尾的離開狀態(tài)讀入標記符號以后轉(zhuǎn)換到箭弧頭從箭弧尾的離開狀態(tài)讀入標記符號以后轉(zhuǎn)換到箭弧頭的進入狀態(tài)。的進入狀態(tài)。若離開狀態(tài)若

18、離開狀態(tài)s的某個標記為的某個標記為other，則表示離開，則表示離開s的其它的其它箭弧標記以外的任意符號。箭弧標記以外的任意符號。每個狀態(tài)轉(zhuǎn)換圖中的狀態(tài)數(shù)量有限，都有唯一的一個每個狀態(tài)轉(zhuǎn)換圖中的狀態(tài)數(shù)量有限，都有唯一的一個起始狀態(tài)（本書用一個進入的箭頭表示）和至少一個起始狀態(tài)（本書用一個進入的箭頭表示）和至少一個終結(jié)狀態(tài)（用雙圈表示）。終結(jié)狀態(tài)（用雙圈表示）。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)182.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u狀態(tài)轉(zhuǎn)換圖識別或接受一定的輸入符號串狀態(tài)轉(zhuǎn)換圖識別或接受一定的輸入符號串從起始狀態(tài)開始，讀進輸入符號串的一

19、個符從起始狀態(tài)開始，讀進輸入符號串的一個符號號a，沿著狀態(tài)轉(zhuǎn)換標記為，沿著狀態(tài)轉(zhuǎn)換標記為a進入下一個狀態(tài)，進入下一個狀態(tài)，重復(fù)執(zhí)行直到進入終結(jié)狀態(tài)。重復(fù)執(zhí)行直到進入終結(jié)狀態(tài)。即，如果存在一個從起始狀態(tài)到終結(jié)狀態(tài)的即，如果存在一個從起始狀態(tài)到終結(jié)狀態(tài)的路徑，路徑上的標記用連接運算連接在一起路徑，路徑上的標記用連接運算連接在一起形成一個符號串，它和輸入符號串相同，則形成一個符號串，它和輸入符號串相同，則稱該輸入符號串可以接受。如果不能進入任稱該輸入符號串可以接受。如果不能進入任何一個終結(jié)狀態(tài)，則稱該狀態(tài)轉(zhuǎn)換圖不能識何一個終結(jié)狀態(tài)，則稱該狀態(tài)轉(zhuǎn)換圖不能識別或接受這個輸入符號串別或接受這個輸入符號串

20、青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)192.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)digit01letterletter對于符號串var1，有狀態(tài)序列111101rav， 例例2.2： 標識符一般定義為字母打頭的字母數(shù)字序列標識符一般定義為字母打頭的字母數(shù)字序列.青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)202.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)5other=1=032例例2.3：類似語言中的關(guān)系符的狀態(tài)轉(zhuǎn)換圖 。在終結(jié)狀態(tài)加了星號*，表示在狀態(tài)1、2和3都還不能確定它們是否是符合最長匹配準則的單詞記號，

21、還需要在讀入一個字符才能確定。而為實現(xiàn)最長匹配的一個超前搜索符號“其它”則不屬于這個單詞，應(yīng)該推給掃描緩沖區(qū)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)212.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)例例2.4：Pascal語言中數(shù)的狀態(tài)轉(zhuǎn)換圖語言中數(shù)的狀態(tài)轉(zhuǎn)換圖 。在這個復(fù)雜的例子中，狀態(tài)在這個復(fù)雜的例子中，狀態(tài)3、5和和8分別表示識別是整數(shù)、不帶指數(shù)部分分別表示識別是整數(shù)、不帶指數(shù)部分的實數(shù)以及帶有指數(shù)部分的實數(shù)，但是，只能在超前搜索一個其它符號以的實數(shù)以及帶有指數(shù)部分的實數(shù)，但是，只能在超前搜索一個其它符號以后，才能在狀態(tài)后，才能在狀態(tài)9確定識別了

22、一個確定識別了一個Pascal的數(shù)。讀者可以自己驗證例子數(shù)的數(shù)。讀者可以自己驗證例子數(shù)2005，+1998， 81.07，2.003 6，看它們是否能被這個轉(zhuǎn)換圖所接受。，看它們是否能被這個轉(zhuǎn)換圖所接受。3digitdigitotherdigitdigitdigit9814562+, E7+,digitEdigitotherother*青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)222.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u基于狀態(tài)轉(zhuǎn)換圖的詞法分析器的實現(xiàn)基于狀態(tài)轉(zhuǎn)換圖的詞法分析器的實現(xiàn)code表示單詞記號的種別；表示單詞記號的種別；value存放標識符

23、或數(shù)在符號表的入口地址；存放標識符或數(shù)在符號表的入口地址；過程過程getghar(ch)從掃描緩沖區(qū)得到一個搜索符號，從掃描緩沖區(qū)得到一個搜索符號，存儲在變量存儲在變量ch中；中；函數(shù)函數(shù)isLetter(ch)和和isDigit(ch)分別檢查分別檢查ch是否是字是否是字母母/數(shù)字；數(shù)字；函數(shù)函數(shù)lookup(token, table) 在符號表在符號表table中查詢是否中查詢是否包含單詞包含單詞token；insert (token, table)在則把單詞在則把單詞token插入符號表插入符號表table中并返回在符號表的地址；中并返回在符號表的地址；函數(shù)函數(shù)reporterror()

24、報告并簡單處理詞法錯誤。報告并簡單處理詞法錯誤。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)232.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法一根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法一讓狀態(tài)轉(zhuǎn)移對應(yīng)一個讀入字符的語句或函數(shù)，讓狀態(tài)轉(zhuǎn)移對應(yīng)一個讀入字符的語句或函數(shù)，然后與轉(zhuǎn)移上的標記比較，如果相等就進入然后與轉(zhuǎn)移上的標記比較，如果相等就進入轉(zhuǎn)移對應(yīng)的程序段或子程序；否則，調(diào)用錯轉(zhuǎn)移對應(yīng)的程序段或子程序；否則，調(diào)用錯誤處理程序。誤處理程序。多個轉(zhuǎn)移就對應(yīng)分支語句；多個轉(zhuǎn)移就對應(yīng)分支語句；如果轉(zhuǎn)移返回自身，形成一個圈，對應(yīng)程序如果轉(zhuǎn)移返

25、回自身，形成一個圈，對應(yīng)程序段的就是循環(huán)語句。段的就是循環(huán)語句。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)242.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)標識符狀態(tài)轉(zhuǎn)換圖的一個實現(xiàn)標識符狀態(tài)轉(zhuǎn)換圖的一個實現(xiàn)int code, value;char token =”;/ 在開始狀態(tài)0do token = token+ch;/ 不斷讀入字母或數(shù)字，合并成一個標識符 getchar(ch);/ 保持在狀態(tài)1 while (!isLetter(ch) | !isDigit(ch)； / isLetter(ch)和isDigit(ch)分別檢查ch是否是字母/數(shù)字

26、/ 進入結(jié)束開始狀態(tài)2code = lookup(token, keywordsTable); / 在關(guān)鍵字表中查詢token，若它是關(guān)鍵字就返回1if (code= =1) return(1, token);/ 返回關(guān)鍵字的單詞記號，假如關(guān)鍵字種別是1else value=insert(token, identifierTable); / 把token插入標識符表，返回入口地址return (2, value)/ 返回標識符的單詞記號，假如標識符種別是2青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)252.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)u根據(jù)狀態(tài)棧

27、圖編寫詞法掃描器的方法二根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法二采用一個變量來記錄當(dāng)前的狀態(tài)，把狀態(tài)轉(zhuǎn)采用一個變量來記錄當(dāng)前的狀態(tài)，把狀態(tài)轉(zhuǎn)換嵌入到一個循環(huán)體內(nèi)的分支語句中，其中換嵌入到一個循環(huán)體內(nèi)的分支語句中，其中的第一個分支測試當(dāng)前狀態(tài)，而嵌入內(nèi)層的的第一個分支測試當(dāng)前狀態(tài)，而嵌入內(nèi)層的第一個分支語句則對給定的狀態(tài)測試輸入符第一個分支語句則對給定的狀態(tài)測試輸入符號，以決定轉(zhuǎn)移進入的狀態(tài)。號，以決定轉(zhuǎn)移進入的狀態(tài)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)262.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)例例2.5：下圖示意的是識別下圖示意的是識別C風(fēng)格注釋，

28、即形式風(fēng)格注釋，即形式/*.*/，的狀態(tài)轉(zhuǎn)換圖。狀態(tài)，的狀態(tài)轉(zhuǎn)換圖。狀態(tài)2中的標記中的標記other是除是除*之外的其它符號，而從狀態(tài)之外的其它符號，而從狀態(tài)3到狀態(tài)到狀態(tài)2的標記的標記other是除是除*和和/之外的其它符號。之外的其它符號。 413 2other*0/other*青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)272.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)int state = 0;while (state = 0, 1, 2, 3 ) switch state case 0: getchar(ch);if (ch = = /) state

29、 = 1; getchar(ch) ;else reporterror();case 1: getchar(ch);if (ch = = *) state = 2; getchar(ch) ;else reporterror();case 2: getchar(ch);if (ch = = *) state = 3; getchar(ch) ;else getcharch(ch); / 還是在狀態(tài)2case 3: getchar(ch);switch ch case /: state = 4; getchar(ch) ; case *: state =3; getchar(ch) ; defa

30、ult: state = 2if (state = = 4 ) return; else reporterror();青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)28Id-keywordsnumberotherotherotherEAotherotherotherdigitotherinIDstartLNE=*= =other*letter, digitletter23inNum*digitdigit*commentGE=*+*/=+*/digit課本圖2.6:int code, value,;char state = “start”;char token =”;sta

31、te_sets表示所有狀態(tài)名的集合青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)292.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)while (state屬于state_sets) switch state case “comment”: getchar(ch); if (ch = = ) state = “start”; getchar(ch) ; case “start”: getchar(ch);switch ch case isletter(ch): state = “inID”; token = ch; getchar(ch) ; case isdig

32、it(ch): state = “inNum”; token = ch; getchar(ch) ; case ch = = : state = “comment”; getchar(ch) ; case ch = = : state = “GE”; token = ch; getchar(ch) ; case ch = =+ : state = “+” ; token = ch; case ch = = : state = “” ; token = ch; case ch = =* : state = “*” ; token = ch; case ch = =/ : state = “/”

33、; token = ch; default:getchar(ch);/ 過濾掉無用的符號 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)302.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)case “inNum”: while (state屬于inNumber, 2, 3) / 處理數(shù) switch state case “inNum”: switch ch / 處理整數(shù) case isdigit(ch): token = token+ch; getchar(ch) ; case ch = = . : state = “2”; token = token+ch;

34、getchar(ch);default: state = “number”; code=10; / 處理實數(shù)case “2”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else reporterror (); case “3”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else code = 11; state = “number”; case “number”: value = insert (token, identifierTab

35、le); return(code, value); 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)312.2 詞法分析器的一種手工實現(xiàn)詞法分析器的一種手工實現(xiàn)case “inID”: while (isletter(ch) | isdigit(ch) token = token+ch; getchar(ch) ; code = lookup(token, keywordsTable); / 在關(guān)鍵字表中查詢token if (code= =1) return(1, token); / 返回關(guān)鍵字的單詞記號 else value=insert(token, identifi

36、erTable); / 把token插入標識符表 return (2, value); / 返回標識符的單詞記號 case “LNE”: getchar(ch); if (ch = = ) getchar(ch); return(3, “”); if (ch = = =) getchar(ch); return(3, “=”); else return(3, “=”); else return(3, “”); case “+”: getchar(ch); return(3, “+”);case “”: getchar(ch); return(3, “”);case “”: getchar(ch

37、); return(3, “”);case “/”: getchar(ch); return(3, “/”);青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)322.3 正規(guī)表達式正規(guī)表達式 u符號、符號串與符號集合符號、符號串與符號集合 定義定義2.1：字母表是有限的非空的符號集合，：字母表是有限的非空的符號集合，字母表中的元素稱作符號。字母表中的元素稱作符號。例如，二進制數(shù)語言的字母表是例如，二進制數(shù)語言的字母表是0, 1；Java語言的字母表可以說是一切可以打印字符組語言的字母表可以說是一切可以打印字符組成的集合。成的集合。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編

38、譯原理與技術(shù)編譯原理與技術(shù)332.3 正規(guī)表達式正規(guī)表達式定義定義2.2：由字母表中的符號所組成的任何有：由字母表中的符號所組成的任何有限序列稱為符號串。一個符號串所包含符號限序列稱為符號串。一個符號串所包含符號的個數(shù)稱為該符號串的長度。的個數(shù)稱為該符號串的長度。l例如，對于字母表例如，對于字母表 a, b，a、b、aa、ab、ba和和abba都是都是 上的符號串。符號串上的符號串。符號串b、ab和和abba的長度分別是的長度分別是1、2和和4。符號串中符號的排列順序。符號串中符號的排列順序十分重要，上面的十分重要，上面的ab和和ba表示不同的符號串。通表示不同的符號串。通常用小寫的希臘字母常

39、用小寫的希臘字母、等表示符號串。等表示符號串。符號符號的長度表示成的長度表示成|，例如，例如|abba|=4。l允許空符號串，即不包含任何符號的符號串，用允許空符號串，即不包含任何符號的符號串，用希臘字母希臘字母 表示，表示，| |=0。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)342.3 正規(guī)表達式正規(guī)表達式l如果如果x=uv是一個符號串，則稱是一個符號串，則稱u是是x的頭，稱的頭，稱v是是x的尾。當(dāng)我們堆一個符號串的某些部分感興趣、的尾。當(dāng)我們堆一個符號串的某些部分感興趣、堆其它部分不感興趣時，通常忽略調(diào)不感興趣的堆其它部分不感興趣時，通常忽略調(diào)不感興趣的部分，

40、而只保留感興趣的部分。部分，而只保留感興趣的部分。l例如，若我們只關(guān)心符號串例如，若我們只關(guān)心符號串x=t中的符號中的符號t，也，也可以用可以用x=.t.表示；同樣，表示；同樣，x=t和和x=t.這兩種表這兩種表示都只關(guān)注符號的頭時符號示都只關(guān)注符號的頭時符號t。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)352.3 正規(guī)表達式正規(guī)表達式定義定義2.3：設(shè)：設(shè)和和是同一字母表上的符號串，把是同一字母表上的符號串，把的各的各個符號相繼地寫在個符號相繼地寫在之后所的到的符號串稱為之后所的到的符號串稱為和和的的連接（并置），連接（并置），記做。顯然，記做。顯然，|=|+|。

41、例如，字母表例如，字母表 a, b, 0, 1上的符號串上的符號串=bb11、=a00，是是bb11a00，而，而是是a00bb11，而且，而且| = | = 7 =| + | = | +| = 4+3 = 7。顯然，對于任何符號串顯然，對于任何符號串，都有，都有 。 定義定義2.4：設(shè)：設(shè)u是某一字母表上的符號串，把是某一字母表上的符號串，把u自身連自身連接接n次，即次，即=u.u(n個個u)，稱作符號串，稱作符號串u的的n次方冪，次方冪，記做記做=un。例如，例如，u1=u，u2=uu，u4=uuuu。特別地，當(dāng)。特別地，當(dāng)n=0時，時，u0= 。顯然，。顯然，uun-1 = un-1u=

42、 un。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)362.3 正規(guī)表達式正規(guī)表達式定義定義2.5：若集合：若集合A中的所有元素都是某字母表上的符號串，則中的所有元素都是某字母表上的符號串，則稱集合稱集合A是該字母表上的符號集合。是該字母表上的符號集合。字母表上的符號集合通常用大寫字母字母表上的符號集合通常用大寫字母A、B、C等表示。例如，等表示。例如，字母表字母表 a, b, 0, 1上長度為上長度為2的符號串集合的符號串集合A= | =xy，并且，并且x和和y是是 中的一個符號中的一個符號；字母表；字母表 上單詞上單詞B= | 是是a, b中的符中的符號串號串。定義

43、定義2.6：兩個符號串集合：兩個符號串集合A和和B的乘積的乘積AB定義為：定義為：AB=uv | u A并且并且v B。例如，設(shè)例如，設(shè)A=a, b，B=0, 1，那么，那么AB=a0, a1, b0, b1，BA=0a, 1a, 0b, 1b，AA=aa, ab, ba, bb。由于對于任何符號。由于對于任何符號串串x都有都有x xx，所以，所以 A=A =A，但是，對于空集，但是，對于空集，卻，卻有等式有等式A=A=。類似于符號串的方冪，可以定義符號串集合的方冪，特別地，類似于符號串的方冪，可以定義符號串集合的方冪，特別地，定義字母表定義字母表A的方冪為的方冪為A0= ，A1=A，An=

44、An-1 A ( n 0 )， 顯然，若顯然，若u An，則，則| u | = n。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)372.3 正規(guī)表達式正規(guī)表達式定義定義2.7：字母表：字母表 的閉包的閉包 * 0 1. n.，正，正閉包閉包 + 1 2. n. 。例如，對于字母表例如，對于字母表 a, b， += a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, .。顯然，顯然， * 0 +， += * = *。 *表示字母表表示字母表 上所有長度的符號串的集合，包括空上所有長度的符號串的集合，包

45、括空符號串；符號串； +表示長度至少為表示長度至少為1的符號串的集合。的符號串的集合。 +實際上就表示了該字母表所構(gòu)成的語言，句子就是實際上就表示了該字母表所構(gòu)成的語言，句子就是其中的符號串。其中的符號串。對于對于C語言，可以說，語言，可以說，C語言是其字母表，也即基本語言是其字母表，也即基本符號正閉包的真子集。符號正閉包的真子集。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)382.3 正規(guī)表達式正規(guī)表達式例例2.6：令字母表：令字母表L=A, B, ., Z, a, b, ., z，D=0, 1, ., 9，那么，那么LD是字母和數(shù)字的集合；是字母和數(shù)字的集合；LD4

46、表示以字母開頭、跟隨表示以字母開頭、跟隨4個數(shù)字的串的集個數(shù)字的串的集合；合；L(LD)15表示長度為表示長度為16的標識符，即以字母的標識符，即以字母開始的開始的16位的字母和數(shù)字串的集合；位的字母和數(shù)字串的集合；D*表示不含空的數(shù)字串的集合。表示不含空的數(shù)字串的集合。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)392.3 正規(guī)表達式正規(guī)表達式u正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集 字母表字母表 上的正規(guī)表達式用來描述一種稱為正規(guī)集的語言。上的正規(guī)表達式用來描述一種稱為正規(guī)集的語言。定義定義2.8：字母表：字母表 上的正規(guī)表達式（簡稱正規(guī)式）按照下列規(guī)上的正規(guī)表達式（簡稱正規(guī)

47、式）按照下列規(guī)則遞歸地定義：則遞歸地定義：（1） 是是 上的正規(guī)式，它表示的正規(guī)集是上的正規(guī)式，它表示的正規(guī)集是 ；（2）是是 上的正規(guī)式，它表示的正規(guī)集是上的正規(guī)式，它表示的正規(guī)集是；（3） 中的任意符號中的任意符號a都是都是 上的正規(guī)式，它表示的正規(guī)集是上的正規(guī)式，它表示的正規(guī)集是a（4）若）若r和和t都是正規(guī)式，它們所表示的正規(guī)集分別是都是正規(guī)式，它們所表示的正規(guī)集分別是L(r)和和L(t)，那么，那么(r)、r|t 、rt和和 r*都是正規(guī)式，表示的正規(guī)集分別是都是正規(guī)式，表示的正規(guī)集分別是L(r)、L(r)L(t)、L(r)L(t)、( L(r) *。根據(jù)顯然定義有下列等式：根據(jù)顯然

48、定義有下列等式： L(a)=a，L( )= ，L()=，L(r)= L(r)，L(rt)= L(r)L(t)，L(r|t)= L(r)L(t)，L(r*)= ( L(r) *。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)402.3 正規(guī)表達式正規(guī)表達式例例2.7：令字母表：令字母表 =a, b, c，那么，那么(a|b)(a|b)aa, ab, ba, bb；(a|c)*表示所有表示所有a和和c組成的符號串，其中包含空串組成的符號串，其中包含空串 ；(a|c)*b(a|c)*表示只包含一個表示只包含一個b的字母表的字母表 上的所有符上的所有符號串，例如號串，例如b，a

49、bc，baaac，caccb，ccbaaa。最多包含一個最多包含一個b的字母表的字母表 上的符號串的集合可以表上的符號串的集合可以表示成示成(a|c)*| (a|c)*b(a|c)*)，或者，或者(a|c)*(b| )(a|c)*。(a|c)*b(a|c)* b表示的集合是什么呢？它表示只含兩個表示的集合是什么呢？它表示只含兩個b的符號串的集合。的符號串的集合。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)412.3 正規(guī)表達式正規(guī)表達式定義定義2.9：如果兩個正：如果兩個正規(guī)式規(guī)式r與與t表示的正規(guī)表示的正規(guī)集相同，則稱它們的集相同，則稱它們的等價的，記做等價的，記做r

50、=t。正規(guī)式等價的例子如正規(guī)式等價的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 定理解釋r|t = t|r| 的交換律r|(s|t) = (r|s)|tr(st) = (rs)t結(jié)合律r(s|t) = rs | rt(r|s)t = rt | st分配律r = r = rr = r = rr | = r吸收律r* = (r | )*閉包運算和之間的關(guān)系青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)422.3 正規(guī)表達式正規(guī)表達式u擴展的正規(guī)式擴展的正規(guī)式 （1）一個或多次重復(fù)：一元后綴算符）一個或多次重復(fù)：一元后綴算符“+”表示一個或多次重復(fù)，表示一

51、個或多次重復(fù)，即正規(guī)式即正規(guī)式r+表示一個或多個表示一個或多個r的串的集合。這樣，的串的集合。這樣，(0|1)+表示所表示所有二進制數(shù)字的集合，而有二進制數(shù)字的集合，而(0|1)*同時還包含了可串。同時還包含了可串。（2）字符集的范圍：對于字母或數(shù)字的集合，可以使用）字符集的范圍：對于字母或數(shù)字的集合，可以使用a|b|.|z或或0|1|.|9。更簡潔的方式是用方括弧，用連接線表示范圍，這樣，。更簡潔的方式是用方括弧，用連接線表示范圍，這樣，上面的字母或數(shù)字就可以分別表示成上面的字母或數(shù)字就可以分別表示成a-z和和0-9。類似的，。類似的，a|b|c|d可以寫成可以寫成a-d或者或者abcd。標

52、識符是字母打頭的字母數(shù)字。標識符是字母打頭的字母數(shù)字串，可以表示成串，可以表示成A-Za-z A-Za-z0-9*。（3）零個或一個：一元后綴算符）零個或一個：一元后綴算符“?”表示零個或一個，表示零個或一個，r?是是r| 的的縮寫。帶符號的整數(shù)可以寫成縮寫。帶符號的整數(shù)可以寫成(+| )?1-90-9*青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)432.3 正規(guī)表達式正規(guī)表達式如果正規(guī)式很長，可以給它命名，使它們可如果正規(guī)式很長，可以給它命名，使它們可以像普通的符號一樣，在隨后的正規(guī)式中使以像普通的符號一樣，在隨后的正規(guī)式中使用這些名字來引用相應(yīng)的正規(guī)式，以便得到用這

53、些名字來引用相應(yīng)的正規(guī)式，以便得到簡潔的正規(guī)式。簡潔的正規(guī)式。如果如果r如是字母表如是字母表 上的正規(guī)式，那么正規(guī)定上的正規(guī)式，那么正規(guī)定義的形式是：義的形式是：name r。這樣，正規(guī)式。這樣，正規(guī)式r的名的名字字name就可以像就可以像 中的符號一樣，在以后構(gòu)中的符號一樣，在以后構(gòu)造造 上正規(guī)式的時候使用。上正規(guī)式的時候使用。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)442.3 正規(guī)表達式正規(guī)表達式例例2.8：Pascal語言的標識符集合是字母開頭的語言的標識符集合是字母開頭的字母數(shù)字串，下面就是這個集合的正規(guī)定義：字母數(shù)字串，下面就是這個集合的正規(guī)定義：lett

54、er A-Za-zdigit 0-9identifier letter( letter| digit )*青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)452.3 正規(guī)表達式正規(guī)表達式例例2.9：Pascal語言的數(shù)是語言的數(shù)是2005，+1998， 81.07，2.003 6這樣的串，即由整數(shù)、小數(shù)和指數(shù)三個部分這樣的串，即由整數(shù)、小數(shù)和指數(shù)三個部分組成。小數(shù)和指數(shù)部分是可選的，其中指數(shù)標記組成。小數(shù)和指數(shù)部分是可選的，其中指數(shù)標記E后后面可以有面可以有+或或 ，再跟上一個或多個數(shù)字，而小數(shù)點，再跟上一個或多個數(shù)字，而小數(shù)點之后必須至少有一個數(shù)字。下面就是之后必須至少有

55、一個數(shù)字。下面就是Pascal語言的數(shù)語言的數(shù)的集合的正規(guī)定義：的集合的正規(guī)定義：digit 0-9digits digit digit*signed + | fraction (.digits)?exponent (E(signed)?digits)?number signed? digits fraction exponent青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)462.3 正規(guī)表達式正規(guī)表達式u正規(guī)表達式的實現(xiàn)和應(yīng)用正規(guī)表達式的實現(xiàn)和應(yīng)用正規(guī)表達式實際上是描述和識別一組字符串的模板正規(guī)表達式實際上是描述和識別一組字符串的模板（模式），它包含字符、元符號（如表

56、示重復(fù)的（模式），它包含字符、元符號（如表示重復(fù)的*和選擇符和選擇符|）和一些具有特殊意義的符號。這個模板）和一些具有特殊意義的符號。這個模板決定什么樣的字符串屬于某一個集合。決定什么樣的字符串屬于某一個集合。正規(guī)表達式在處理文本方面具有強大的能力，它在正規(guī)表達式在處理文本方面具有強大的能力，它在計算機領(lǐng)域的應(yīng)用不僅僅局限于構(gòu)造編譯器的詞法計算機領(lǐng)域的應(yīng)用不僅僅局限于構(gòu)造編譯器的詞法掃描器，其它著名的應(yīng)用還包括掃描器，其它著名的應(yīng)用還包括UNIX操作系統(tǒng)的操作系統(tǒng)的命令工具如命令工具如grep，處理復(fù)雜文本分析與操作的腳本，處理復(fù)雜文本分析與操作的腳本語言語言Perl，Tcl，Python，P

57、HP和和awk以及通用程序以及通用程序開發(fā)編輯器開發(fā)編輯器emacs。由于正規(guī)表達式的重要而廣泛的應(yīng)用，由于正規(guī)表達式的重要而廣泛的應(yīng)用，Java語言通語言通過包過包java.util.regex還對正規(guī)表達式的處理提供了直還對正規(guī)表達式的處理提供了直接支持。接支持。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)472.4 有限自動機有限自動機 u為什么引入有限自動機為什么引入有限自動機確定的有限自動機和不確定的有限自動機都確定的有限自動機和不確定的有限自動機都能識別正規(guī)集，即它們識別的語言正好就是能識別正規(guī)集，即它們識別的語言正好就是正規(guī)式所能表達的語言，而且在識別語

58、言的正規(guī)式所能表達的語言，而且在識別語言的能力上，它們完全等價。能力上，它們完全等價。但是，實現(xiàn)這兩類有限狀態(tài)機的效率不同，但是，實現(xiàn)這兩類有限狀態(tài)機的效率不同，用它們構(gòu)造的詞法分析器在識別語言中單詞用它們構(gòu)造的詞法分析器在識別語言中單詞記號的效率方面也有顯著的差別。記號的效率方面也有顯著的差別。 正規(guī)式不確定的有限自動機確定的有限自動機詞法分析器青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)482.4 有限自動機有限自動機u確定的有限自動機確定的有限自動機 DFA定義定義2.10：一個確定的有限自動機：一個確定的有限自動機DFA M是五元組是五元組，其中：，其中：（1）

59、S是非空的有限的狀態(tài)集合；是非空的有限的狀態(tài)集合；（2） 是非空的輸入字母表；是非空的輸入字母表；（3）T是部分單值映射是部分單值映射S S，又稱轉(zhuǎn)移函數(shù)；，又稱轉(zhuǎn)移函數(shù)；T(s1, a)= s2表示輸入符號表示輸入符號a時，把狀態(tài)時，把狀態(tài)s1轉(zhuǎn)換到轉(zhuǎn)換到s2，成，成為當(dāng)前狀態(tài)；為當(dāng)前狀態(tài)；（4）s0 S，是唯一的起始狀態(tài)；，是唯一的起始狀態(tài)；（5）F S，是非空的終結(jié)狀態(tài)。，是非空的終結(jié)狀態(tài)。被被M接受或識別的語言，記做接受或識別的語言，記做L(M)，定義為字符串，定義為字符串的集合，其中每個的集合，其中每個ci，并且存在狀態(tài)序列，并且存在狀態(tài)序列s1=T(s0, c1), s2=T(s1

60、, c2), . , sn=T(sn-1, cn)，sn F。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)492.4 有限自動機有限自動機例例2.10：一個有限自動機：一個有限自動機DFA N= ，其中，其中T的定義如下的定義如下:T(A, +)=BT(A, )=BT(A, )=CT(A, d)=DT(B, )=DT(B, d)=CT(C, )ET(C, d)=CT(D, d)E T(E, d)E狀態(tài)狀態(tài)A是起始狀態(tài)，是起始狀態(tài)，E是終結(jié)狀態(tài)。是終結(jié)狀態(tài)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)502.4 有限自動機有限自動機轉(zhuǎn)換函數(shù)可以