藍色情懷

語法剖析自動生成器CScanGenner的設計與實現

ScanGen是一種表驅動形式的詞法分析器，它最後產生的結果不是一個實實在大的詞法分析器程式，而是一張轉換表，通過這種轉換表去驅動真正的詞法分析器的運行。舉個例子，我們先來想一下我們自己是怎樣識別一個單詞串的，比如說識別一個C語言的變數名吧：

1. 我們首先看第一個符號是不是下劃線或者字母，如果是的話我們就把這個字元加入輸出緩衝區，並進入下一步。

2. 繼續查看緊跟著的這個符號是不是下劃線、字母或數位，如果是我們就把這個字元加入輸出緩衝區，並重複這一步，如果是空格我們就進入第三步。

3. 表明變數名定義完成，把輸出緩衝區中的內容返回，這就是一個被識別出來的變數名。

上面這個步驟可以用如下的一幅圖來表示：

上面這張圖，我們就稱之為狀態轉換圖，用語言可以如下描述：

• 在狀態是1的情況下如果當前輸入字元是下劃線或字母就轉到下一狀態2。

• 在狀態是2的情況下如果當前輸入字元是下劃線、字母、數位就轉到下一狀態2。

• 在狀態是2的情況下如果當前輸入字元是空格則轉到下一狀態3。

• 在狀態是3的情況下，把輸出緩衝區的內容返回，表明一個單詞串被識別出來。

從上面的文字描述中我們可以看出，其實決定詞法分析器怎麼運作的有兩個關鍵因素，一個因素是當前狀態，另一個因素是當前的輸入字元。現在，我們把當前狀態做為行索引，當前字元做為列索引，就得到一張如下的表：

上面這張表就被視為詞法分析器的驅動表，這樣，我們的詞法分析器就有如下一樣的很簡單的結構：

DRIVER_TABLE M[][];

string buffer;

char ch;

STATE s = 1; // 初始狀態為1

while(input.get(ch))

{

s = M[s][ch]; // 進入下一狀態

if(s == 2)

{

buffer += buffer;

}

else if(s == 3)

{

return buffer;

}

else

{

printf( "ERROR!" );

}

}

從上面可見，由於有那張詞法分析器的驅動表的存在，使得我們的詞法分析程式變得非常簡單。由於ScanGen生成的結果就是那張驅動表，因此，這還帶來另外一個好處，也就是詞法分析器的主體程式可以用任何語言書寫，而不像Lex，Lex最後生成的結果是實實在在的詞法分析器的C/C++程式，因而你不用其他語言來使用Lex。當然ScanGen也有一個弱點，就是轉換表所含的資訊相對較少，因此，這限制了詞法分析器的隨意度，它不像Lex那樣靈活。

ScanGen最早是由微斯康星大學的一個教授寫的，版權屬於微斯康星大學，用的語言是Pascal，它可以把用戶書寫的詞法說明文件（這在後面會詳細論述）轉換成一張驅動表。CScanGenner可以算是ScanGen的一個C++版本，它用C++語言書寫的，並且取消了原ScanGen對詞法說明文件的一些限制（比如說最大規模，單詞串最大長度等），另外，在詞法說明文件的描述上支持C風格而不是原來的Pascal風格（最大的一點變化就是大小寫相關），另外，CScanGenner是開源軟體，你可以在MIT許可協定[1]下隨意使用。

本文不是CScanGenner的說明文檔，只是描述一下他在實現上的原理及一些實現中的細節問題，關於CScanGenner的詳細說明，你可以訪問純C論壇：http://purec.binghua.com或者http://iamxiaohan.nease.net取得。

單詞串其實都是通過一種稱之為正則運算式的東東定義的，或說可以用正則運算式來描述，比如上面那個例子就可以用如下的一個正則運算式來對其進行描述：

ID := (下劃線|字母).(下劃線|字母|數位)*;

上面這個就是一個正則運算式，「|」表示「或」關係，「.」表示「連接」關係，「*」表示出現零次或多次，上面的意思就是：下劃線或者字母后面，出現零次或多次下劃線或者字母或者數位，這個符號串被定義成一個ID（也就是我們常說的變數名）。當然，正則運算式還有「+」：表示出現一次或多次；「？」表示出現零次或一次……等等運算符，有興趣的可以在網上搜索一下，這裡就不詳細描述了。

