天津大學(xué)編譯原理講義-Part3詞法分析1

1、Part3Part3詞法分析詞法分析授課：胡靜授課：胡靜內(nèi)容提要內(nèi)容提要詞法分析器的作用詞法分析器的作用詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)狀態(tài)圖狀態(tài)圖詞法分析程序的自動(dòng)生成詞法分析程序的自動(dòng)生成有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)一個(gè)簡(jiǎn)單的編譯器結(jié)構(gòu)一個(gè)簡(jiǎn)單的編譯器結(jié)構(gòu)簡(jiǎn)單的前端結(jié)構(gòu)簡(jiǎn)單的前端結(jié)構(gòu)編譯前端是如何進(jìn)行工作的編譯前端是如何進(jìn)行工作的編譯前端是如何進(jìn)行工作的編譯前端是如何進(jìn)行工作的第一步：詞法分析第一步：詞法分析詞法分析器在編譯器中的位置詞法分析器在編譯器中的位置詞法分析是編譯的第一階段。其任務(wù)是從左到右逐字的對(duì)源詞法分析是編譯的第一階段。其任務(wù)是從左到右逐字的對(duì)源程序進(jìn)行掃描，產(chǎn)生一

2、個(gè)一個(gè)的單詞符號(hào)，把作為字符串的程序進(jìn)行掃描，產(chǎn)生一個(gè)一個(gè)的單詞符號(hào)，把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。源程序改造成為單詞符號(hào)串的中間程序。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行 。也。也可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程序調(diào)用可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器符號(hào)表符號(hào)表源程序源程序記號(hào)記號(hào)取下一取下一個(gè)記號(hào)個(gè)記號(hào)詞法分析程序的功能詞法分析程序的功能詞法分析：根據(jù)詞法

3、規(guī)則識(shí)別及組合單詞，進(jìn)行詞法檢查詞法分析：根據(jù)詞法規(guī)則識(shí)別及組合單詞，進(jìn)行詞法檢查對(duì)數(shù)字常數(shù)完成數(shù)字字符串到二進(jìn)制數(shù)值的轉(zhuǎn)換對(duì)數(shù)字常數(shù)完成數(shù)字字符串到二進(jìn)制數(shù)值的轉(zhuǎn)換刪去空格字符和注釋刪去空格字符和注釋詞法分析器的輸出形式詞法分析器的輸出形式 詞法分析器所輸出的單詞符號(hào)常常表示成如下的二元詞法分析器所輸出的單詞符號(hào)常常表示成如下的二元式：式：（單詞種別，單詞符號(hào)的屬性值）（單詞種別，單詞符號(hào)的屬性值）單詞符號(hào)的屬性信息是指單詞符號(hào)的特性或特征，屬性單詞符號(hào)的屬性信息是指單詞符號(hào)的特性或特征，屬性值則是反應(yīng)特性和特征的值。值則是反應(yīng)特性和特征的值。對(duì)于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信息的符號(hào)表項(xiàng)的

4、對(duì)于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信息的符號(hào)表項(xiàng)的指針作為其屬性值指針作為其屬性值對(duì)于某個(gè)常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為其屬對(duì)于某個(gè)常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為其屬性值。性值。 單詞符號(hào)分類舉例單詞符號(hào)分類舉例 單詞符號(hào)單詞符號(hào) 種別編碼種別編碼助憶符助憶符DIMDIM1 1$DIM$DIMIFIF2 2$IF$IFDODO3 3$DO$DOSTOPSTOP4 4$STOP$STOPENDEND5 5$END$END標(biāo)識(shí)符標(biāo)識(shí)符6 6$ID$ID常數(shù)常數(shù)7 7$INT$INT單詞符號(hào)單詞符號(hào)種別編碼種別編碼助憶符助憶符= =8 8$ASSIGN$ASSIGN+ +9 9$PLUS$

5、PLUS* *1010$STAR$STAR* * *1111$POWER$POWER, ,1212$COMMA$COMMA( (1313$LPAR$LPAR) )1414$RPAR$RPAR運(yùn)算符可采用一字一種的分運(yùn)算符可采用一字一種的分法。也可以把具有一定共性法。也可以把具有一定共性的運(yùn)算符視為一種的運(yùn)算符視為一種 界符一般用一符一種的分法。界符一般用一符一種的分法。分類方法分類方法: :關(guān)鍵字：可將關(guān)鍵字：可將其全體視為一其全體視為一種，也可以一種，也可以一字一種。后者字一種。后者更方便。更方便。標(biāo)識(shí)符：一般標(biāo)識(shí)符：一般統(tǒng)歸為一種統(tǒng)歸為一種 常數(shù)則宜按照常數(shù)則宜按照類型（整型、類型（整型、

