編譯原理（4）第二章 詞法分析

接下來的幾章，就是對編譯過程的每個步驟的分析。先來詞法分析。

詞法分析的任務：從左至右逐個字元地掃描源程序，產生一個個單詞符號，把源程序的字元串改造成為單詞符號串，也就是我們之前說的中間程序。

詞法分析器/掃描器：執行詞法分析的程序。

詞法分析器/掃描器的功能：輸入源程序（串），輸出單詞符號。

2.1對詞法分析器的要求

2.1.1詞法分析器的功能和輸出形式

功能：輸入源程序，輸出單詞符號。

單詞符號：一個程序語言的基本語法符號，五種。

單詞符號的表示形式：詞法分析器所輸出的單詞符號常常表示成二元式（單詞種類，單詞自身的值）。

單詞種別可用以下形式表示：

1.一類單詞統一用一個整數值代表其屬性。例如：1代表關鍵字，2代表標誌符等；

2.每個單詞一個類別。例如：1代表BEGIN,2代表END等。

單詞自身的值可以表示成：常量的二進位表示；常量、變數等在符號表中的地址碼等等。

注意：一個語言的單詞符號怎麼分，分幾種，怎麼編碼，是一個技術問題。標誌符一般同歸為一種，常數適合按類型（整、實、布爾）分。關鍵字可以全體視為一種，也可以一字一種，運算符可以一符一種，也可以把具有一定共性的視為一種，界符一般一符一種。如何改進分種主要取決於處理上的方便。

一符一種分的話，就沒有必要有單詞自身值了，本身種類就已經反應了值，否則要查符號表。

這是例子：

2.1.2詞法分析和語法分析的關係

在上一章有個「遍「的概念，我們當時講，可能有時候不需要五遍掃描。這裡就從遍數上來分析一下scanner和語法分析的關係。

第一種，如果把詞法分析作為單獨的一遍：

從外存中讀取到源程序的字元串，然後分析輸出單詞符號，最後語法分析器就接收到了這個分析好的單詞串。

第二種，把詞法分析器裝在語法分析器中：

這樣一上來就開始語法分析，遇到一部分字元，那沒辦法，語法分析不認識，會調用作為子程序的詞法分析器，然後對scanner分析的結果單詞串，進行語法分析，再去讀下一串字元，直到分析完了整個源程序的串。

2.2詞法分析器的設計

我們這裡課程的設計前提是把scanner裝在語法分析器裡面。

2.2.1預處理

詞法分析器的第一步是輸入源程序文本，輸入串一般放在一個緩衝區中，叫輸入緩衝區，詞法分析的工作（識別輸入串輸出單詞符號）可以直接在這個緩衝區進行。但在許多情況下，把輸入串預處理一下，對單詞符號的識別工作將會比較方便。

上圖中必要性裡面舉的這些編輯性字元啊還有其他一些注釋啊，它們都不是程序的必要組成部分，它們存在只是為了改善程序的易讀性，讓程序更易於理解，程序員寫注釋是一個好習慣，但編譯器不需要這些，預處理就可以剔除這些。（舉個例子，比如有些語言把空白符（一個或多個）當做單詞符號之間的間隔，即界符，預處理的工作就是把多個空白結合成一個，又比如注釋僅僅是為了讓人理解程序，預處理就會刪掉這些注釋）

我們設想構造一個預處理子程序，能夠完成這樣的任務。詞法分析器調用它時，它就處理一串確定長度的輸入字元，並將其裝進詞法分析器指定的緩衝區中（稱為掃描緩衝區），這樣分析器就可以在掃描緩衝區中直接進行預處理之後的單詞符號的識別，而免去了很多繁瑣事務。如下圖：

分析器對掃描緩衝區進行掃描時一般用兩個指示器，一個指向當前正在識別的單詞的開始位置（新單詞的首字元）叫起點指示器，另一個用於向後搜索以尋找單詞的終點，叫搜索指示器。搜索指示器搜索到並分析出 這是某個單詞的終點時候，就把兩個指示器之間包括的串視為一個單詞符號。但是要考慮一個問題，我們的掃描緩衝區的大小是有限的，有可能出現一個情況，就是從輸入緩衝區預處理完的串裝進掃描緩衝區時候，一次沒有裝完（往往不可能一次就幹完），末尾的某個單詞被分開了，比如GOTO，只有GO進去了。

這就比較棘手了。為了解決這個問題，掃描緩衝區最好使用一個如下所示的一分為二的區域：

我們這裡假定每個半區可容120個字元，而這兩個搬去又是互補使用的，如果搜索指示器從單詞起點出發搜索到搬去邊緣還沒有達到單詞終點，就會調用預處理程序，把後續的120個輸入字元裝進另一個半區，搜索指示器進去那個半區再掃描就好了，這就不存在斷掉的問題了，相當於是個循環鏈表。而還有沒有可能出現意外呢？當然可能，加入某個標誌符或者常數的長度超過120了，這神仙也沒辦法，所以應該在長度上加以一定的限制。

2.2.2單詞符號的識別：超前搜索

上面我們了解了掃描緩衝區和預處理的一些知識，我們再考慮一下這些單詞符號應該怎麼掃描，就是說詞法分析器如何確定斷詞的，如何知道那就是個單詞符號，舉個例子，比如看到I了，應該不會停下，往後走看到個F，你敢說就是IF嗎，這是有問題的，他需要繼續往下掃描，看到個括弧，OK，可以確定前面是個IF，對於IF以外其他的更複雜的關鍵字，這看上去還是不太容易的一件事情。下面我們就學習單詞符號識別的一個簡單方法——超前搜索。

