在之前的六篇文章中，我比較詳細的介紹了與詞法分析器相關的算法。它們都比較關注於實現的細節，感覺上可能比較凌亂，本篇就從整體上介紹一下如何定義詞法分析器，以及如何實現自己的詞法分析器。
第二節完整的介紹了如何定義詞法分析器，可以當作一個詞法分析器使用指南。如果不關心詞法分析器的具體實現的話，可以只看第二節。
一、類庫的改變
首先需要說明一下我對類庫做的一些修改。詞法分析部分的接口，與當初寫《C# 詞法分析器》系列時相比，已經發生了不小的改變，有必要做一下說明。
1. 詞法單元的標識符
詞法單元（token）最初的定義是一個 Token 結構，使用一個 int 屬性作為詞法單元的標識符，這也是很多詞法分析器的通用做法。
但後來做語法分析的時候，感覺這樣非常不方便。因為目前還不支持從定義文件生成詞法分析器代碼，只能在程序裡面定義詞法分析器。而 int 本身是不具有語義的，作為詞法單元的標識符來使用，不但不方便還容易出錯。
後來嘗試過使用字符串作為標識符，雖然解決了語義的問題，但仍然容易出錯，實現上也會復雜些（需要保存字符串字典）。
而既簡單，又具有語義的解決方案，就是使用枚舉了。枚舉名稱提供了語義，枚舉值又可以轉換為整數，而且還能夠提供編譯期檢查，完全避免了拼寫錯誤，所以現在的詞法單元便定義為 Token<T> 類，與之相關的很多類也同樣帶上了泛型參數 T。
2. 命名空間
之前的命名空間是 Cyjb.Compiler 和 Cyjb.Compiler.Lexer，現在被改成了 Cyjb.Compilers 和 Cyjb.Compilers.Lexers，畢竟命名空間名稱還是比較適合使用復數。
3. 詞法分析器上下文
之前對詞法分析器上下文的切換，可以使用上下文的索引、標簽或 LexerContext 實例本身。但現在只能夠通過標簽進行切換，這樣實現起來更簡單些，使用上也不會受到過多影響。
4. DFA 的表示
原先 LexerRule 類中對 DFA 的表示有些簡單粗暴，對於不了解具體實現的人來說，很難理解 DFA 的表示。現在重新規劃了 LexerRule<T> 類中的接口，理解起來會更容易些。
二、定義詞法分析器
這一節是 Cyjb.Compilers 類庫中詞法分析器的使用指南，包含了完整的文檔、實例以及相關注意事項。類庫的源碼可以從 Cyjb.Compilers 項目找到，類庫文檔請參見 wiki。
1. 定義詞法單元的標識符
前面說到，目前是使用枚舉類型作為詞法單元的標識符，這個枚舉類型中的字段可以任意定義，沒有任何限制。不過，為了方便之後的語法分析部分，特別要求枚舉值必須是從 0 開始的整數，枚舉值最好是連續的，因為不連續的枚舉值會導致語法分析部分浪費更多的空間。
使用特殊的值 -1 來表示文件結束（EndOfFile），該值可以從 Token<T>.EndOfFile 字段得到，也可以通過 Token<T>.IsEndOfFile 屬性獲取詞法單元是否表示文件結束。
這裡仍然使用計算器作為示例，以下代碼便定義了作為標識符的枚舉：
在使用的時候，顯然會比整數更加方便。
2. 定義詞法分析器的上下文
詞法分析器的所有定義都是從 Cyjb.Compilers.Grammar<T> 類開始的，因此首先需要實例化一個 Grammar<T> 類的實例：
詞法分析器的上下文，可以用來控制規則是否生效。上下文有兩種類型：包含型或者排除型。
如果當前是包含型上下文，那麼會激活當前上下文的所有規則，同時會激活所有沒有指定任何上下文的規則。
如果當前是排除型上下文，那麼只會激活當前上下文的所有規則，其它任何規則都不會被激活。
使用以下的方法來分別定義排除型和包含型的詞法分析器上下文，label 參數即為上下文的標簽：
默認的詞法分析器上下文是 "Initial"，通過該標簽可以切換到默認的上下文中。需要特別注意的是，由於實現上的原因，上下文必須先於所有終結符定義。
例如，以下的代碼定義了一個包含型上下文 Inc，以及一個排除型上下文 Exc。
3. 定義正則表達式
使用以下的方法來定義正則表達式：
正則表達式可以通過 Cyjb.Compilers.RegularExpressions.Regex 類的相關方法構造得到，也可以直接使用表示正則表達式的字符串，相關定義的規則可以參考 《C# 詞法分析器（三）正則表達式》。
注意，這裡定義的正則表達式僅僅用於簡化終結符定義，方便重復使用一些通用或復雜的正則表達式，並沒有其它的作用。這裡定義的正則表達式也不可以包含向前看符號（/）、行首限定符（^）、行尾限定符（$）或者上下文（<context>）。
例如，以下代碼定義了一個名為 digit 的正則表達式，以後需要表示數字的時候，就可以直接通過 “{digit}” 來引入，而不需要每次都寫 “[0-9]+”。
4. 定義終結符
使用 Grammar<T>.DefineSymbol 方法的相關重載來定義終結符，如以下代碼所示：
這些重載被分成了三組。第一組重載，接受 T id 作為與詞法單元對應的標識符，和相應的正則表達式及其上下文。當相應的終結符被匹配後，自動返回標識符為 id 的 Token<T> 實例。
第二組重載，具有額外的參數 action，這是只包含一個 ReaderController<T> 參數的委托，當匹配了相應的終結符時，就會被調用。通過 ReaderController<T> 的相應屬性和方法，可以對詞法分析過程進行一些控制。
最後一組重載，缺少了標識符 id，也就無法自動返回 Token<T> 實例，因此必須指定匹配到相應終結符時要執行的方法。
在成功匹配某個終結符時，就會執行相應的動作，該動作是一個 Action<ReaderController<T>> 類型的委托。
ReaderController<T> 類包含了與當前匹配的終結符相關的信息，包括上下文、標識符、源文件和文本。主要的方法有 Accept、More、Reject 以及操縱上下文的方法 BeginContext、PopContext 和 PushContext。
Accept 方法會接受當前的匹配，詞法分析器會返回表示當前匹配的 Token<T> 實例。
More 方法會通知詞法分析器，保留本次匹配的文本。假設本次匹配的文本是 "foo"，下次匹配的文本是 "bar"，如果本次匹配時調用了 More 方法，下次匹配的文本就會變成 "foobar"。
Reject 方法會拒絕當前的匹配，轉而使用次優的規則繼續嘗試匹配。詳細信息請參考《C# 詞法分析器（六）構造詞法分析器》的 2.4 節“支持 Reject 動過的詞法分析器”。
Accept 方法和 Reject 方法不能夠在一次匹配中同時調用，因為它們是互斥的動作。如果在一次匹配中兩個方法都沒有調用，那麼詞法分析器會什麼都不做——丟棄本次匹配的結果，直接進行下一次匹配。
對於詞法分析器上下文的控制，簡單的用法就是利用上下文來切換匹配的規則集，以實現一些“次級語法”，可以參考《C# 詞法分析器（六）構造詞法分析器》的 3.3 節給出的示例“轉義的字符串”。
下面給出計算器的終結符定義。其中，Id 的定義是通過引入正則表達式 digit 來完成的，而且它定義了自己的動作，會將自己對應的文本轉換為 double 類型，並保存到 Token<T>.Value 屬性中。最後一條語句，通過定義空的動作，使得匹配到的空白被丟棄。
5. 構造詞法分析器
以上四步便完成了詞法分析器的定義，接下來就是構造詞法分析器。使用以下四個方法，就可以直接構造出相應的詞法單元讀取器（TokenReader<T> 的子類的實例）：
查看本欄目
三、自定義詞法分析器
Cyjb.Compilers 項目中，提供了完整的詞法分析器實現。但是，在實際的使用中，難免會遇到各種各樣的需求，可能已實現的詞法分析器是無法滿足的，此時就必須自己完成詞法分析器了。
在完成定義詞法分析器後，可以從 Grammar<T>.LexerRule 屬性獲取到一個 Cyjb.Compilers.Lexers.LexerRule<T> 對象，該實例中存儲了一個詞法分析器所需的全部信息，並且不會依賴於原始的 Grammar<T> 對象。它就是自定義詞法分析器的核心。
下圖是與 LexerRule<T> 對象相關的類圖。這四個類表示了詞法分析器的核心信息，即生成的 DFA 的數據。
圖 1 與 LexerRule<T> 相關的類圖
LexerRule<T>.CharClass 屬性保存了與字符類相關的數據，這是一個長度為 65536 的數組，保存了每個字符所屬的字符類。使用從 0 開始的連續整數表示不同的字符類，所有包含的字符類的數量可從 LexerRule<T>.CharClassCount 屬性獲取。關於字符類的詳細信息，請參考《C# 詞法分析器（四）構造 NFA》的第三節“劃分字符類”。
LexerRule<T>.Contexts 屬性保存了與詞法分析器的上下文相關的數據，這是一個字典，其鍵為上下文的標簽，值為相應的 DFA 頭節點索引。LexerRule<T>.ContextCount 屬性表示了上下文的數量。
LexerRule<T>.Symbols 屬性是定義的終結符的列表，列表的每一項都是一個 SymbolData<T> 結構，包含終結符的標識符、動作和向前看信息。
LexerRule<T>.States 屬性是詞法分析器的 DFA 狀態的列表，列表的每一項都是一個 StateData 結構，包含相應 DFA 狀態的轉移和對應的終結符索引。這個列表中實際上包含 ContextCount×2 個 DFA，這些 DFA 的首節點索引是從 0 到 ContextCount×2-1，其中每個上下文對應 2 個 DFA，前一個 DFA 對應於當前上下文中的所有非行首規則，用於從非行首位置進行匹配；後一個 DFA 對應於當前上下文中的所有規則，用於從行首位置進行匹配。索引為 i 的上下文，對應的兩個 DFA 就是 i*2 和 i*2+1。關於行首和非行首規則的詳細信息，請參考《C# 詞法分析器（四）構造 NFA》的第四節“多條正則表達式、限定符和上下文”。
以上就是詞法分析器所需的信息，只要獲取了這些信息，就可以根據需要，構造自己的詞法分析器。詳細的實現，請參考《C# 詞法分析器（六）構造詞法分析器》中提供的算法，甚至可以將數據寫入 .cs 文件中（甚至可以使用其它語言實現，因為數據本身是不影響實現的），實現詞法分析器的生成（雖然現在我還仍未實現這點）。
以上的數據，全部是以比較容易理解的形式存儲的，未進行壓縮，所以可能會占用比較多的空間。在具體的實現中，可以根據需要改變數據存儲格式，或選用一些壓縮算法（如使用四數組壓縮 DFA 狀態）。
作者：CYJB
出處：http://www.cnblogs.com/cyjb/