6、實(shí)型、布爾型實(shí)型、布爾型等）分種等）分種單詞符號(hào)輸出例子單詞符號(hào)輸出例子對(duì)于對(duì)于C+語(yǔ)言的代碼：語(yǔ)言的代碼：while (i = j) i-;經(jīng)詞法分析器處理后，應(yīng)該成為：經(jīng)詞法分析器處理后，應(yīng)該成為：=, -詞法分析中的錯(cuò)誤詞法分析中的錯(cuò)誤詞法分析器不能從全局的角度考察源程序，所以能在詞法分析器不能從全局的角度考察源程序，所以能在詞法分析階段發(fā)現(xiàn)的錯(cuò)誤是有限的。詞法分析階段發(fā)現(xiàn)的錯(cuò)誤是有限的。主要是不符合合主要是不符合合法標(biāo)識(shí)符拼寫(xiě)的錯(cuò)誤。法標(biāo)識(shí)符拼寫(xiě)的錯(cuò)誤。 例如，如果詞法分析器第一次碰到如下的例如，如果詞法分析器第一次碰到如下的C語(yǔ)言程序：語(yǔ)言程序：fi(a=f(x)詞法分析器無(wú)法區(qū)別詞

7、法分析器無(wú)法區(qū)別fi究竟是關(guān)鍵字究竟是關(guān)鍵字if的錯(cuò)誤拼寫(xiě)還的錯(cuò)誤拼寫(xiě)還是一個(gè)未聲明的函數(shù)標(biāo)識(shí)符。由于是一個(gè)未聲明的函數(shù)標(biāo)識(shí)符。由于fi是合法的標(biāo)識(shí)符，是合法的標(biāo)識(shí)符，詞法分析器必須返回該標(biāo)識(shí)符的記號(hào)，讓編譯器的其詞法分析器必須返回該標(biāo)識(shí)符的記號(hào)，讓編譯器的其他階段去處理這種錯(cuò)誤。他階段去處理這種錯(cuò)誤。 詞法分析中的錯(cuò)誤恢復(fù)詞法分析中的錯(cuò)誤恢復(fù)在詞法分析階段對(duì)錯(cuò)誤進(jìn)行糾正的假設(shè)前提：大多數(shù)詞法錯(cuò)在詞法分析階段對(duì)錯(cuò)誤進(jìn)行糾正的假設(shè)前提：大多數(shù)詞法錯(cuò)誤是多、漏或錯(cuò)了一個(gè)字符或者相鄰的兩個(gè)字符錯(cuò)位的結(jié)果。誤是多、漏或錯(cuò)了一個(gè)字符或者相鄰的兩個(gè)字符錯(cuò)位的結(jié)果。 對(duì)錯(cuò)誤進(jìn)行修補(bǔ)最直觀的策略是看：對(duì)錯(cuò)誤進(jìn)

8、行修補(bǔ)最直觀的策略是看：剩余輸入的前綴能否通剩余輸入的前綴能否通過(guò)上面的一個(gè)變換變成一個(gè)合法的詞素。過(guò)上面的一個(gè)變換變成一個(gè)合法的詞素。最簡(jiǎn)單的錯(cuò)誤恢復(fù)策略是最簡(jiǎn)單的錯(cuò)誤恢復(fù)策略是“緊急方式緊急方式”恢復(fù)，即反復(fù)刪除掉恢復(fù)，即反復(fù)刪除掉剩余輸入最前面的字符，直到詞法分析器能發(fā)現(xiàn)一個(gè)正確的剩余輸入最前面的字符，直到詞法分析器能發(fā)現(xiàn)一個(gè)正確的記號(hào)為止。記號(hào)為止。其他的恢復(fù)動(dòng)作包括：刪除一個(gè)多余的字符、插入一個(gè)遺漏其他的恢復(fù)動(dòng)作包括：刪除一個(gè)多余的字符、插入一個(gè)遺漏的字符、用一個(gè)正確的字符代替一個(gè)不正確的字符、交換兩的字符、用一個(gè)正確的字符代替一個(gè)不正確的字符、交換兩個(gè)相鄰的字符個(gè)相鄰的字符 詞法分

9、析器的設(shè)計(jì)與實(shí)現(xiàn)詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)輸入、預(yù)處理和單詞的識(shí)別（超前搜索）輸入、預(yù)處理和單詞的識(shí)別（超前搜索）預(yù)處理，主要是針對(duì)空白符、跳格符、回車符和換行符等編預(yù)處理，主要是針對(duì)空白符、跳格符、回車符和換行符等編輯性字符的處理。輯性字符的處理。 輸入輸入輸入緩沖區(qū)輸入緩沖區(qū)列表列表預(yù)處理子程序預(yù)處理子程序掃描器掃描器掃描緩沖區(qū)掃描緩沖區(qū)單詞符號(hào)單詞符號(hào)雙緩沖區(qū)技術(shù)雙緩沖區(qū)技術(shù)關(guān)鍵字的識(shí)別關(guān)鍵字的識(shí)別 像像FORTRAN這樣的語(yǔ)言，關(guān)鍵字不加以特殊保護(hù)，這樣的語(yǔ)言，關(guān)鍵字不加以特殊保護(hù)，關(guān)鍵字和用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間沒(méi)有特殊的關(guān)鍵字和用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間沒(méi)有特殊的界符做間隔。這使

