這是關於編譯原理的第三篇筆記。

編譯有五大步驟，本篇筆記將會講解編譯的第一步：詞法分析。

詞法分析的任務是：從左往右逐個字符地掃描源程序，產生一個個的單詞符號。也就是說，它會對輸入的字符流進行處理，再輸出單詞流。執行詞法分析的程序即 詞法分析器 ，或者說掃描器。

1.詞法分析的成果

詞法分析的成果就是由一系列單詞符號構成的單詞流。單詞符號其實就是 token，一般有以下五大類：

• 關鍵字：例如 while ， if ， int 等
• 標識符：變量名、常量名、函數名等
• 常數：例如， 100 ， 'text' ， TRUE 等
• 運算符：例如 + ， * ， / 等
• 界符：逗號，分號，括號，點等

具體來說，一個單詞符號在形式上是這樣的一個二元式： （單詞種別，單詞符號的屬性值） 。

單詞種別：

單詞種別通常用整數編碼。一個語言的單詞符號如何分種，分成幾種，怎樣編碼是一個技術問題。它取決於處理上的方便。

• 標識符一般統歸爲一種。比如說變量 a 和 b ，可能我們都只用 1 作爲它們的單詞種別。
• 常數則宜按類型（整、實、布爾等）分種，比如說整數可能用 2 表示，布爾值可能用 3 表示。
• 關鍵字可以把全體視爲一種，也可以一字一種。
• 運算符可以把具有一定共性的運算符視爲一種，也可以一符一種。
• 界符一般是一符一種。

單詞符號的屬性值

由上面的單詞種別可以知道，關鍵字、運算符、界符基本都是一字（或者一符）對應一個種別，所以只依靠單詞種別即可確切地判斷出具體是哪一種單詞符號了。但是標識符和常數卻不是這樣，一個種別可能對應好幾個單詞符號。所以我們需要藉助單詞符號的屬性值 做進一步的區分 。

對於標識符類型的單詞符號，它的屬性值通常是一個指針，這個指針指向符號表的某個表項，這個表項包含了該單詞符號的相關信息；對於常數類型的單詞符號，它的屬性值也是一個指針，這個指針指向常數表的某個表項，這個表項包含了該單詞符號的相關信息。

以 while(i>=j)i++ 爲例，它的單詞符號流大概如下：

<while,->
<(,->
<id,pointer1>  
<>=,->  
<id,pointer2>  
<),->  
<id,pointer3>
<++,->    
<;,->

注意：實際上，對於關鍵字、界符這些，應該用整數表示單詞種別，不過這裏爲了便於區分，直接用對應的單詞符號表示了。對於標識符，由於 id 這個單詞種別可能對應多個標識符，所以可以看到我們用不同的指針進行了標識。其它不需要標識的，則統一用短橫線代替。

2. 詞法分析的要點

2.1 是否作爲一趟？

按照我們常規的想法，應該是詞法分析器掃描整個源程序，產生單詞流，之後再由語法分析器分析生成的單詞。如果是這樣，那麼就說詞法分析器獨立負責了一趟的掃描。但其實，更多的時候我們認爲詞法分析器並不負責獨立的一趟，而是作爲語法分析器的子程序被調用。也就是說，一上來就準備對源程序進行語法分析，但是語法分析無法處理字符流，所以它又回過頭調用了詞法分析器，將字符流轉化成單詞流，再去分析它的語法。以此類推，後面每次遇到字符串流，都是這樣的一個過程。

2.2 輸入和預處理

字符流輸入後首先到達 輸入緩衝區 ，在詞法分析器正式對它進行掃描之前，還得先做一些預處理的工作。預處理子程序會對 一定長度 的字符流進行處理，包括去除註釋、合併多個空白符、處理回車符和換行符等。處理完之後再把這部分字符流送到 掃描緩衝區 。此時，詞法分析器才正式開始拆分字符流的工作。