還記得那前面那幅狀態轉換圖麼？它同上面的正則運算式其實都是描述的同樣一個東東，這就使我們不得不懷疑它們之間是否存在一種轉換關係？實際上，形式語言的理論告訴我們：正則運算式是可以轉換成為一張轉換圖的（有限狀態機）。我們現在就來看看一這種轉換。

正則運算式其實有三種最基本的關係：

• 一是連接關係：

C = A.B

它可以用如下的方式轉換：

這就是正則運算式C所對應的狀態圖，紅色線表示輸入可以是epsilon，即可以為空，什麼都不做就能非常自由的從一個狀態由紅線進入到下一個狀態。

• 二是「或」關係：

C = A|B

它可以用如下的方式轉換：

三是「*」關係：

C = A*

它可以用如下的方式轉換：

另外的關係都可以由這三種關係合成，比如「+」關係：

A+ = A.A*

上面種種表明，我們能找到一種方法，把一個描述詞法的正則運算式轉換成一張狀態表（有限自動機），而狀態表可以很簡單的轉換為我們的二維表（如前所示），這樣我們的驅動表就可以產生出來了。不過上面的狀態表有這樣一個問題：假如存在如下的一張狀態表：

上面這個自動機其實等價於：ab|a，但現在問題來了，在狀態1下，輸入a本來應當是到狀態2，但是由於狀態1有一根紅線到狀態3，即在狀態1下，可以不輸入任何字元自由的到狀態3，故而，可以是狀態1先到狀態3然後在根據輸入的a到狀態4，也就是說在狀態1下，面對輸入a，可以到狀態2也可以到狀態4，如下圖一般：

如果是這樣的話，那麼在狀態表中，就會出現一個表格中填入了兩個動作，一個動作是到狀態2，另一個動作是到狀態4，這對於詞法掃瞄程式來說是一個無法處理的事情，因為它不知道是應當按照動作一，還是應按照動作二進行。

上面的狀態圖反應的一種狀態機稱之為不確定有限狀態機（NDFA），而詞法掃瞄程式處理的必須是確定有限狀態機（DFA），因此，必須採用一種演算法把一個NDFA轉換成一個DFA，有一種演算法非常常用，這就是所謂的子集化演算法。

首先，我們從狀態1開始，對狀態1求它的epsilon閉集，即求得所有可以由狀態1通過紅線（即無需輸入字元，或說輸入字元為空（epsilon））所能達到的狀態的集合。在上例中就是：狀態1，狀態3。這是需要注意的是，在求的時候應當是一個遞迴的演算法，即狀態1能通過epsilon到狀態3，那麼應當把狀態3加入到這個集合中來，隨後還要求狀態3可以通過epsilon所達到的狀態n，這個n也應當加入集合中，因為狀態1可以不需要輸入字元就能達到狀態3，而狀態3不需要輸入字元就能達到狀態n，相當於狀態1可以不需要輸入字元就能達到狀態n，故而，狀態n也就加入集合之中。現在我們可以開始構造一個新的狀態圖：

生成了一個新狀態A，它含有原狀態1，3。

下面我們考查這個新狀態A中的原狀態，狀態1輸入是a時，會轉到狀態2，原狀態3輸入是a時會轉到狀態4，於是我們可以構造一個新的狀態B，讓它含有狀態2及狀態4，如下所示：

這時我們就得到了一個確定的東東，即在狀態A下輸入a時，只能到狀態B，這就是一個確定的DFA。在實際的求解過程中，我們還應對B的每個元素就它的epsilon閉集，即，如果2或者4能通過不輸入任何字元到達狀態m，那麼m也應被加入到狀態B中。

繼續我們的演算法，當B中的狀態2遇到輸入b後，會轉到狀態4，因此，我們還需構造一個新的狀態C，讓它含有狀態4：