關鍵字的識別

FORTRAN這個語言，不像C語言那樣，它不保護關鍵字，只要不引起矛盾，用戶可以直接用關鍵字作為普通的標識符，關鍵字和用戶自定義的標識符或者標號之間沒有特殊的界符作間隔。這樣識別一串字元到底是關鍵字還是用戶定義的標識符，就是一件困難的事情，示例如下：

這幾個FORTRAN語句的意思簡單介紹一下，第一句是個循環，它是用DO，而不是我們熟悉的FOR，99是個標號，循環結束後跳到99標號的那個位置，K是循環變數，然後「=初值，終值「，現在看第三句，是不是看到DO99K，就覺得這是個循環呢？大錯特錯了，這是個標識符，它滿足標識符的定義：字母開頭的字母數字串，因為往後看那個1後面不是逗號而是點號。再看第二句，這個IF是個邏輯判斷，M是不是等於5，為真就執行I=10，再看第四句，那是個邏輯判斷嗎？不是，這是FORTRANl裡面的數組。。數組名叫IF，因為右括弧後面是個等號。

那這到底是怎麼識別關鍵字DO和IF呢？實際上從上面那段話中兩個「因為」大概能看出來了，我們是通過繼續往後掃描解決的。也就是超前搜索。再分析一下，這要求詞法分析器必須能夠區分1,3和2,4。1,3的區別在於等號之後的第一個界符：一個是逗號，一個是句末符。2,4的區別是有括弧後的第一個字元一個是字母，一個是等號。為了識別關鍵字，詞法分析器必須要做到往後掃描很多個字元，直到能夠確定這個詞性的地方為止。也就是不能一看見DO，那就判定他是DO關鍵字，只有超前掃描，越過所有字母和數字，看有沒有等號，如果有，繼續掃描，看下一個界符是不是逗號，如果是才可以確定是DO關鍵字，而不是用戶定義的標識符的一部分。而IF的道理是一樣的。

標識符的識別

多數語言的標識符是字母開頭的「字母/數字」串，而且在標識符出現都後面跟著算符或者界符，標誌符的斷詞界限一般是很明顯的。

常數的識別

多數語言的常熟表示也大體相似，識別比較直接，但有些依然需要超前搜索，看上面所舉的FORTRAN語句的第二句，5.EQ.M，只有當超前搜索掃描到字母Q時候，才能確定5的詞性是個常數，5.E08和5.EQ.M頭三個字元完全一樣，5.E08是FORTRAN裡面的科學計數法。

算符和界符的識別

比如++，>=,--這類算符，依然需要超前搜素，不可能遇到個+，就說它是加號。

2.2.3狀態轉換圖

前面我們學習的是在做詞法分析器時候，需要考慮的一些問題，預處理，超前搜索等等。狀態轉換圖部分研究的問題是詞法分析器怎麼寫，它是設計詞法分析程序的好的工具，定義如下：

一個狀態轉換圖可以用於識別一定的字元串，舉例如下：

圖a，初始狀態是1，如果檢測到輸入字元是個X就得到2狀態，如果是個Y就得到3狀態

圖b，就是個識別標識符（以字母開頭的字母數字串）的轉換圖，初始狀態是0，首先必須以字母開頭，才能進入狀態1，接著如果讀取到輸入是字母或者數字，保持狀態1，如果讀到其他字元，那就到達終態2了，意味著已經識別出了一個標識符，識別過程宣布終止，並且把這個字元退換到輸入串。圖c同理。（這個圖b在有一定問題，這樣識別標識符有漏洞，我們下面會講）

下面我們看一個識別FORTRAN中實型常數的轉換圖：

下面結合一個綜合的例子來看一下，這是一個簡易的語言，我們看到其中有五個定義符，標識符，還有常數，還有算符界符：

我們現在來為它設計個詞法分析器，先要考慮的問題是當我們看到一個定義符的時候，我們要轉化成什麼樣子的二元式，看到一個正數的時候，又是要輸出什麼樣子的二元式等等。上面這個圖已經給出來單詞的種別編碼和單詞的值了，所以輸出已經定義好了。接下來，為了實現這個輸出，我們使用狀態圖的方法。

這實際上細心一點，我們就發現，這上面幾個部分不就是前幾個識別標識符和識別常數那塊舉例的狀態轉換圖嗎，所以實際上一個複雜的詞法分析的狀態轉換圖往往是由多個狀態轉換圖集合而來的。這塊我們發現一個問題，如果輸入IF後面再跟個括弧什麼的，那麼會看到在2那個地方終止了，也就是定義符也就是關鍵字和標識符是同一個出口。那這個設計就是有問題的，怎麼區分這兩種單詞符號呢？想一下，這裡還應該有一個查表的動作，把終止狀態下得到的串去查一下定義符的表，如果查到了，那就是定義符，如果沒有查到那就是標識符，當然在FORTRAN中我們前面已經見識到了，查表也沒有作用，就需要超前搜索，設計更加複雜的轉換圖了。

2.2.4狀態轉換圖的實現

詞法分析用狀態圖來描述特別舒服和簡單，我們現在要做的是把狀態圖翻譯成程序（狀態圖實際上是你的演算法，或者說是偽代碼），實現狀態轉換圖的一個簡單辦法就是讓每個狀態節點對應一小段程序，我們引入一組全局變數和過程。將它們作為實現轉換圖的基本成分：

第四講視頻結束了。。今天效率很低。睡了。希望明天好一些。不要放棄。。

推薦閱讀：