詞法分析器對掃描緩衝區進行掃描時一般使用兩個指示器： 起點指示器 指向當前正在識別單詞的開始位置， 搜索指示器 用於向前搜索以尋找單詞的終點。問題在於，就算緩衝區再大，也難保不會出現突破緩衝區長度的單詞符號。也就是說，輸入緩衝區把處理好的一段字符流送到掃描緩衝區時，掃描緩衝區可能裝不下這段字符流，在這種情況下，如果依然只用一個緩衝區存放字符流，可能會導致某個過長的單詞符號無法被正確讀取。因此，掃描緩衝區最好使用如下一分爲二的區域：

這樣，在搜索指示器向前搜索到 A 半區邊緣時，如果發現還沒有找到單詞符號的終點，那麼就會調用預處理程序把剩下的部分送到 B 半區，搜索指示器再來到 B 半區掃描。這樣就可以避免截斷，從而將這個過長的單詞符號順利銜接起來。如果單詞符號實在太長，兩個半區都無法解決，那就沒轍了。所以應該對單詞符號的長度加以限制。

2.3 超前掃描

像 FORTRAN 這樣的語言，關鍵字不加保護（只要不引起矛盾，用戶可以用它們作爲普通標識符），關鍵字和用戶自定義的標識符或標號之間沒有特殊的界符作間隔。這使得關鍵字的識別變得很麻煩。比如 DO99K=1,10 和 DO99K=1.10 。前者的意思是，K 從 1 變到 10 之後，跳轉到第 99 行執行；後者的意思是，爲變量 DO99K 賦值 1.10。問題在於，我們並不能在掃描到 DO 的時候就肯定這是一個關鍵字，事實上，它既有可能是關鍵字，也有可能作爲標識符的一部分。而具體是哪一種，只有在我們掃描到 =1 後面才能確定 —— 如果後面是逗號，則這是關鍵字，如果是點號，則是標識符的一部分。

也就是說，我們需要 超前掃描 到達第一個界符 = ，但是 = 還不能確定，再 繼續超前掃描 到達第二個界符（逗號或者點號），這時候才能完全確定。

3. 詞法分析的模型

3.1 狀態轉換圖

狀態轉換圖是設計詞法分析程序的一種模型，我們可以藉助這個模型體會 識別某個特定字符串 的過程。它是一張有限方向圖，結點表示狀態，結點之間的箭弧上有字符，表示遇到該字符就將其讀進來，並且轉換到另一個狀態。以下面這張圖爲例，在狀態 0 下如果輸入的是字母，則將字母讀進來，並進入狀態 1 ；在狀態 1 下如果輸入的是字母或者數字，則將其讀進來並重新進入狀態 1 。不斷重複，直到輸入的不是字母和數字，這時候也 將其讀進來 ，並進入狀態 2。狀態 2 是終態，有一個 * 作爲標記，標記着多讀進來一個不屬於目標的符號，應該把它退還給原輸入串。這張圖實際表示的是標識符類型的輸入串。

狀態轉換圖的結點（狀態）個數是有限的，其中有一個初態，以及至少一個終態（同心圓表示）。

左圖是 FORTRAN 語言的一些單詞符號，右圖是對應的狀態轉換圖：

狀態轉換圖的實現：

比如上面的狀態轉換圖，它的詞法分析器大概如下：

3.2 正規式與有限自動機

狀態轉換圖是製造詞法分析器的模型，不過這個模型過於具體，我們應該想個辦法，用一種 更接近數學的、更爲形式化 的方法來表示狀態轉換圖。而這種狀態轉化圖的形式化表達，就是 有限自動機 。由於有限自動機涉及到了正規式、正規集等其它概念，所以我們這裏先普及一下這些概念。

① 正規式與正規集

推導

正規式和正規集都是相對於字母表來說的概念，通常說“xx 字母表的正規式是......，字母表的正規集是......”。對於正規式和正規集，我們採用 遞歸 的方式進行定義。即，對於某個給定的字母表 ∑ ，規定：

• ε 和 Ø 都是該字母表的正規式，這兩個正規式分別表示了 {ε} 和 Ø 這兩個正規集
• 字母表上的任意一個元素 a 都是字母表的正規式，它表示了 {a} 這個正規集
• 如果 a 和 b 都是字母表上的正規式，且分別表示了 L(a) 和 L(b) 這兩個正規集。那麼， (a|b) ， (ab) ， (a)* 也都是正規式，它們分別代表了 L(a)∪L(b) ， L(a)L(b) 和 (L(a))* 這幾個正規集。（笛卡爾積和閉包）
• 僅由有限次使用上面三條規則而得到的表達式纔是字母表上的正規式，僅由這些正規式表示的字集纔是字母表上的正規集