由於原來的NDFA中，狀態4是終態，也就是說：在NDFA中，如果狀態4出現，即表明當前的輸入串（被放在輸出緩衝區中的東東）應當被接收（將輸出緩衝區中的東東返回）。現在在DFA中，對於狀態B來說，它含有NDFA中的終態4，但是也含有非終態2，那麼這個輸出緩衝區中的東東應不應當返回呢？這就需要由後面的輸入決定了，如果後面的輸入是b，說明它不應當返回，它還應轉到狀態C去，因為這其實是到達了原NDFA中的，現在DFA中的狀態B中的狀態2，如果後面的輸入是其他字元，則說明它應當返回了，這其實是到達了原NDFA中的，現在DFA中的狀態B中的狀態4，真正的終態。這裡還可以發現一個很有興的現象：正則運算式其實是一種最大正向匹配演算法，它總是盡力的嘗試去匹配更多的輸入。

上面描述的其實是形式語言的一些原理性的東東，在任一本形式語言的書或者某些編譯原理的書中都會有較為詳細的論述，這裡只是簡單的介紹了一下，用以說明CScanGenner所採用的演算法原理，如果對這部份內容想詳細瞭解的朋友，可以參閱相關資料。

上面介紹的就是CScanGenner實現的演算法基理，總結一下，說簡單一點，就是由用戶根據需要用正則運算式編寫詞法說明文件，然後，CScanGenner根據這些說明文件，把說明文件中的正則運算式先轉換成一個一個的NDFA，再把這一個一個的NDFA合在一起當成一個由「或」關係組成的巨大的NDFA，隨後對這個巨大的NDFA，應用前述的子集化演算法轉化成一個巨大的DFA，最後再把這個DFA轉換成一張驅動表輸出，至此，CScanGenner的 工作完成，用戶可以使用這張驅動表驅動自己的詞法驅動程式。下面我們就來看看這其間的一些實現上的細節問題，當然，由於篇幅有限（最主要的還是認為沒有必 要），筆者不會完全描述所有的細節，只是對筆者覺得有意義的地方進行一些闡述。其中若有不當之處，歡迎您來信指教，筆者的電子郵箱是: xieyubo@gmail.com。

CScanGenner所採用的分析方法是最簡單的遞迴下降法，它對每一個語法項的處理都有一個函數進行，關於CScanGenner的語法定義及遞迴處理函數請參見CScanGenner的源代碼。如果你對遞迴下降的語法處理方法還不太熟悉，請參見本文參考文獻一的前兩章，它用一個很小而很簡單的例子說明了什麼是遞迴下降，怎麼編寫遞迴下降的分析程式。這裡就不詳細描述CScanGenner是怎麼使用遞迴下降的，主要來看看它是怎麼進行從正則運算式到NDFA再到DFA的轉換的。

首先我們來看看一個隻含有兩個詞法描述，即兩個正則運算式的例子:

Slash = 『\』;

LineTernimator = 10, 13;

Letter = 『a』..』z』, 『A』..』Z』;

UnderLine = 『_』;

Digit = 『0』..』9』;

SingleLineComment = Slash . Slash . NOT(LineTerminator)*;

Identifier = (Letter,UnderLine).(Letter,UnderLine,Digit)*

上面藍色部份就是正則運算式，而深紅色部份是對字元所屬類別的定義。正則運算式定義了兩個在C語言中常用的詞法符號，一個就是單行註釋，另一個就是前面已經描述過的識別字。現在我們來主要看看單行註釋這個正則運算式是怎麼被CScanGenner所翻譯的。

CScanGenner在用遞迴下降法掃瞄這個正則運算式的時候會邊掃瞄邊構造出它的語法樹。比如，先掃瞄了SingleLineComment，於是把這個構造為一個樹根：

隨後，它用一個函數對整個右邊式子進行處理，而這個函數將返回一個指標，由根結點保留住這個指標，類似下面的代碼：

RegularExp.pointer = HandleRightExp();

而在HandleRightExp()中，它又會用遞迴的方式處理它的每個小部份，比如：整個右部會被視為：Slash . Operator2，如下所示：