10、得關(guān)鍵字的識(shí)別甚為麻煩。界符做間隔。這使得關(guān)鍵字的識(shí)別甚為麻煩。1.DO99K = 1, 102.IF(5.EQ.M) I = 103.DO99K = 1.104.IF(5.EQ.M) = 55其中，語(yǔ)句其中，語(yǔ)句1和和2是是DO和和IF語(yǔ)句，他們都是以基本字開(kāi)語(yǔ)句，他們都是以基本字開(kāi)頭的，語(yǔ)句頭的，語(yǔ)句3和和4是賦值語(yǔ)句，都是以用戶自定義的標(biāo)是賦值語(yǔ)句，都是以用戶自定義的標(biāo)識(shí)符開(kāi)頭的。識(shí)符開(kāi)頭的。 其他單詞符號(hào)的識(shí)別其他單詞符號(hào)的識(shí)別標(biāo)識(shí)符的識(shí)別標(biāo)識(shí)符的識(shí)別多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開(kāi)頭的多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開(kāi)頭的“字母字母/數(shù)字?jǐn)?shù)字”串，而且在程序串，而且在程序中標(biāo)識(shí)符的出現(xiàn)都后跟這算符或者

11、界符。因此標(biāo)識(shí)符的識(shí)別沒(méi)有中標(biāo)識(shí)符的出現(xiàn)都后跟這算符或者界符。因此標(biāo)識(shí)符的識(shí)別沒(méi)有太大的困難。太大的困難。常數(shù)的識(shí)別常數(shù)的識(shí)別基本來(lái)講常數(shù)的識(shí)別也是很直接的，有些需要用到基本來(lái)講常數(shù)的識(shí)別也是很直接的，有些需要用到超前搜索超前搜索。如如5.E08和和5.EQ.M。算符和界符的識(shí)別算符和界符的識(shí)別詞法分析器將那些多個(gè)字符復(fù)合成的算符和界符詞法分析器將那些多個(gè)字符復(fù)合成的算符和界符(如如+、-、=)拼合成一個(gè)單詞符號(hào)。因?yàn)檫@些單詞符號(hào)是不可分的整體，若分拼合成一個(gè)單詞符號(hào)。因?yàn)檫@些單詞符號(hào)是不可分的整體，若分劃開(kāi)來(lái)，便失去了原來(lái)的意義。劃開(kāi)來(lái)，便失去了原來(lái)的意義。這里需要超前搜索。這里需要超前搜索

12、。狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是一張有限方向圖；狀態(tài)轉(zhuǎn)換圖是一張有限方向圖；結(jié)點(diǎn)代表狀態(tài)，用圓圈表示；結(jié)點(diǎn)代表狀態(tài)，用圓圈表示；狀態(tài)之間用箭弧連接，狀態(tài)之間用箭弧連接，箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)（即箭弧始結(jié)箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中一個(gè)被人為是初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)中一個(gè)被人為是初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)（用雙圓圈表示）。（用雙圓圈表示）。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接收）一定的

13、字符串。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接收）一定的字符串。狀態(tài)轉(zhuǎn)換圖示例狀態(tài)轉(zhuǎn)換圖示例終態(tài)結(jié)點(diǎn)上打了一個(gè)星號(hào)終態(tài)結(jié)點(diǎn)上打了一個(gè)星號(hào)*，意味著多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符部分的字，意味著多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符部分的字符，應(yīng)該把它退還給輸入串。符，應(yīng)該把它退還給輸入串。如果在狀態(tài)如果在狀態(tài)0時(shí)的輸入不能符合任何一條轉(zhuǎn)換路徑，那么就說(shuō)明這個(gè)轉(zhuǎn)換時(shí)的輸入不能符合任何一條轉(zhuǎn)換路徑，那么就說(shuō)明這個(gè)轉(zhuǎn)換圖工作不成功，不能識(shí)別出標(biāo)識(shí)符。圖工作不成功，不能識(shí)別出標(biāo)識(shí)符。 轉(zhuǎn)換圖示例轉(zhuǎn)換圖示例識(shí)別整數(shù)的轉(zhuǎn)換圖識(shí)別整數(shù)的轉(zhuǎn)換圖識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖實(shí)例狀態(tài)轉(zhuǎn)換圖實(shí)例其中的假設(shè)條件是：其中的假設(shè)條