根據上面這四條規則，我們可以遞歸列舉出某個字母表的正規式和對應的正規集

例如對於給定的字母表 ∑ = {a,b} ，我們可以像下面這樣推導出它的正規式和對應的正規集：

ba* ： a 是正規式，所以 a* 也是正規式（規則二），所以 ba* 也是正規式（規則二）。 a 表示 {a} 這個集合，加上星號則表示該集合的閉包， b 表示 {b} 這個集合，所以並排放在一起表示兩個集合作笛卡爾積運算

等價的正規式

如果兩個正規式 U 和 V 表示的正規集相同，則認爲這兩個正規式等價，記作 U = V 。例如， b(ab)* 和 (ba)*b 就是等價的兩個正規式。它們表示的集合形如 {ba,bb,bab,babab,babababab,......} 。可以看出這個集合的元素特點是，以 b 開頭，後面跟着 a 和 b 自由組合的符號串。在沒有引入正規式的概念之前，要表示這樣的集合是比較麻煩的，但現在則方便很多。

正規式運算規則

對於正規式 U ， V ， W ，它們滿足下面的運算規律：

1、交換律：U|V＝V|U

2、結合律：U|(V|W)＝(U|V)|W

3、結合律：(UV)W=U(VW)

4、分配律：U(V|W) = UV|UW

5、分配律： (V|W)U = VU|WU

6、零一律：εU=U

7、零一律：Uε=U

最後再來看一道題：

先來劃分結構，以 d* 開頭，說明第一個部分是一個整數，第二個部分是 (.dd*|ε) ，可以取空，第三個部分是 (e(+|-|ε)dd*|ε) ，同樣可以取空。如果後面兩個部分都取空，則肯定代表一個整數；如果第二個部分不取空，則會出現小數點，表明這時候會是一個小數；如果第三個部分不取空，則會出現 e ，表明這是一個用科學計數法表示的數字。綜上，這個正規式表示的是所有無符號數構成的集合。

有個需要注意的地方是， d* 已經可以表示所有整數了，爲什麼小數點後使用的是 dd* 而不是 d* 呢？這裏其實是起到一個佔位的作用，因爲單純用 d* 的話，其實也包括了空符號串，但是既然出現了小數點，後面至少要跟一位數，不能爲空。所以這裏用 dd* 。對於 e 後面也是同理，既然出現了 e ，後面就不能爲空了。

② 確定有限自動機

1. 確定有限自動機的結構

我們先來回顧一下這副狀態轉換圖：

考慮到要用形式化的方法來表示它，我們得先考慮轉換圖的一些重要組成因素。

• 首先想到的是，必須得有一個集合用來保存所有的狀態
• 還需要有一個集合用來保存所有的輸入字符
• 在某一個狀態下，根據輸入的字符不同，會跳轉到不同的狀態，這三者構成一個聯繫，多個聯繫自然也需要保存起來
• 初態是特殊的，需要單獨保存
• 終態也是特殊的，需要單獨保存

那麼，我們可以構造一個有限的狀態集合 S ，用以保存該轉換圖的所有狀態；構造一個有限的字母集合 ∑，用以保存每一個輸入的字符；構造包括多個 單值映射對 的 δ，每一對都表示從“當前狀態和輸入字符”到“跳轉狀態”的映射關係。具體地說，用 δ(s,a) = a' 表示，當前狀態爲 s 且輸入字符爲 a 時，跳轉到狀態 a' ；此外，需要用來自於狀態集合 S 的 s0 作爲唯一的初態；最後，構造一個終態集合 F，它是 S 的子集，可取空。

這樣，我們就有了 S，∑，δ，s0，F。這五個元素在一起就構成了我們要講的是 確定有限自動機 。即，確定有限自動機 DFA 可用如下的五元式表示：

M = {S，∑，δ，s0，F}

2. 確定有限自動機的其它表示