其中的Operator2就是「Slash . NOT(LineTerminator)*」，隨後，系統又會調用函數對Operator2進行處理，如此一步一步的遞迴下去，最後就得到了如下一棵語法樹：

    這樣，一根語法樹就構造出來了，並且，在這棵語法樹上，我們保存了這個正則運算式的所有資訊，CScanGenner就是這樣，把用戶輸入的正則運算式首先全部轉換成了這樣的語法樹保存在了記憶體中。

隨後，CScanGenner開始將正則運算式轉換成NDFA，也即它每棵語法樹都轉換成一個NDFA。

對於「.」這個連接操作而言，要想生成它的NDFA（還記得前面描述的將正則運算式轉換成嚮應的狀態圖的方法嗎？）必須先要生成它左右兩個運算元的NDFA，然後再把這兩個NDFA連接起來，因此在這裡CScanGenner採用的是「後根遍曆」演算法來遍曆整個語法樹，並在遍曆的同時生成對應的NDFA，由於一個正則運算式就對應一個語法樹，因此，當整個語法樹都轉換成一個NDFA的時候，這個正則運算式也就轉換成了其相應的NDFA。

在前面我們已前描述了怎樣把由「.」（連接）、「*」（閉集）、「|」（或）關係組合的兩個NDFA合成一個NDFA，現在我們來看一看對於葉結點（如上圖的「Slash」結點）怎麼轉換成一個NDFA。其實這非常簡單，讓我們用下面一幅圖來說明：

上圖中還有一個NOT（非）關係，它可以是如下的格式：

NOT(A, B, C, … )

對於上面這種「非」關係，在CScanGenner中是把它轉換成一個大的「|」（或）關係來處理的，首先，它把所有的類別都加入一個集合中，然後，再把NOT括弧中涉及到的類別從集合中刪除，這樣就得到了一個許可集合，然後，按照「|」（或）關係，把這個集合中所有的元素（當然，每個元素會以產生「Slash」的NDFA一樣的方式先產生一個NDFA）產生的NDFA組合成一個NDFA。

現在我們來看看CScanGenner中是用怎樣一種結構來表示一個NDFA的。從狀態轉換圖上我們可以直觀的看到一個NDFA由若干個狀態（即圖中的小圈）組成，每一個狀態還有一定數量的轉換邊，而每一個轉換邊上還綁定著一個輸入字元，並且，每個轉換邊還指出了通過它可以達到的狀態。

在CScanGenner中，首先定義了一個名為：struct_transEdge的結構來表示轉換表：

struct struct_transEdge

{

int classNum;

int nextState;

enum_tossSaveFlag tossSaveFlag;

};

其中classNum指明了綁定在這條轉換邊上的輸入字元，nextState指明了這條轉換邊指向的狀態，tossSaveFlag這個標誌在後面會有詳細描述，這裡暫時不用理會它。

接著，CScanGenner定義了一個名為：struct_triple的結構來表示NDFA中的一個狀態：

struct struct_triple

{

int transEdgeNum;

struct_transEdge transEdge1;

struct_transEdge transEdge2;

};

從這個結構上我們可以看見，在CScanGenner中的每個NDFA的狀態最多含有兩個轉換邊，這主要是為了方便處理，那兩條轉換邊是不是就足夠了呢？如果遇見下面的情況怎麼辦：

這種情況其實可以加入epsilon轉換邊（即前面的狀態圖中所使用的紅色邊，它表示可以不需要任何輸入即能在兩個狀態之前自由轉換）及輔助狀態來保證每個狀態最多有兩個轉換邊，如上面的狀態圖可轉換為：

一個正則表達示所對應的NDFA，其實就是一個struct_triple元素組成的陣列，這樣我們就把用戶輸入的正則運算式轉換成了一個一個的NDFA，也即一個一個的由struct_triple元素組成的陣列。

接下來，我們就應當把所有的這些NDFA轉換成一個DFA了。系統把所有的這些NDFA（每一個正則運算式對會產生一個NDFA）看做是由或關係組成的一個巨大的NDFA，如下圖所示：

然後，用本文開頭所描述的子集化方法，把所有的NDFA轉換成了DFA，最後，把這DFA輸出為一張狀態表，CScanGenner的任務也就完成了。