14、件是：1.1.關(guān)鍵字都是保留字，不允許使用他們作為自己關(guān)鍵字都是保留字，不允許使用他們作為自己定義的標(biāo)識(shí)符定義的標(biāo)識(shí)符2.2.將關(guān)鍵字作為一類特殊標(biāo)識(shí)符來(lái)處理。把它們將關(guān)鍵字作為一類特殊標(biāo)識(shí)符來(lái)處理。把它們預(yù)先安排在一張表格中。預(yù)先安排在一張表格中。3.3.再次，如果關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒(méi)有確再次，如果關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒(méi)有確定的運(yùn)算符或界符做間隔，則必須至少用一個(gè)空定的運(yùn)算符或界符做間隔，則必須至少用一個(gè)空白符做間隔。白符做間隔。狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)ch：字符變量，存放最新讀進(jìn)的源程序字符：字符變量，存放最新讀進(jìn)的源程序字符strToken：字符數(shù)組，存放構(gòu)成單詞符號(hào)的

15、字符串：字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串GetChar：子程序過(guò)程，將下一個(gè)輸入字符讀到：子程序過(guò)程，將下一個(gè)輸入字符讀到ch中，搜索指中，搜索指示器前移一個(gè)字符位置。示器前移一個(gè)字符位置。GetBC：子程序過(guò)程，檢查：子程序過(guò)程，檢查ch中的字符是否為空白。如果是，中的字符是否為空白。如果是，則調(diào)用則調(diào)用GetChar，直至，直至ch中進(jìn)入一個(gè)非空白字符。中進(jìn)入一個(gè)非空白字符。Concat：子程序過(guò)程，將：子程序過(guò)程，將ch中的字符連接到中的字符連接到strToken之后。之后。IsLetter和和IsDigit： 布爾函數(shù)過(guò)程，它們分別判斷布爾函數(shù)過(guò)程，它們分別判斷ch中的字符中的字符是

16、否為字母和數(shù)字。是否為字母和數(shù)字。Reserve：整型函數(shù)過(guò)程，對(duì)：整型函數(shù)過(guò)程，對(duì)strToken中的字符串查找保留字中的字符串查找保留字表，若它是一個(gè)保留字則返回它的編碼，否則返回表，若它是一個(gè)保留字則返回它的編碼，否則返回0值。值。Retract：子程序過(guò)程，將搜索指示器回調(diào)一個(gè)字符位置，將：子程序過(guò)程，將搜索指示器回調(diào)一個(gè)字符位置，將ch置為空白字符置為空白字符狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)( (續(xù)續(xù)1)1)InsertId：整型函數(shù)過(guò)程，將：整型函數(shù)過(guò)程，將strToken中的標(biāo)識(shí)符插中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針入符號(hào)表，返回符號(hào)表指針I(yè)nsertConst：整型函數(shù)過(guò)程，

17、將：整型函數(shù)過(guò)程，將strToken中的常數(shù)插中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。入常數(shù)表，返回常數(shù)表指針。 關(guān)于出錯(cuò)處理的一些說(shuō)明：關(guān)于出錯(cuò)處理的一些說(shuō)明：如果后面還有狀態(tài)圖，出現(xiàn)在這個(gè)地方的代碼應(yīng)為：如果后面還有狀態(tài)圖，出現(xiàn)在這個(gè)地方的代碼應(yīng)為：將搜索指示器回退一個(gè)位置，并令下一個(gè)狀態(tài)圖開(kāi)始將搜索指示器回退一個(gè)位置，并令下一個(gè)狀態(tài)圖開(kāi)始工作。工作。如果后面沒(méi)有其他的狀態(tài)圖，則出現(xiàn)在上述位置的代如果后面沒(méi)有其他的狀態(tài)圖，則出現(xiàn)在上述位置的代碼應(yīng)該進(jìn)行真正的出錯(cuò)處理，報(bào)告源程序含有非法符碼應(yīng)該進(jìn)行真正的出錯(cuò)處理，報(bào)告源程序含有非法符號(hào)，并進(jìn)行善后處理。號(hào)，并進(jìn)行善后處理。 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)( (續(xù)續(xù)1)1)對(duì)于不含回路的分叉結(jié)點(diǎn)來(lái)說(shuō)，可讓它對(duì)應(yīng)一個(gè)對(duì)于不含回路的分叉結(jié)點(diǎn)來(lái)說(shuō)，可讓它對(duì)應(yīng)一個(gè)switch語(yǔ)句，語(yǔ)句，或一組或一組ifthenelse語(yǔ)句語(yǔ)句GetChar()i