正如我們所說的，有限自動機是抽象層面上的形式化表達，而它在具體層面上的表達就是之前所講的狀態轉換圖。另外，確定有限自動機還可以用一個矩陣來表示，這樣的矩陣即 狀態轉換矩陣 。它的行表示當前狀態，列表示輸入字符，而矩陣元素則表示跳轉狀態，也就是 δ(s,a) 的值。

以 DFA M = （{0，1，2，3，4}，{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

那麼它的狀態轉換矩陣如下所示：

當前狀態	a	b
0	1	2
1	3	2
2	1	3
3	3	3

3. 確定有限自動機的作用

確定有限自動機是狀態轉換圖的形式化表達，它可以用於識別（或者說讀出、接受） 正規集 。

對於 ∑* 中的任何一個字 a，若存在一條從初態結點到某一終態結點的通路，且這條通路上所有箭弧的標記符連接成的字等於 a，則稱 a 爲 DFA M 所識別（讀出或接受）。

如果 M 的初態結點同時也是終態結點，那麼就說空符號串可以被 M 所識別。

DFA M 可以識別的字的全體記爲 L(M)。

看下面的例子：

這是某個確定有限自動機對應的狀態轉換圖，那麼這個 DFA M 可以識別什麼樣的正規集呢？我們可以先走幾條路線看看（假定在遇到狀態 3 就停止），不難發現它可以識別出諸如 aa ， bb ， abb ， baa 這樣的符號串。這樣的符號串的特點是，中間要麼是 aa ，要麼是 bb ，所以首先確定中間是 (aa|bb) 。由於 aa 和 bb 都可以獨立存在，說明 (aa|bb) 的前面和後面必須可以是空符號串，說到空符號串，我們會想到閉包，所以它的前面後面必定會分別出現一個閉包。考慮前面，可以出現 a 或者 b ，所以前面應該是 (a|b)* ；考慮後面，我們在遇到狀態 3 的時候就停止了，但實際上，在這之後遇到 a 或者 b ，狀態變化會循環往復，也就是說，不管遇到什麼樣的 ab 組合符號串，都能夠被識別並循環轉換到狀態 3，這裏說明後面的狀態是任意的，所以確定後面是 (a|b)* 。

結合起來，這個有限自動機可以識別的正規集可以用正規式 (a|b)*(aa|bb)(a|b)* 表示。

③ 非確定有限自動機

1. “確定”和“不確定”指的是什麼？

“確定”指的是，五元式中的映射是一個單值函數，也就是說，在當前狀態下，面對某個輸入字符， 其跳轉狀態是唯一確定的 ，即只會跳轉到某一個值。但是，有的時候映射是多值函數，也就是說，在某個輸入字符下 有多個跳轉狀態可供選擇 。具有這樣特點的有限自動機，就叫做 非確定有限自動機 。

2. 非確定有限自動機的結構

非確定有限自動機可以用如下的五元式表示：

M = {S，∑，δ，s0，F}

• S 仍然是狀態集合，∑ 仍然是輸入字符集合，F 仍然是終態集合。
• 但是，s0 不再表示單個初態，而是表示一個非空的初態集合
• 另外，正如前面所說的，δ 不再是一個從“當前狀態和輸入字符”到“跳轉狀態”的單值映射，而是從 “當前狀態和輸入字符集合閉包” 到 “跳轉狀態集合” 的子集映射。簡單地說就是，它接受的不一定是單個字符，且在單一輸入下可以跳轉到多個狀態

3. 非確定有限自動機的作用

非確定有限自動機同樣可以用於識別（或者說讀出、接受） 正規集 。

對於 ∑* 中的任何一個字 a，若存在一條從初態結點到某一終態結點的通路，且這條通路上所有箭弧的標記符連接成的字等於 a，則稱 a 爲 NFA M 所識別（讀出或接受）。

如果 M 的初態結點同時也是終態結點，或者 存在一條從某個初態結點到某個終態結點的 ε 通路 ，那麼就說空符號串 ε 可以被 M 所識別。（因爲輸入符號來自於集合閉包，所以輸入符號接受空符號串 ε）

看下面的例子：

假設有非確定有限自動機 NFA M＝({0,1,2,3,4},{a,b},δ,{0},{2,4}) ，其中，

δ(0,a)={0,3}    δ(2,b)={2}

δ(0,b)={0,1}    δ(3,a)={4}

δ(1,b)={2}      δ(4,a)={4}

δ(2,a)={2}      δ(4,b)={4}

可以看到，有不少 δ 是被映射到 S 的一個子集，而不是像確定 DFA 那樣映射到一個輸入字符。這個 NFA 對應的狀態轉換圖如下：

這裏會發現，這個 NFA 所能識別的正規集和之前的 DFA 是一樣的，都是含有相繼兩個 a 或者相繼兩個 b 的符號串。事實上，儘管 DFA 是 NFA 的特例，但是對於每個 NFA M，都會有一個 DFA M‘ 與之對應，使得 L(M) = L(M') 。這時候，我們就說 NFA M 等價於 DFA M’。

③ 非確定有限自動機的確定化

非確定有限自動機的確定化，指的就是將非確定有限自動機轉換爲一個 與之等價 的確定有限自動機。總的來說分爲兩步，第一步是利用等價轉換規則細化 NFA 狀態轉換的過程；第二步是利用子集法對第一步轉化得到的 NFA 進行確定化。由於第二步又涉及到了一些概念，所以這裏我們先來對這些概念進行解釋。

相關概念：

（1）空閉包集合

若 I 是一個狀態集合的子集，那麼 I 會有一個空閉包集合，記作 ε-closure(I) 。這個空閉包集合同樣是一個狀態集合，它的元素符合以下幾點：

I
I

以下面這張圖爲例：

ε-closure({5,3,4}) 會等於多少呢？這裏的 I 是 {5,3,4} ，所以空閉包集合一定包含了5，3，4。從 5 出發，經過一條 ε 弧到達 6，兩條 ε 弧到達 2，所以 6 和 2 也是閉包集合的元素；從 3 出發，經過一條 ε 弧到達 8，所以 8 也是；從 4 出發，經過一條 ε 弧 7，所以 7 也是。綜上， ε-closure({5,3,4}) = {5，3，4，6，2，8，7} 。

（2） Ia

若 I 是一個狀態集合的子集，那麼它相對於狀態 a 的 Ia 等於 ε-closure(J) 。其中， J 表示的是，從 I 中每個狀態出發， 經過標記爲 a 的單條弧而到達的狀態 的集合。也就是說， Ia 表示的是從 I 中每個狀態出發，經過標記爲 a 的弧而到達的狀態，再加上從這些狀態出發，經過任意條 ε 弧能夠到達的狀態。

還是以這幅圖爲例：

當 I 是 {1，2} 的時候， Ia 等於多少呢？

• 從 1 出發，經過 a 弧能夠到達 5 和 4，所以 5，4 屬於 Ia 。從 5，4 出發，經過 ε 弧能夠到達 6，2，7，所以 6，2，7 屬於 Ia
• 從 2 出發，經過 a 弧能夠到達 3，所以 3 屬於 Ia 。從 3 出發，經過 ε 弧能夠到達 8，2，7，所以 8 屬於 Ia

綜上， Ia = {5,4,6,2,7,3,8}

下面，介紹具體的確定化過程。

第一步：規則轉換

第一條和第二條都好理解，重點在第三條規則。爲什麼右邊的圖可以等價於左邊的圖呢？ A* 其實表示的是類似 {ε，A，AA，AAA，AAAA，......} 這樣的集合，因爲 A 自由組合形成的符號串是可以用一個 A 的自循環來表示的，所以中間有一個自循環，而 ε 則可以用 εε 來表示，所以考慮在前後各加一個 ε，對於 A 的符號串不影響。

第二步：子集法轉換

子集法的核心是，針對上面規則轉換後得到的 NFA，畫出它的狀態轉換矩陣，這個矩陣的矩陣元素是映射的子集，不是單值，而我們要做的事情就是把這個子集用一個單值來表示。也就是說，對於 NFA 的每一組映射狀態集，都用一個來自 DFA 的映射單值與之對應，從而求出等價的 DFA。

假設經過第一步，我們已經得到下面的 NFA：

選取 NFA 的 初態集合的空閉包 作爲初始集合 I ，這個集合 I 將是 ε-closure({i}) = {i,1,2} 。同時由於輸入符號只有 a 和 b，所以第二列爲 Ia ，第三列爲 Ib 。得到如下這個表：

	Ia	Ib
{i，1，2}

根據前面的說法求解 Ia 和 Ib 。從 i 出發沒有 a 弧，無視之；從 1 出發經過 a 弧 到達 1，從 2 出發經過 a 弧到達 3；從 1 出發經過 ε 弧到達 2，從 1 出發沒有 ε 弧。所以， Ia = {1,2,3} 。從 i 出發沒有 b 弧，無視之；從 1 出發經過 b 弧到達 1，從 2 出發經過 b 弧到達 4。從 1 出發經過 ε 弧到達 2，從 4 出發沒有 ε 弧，所以 Ib = {1,2,4} 。記新得到的兩個

集合爲 A 和 B，得到下面的表：

	Ia	Ib
{i，1，2}	A： {1,2,3}	B： {1,2,4}

將新得到的集合 A 和 B 作爲第一列的元素，得到下面的表：

	Ia	Ib
{i，1，2}	A： {1,2,3}	B： {1,2,4}
A： {1,2,3}
B： {1,2,4}

分別對 A 集合和 B 集合求解對應的 Ia 和 Ib ，得到下表（對於同樣形式的集合仍採取之前命名，僅對新出現集合給定新的命名）：

	Ia	Ib
{i，1，2}	A： {1,2,3}	B： {1,2,4}
A： {1,2,3}	C： {1,2,3,5,6,f}	B： {1,2,4}
B： {1,2,4}	A： {1,2,3}	D： {1,2,4,5,6,f}

將新得到的 C、D 集合作爲第一列的元素，同樣求解 Ia 和 Ib ，得到下面的表：

	Ia	Ib
{i，1，2}	A： {1,2,3}	B： {1,2,4}
A： {1,2,3}	C： {1,2,3,5,6,f}	B： {1,2,4}
B： {1,2,4}	A： {1,2,3}	D： {1,2,4,5,6,f}
C： {1,2,3,5,6,f}	C： {1,2,3,5,6,f}	E： {1,2,4,6,f}
D： {1,2,4,5,6,f}	F： {1,2,3,6,f}	D： {1,2,4,5,6,f}

同理，繼續推導，直到再也沒有新集合出現：

	Ia	Ib
{i，1，2}	A： {1,2,3}	B： {1,2,4}
A： {1,2,3}	C： {1,2,3,5,6,f}	B： {1,2,4}
B： {1,2,4}	A： {1,2,3}	D： {1,2,4,5,6,f}
C： {1,2,3,5,6,f}	C： {1,2,3,5,6,f}	E： {1,2,4,6,f}
D： {1,2,4,5,6,f}	F： {1,2,3,6,f}	D： {1,2,4,5,6,f}
E： {1,2,4,6,f}	F： {1,2,3,6,f}	D： {1,2,4,5,6,f}
F： {1,2,3,6,f}	C： {1,2,3,5,6,f}	E： {1,2,4,6,f}

現在，用字母命名代替所有的集合（初始集合給定名字 S ），得到下面的矩陣：

	Ia	Ib
S	A	B
A	C	B
B	A	D
C	C	E
D	F	D
E	F	D
F	C	E

這個矩陣實際上已經是一個 DFA 矩陣。我們再以初始集合 S 將作爲初態，包含原始 NFA 終態的集合（即 C、D、E、F）作爲終態，畫出它對應的狀態轉換圖，如下：

那麼，這個轉換圖實際上就是與最初 NFA 等價的 DFA 所對應的轉換圖了，到這裏，我們就完成了對非確定有限自動機進行確定化的工作了。

最後我們再對這篇筆記涉及的知識點做一下回顧。首先我們解釋了詞法分析的結果，也就是單詞符號，之後講解了一些詞法分析過程中的要點（預處理、超前掃描），最後則是本篇筆記的重點，詞法分析的模型，包括狀態轉換圖以及它的形式化表達 —— 有限自動機。

到這裏，詞法分析的內容還沒有結束。剩下的內容我們將在下一篇筆記中繼續講解。

相關文章