上面描述的東東就是整個CScanGenner的核心演算法及實現方式，至於更詳細的內容請參看CScanGenner的源代碼，其中有很詳細的註釋。

下面我們來談談這其中可能會遇到的一些問題，及CScanGenner對之的處理方式。對於這些問題，如果您有更好的處理方式的話，請來信告訴我。

第一個問題，我們來看看如果用戶有兩個正則運算式可以匹配一個輸入，比如對於正則運算式：a|ab*，它的狀態圖如下所示：

在這種情況下，如果我們仍用前面的子集化方法，那麼得到的DFA的狀態轉換圖就如下所示：

現在問題出來了，看上圖的第二個狀態，它含有原NDFA中的狀態2、3。在原來的NDFA中，狀態2、3都是終態，因此上圖的第二個狀態所對應的終態到底應當是原NDFA中狀態2所對應的終態還是狀態3所對應的終態呢？這就起了衝突，也即，如果用戶的詞法描述檔中有類式的情形：

TOKEN A = a;

TOKEN B = ab*;

那麼，CScanGenner在最後產生出的DFA中就會發現有一個狀態包含了兩個NDFA中的終態，這就說明一個輸入可以被兩個正則運算式進行匹配，對於這種情況，CScanGenner會直接輸出錯誤資訊。

還有一個問題是由{TOSS}指示符引起的。CScanGenner繼承了原ScanGen的一個特點，就是可以使用一個稱之為{TOSS}的指示符，這個指示符會指示當前的輸入字元不被加入到輸出緩衝區中，這在某些時候是非常有用的，比如，下面一個正則運算式：

Slash = 『』;

Quote = 『」』;

TOKEN A = Slash{TOSS} . Quote;

上面這個正則運算式可以匹配一個轉義符與引號連用的情況（「），在這種情況下，由於Slash後面有{TOSS}因此，Slash符號()就不被加入輸出緩衝區中，這樣最後返回給用戶的TOKEN就是單純的Quote(「)了。再比如在對字串就是匹配時，我們可以在正則運算式中對開頭與結尾的兩個引號後加上{TOSS}標誌，這樣只有字串的內容可以被返回給用戶串，而字串開頭與結尾的引號就不會返回給用戶了。

但是{TOSS}標記符的濫用也會導致一些問題，比如看下面的一個正則運算式：

a{TOSS}b|ac

它的意思是如果輸入是ab的話就不返回前面的a，如果是ac的話就原樣返回a（不進行TOSS操作），這個正則運算式的狀態圖如下所示：

現在我們用子集化的方式把它轉換成DFA：

問題就出來了，對於那個a，我是應當加入{TOSS}還是不應當加入{TOSS}呢？這就起了衝突。對於出現這種情況，目前的CScanGenner的解決之道就是簡單的將其做為一種錯誤給報告出來。

這裡還需要把前面的一個遺留問題提一下，在支持{TOSS}指示符後，每個轉換邊又多了一個屬性來保存這個轉換邊上是否使用了{TOSS}指示符，還記得前面描述轉換邊的結構體：struct_transEdge中有一個tossSaveFlag標誌嗎？

CScanGenner是一個開放原始碼的軟體，目前它已經幾個項目中實際運用了，但是他還不是一個很完善的東東，比如說它最後生成的DFA還沒有優化，不是最簡DFA，另外前面所談到的問題的解決方式還比較初級。非常歡迎您能對CScanGenner進行開發與完善，也歡迎您在您的專案中自由的使用這個工具（當然，需要您遵守MIT許可協定:），你可以參考網址：http://code.google.com/p/xyb/wiki/csg以獲得關於它的全部源代碼及其餘資源。

[1] MIT許可協定由BSD協定發展而來，與BSD協議幾乎完全相同，並且取消了廣告條款的限制。簡單來說就是只要聲明你的項目源於誰，你基本上就可以完全自由的處理所獲得的資源，包括商業使用。詳細內容可以查看：http://www.opensource.org/licenses/mit-license.php

[2] 原始碼下載：svn co http://xyb.googlecode.com/svn/trunk/csg csg