[轉]裝配腦袋：自己動手開發編譯器

原文：http://www.cnblogs.com/Ninputer/archive/2011/06/06/2073908.html

自己動手開發編譯器（零）序言

好久沒寫部落格了，一來是自己懶，二來是最近一段時間都沒有做什麼自己認為可以分享的東西。這幾天剛好重拾了一個一直打算做但沒做的編譯器類庫，算是積累了一點小小的經驗吧。本來我已經發到了Github上，也在微網誌上零星介紹了一些，但是我最終意識到，如果不寫一個詳細的文檔，别人就不能容易地學習、了解和使用它。甚至于我自己也可能會把這次研究出來的小小成果給忘了。是以，必須下決心動一動筆頭，也算是對老長時間不些部落格的彌補吧。

[轉]裝配腦袋：自己動手開發編譯器

本篇是系列的第零篇，我首先要介紹一下些這個系列的目的。從很久以來，編譯器的技術就是計算機科學的基礎。我想程式設計語言在大家軟體開發生活中的重要性不言而喻。那麼，為什麼我們需要了解編譯器内部的原理呢？有很多原因：首先，編譯原理是一門經過長期實踐完善的理論，它涵蓋了很多算法，都是非常經典的算法。從前端到後端，編譯器設計到的很多算法，都很強大、快速。比如我們經常要用到的正規表達式解析字元串的算法。通過學習編譯原理，可以更加深刻地了解和應用這些算法。比如明白正規表達式能夠表示何種語言，不能表示何種語言，何時性能最好，何時性能不好等，這樣就能夠在實踐中更加科學地加以采用。其次，我們處在一個程式設計語言爆發的時代，我們所熟悉的語言每個版本都有新特性，更不要說各種新型語言、腳本、DSL和其他基于格式化文本的協定層出不窮。掌握一些編譯原理的知識能讓我們在這個時代更具有主動性。大家都知道，老趙最近開發的Jscex，它給javascript引入了優美的異步程式設計模型。相信大家不僅想崇拜老趙，更想知道為什麼他能開發出這種創新的技術吧？其實很多知識就來自于編譯原理。最後，我想說下我自己的學習目的。大家最近都知道C#5就快要出來了，在感歎變化之快的同時，是否也有一絲遺憾，那就是自己心目中的語言特性還是沒有出現在C#5中呢？我相信各位有些人對程式設計語言的發展是感興趣的，那麼就不要停留在對各個語言特性品頭論足的階段了，動手來實作自己心中的想法吧！隻有實踐，才能知道自己的想法是不是對的，是不是有價值。實踐是最好的學習方式。我想各位起碼在大學期間都學過了編譯原理這門課程，但是還有許多實際問題值得挑戰，比如C#和VB等語言的源檔案裡支援中文，甚至變量和函數都可以用中文，那麼怎麼做才能在程式設計語言裡支援中文？在大學學習的時候，也許沒有處理過面向對象語言，那麼面向對象語言有什麼不同？有很多重載方法的時候，如何挑選一個最合适的？甚至再進階一步可以考慮如何實作一個支援泛型的程式設計語言？Lambda表達式捕獲變量是怎麼做到的等等。至于編譯器後端，那更是一個廣闊的話題，涉及的技術可能幫助你深入作業系統和硬體的内部。

在一般人眼裡，編譯原理是個比較難掌握的理論體系。首先必須承認編譯器涉及的技術非常廣泛，每一種又可以非常深入，确實像個無底洞。是以這次我采用一個實際的例子，編寫一個簡單但具有基本功能的程式設計語言，在這個過程中逐個了解其中的技術。這樣就可以邊學習邊實踐。建議感興趣的同學跟着動手實踐，體會其中的樂趣。我并不會完全重複編譯原理書本中的理論，而是會面向對現代編譯器中的實際問題進行讨論。我想讓我這個系列具有較高的實踐價值。

本系列将會圍繞我開發的一個編譯器開發庫——VBF.Compilers來進行。這個庫涉及編譯器前端各個階段所需要的工具，如詞法分析器、文法分析器的構造，以及讀取源檔案、記錄編譯錯誤的輔助設施等。完全由我來開發。有人可能要問我為何不用些現成的工具，比如ANTLR之類的呢？首先這些現成工具都有一些小毛病，不能令我完全滿意；其次我的VBF與這些工具不同，它是一個純粹的類庫，隻需要在VB或C#中引用，然後用VB或C#的文法來編寫，就可以寫出各種編譯器子產品來。比起依靠一堆工具架構的，我更喜歡類庫這種形式。另外我的類庫中也包含了我的一些小小創新，希望能給編譯器開發帶來一些友善。在這個系列裡，我會兼顧VBF.Compilers的實作原理和其用法。大家如果想快一點實踐呢，可以直接使用我的類庫；如果不喜歡我的類庫呢，也可以自己實作或者用别的代替，總之看大家的興趣了。作為例子，我會在這個系列中實作一個C#語言的極小子集miniSharp，它的文法大家都再熟悉不過了，各位有興趣可以對其随意擴充。

VBF.Compilers類庫和例子的源代碼已經全部上傳至Github:https://github.com/Ninputer/VBF 請大家自行用git下載下傳最新的代碼。（注，請别擔心，它雖然叫”VBF“但其實100%是C#開發的……）。另外歡迎大家關注我的微網誌：http://weibo.com/ninputer 我會經常在上面播報開發狀态，另有許多其他豐富的資訊~

好，那就請大家期待我這一系列的文章吧。

自己動手開發編譯器（一）編譯器的子產品化工程

本系列的第一篇，我想概述一下編譯器的構造，同時幫助大家了解編譯器中各個組成部分的用途。想必大家看别的編譯原理書籍，大都在第一章或者序言之類的地方，将編譯器分成許多子產品，然後每一個子產品負責編譯的特定階段，最後串起來組成完整的編譯器。比如下面這張圖就是虎書（Modern Compiler by Andrew W. Appel）第一章中出現的編譯器階段示意圖：

那麼，為什麼要将編譯器拆成一個個階段，一個個子產品呢？答案是，為了更加容易設計和了解。一個完成編譯器怎麼也算是一項大工程，如果不将其分解，将是非常難以編寫和維護的。而編譯器的子產品劃分得越清晰，工作就越簡單。比如在詞法分析階段将輸入的字元流轉化成單詞（token）流，就大大減少了文法分析階段需要判斷的輸入種類，在簡化設計的同時還有助于提高性能。此外子產品化還将編譯器各個階段的工作盡量獨立開。比如編譯器可以進行與具體CPU無關的優化，也可以針對某種CPU進行特定的優化，都可以分别獨立進行而不用重新設計整個系統。

有個事實可能會令人感到驚訝，編譯器的各個階段和子產品如何設計，甚至跟這種程式設計語言的文法有關。比如早期的程式設計語言Fortran，在設計當初人們還沒有掌握現在這麼多編譯原理的理論，它的文法就不能像當今的語言一樣清晰地分成詞法分析和文法分析等階段。因為Fortran的文法并不包含可以用自動機獨立處理的詞法結構。于是，Fortran語言的編譯器在文法分析方面就比較繁雜。有一些曆史背景的語言也可能會具有這種複雜化的文法，比如Visual Basic也屬于不能用獨立的、基于自動機的詞法分析器來掃描的語言。是以VB的文法分析器就要比諸如C#等思路較新語言的難寫很多。另外一個例子是早期的Pascal語言和某些C語言允許用一些特定的文法來指定某變量為寄存器變量（也許在近期的Delphi中仍然存在，求證）。這是因為當時還沒有非常有效的寄存器配置設定算法，需要程式員憑自己的經驗來決定。在今天如果一種語言還允許顯式指定某個變量是寄存器變量，就會幹擾寄存器配置設定子產品的設計。綜上所述我想給各位未來的編譯器設計師們一個建議，好好設計你們的文法，就能大大簡化編譯器的設計！

除了簡化設計之外，将編譯器的各個階段子產品化還有更大的價值。原先我們認為編譯器隻要把源檔案編譯成最終的目标代碼就好了。但是随着各種各樣的開發工具出現——編輯器、自動完成、調試器、重構工具、測試覆寫率檢測、性能剖析器…… 人們發現編譯器編譯過程中，各個階段産生的結果都可能是非常有價值的。将編譯器内部結構和中間結果暴露給使用者是必然的趨勢。比如Visual Studio下一代産品中将提供的Compiler as a Service特性，其做法就是将編譯器的内部子產品暴露給使用者成為一種服務。我舉幾個例子可以讓大家看到編譯器子產品的輸出有哪些可能的用途：

編譯器的階段	産生的結果	用途
詞法分析	單詞流	文法高亮
文法分析	抽象文法樹	文法高亮；代碼格式化；代碼折疊
語義分析	帶類型資訊和符号表的抽象文法樹	重命名；重構；代碼自動生成；代碼自動改寫
資料流分析	控制流圖、沖突圖	編輯後繼續運作（Edit and Continue）

這裡我隻是舉幾個簡單的例子，以上結果的用途當然不會僅限于此。我相信将編譯器的内部子產品暴露給使用者還能産生無數有趣和有價值的應用。

上述編譯器的各個階段還可以根據其用途分成兩個大階段：詞法分析、文法分析和語義分析重點在處理程式設計語言的符号系統上，統稱為編譯器的前端（front-end），而中間代碼生成、規範化、指令選擇、控制流分析、資料流分析、寄存器配置設定、指令流出、彙編、連結等着重處理代碼計算邏輯的階段統稱為編譯的後端（back-end）。應該說現代編譯器研究的工作重點是編譯器的後端，因為前端的技術已經相對非常成熟。但是前端的技術對我們日常開發來講可能更有機會用到，而且通常更具趣味。是以我也會花較多時間在前端技術上。當大家完成一種編譯器的前端後，有幾種實作後端的選擇：

使用CLR或Java虛拟機作為後端。因為這些大型虛拟機的抽象程度極高，這種方法是最容易的。非常适合動态語言和腳本。
采用可靠的開源或商業後端架構。比如著名的LLVM（http://llvm.org/）。這樣可以直接利用LLVM的性能優化成果，以及跨平台等特性。
自己實作後端。要做的事情比較多，但更有助于了解翻譯和優化代碼的技術。
解釋執行。不解釋。。。

我将展示的例子miniSharp雖然是C#文法的子集，但是并沒有限定必須運作在CLR之上。我會将它設定成一個可重定向的語言，即可以針對多種後端。這樣就可以用一個例子示範盡可能多的技術。我也會視我自己的能力範圍和工作進度動态調整本系列的内容。也希望大家繼續關注VBF.Compilers項目（https://github.com/Ninputer/VBF）和我的微網誌（http://weibo.com/ninputer）！敬請期待下一篇。

自己動手開發編譯器（二）正則語言和正規表達式

從今天這一篇起，我們就來正式揭開編譯器的奧秘。首先我們接觸到的子產品是詞法分析器，也叫詞法掃描器，代碼裡我常常叫它Scanner。昨天我稍微解釋了一下為什麼需要将詞法分析單獨分離出來，今天來回顧一下這個問題。請看下面這段C#代碼：

string str = "Hello World";

即使沒有文法高亮，這段代碼也可以很明顯地分成好幾部分。首先是關鍵字string，之後是變量名str，然後是等号=，接下來是一個字元串字面常量”Hello World”。現代語言如C#這樣的，都能明顯地将源代碼分斷成這樣具有明确含義的片段，我們稱之為詞素（lexeme）。與描述整個C#語言的文法相比，我們用比較簡單的規則就能描述不同類型的詞素。比如上面這段代碼中出現的詞素用白話來描述的話就是：

類型	規則	例子
關鍵字string	正好是s-t-r-i-n-g這幾個字母按順序組成	string
辨別符（變量名）	由字母開頭，後面可以跟零個或多個字母或數字，但不能與關鍵字沖突	str
等号	一個=符号	=
字元串字面常量	由雙引号開始，中間可以包含任意個不是雙引号的字元，最後以雙引号結尾	"hello world"
分号	一個;符号	;

我們看到，不同詞素可以根據其特征劃分到幾個類型當中，而接下來的文法分析階段，就可以直接以詞素的類型——我們稱之為單詞（token）——作為輸入。token有時候也翻譯成令牌、記号、象征什麼的，在本文中統一稱為單詞。如此可見，隻要用相對簡潔的規則，就能把原本字元串組成的源檔案，分解為一串單詞流，這樣就能大大簡化接下來的文法分析。這就是我們把詞法分析單獨分出來作為一個子產品的根本原因。

不過，上面表格中所列的規則是用白話來描述的，我們希望能用一種形式化的語言來進行描述，以便計算機自動進行處理。正規表達式就是一個理想的選擇。

大家日常程式設計中估計多多少少都接觸過正規表達式，用它來比對字元串等，也可能已經很熟悉其文法了。但我這次想從正規表達式的最基本概念來重新介紹一次，主要想讓大家更深地了解它。首先我們要重新定義一下“語言”這個概念。“語言”就是指字元串的集合，其中的字元來自于一個有限的字元集合。也就是說，語言總要定義在一個有限的字元集上，但是語言本身可以既可以是有窮集合，也可以是無窮集合。比如“C#語言”就是指滿足C#文法的全體字元串的集合，它顯然是個無窮集合。當然也可以定義一些簡單的語言，比如這個語言{ a }就隻有一個成員，那就是一個字母a。後面我們都用大括号{}來表示字元串的集合。所謂正規表達式呢，就是描述一類語言的一種特殊表達式，正規表達式共有2種基本要素：

表達式ε表示一個語言，僅包含一個長度為零的字元串，可以了解為{ String.Empty }，我們通常把String.Empty記作ε，讀作epsilon。
對字元集中任意字元a，表達式a表示僅有一個字元a的語言，即{ a }。

同時正規表達式定義了3種基本運算規則：

兩個正規表達式的并，記作X|Y，表示的語言是正規表達式X所表示的語言與正規表達式Y所表示語言的并集。比如a|b所得的語言就是{a, b}。類似于加法
兩個正規表達式的連接配接，記作XY，表示的語言是将X的語言中每個字元串後面連接配接上Y語言中的每一種字元串，再把所有這種連接配接的結果組成一種新的語言。比如令X = a|b，Y = c|d，那麼XY所表示的語言就是{ac, bc, ad, bd}。因為X表示是{a, b}，而Y表示的是{ c, d}，連接配接運算取X語言的每一個字元串接上Y語言的每一個字元串，最後得到了4種連接配接結果。這類似于乘法
一個正規表達式的克林閉包，記作X*，表示分别将零個，一個，兩個……無窮個X與自己連接配接，然後再把所有這些求并。也就是說X* = ε | X | XX | XXX | XXX | ……。比如a*這個正規表達式，就表示的是個無窮語言{ ε, a, aa, aaa, aaaa, …. }。這相當于任意次重複一個語言。

以上三種運算寫在一起時克林閉包的優先級高于連接配接運算，而連接配接運算的優先級高于并運算。以上就是正規表達式的全部規則！并不是很難了解對吧？下面我們用正規表達式來描述一下剛才各個詞素的規則。

首先是關鍵字string，剛才我們描述說它是“正好是s-t-r-i-n-g這幾個字母按順序組成”，用正規表達式來表示，那就是s-t-r-i-n-g這幾個字母的連接配接運算，是以寫成正則表達是就是string。大家一定會覺得這個例子很無聊。。那麼我們來看下一個例子：辨別符。用白話來描述是“由字母開頭，後面可以跟零個或多個字母或數字”。先用正規表達式描述“由字母開頭”，那就是指，可以是a-z中任意一個字母來開頭。這是正規表達式中的并運算：a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z。如果每個正規表達式都這麼寫，那真是要瘋掉了，是以我們引入方括号文法，寫在方括号裡就表示這些字元的并運算。比如[abc]就表示a|b|c。而a-z一共26個字母我們也簡寫成a-z，這樣，“由字母開頭”就可以翻譯成正規表達式[a-z]了。接下來我們翻譯第二句“後面可以跟零個或多個字母或數字”這句話中的“零個或多個”可以翻譯成克林閉包運算，最後相信大家都可以寫出來，就是[a-z0-9]*。最後，前後兩句之間是一個連接配接運算，是以最後描述辨別符“語言”的正規表達式就是[a-z][a-z0-9]*。其中的*運算也意味着“辨別符”是一種無窮語言，有無數種可能的辨別符。本來就是這樣，很好了解對吧？

從上面例子可以看出，正規表達式都可以用兩種要素和三種基本運算組合出來。但是如果我們要真的拿來描述詞法單詞的規則，需要一些便于使用的輔助文法，就像上邊的方括号文法那樣。我們定義一些正規表達式的擴充運算：

方括号表示括号内的字元并運算。[abc]就等于a|b|c
方括号中以^字元開頭，表示字元集中，排除方括号中的所有字元之後，所剩字元的并運算。[^ab]就表示除了ab以外所有字元求并。
圓.點表示字元集内所有字元的并。是以 .* 這個表達式就能表示這種字元集所能組成的一切字元串。
X?表示 X|ε 。表示X與空字元串之間可選。
X+表示XX*。這等于限制了X至少要重複1次。

用過正規表達式的同學應該都熟悉以上運算了。其實.NET中的正規表達式還提供更多的擴充文法，但我們這次并不使用.NET的正則庫，是以就不列出其餘的文法了。

我們把所有能用正規表達式表示的語言稱作正則語言。很遺憾，并非所有的語言都是正則語言。比如C#，或者所有程式設計語言、HTML、XML、JSON等等，都不是正則語言。是以不能用正規表達式定義上述語言的規則。但是，用正規表達式來定義詞法分析的規則卻是非常合适的。大部分程式設計語言的詞素都可以用一個簡單的正規表達式來表達。下面就是上述單詞的正規表達式定義。

類型	正規表達式	例子
關鍵字string	string	string
辨別符（變量名）	[a-z][a-z0-9]*	str
等号	=	=
字元串字面常量	"[^"]*"	"hello world"
分号	;	;

我們大家平時熟悉的正規表達式是寫成上文這樣的字元串形式。但這次我們要自己處理正規表達式，寫成字元串顯然增加了處理的難度（要解析正規表達式字元串）。是以在VBF.Compilers庫的詞法分析庫中，我引入了一種用對象來表示正規表達式的手法。我定義了一個RegularExpression基類，然後為每一種正規表達式要素或運算編寫了一個子類：

其中AlternationExpression就是“并”運算，ConcatenationExpression就是“連接配接”運算，EmptyExpression當然就表示ε空字元串，KleeneStarExpression表示“克林閉包”運算（你現在可以知道克林閉包也可以叫做克林星——本來就是一星号嘛）和表示單一字元的SymbolExpression。像SymbolExpression裡面其實就儲存了它所表示的一個字元，而AlternationExpression下面儲存了兩個RegularExpression執行個體，用來表示并運算的雙方。是以，任何正規表達式都能用RegularExpression的對象樹來表示。比如正規表達式[a|b]*就可以表示為：

RegularExpression re = new KleeneStarExpression(
             new AlternationExpression(
             new SymbolExpression(\'a\'), new SymbolExpression(\'b\')));

有點像Linq to XML有木有？雖然它寫起來比字元串長了那麼一點點（觀衆：是長好多吧……），但是我們不需要解析字元串就可以獲得它的結構，這對下一步進行處理非常有幫助。好吧，我承認全都寫這麼長也受不了，是以我定義了一些輔助的靜态方法和運算符重載。上面的正規表達式可以寫成：

var re = (RE.Symbol(\'a\') | RE.Symbol(\'b\')).Many();

其中RE其實是要用using RE=VBF.Compilers.Scanners.RegularExpression;語句來聲明的别名。雖然它還是比字元串的正規表達式長一些，但考慮到無需解析字元串帶來的友善，就忍了吧。等到後面文法分析學習完了以後我會帶大家自己開發正規表達式字元串的解析器。

接下來的問題是，怎麼用正規表達式表示的規則來進行詞法分析呢？正規表達式利于我們了解單詞的規則，但并不能拿來直接解析字元串。為此我們要引入有窮自動機的概念來真正處理輸入字元串。敬請期待下一篇。

同時大家别忘了關注VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（三）有窮自動機

上回我們說到用正規表達式來表示詞法分析中的單詞規則。正規表達式的規則很容易了解，但是正規表達式并不能直接用來解析字元串，我們還要引入一種适合轉化為計算機程式的模型。今天我們引入的這種模型就叫做有窮自動機（finite automation，FA）,有時也叫有窮狀态機（finite state machine）。有窮自動機首先包含一個有限狀态的集合，還包含了從一個狀态到另外一個狀态的轉換。有窮自動機看上去就像是一個有向圖，其中狀态是圖的節點，而狀态轉換則是圖的邊。此外這些狀态中還必須有一個初始狀态和至少一個接受狀态。下面的圖展示了一個有窮自動機，有根從外邊來的箭頭指向的狀态表示初始狀态，有個黑圈的狀态是接受狀态：

現在我們來看看有窮自動機怎麼處理輸入的字元串：

一開始，自動機處于初始狀态
輸入字元串的第一個字元，這時自動機會查詢目前狀态上與輸入字元相比對的邊，并沿這條邊轉換到下一個狀态。
繼續輸入下一個字元，重複第二步，查詢目前狀态上的邊并進行狀态轉換
當字元串全部輸入後，如果自動機正好處于接受狀态上，就說該自動機接受了這一字元串。

剛才我們畫的自動機，假如輸入的字元串是"hello"（帶引号）。一開始狀态機處于狀态1，輸入引号以後就沿引号的邊轉換到了狀态2；接下來輸入hello都會沿着a-z這條邊回到狀态2，最後輸入引号，轉換到了狀态3。由于狀态3是接受狀态，那麼這個自動機就會接受這個字元串。而如果字元串是"abc（不帶後面的引号），那麼當字元串輸入完畢之後自動機會處在狀态2，而狀态2不是接受狀态，是以這個自動機就不接受"abc這個字元串。一個自動機接受的所有字元串組成的集合稱作這個自動機的語言。這裡語言的概念和上一回我們介紹正規表達式的語言概念是一樣，都表示一個有限字元集上的字元串集合。

上面我們畫的自動機是一個确定性有窮自動機（DFA），其特點是從每一個狀态隻能發出一條具有某個符号的邊。也就是說不能出現同一個符号出現在同一狀态發出的兩條邊上。但是，還有一種非确定性有窮自動機（NFA），它允許從一個狀态發出多條具有相同符号的邊，甚至允許發出标有ε（表示空）符号的邊，也就是說，NFA可以不輸入任何字元就自動沿ε邊轉換到下一個狀态。下圖展示了一個非确定性有窮自動機：

非确定性有窮自動機在遇到兩條邊上有相同的符号，會選擇哪一邊呢？遇到ε邊到底會轉移還是不會轉移呢？答案是，NFA會自動猜測應該選擇哪一條邊，而且每次都能猜對。比如說，上面的NFA，假如輸入字元串是aa，它就會選擇右邊這條路徑，并且接受這個字元串；假如輸入字元是aaa，它就會走左邊這條路徑，并接受字元串。它絕不會在輸入字元是aaa的時候選擇右邊路徑然後做出不接受這一判斷。由于我們的計算機并沒有這種“猜測”能力，大家可能會對NFA具有這種能力感到奇怪。有些人在剛剛接觸這些概念的時候可能會覺得NFA因為具有自動猜測的能力，應該要比DFA更加強大。但事實上是，DFA、NFA和正規表達式是等價的，任何NFA都存在一個與之接受同樣語言的DFA，和一個定義相同語言的正規表達式；同理任何正規表達式，也存在一個接受其所定義語言的NFA和一個DFA。這三種模型雖然定義迥然不同，但卻表示同樣的正則語言。幸運的是，隻需要很簡單的規則，就能把任何正規表達式轉化成NFA，而任何一個NFA又都可以轉化為DFA，這樣我們就能把正規表達式轉化為易于程式設計的DFA，來真正進行詞法分析的工作。（注，也有正規表達式引擎直接模拟NFA的運作來解析字元串，有興趣的讀者可以自行尋找有關的資料。）

現在我們來看怎麼把正規表達式轉化為NFA。我們上次學到正規表達式有兩種基本要素——字元表達式和ε表達式，以及三種基本運算——并、連接配接和閉包。首先我們來看最基礎的ε表達式，它的NFA是這樣的：

接下來是字元表達式a，它的NFA是這樣：

所有正規表達式都可以轉化為一個有一條輸入邊，以及一個接受狀态的的正規表達式，我們先假設一個一般的正規表達式的NFA是這樣：

然後我們定義兩個正則表達試的并運算，X|Y的NFA為：（實際應用中，常常可以簡化掉一部分ε轉換邊）

兩個這正規表達式的連接配接運算，XY的NFA為：

一個正規表達式的克林閉包運算，Y*的NFA為：

遞歸運用以上規則，就可以把任何正規表達式轉化為NFA。我們來試試看。上次研究了辨別符的正規表達式[a-z][a-z0-9]*，運用以上規則，轉換成的NFA是：

詞法分析時，我們要把所有的單詞的正規表達式分别轉換成NFA，然後用“并”的關系将所有NFA連接配接到一起，就成了詞法分析所需的最終NFA。

下面我們來看看上述邏輯在VBF.Compilers中是如何實作的。上次我們定義了一個RegularExpression基類和它的五個子類，分别對應于正規表達式的基本要素和基本運算。考慮到将正規表達式轉換為NFA是一個相對獨立的操作，是以我們采用Visitor模式，定義一個抽象類作為Visitor:

public abstract class RegularExpressionConverter<T>
{
    protected RegularExpressionConverter() { }

    public T Convert(RegularExpression expression)
    {
        if (expression == null)
        {
            return default(T);
        }

        return expression.Accept(this);
    }

    public abstract T ConvertAlternation(AlternationExpression exp);

    public abstract T ConvertSymbol(SymbolExpression exp);

    public abstract T ConvertEmpty(EmptyExpression exp);

    public abstract T ConvertConcatenation(ConcatenationExpression exp);

    public abstract T ConvertAlternationCharSet(AlternationCharSetExpression exp);

    public abstract T ConvertStringLiteral(StringLiteralExpression exp);

    public abstract T ConvertKleeneStar(KleeneStarExpression exp);
}

然後我們給RegularExpression類加上一個Accept抽象方法，讓其子類分别實作。比如，KleeneStarExpression類的Accept就可以寫成這樣：

internal override T Accept<T>(RegularExpressionConverter<T> converter)
{
    return converter.ConvertKleeneStar(this);
}

最後我們實作一個NFAConverter，實作抽象類RegularExpressionConverter<NFAModel>。其中NFAModel是我們自己定義的NFA對象模型，其中定義了狀态節點、邊等概念。下面就是NFAConverter中翻譯克林閉包的規則：

public override NFAModel ConvertKleeneStar(KleeneStarExpression exp)
{
    var innerNFA = Convert(exp.InnerExpression);

    var newTail = new NFAState();
    var entry = new NFAEdge(newTail);

    innerNFA.TailState.AddEmptyEdgeTo(newTail);
    newTail.AddEdge(innerNFA.EntryEdge);

    var kleenStarNFA = new NFAModel();

    kleenStarNFA.AddStates(innerNFA.States);
    kleenStarNFA.AddState(newTail);
    kleenStarNFA.EntryEdge = entry;
    kleenStarNFA.TailState = newTail;

    return kleenStarNFA;
}

代碼應當是相當直覺的，它就是重複上面畫圖的邏輯，先将克林閉包内部的表達式轉換成NFA，再建立一些輔助的外圍狀态和相應的狀态轉換。

有了從正規表達式轉換到NFA的算法之後，我們還需要NFA到DFA的轉換。這個轉換算法稱作“子集構造”。我們前面說過NFA遇到同一狀态發出帶有同一符号的不同的邊時，能自動猜測轉移到哪一邊。而子集構造的思想就是不猜測NFA會轉移到哪個狀态，而是假設NFA能同時處于所有可能的狀态。比如，我們重新考慮前面最開始展示的NFA。一開始，這個NFA的初始狀态就包含兩個ε轉換，我們假設NFA能同時處于所有這種ε轉換的目标狀态上，也就是說它的初始狀态其實是三個狀态的集合：

我們稱這三個狀态為初始狀态的ε-閉包（ε-closure）。接下來，如果輸入了字元a，那麼NFA就可以從目前狀态的ε-閉包内任何狀态開始，通過字元a的邊進行狀态轉換。這時，我們就得到NFA的下一個狀态：

接下來再次輸入字元a，我們也可以從目前狀态集合出發，找到下一個狀态集合：

如果字元串到此為止，這時NFA的狀态集合中包含了一個接受狀态，是以NFA決定接受字元串“aa”。也就是說，這次沒有用到猜測能力，就成功地解析了aa這個字元串。這樣我們就了解到，一定存在一個DFA，它的每個狀态都是NFA狀态的的一個子集。下面我簡單轉述一下虎書中有關子集構造算法。令edge(s, c)表示從狀态s沿着标有字元c的邊可以達到的所有NFA狀态的集合。對狀态集合S，closure(S)是從S中的狀态出發，無需接受任何字元，隻沿ε邊就可以達到的狀态組成的集合，可以用疊代法來求出：

接下來我們定義輸入一個字元之後的動作規則，從NFA狀态集合d中的狀态出發，輸入符号c，所能達到的NFA的新的狀态集合記作DFAedge(d, c)，它定義為

最後，假設構成語言的字元集是Σ，構造出整個DFA的算法是：

以上代碼在了解了子集構造的基本原理之後很容易就能夠轉換成代碼。VBF.Compilers中的NFA->DFA轉換代碼比較長，我就不貼在這裡了，有興趣的可以到github上自行下載下傳。

将正規表達式通過NFA最後轉化為DFA之後，如何進行真正的字元串掃描工作就是水到渠成的工作了。我們下一篇将介紹具體的做法，以及針對Unicode字元集的處理方式。下一篇我還會介紹VBF.Compilers.Scanners類庫的基本用法。如果大家不想自己實作整套算法，那麼下回就可以參考我的文章，用VBF庫制造出任意的詞法分析器來。是以，敬請期待下一篇！

此外别忘了關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（四）利用DFA轉換表建立掃描器

上回我們介紹了兩種有窮自動機模型——确定性有窮自動機DFA和非确定性有窮自動機，以及從正規表達式經過NFA最終轉化為DFA的算法。有些同學表示還是難以了解NFA到底怎麼轉化為DFA。是以本篇開頭時我想再多舉一個例子，看看NFA轉化為DFA之後到底是什麼樣。首先我們看下面的NFA，它是從一組詞法分析所用的正規表達式轉換而來的。這個NFA合并了IF、ID、NUM、error這四個單詞的NFA。是以，它的四個接受狀态分别代表遇到了四種不同的單詞。

用上一篇學到的方法，我們需要求出一個DFA，它的每個狀态都是NFA狀态集合的一個子集。首先我們要定義任何狀态的ε-閉包，之是以叫ε-閉包，是因為它對ε轉換而言是封閉的，也就是說ε-閉包内任何狀态，經過ε轉換之後，都還是閉包内的一個狀态。接下來，從初始狀态ε-閉包開始，我們要計算輸入任何一種字元後，NFA所能轉換到的下一個狀态集合。這一步的公式是：

其中那個U型的符号，表示：對NFA狀态集合d中的任何狀态s，求出s在遇到符号c之後所能達到的所有狀态組成的集合，再把所有這種集合求并集。最後，再對這個集合求出ε-閉包。我很難找出一種更簡單的描述方式，簡而言之就是要計算出NFA狀态集合d，在輸入符号c之後，所能達到的一切狀态的新集合。而這個集合，就會變成DFA的一個狀态，這個狀态是從d，沿着一條标有c的邊達到的。我們首先求出初始狀态的ε-閉包作為DFA的初始狀态，然後，我們要反複從目前已知的NFA狀态集合出發，計算輸入任意字元後所能達到的新狀态集合，直到不能再找出新的NFA狀态集合為止。這一段算法的确是有一點考驗思考能力的，是以建議大家畫幾個簡單的NFA，照着上一篇中的公式比劃一下，多思考思考，一定可以了解的。下面我貼出上邊NFA轉換而成的DFA，讓大家對NFA轉成的DFA有個感性的認識：

大家可以看出，轉換而成的DFA每一個狀态都是由若幹個原NFA狀态組成的集合。而任何狀态集合，其中隻要有一個是NFA的接受狀态，我們就将它作為DFA的接受狀态。注意，有些狀态中可能包含不止一個NFA接受狀态。比如上圖接受IF的狀态是NFA的狀态集合{3,6,7,8}，其中3号是NFA中接受IF的狀态，而8号則是NFA中接受ID的的狀态。那麼為什麼我們選擇讓DFA狀态接受IF而不是ID呢，因為IF是關鍵字，ID是辨別符，我們必須讓IF的優先級高于ID，不然就無法在詞法分析的時候解析出if關鍵字。也就是說，在設計詞法分析其的時候我們要讓所有的保留關鍵字優先級高于ID，這一點就是在DFA接受狀态的選取上展現出來的。

一旦完成了NFA->DFA的轉換，DFA狀态就沒有必要保留原來NFA狀态集合的資訊了，我們完全可以把DFA進一步抽象為一個表，其中表的一行就是DFA的一個狀态，而每一列就是一個字元。這是上一篇我們引入的第一個DFA：

将這個DFA寫成狀态轉換表的形式，就成了這樣：

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	"
1	2
2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	3
3

這個表可能跟大家想象當中有一點點不一樣，我們來觀察一下：首先這個表比DFA狀态圖中多一個狀态0，而且這個狀态上，無論輸入什麼字元都轉到狀态0上。我們稱這個狀态為停機狀态。在實踐當中，我們一律使用狀态0作為停機狀态。停機狀态的含義就是，一旦狀态機到達這個狀态就“死”了，它再也不能離開這個狀态。等一下我們再看為什麼需要這個停機狀态，先來看看狀态1。在這個狀态上，當輸入字元是"（引号）的時候，就會轉換到狀态2，這跟上面的DFA狀态圖一緻；而如果輸入字元是a-z之類的，全部都轉到狀态0，也就是停機狀态。這意味着在狀态1，接受這些（a-z）字元是未定義的，會導緻DFA死掉。接下來是狀态2，這個狀态應該和大家的預期是一樣的，a-z的字元輸入，會回到狀态2，而輸入引号則會轉到狀态3。最後是狀态3，因為狀态3沒有發出任何邊，是以狀态3上任何輸入字元都會導緻停機。最後我們回過頭來考慮為什麼需要停機狀态，因為我們需要它來判斷是否檢測到了一個單詞。用DFA狀态轉換表進行詞法分析的步驟是：

一開始，讓DFA處于狀态1（而不是0，切記！）。
輸入字元串的一個字元，并且檢查表中對應于這個字元的下一個狀态。
轉換到下一個狀态。同時，如果這個狀态不是0，用另一個變量記住這個狀态。
不斷輸入字元串進行狀态轉換，直到目前狀态為0（停機狀态）。
檢查另外一個變量記住的上一個狀态，如果上一個狀态是接受狀态，報報告成功掃描一個單詞；如果不是接受狀态，報告詞法錯誤。
如果要繼續解析，需要将DFA的狀态恢複到1（而不是0），再重新開始。

也就是說，我們總要等到DFA運作到停機狀态，也就是死了之後才判斷是否成功掃錨到一個單詞，這是因為我們想要詞法分析器進行最長比對。比如我們解析C#代碼：string1 = null; 這句代碼中的string1是一個辨別符，代表一個變量。如果詞法掃描器剛剛掃描到string，就報告發現了“關鍵字string”，那這裡邏輯就不對了。而如果等到DFA狀态抓換到停機狀态時再判斷，就能判斷到最長可能的的單詞。比如，當詞法分析器分析到了string時，它仍然沒有停機，于是就輸入了下一個字元"1"，這時詞法分析的狀态就從接受“關鍵字string”的狀态轉換到接受“辨別符”的狀态；然後詞法分析器發現下一個字元是空格，而空格接在string1後面并不是任何合法的單詞，是以它就會轉到停機狀态。最後我們判斷停機前最後一個狀态是接受“辨別符”的狀态，于是報告成功掃描辨別符string1。這樣就實作了最長比對的目的。

在VBF.Compilers.Scanners庫中，我采用的是一個二維數組來存儲的DFA狀态轉換表。其中有一個FiniteAutomationEngine.cs中包含了儲存DFA轉換表，以及進行狀态轉換操作的任務。最後Scanner類實作了真正的詞法分析邏輯。大家如果對上述語言描述的算法有興趣，可以直接去看這兩個類的實作。

接下來我們要考慮一個非常實際的問題。如果詞法分析器要支援Unicode字元集（UTF-16）上字元串的解析，那麼DFA轉換表會非常大。實際上，如果要支援中文的注釋、字元串或者辨別符，DFA轉換表會有4萬列以上，最多可以有65536列。這樣隻要一個狀态就會占掉sizeof(int) x 65536= 256KB的記憶體。像C#這樣的語言，DFA可能會多至幾百個狀态。即使是我們要做的C#超小子集miniSharp，也有140個狀态。這樣光DFA狀态轉換表就要占35MB記憶體。雖然現在計算機動辄就有8G記憶體，但是CPU的二級或三級緩存通常隻有幾MB，如果不能将DFA轉換表全部放進二級緩存的話，效率必然大大受到影響。我們觀察一下上面列出的DFA狀态轉換表，會發現從a-z這些字元的列都是完全一樣的，它們全都在狀态1轉到狀态0；在狀态2轉換到狀态2；在狀态3轉到狀态0。我們稱這樣轉換表的列完全相同的字元稱作同一個等價類。如果我們的DFA狀态轉換表不用字元作為列，而是使用等價類的話，就能大大縮小狀态轉換表的體積。然後，我們隻要用一個字元->等價類的映射表，就能用O(1)的時間複雜度，将任意字元映射到它的等價類。比如，在應用等價類之後，上面展示的DFA可以變成：

等價類表：

轉換表：

1
1	2
2	2	3
3

這樣一來，隻需要有一個一行的等價類表。而因為最多也就隻有65536個等價類（每種字元一個等價類），是以這個等價類表可以聲明成ushort[65536]，它隻會占128K記憶體。經過壓縮之後，miniSharp語言的等價類一共隻有57個。是以140個狀态隻需要不到32KB的記憶體即可裝下，現在它可以完全裝載到CPU的二級緩存中了，完美達成目标！

在VBF.Compilers類庫中，為了NFA-> DFA算法的高效，甚至在NFA時就計算了等價類表。當然在NFA階段計算得沒有DFA階段這樣精确，是以在轉換成DFA之後會再次計算等價類表。這種所謂的雙重壓縮法，把處理大量Unicode字元集NFA轉換所需要的數小時時間減小到了幾百毫秒。

接下來，我們就來簡單了解一下VBF.Compilers.Scanners庫的用法。首先，要寫自己的詞法分析器，需要引用VBF.Compilers.Common.dll庫和

VBF.Compilers.Scanners.dll。其中Common庫包含一個儲存編譯錯誤的類，和一個重要的類：SourceReader。這個類可以将任何TextReader作為輸入，而且還支援在讀取的過程中統計目前源代碼的行、列。是以詞法分析器就依賴于這個類來進行源代碼輸入。要定義一個詞法分析器，需要一個最基礎的類——Lexicon類。這個類相當于一個字典，它會儲存所有單詞的定義，同時在内部進行正規表達式到DFA的轉換等工作。下面的代碼示範了Lexicon類的用法：

using RE = VBF.Compilers.Scanners.RegularExpression;

…

Lexicon lexicon = new Lexicon();
LexerState lexer = lexicon.DefaultLexer;

Token IF = lexer.DefineToken(RE.Literal("if"));
Token ELSE = lexer.DefineToken(RE.Literal("else"));
Token ID = lexer.DefineToken(RE.Range(\'a\', \'z\').Concat(
    (RE.Range(\'a\', \'z\') | RE.Range(\'0\', \'9\')).Many()));
Token NUM = lexer.DefineToken(RE.Range(\'0\', \'9\').Many1());
Token WHITESPACE = lexer.DefineToken(RE.Symbol(\' \').Many());

ScannerInfo info = lexicon.CreateScannerInfo();

我們來逐行解讀一下這些代碼。首先Lexicon類直接用new就可以建立出來，無需任何參數。接下來是這樣代碼：

LexerState lexer = lexicon.DefaultLexer;

這行代碼調用了lexicon的DefaultLexer屬性，傳回了一個LexerState對象，它代表一個詞法分析器的整體狀态。後面我們就要用這個對象來定義單詞的正規表達式。預設情況下，DefaultLexer是唯一的LexerState，而且不用建立新的LexerState對象。但是假如我們需要讓某些詞素在不同環境下展示為不同的類型，就可以定義新的LexerState。比如說“get”這個詞素通常應該是一個辨別符，而在定義屬性的上下文環境下，它就變成了一個關鍵字。LexerState允許派生子狀态來支援這種場景。但目前我們先暫考慮隻有DefaultLexer的情況。

在拿到DefaultLexer之後即可使用DefineToken方法定義單詞。DefineToken接受一個RegularExpression對象作為參數。RegularExpression類（在代碼中簡寫為RE）的靜态方法可以表示正規表達式的基本運算和幾種常用的擴充運算。下面的表列出了RegularExpression常見用法：

RegularExpression類的用法	例子	表示的正規表達式
\| 運算符 Union方法	x \| y x.Union(y)	x\|y
>> 運算符 Concat方法	ｘ >> y ｘ.Concat(y)	xy
Many方法	x.Many()	x*
Many1方法	x.Many1()	x+
Optional方法	x.Optional()	x?
Range靜态方法	RE.Range(\'0\', \'9\')	[0-9]
CharSet靜态方法	RE.CharSet("abc")	[abc] （并運算）
Literal靜态方法	RE.Literal("abc")	abc （連接配接運算）
Repeat方法	x.Repeat(5)	xxxxx
CharsOf靜态方法	RE.CharsOf(c => c == \'a\')	[a] （根據lambda表達式建立一組字元的并運算集合）
Symbol靜态方法	RE.Symbol(\'a\')	a

大家可以看上面的代碼，結合這個表來學習RegularExpression的各種用法。注意，定義Token的先後順序決定了各個單詞的優先級，排在前面的更加優先。為了確定保留關鍵字的優先級，所有關鍵字必須在辨別符ID之前定義。在所有的單詞都定義完畢之後，我們調用Lexicon的CreateScannerInfo方法來得到一個ScannerInfo對象。這個對象就包含了已經轉換好的DFA和各種詞法分析器運轉所需要的參數。下一步，我們就可以用ScannerInfo對象建立出Scanner對象，請看下面的代碼：

Scanner scanner = new Scanner(info);

string source = "asdf04a 1107 else";
StringReader sr = new StringReader(source);

scanner.SetSource(new SourceReader(sr));
scanner.SetSkipTokens(WHITESPACE.Index);

Lexeme l1 = scanner.Read();
Console.WriteLine(l1.TokenIndex); //等于ID.Index
Console.WriteLine(l1.Value); //等于 asdf04a

Lexeme l2 = scanner.Read();
Console.WriteLine(l2.TokenIndex); //等于NUM.Index
Console.WriteLine(l2.Value); //等于 1107

Lexeme l3 = scanner.Read();
Console.WriteLine(l3.TokenIndex); //等于ELSE.Index
Console.WriteLine(l3.Value); //等于 else

Lexeme l4 = scanner.Read();
Console.WriteLine(l4.TokenIndex); //等于info.EndOfStreamTokenIndex
Console.WriteLine(l4.Value); //等于 null

建立Scanner對象時，需要傳入上一步生成的ScannerInfo對象，接下來可以指定輸入的源代碼。這裡我們用StringReader來讀取一段字元串源代碼。注意Scanner的SetSkipTokens方法，可以設定詞法掃描器自動跳過的單詞。比如我們不希望詞法分析器傳回空白字元的詞素，就設定跳過WHITESPACE單詞。在操作Scanner類的時候，所有與Token相關的操作都是通過Token.Index（一個整數）來完成的，因為Scanner内部僅僅儲存了Token在Lexicon内部的索引值，這樣可以減小記憶體使用并且提高效率。

一切準備就緒之後就可以調用scanner.Read()方法來進行詞法分析了！每次調用scanner.Read()會傳回下一個詞素（Lexeme對象），從Lexeme的屬性中我們可以拿到該詞素對應的單詞類型（仍然是以Token.Index整數形式），詞素的字元串表示（Value屬性）以及詞素在源代碼中位置等豐富的資訊。當掃描到檔案或字元串尾部時，scanner.Read()會傳回一個特殊的詞素表示End Of Stream。這個特殊詞素的TokenIndex可以從ScannerInfo對象查詢到（每個ScannerInfo的EndOfStreamTokenIndex會不一樣）。大家可以試着運作一下上述代碼，并且修改自己的詞法定義或源代碼，來觀察Scanner類的各種行為。另外VBF.Compilers.Scanner庫還提供了兩種具有特殊能力的Scanner——分别是PeekableScanner和ForkableScanner，未來的篇章中我們會用到它們的特殊能力。

到本篇為止，我們已經完整地讨論了詞法分析所需的各種技術和VBF的實作。下一篇我們将讨論miniSharp語言的詞法定義，并真正實作miniSharp的詞法分析器。屆時大家可以學到怎麼建立支援中文的辨別符和注釋的正規表達式。敬請期待！

此外别忘了關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（五）miniSharp語言的詞法分析器

多謝各位的一直以來的支援，我們今天總算走到了實踐的一步。今天我們要用VBF.Compilers的詞法分析庫來開發一個小型語言——miniSharp的詞法分析。miniSharp是C#語言的子集，miniSharp程式的語義就等于把它當做C#的語義。但是miniSharp隻支援很少的語言特性，以降低制作編譯器的難度。簡單來說miniSharp有如下特征：

隻有一個源檔案，不能引用其他dll（甚至不能引用.NET的類庫）。
沒有命名空間。
第一個類必須是靜态類，而且裡面隻能定義一個靜态方法Main作為程式入口。
隻能定義類，沒有枚舉、結構體、接口、委托等。
類的成員隻有私有的字段和共有的非靜态方法兩種。不支援虛方法。
方法必須有傳回值，除了Main方法之外。
支援的類型隻有int、bool、int[]和自定義的類。不支援其他類型。
僅支援一個庫函數System.Console.WriteLine，隻支援參數是int的用法。
隻支援if-else語句、while語句、指派語句、變量聲明語句和調用WriteLine語句。
隻支援+、-、*、/、>、<、==、&&、||和!運算符
每個方法隻能有一個return語句，必須是方法最後一條語句。
其他C#特性皆不支援。

大家肯定覺得這個語言“閹割”得實在太厲害了，我感興趣的泛型、Lambda表達式、Linq啥的統統都不支援，還寫個什麼勁呀。但是我勸告各位不要一口吃個胖子。如果寫大型語言，會耗費很大的經曆在文法分析、語義分析這兩步上，甚至可能會遇到困擾很久的問題，導緻我們不能很快地體驗編譯器後端的技術。是以咱們先從簡單的語言開始，一步一步來。基本原理都是一樣的，等大家熟悉之後自然就可以自己往裡面加入任何想加的特性。注：miniSharp設計參考了虎書Java版中的miniJava語言。

今天我們首先來看miniSharp的詞法分析。miniSharp語言的單詞根據優先級和不同種類可以分成以下五類：

關鍵字
辨別符
整型數字常量
各種标點符号
空白符、換行符和注釋

關鍵字大家都好了解。辨別符是有必要仔細考慮的單詞，因為我們希望miniSharp像C#一樣支援用中文做變量名或函數名，是以肯定不能使用“下劃線或字母開頭，後面跟下劃線、字母或數字”這樣的定義。參考C#語言規範，我們要用Unicode字元分類來定義辨別符。後面整型、标點符号什麼的無需多說，最後我們要讨論一下空白符、換行符和注釋的詞法規則。

先從簡單的開始，我們要為miniSharp中每一種關鍵字建立一個單詞類型。這些關鍵字都不能用作辨別符，是以都是保留字。所有關鍵字的正規表達式都是一串字元的連接配接運算，是以我們直接用RegularExpression的Literal方法來定義：

var lex = lexicon.DefaultLexer;

//keywords
K_CLASS = lex.DefineToken(RE.Literal("class"));
K_PUBLIC = lex.DefineToken(RE.Literal("public"));
K_STATIC = lex.DefineToken(RE.Literal("static"));
K_VOID = lex.DefineToken(RE.Literal("void"));
K_MAIN = lex.DefineToken(RE.Literal("Main"));
K_STRING = lex.DefineToken(RE.Literal("string"));
K_RETURN = lex.DefineToken(RE.Literal("return"));
K_INT = lex.DefineToken(RE.Literal("int"));
K_BOOL = lex.DefineToken(RE.Literal("bool"));
K_IF = lex.DefineToken(RE.Literal("if"));
K_ELSE = lex.DefineToken(RE.Literal("else"));
K_WHILE = lex.DefineToken(RE.Literal("while"));
K_SYSTEM = lex.DefineToken(RE.Literal("System"));
K_CONSOLE = lex.DefineToken(RE.Literal("Console"));
K_WRITELINE = lex.DefineToken(RE.Literal("WriteLine"));
K_LENGTH = lex.DefineToken(RE.Literal("Length"));
K_TRUE = lex.DefineToken(RE.Literal("true"));
K_FALSE = lex.DefineToken(RE.Literal("false"));
K_THIS = lex.DefineToken(RE.Literal("this"));
K_NEW = lex.DefineToken(RE.Literal("new"));

其中的lexicon是我們上一回介紹的Lexicon類建立的執行個體。

接下來我們重點來看辨別符的詞法。我們不支援C#中@開頭的辨別符，是以隻考慮一種情況。C# Spec規定辨別符開頭字元必須是一個“字母類”字元或者下劃線“_”字元。其中“字母類”并非隻是大小寫字元，而是Unicode分類中的Lu、Ll、Lt、Lm、Lo、Nl這些類别的字元。含義分别如下：

Lu表示大寫字母，包含所有語言中的大寫字母。
Ll表示小寫字母，包含所有語言中的小寫字母。
Lt表示所有詞首大寫字母（titlecase）。
Lm表示所有修飾字母（modifier）。
Lo表示其他字母，如中文、日文的字元。
Nl表示數字，但不是十進制數字，而是字母表示的。比如羅馬數字。

辨別符第二個字元開始，允許“字母類”字元和下劃線以外，還允許以下類型的字元：

組合類字元，Unicode分類Mn和Mc
十進制數字，Unicode分類Nd
連接配接類字元，Unicode分類Pc
格式類字元，Unicode分類Cf

用VBF.Compilers.Scanners類庫時，可以使用RegularExpression.CharsOf方法，借助Lambda表達式來生成Unicode字元的并集。目前我的設計處理這一塊不是十分高效，是以miniSharp的詞法就稍微簡化一點，允許以字母類的字元或下劃線開頭，然後零個或多個字母類字元、下劃線或數字，也即不支援上述定義中組合類、連接配接類和格式類字元。定義辨別符的正規表達式寫法如下：

var lettersCategories = new[] 
{ 
    UnicodeCategory.LetterNumber,
    UnicodeCategory.LowercaseLetter,
    UnicodeCategory.ModifierLetter,
    UnicodeCategory.OtherLetter,
    UnicodeCategory.TitlecaseLetter,
    UnicodeCategory.UppercaseLetter
};

var RE_IdChar = RE.CharsOf(c => lettersCategories.Contains(Char.GetUnicodeCategory(c))) | RE.Symbol(\'_\');

ID = lex.DefineToken(RE_IdChar >>
    (RE_IdChar | RE.Range(\'0\', \'9\')).Many(), "identifier");

大家可以看到我用了.NET類庫中的Char.GetUnicodeCategory方法來判斷Unicode分類。将來的VBF類庫中可能會提供Unicode分類的直接支援。接下來是整型常量和标點符号，沒有啥好說的，直接看代碼：

INTEGER_LITERAL = lex.DefineToken(RE.Range(\'0\', \'9\').Many1(), "integer literal");

//symbols

LOGICAL_AND = lex.DefineToken(RE.Literal("&&"));
LOGICAL_OR = lex.DefineToken(RE.Literal("||"));
LOGICAL_NOT = lex.DefineToken(RE.Symbol(\'!\'));
LESS = lex.DefineToken(RE.Symbol(\'<\'));
GREATER = lex.DefineToken(RE.Symbol(\'>\'));
EQUAL = lex.DefineToken(RE.Literal("=="));
ASSIGN = lex.DefineToken(RE.Symbol(\'=\'));
PLUS = lex.DefineToken(RE.Symbol(\'+\'));
MINUS = lex.DefineToken(RE.Symbol(\'-\'));
ASTERISK = lex.DefineToken(RE.Symbol(\'*\'));
SLASH = lex.DefineToken(RE.Symbol(\'/\'));
LEFT_PH = lex.DefineToken(RE.Symbol(\'(\'));
RIGHT_PH = lex.DefineToken(RE.Symbol(\')\'));
LEFT_BK = lex.DefineToken(RE.Symbol(\'[\'));
RIGHT_BK = lex.DefineToken(RE.Symbol(\']\'));
LEFT_BR = lex.DefineToken(RE.Symbol(\'{\'));
RIGHT_BR = lex.DefineToken(RE.Symbol(\'}\'));
COMMA = lex.DefineToken(RE.Symbol(\',\'));
COLON = lex.DefineToken(RE.Symbol(\':\'));
SEMICOLON = lex.DefineToken(RE.Symbol(\';\'));
DOT = lex.DefineToken(RE.Symbol(\'.\'));

稍微說明一點，整型常量和上面的辨別符的詞法，在調用lex.DefineToken時都多傳了一個參數。這個參數是可選的描述資訊，如果不傳會直接使用正規表達式的字元串形式。而辨別符的正規表達式有4萬多個字元那麼長而且沒有可讀性，是以加一個額外字元串描述一下。它将來會被用于生成編譯錯誤資訊。

最後我們來寫空白符、換行符和注釋的正規表達式。這三個是完全按照C# spec的規範編寫的。其中注釋包含了兩種：//開頭直到換行的注釋已經/*開頭直到*/的多行注釋。大家可以學習一下它們的正規表達式怎麼寫：

var RE_SpaceChar = RE.CharsOf(c => Char.GetUnicodeCategory(c) == UnicodeCategory.SpaceSeparator);

WHITESPACE = lex.DefineToken(RE_SpaceChar | RE.CharSet("\u0009\u000B\u000C"));

LINE_BREAKER = lex.DefineToken(
    RE.CharSet("\u000D\u000A\u0085\u2028\u2029") |
    RE.Literal("\r\n")
);

var RE_InputChar = RE.CharsOf(c => !"\u000D\u000A\u0085\u2028\u2029".Contains(c));
var RE_NotSlashOrAsterisk = RE.CharsOf(c => !"/*".Contains(c));
var RE_DelimitedCommentSection = RE.Symbol(\'/\') | (RE.Symbol(\'*\').Many() >> RE_NotSlashOrAsterisk);

COMMENT = lex.DefineToken(
    (RE.Literal("//") >> RE_InputChar.Many()) |
    (RE.Literal("/*") >> RE_DelimitedCommentSection.Many() >> RE.Symbol(\'*\').Many1() >> RE.Symbol(\'/\'))
);

最後還有一點後續的代碼，從Lexicon對象生成ScannerInfo，再生成Scanner：

ScannerInfo info = lexicon.CreateScannerInfo();
Scanner scanner = new Scanner(info);

string source = "//任意miniSharp源代碼";
StringReader sr = new StringReader(source);

scanner.SetSource(new SourceReader(sr));
scanner.SetSkipTokens(WHITESPACE.Index, LINE_BREAKER.Index, COMMENT.Index);

這樣就完成了！我們建立了一個完整的miniSharp詞法分析器。現在它就能分析所有miniSharp源代碼了。注意我們設定了該詞法分析器忽略所有空白符、換行以及注釋，是為了後面文法分析簡便而考慮的。各位讀者可以自己試着任意擴充這個詞法分析器，比如增加字元串常量的詞法、更多關鍵字和運算符甚至前所未有的新詞法。祝各位實踐愉快！下一篇開始我們要進入另一個重要的環節——文法分析部分，敬請期待。

此外别忘了關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器特别篇——用詞法分析器解決背誦聖經問題

這幾天比較忙，讓大家久等了。但是我文法分析篇還需要一些準備，是以今天帶來一個特别娛樂項目。其實也正好想多舉一些例子，介紹VBF.Compilers.Scanner庫的使用方法。今天的問題來自于一道騰訊的PHP面試題，原題如下：

我們碰到了大麻煩，一個新來的傳教士惹惱了上帝，上帝很憤怒，要求我們把聖經背熟，直至他說哪個單詞，我們就要飛快的回答出這個單詞在第幾行第幾個單詞位置。聽說你是個優秀的程式員，那麼髟助我們完成這個不可能的任務吧。

要求如下：

1）/myworks/example/bbe.txt，98版本英文聖經一本

2）輸入部分要求如下：php ./example.php [單詞]

3）輸出部分如下：[單詞] 1,2 2,4 5,6表示：此單詞在1行2列（第二個單詞），2行4列...

說明：

1）此文本4MB之巨...

2）單詞的含義：由英文字母（大小寫），數字（0-9）組成的串

3）提供給你的機器OS為ubuntu 9.10，記憶體隻有1G，而且，很不幸的，其中700M用來做了别的

4）上機考試不允許上網，但我裝了man文檔以及讀取CHM以及PDF的閱讀器，在電腦的桌面的CHM檔案夾中，有相應的PHP參考手冊

5）算法複雜度要求不能大于O（N^2）（就是N的平方）

6）什麼？PHP低效且用起來不順手，好的，你可以用别的語言來實作。但注意：提供給你的機器上隻有python 2.4/perl 5.8/gcc[g++] 4.1

原題是要求使用PHP的，我們隻是娛樂，不是真面試，當然就無視各種規定了。這道題不必使用詞法分析的原理，可以寫出很快的算法。但是用詞法分析庫來實作也是個不錯的注意，因為DFA詞法分析是O(N)的算法而且實際執行起來效率相當不錯。下面我們就用VBF.Compilers.Scanner庫來解決這道題：

Imports VBF.Compilers.Scanners
Imports VBF.Compilers.Scanners.RegularExpression
Imports System.IO

Module Program

    Sub Main(args As String())
        Dim findword = args(0)

        Dim bibleLexicon As New Lexicon()
        Dim lex = bibleLexicon.DefaultLexer

        \'定義要尋找單詞的詞法
         Dim TARGET = lex.DefineToken(Literal(findword))
        \'定義一般單詞的詞法
         Dim WORD = lex.DefineToken((Range("0"c, "9"c) Or
                                    Range("a"c, "z"c) Or
                                    Range("A"c, "Z"c)).Many1)
        \'定義換行
         Dim LF = lex.DefineToken(Symbol(vbLf) Or Literal(vbCrLf))
        \'定義其他所有符号均忽略
         Dim OTHER = lex.DefineToken(Range(ChrW(0), ChrW(255)))

        Dim bibleScanner As New PeekableScanner(bibleLexicon.CreateScannerInfo())
        bibleScanner.SetSkipTokens(OTHER.Index)

        Using sr As New StreamReader("bible.txt")
            Dim source As New SourceReader(sr)
            bibleScanner.SetSource(source)

            Dim scannerWatch As New Stopwatch

            Dim lines = 1, columns = 1, totalwords = 0, targetwords = 0
            scannerWatch.Start()
            Do While bibleScanner.Peek() <> bibleScanner.ScannerInfo.EndOfStreamTokenIndex
                Dim x As Lexeme = bibleScanner.Read()

                Select Case x.TokenIndex
                    Case TARGET.Index
                        Console.WriteLine("第{0}行,第{1}列", lines, columns, x.Value)
                        columns += 1
                        targetwords += 1
                        totalwords += 1
                    Case WORD.Index
                        columns += 1
                        totalwords += 1
                    Case LF.Index
                        lines += 1
                        columns = 1
                End Select
            Loop
            scannerWatch.Stop()

            Console.WriteLine("總單詞數: " & totalwords)
            Console.WriteLine("目标單詞出現次數: " & targetwords)
            Console.WriteLine("消耗時間: " & scannerWatch.ElapsedMilliseconds)
        End Using
    End Sub

End Module

這就是完整的代碼。為了統計是第幾個單詞，我們按照題目的規定，定義了一般單詞的詞法，目标單詞的詞法，并且忽略所有其他字元（設定為SkipTokens）。分析過程就是不斷讀取下一個單詞，直到檔案的末尾。注意，這次我展示的是具有超前檢視功能的PeekableScanner類，它可以超前檢視任意多個單詞，其實也可以用普通的Scanner而且性能更好。現在大家可以試試聖經中出現了什麼單詞，比如我們試一下apple：

第5769行,第29列
第14112行,第8列
第16578行,第14列
第17558行,第8列
第17646行,第25列
第20351行,第34列
第22304行,第23列
第22908行,第31列

可見我手裡這本聖經出現了8次apple（我特意看了前面，亞當和夏娃吃的是fruit，不是apple……）。如果搜microsoft的話發現聖經中并沒有出現，怪不得蘋果最近這麼風光……

源代碼和聖經檔案可以在這裡下載下傳：BibleFinder.7z

另外有不少同學問虎書是什麼書，這裡有龍書、虎書和鲸書的介紹：http://unistd.blog.51cto.com/1126453/260372。下一篇開始我們正式進入文法分析部分。希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（六）上下文無關語言和文法

上回我們已經學習了文法分析第一階段——詞法分析的原理和工具，介紹了正規表達式、正則語言和DFA等工具。今次我們要開始涉及編譯器前端最重要的階段——文法分析。簡單而言，這一步就要完整地分析整個程式設計語言的文法結構。上回說到詞法分析的結果是将輸入的字元串分解成一個個的單詞流，也就是諸如關鍵字、辨別符這樣有特定意義的單詞。一種完整的程式設計語言，必須在此基礎上定義出各種聲明、語句和表達式的文法規則。觀察我們所熟悉的程式設計語言，其文法大都有某種遞歸的性質。例如四則運算與括号的表達式，其每個運算符的兩邊，都可以是任意的表達式。比如1+a是表達式，(1+a)*(2 – c)也是表達式，((a+b) + c) * (d – e)也是表達式。再比如if語句，其if的塊和else的塊中還可以再嵌套if語句。我們在詞法分析中引入的正規表達式和正則語言無法描述這種結構，如果用DFA來解釋，DFA隻有有限個狀态，它沒有辦法追溯這種無限遞歸。是以，程式設計語言的表達式，并不是正則語言。我們要引入一種表現能力更強的語言——上下文無關語言。

要介紹上下文無關語言，我們先來了解一下定義上下文無關文法的工具——産生式的寫法。我們還是使用程式設計語言的表達式作為例子，但這次我們假設表達式隻有三種——單個表示變量名辨別符、括号括起來的表達式和兩個表達式相加。比如a是一個變量表達式，a+b是兩個變量表達式相加的表達式，(a+b)是一個括号表達式。我們用符号E來表示一個表達式，那麼這三種表達式分别可以定義為：

E → id

E → E + E

E → ( E )

這種形式的定義就叫做産生式。出現在→左側符号E稱作非終結符（nonterminal symbol），代表可以繼續産生新符号的“文法變量”。符号→表示非終結符可以“産生”的東西。而上述産生式中的藍色id、+、（等符号，是具有固定意義的單詞，它們不再會産生新的東西，稱作終結符（terminal symbol）。注意，非終結符可以出現在産生式的右側，這就是具有遞歸性質文法的來源。産生式經過一系列的推導，就能夠生成各種完全由終結符組成的句子。比如，我們示範一下表達式(a + b) + c的推導過程：

E => E + E => (E) + E => (E + E) + E => (a + E) + E => (a + b) + E => (a + b) + c

推導過程中的=>代表将目前句型中的一個非終結符替換成産生式右側的内容。以上推導過程中，我們每次都将句型中最左邊一個非終結符展開，是以這種推導稱為最左推導。當然也有最右推導，不同之處就算是每次将句型中最右邊的非終結符展開：

E => E + E => E + c => (E) + c => (E + E) + c => (E + b) + c => (a + b) + c

可見，同一個結果可以具有多種不同的推導過程。使用最左推導時，句型的左側逐漸變得隻有終結符；而最右推導正好相反，推導過程中句型的右側逐漸變得隻有終結符，最終結果都是整個句子變為終結符。所有符合文法定義的句子，都可以用文法的産生式推導出來。

我們文法分析的目的是解析輸入的單詞流(a + b) + c，得到它的文法分析樹。先來看看文法分析樹是什麼樣的。還是以(a + b) + c為例，文法分析樹是這樣的：

文法分析樹的每一個節點都是一個非終結符或者終結符，其中終結符都是樹的葉子結點（沒有子節點），而非終結符都是有子節點的。一旦我們得到了文法分析樹，就可以很容易地進行後續的語義分析，比如這個表達式的語義是“先将a和b代表的變量相加，再把所得的結果與c代表的變量相加”。那麼文法分析樹是怎麼得到的呢，其實剛才的産生式推導過程，就可以順便建立文法分析樹，隻要在展開非終結符的同時，在文法分析樹中相應的節點下加入非終結展開的結果即可生成。下面我們用動畫示範上述産生式通過最左推導和最右推導産生(a + b) + c文法分析樹的過程：

最左推導	最右推導
[轉]裝配腦袋：自己動手開發編譯器	[轉]裝配腦袋：自己動手開發編譯器

我們可以看到最左推導和最右推導的文法分析樹是一樣的，這證明用相同的文法解析同樣的輸入也至少存在兩種不同的分析方法。後續篇章介紹的遞歸下降法就是一種最左推導的分析方法，而另一類非常流行的LR分析器則是基于最右推導的分析方法。目前流行的編譯器開發方式是在文法分析階段構造一棵真正的文法分析樹，然後再通過周遊文法樹的方法進行後續的分析，是以最左推導和最右推導的過程對我們來講差別不大。

我們剛才舉的例子中，表達式(a + b) + c隻能有一種文法分析樹。但另外一些文法分析的輸入，可能存在多種文法分析樹，這稱為歧義。剛才的文法其實就是有歧義的（在哪裡？請大家思考一下），但為了更清楚地表達歧義的危害，我們再舉一個新的例子，它在前面例子中增加了乘法：

E → id

E → E + E

E → E * E

E → ( E )

如果用上述産生式推導出表達式a * b + c，就有兩種可能的最左推導：

最左推導1：E => E + E => E * E + E => a * E + E => a * b + E => a * b + c

最左推導2：E => E * E => a * E => a * E + E => a * b + E => a * b + c

這兩種推導的文法樹是不一樣的：

推導1	推導2
[轉]裝配腦袋：自己動手開發編譯器	[轉]裝配腦袋：自己動手開發編譯器

我們剛才讨論了，文法分析樹将用于下一步的語義分析。而在語義分析中，上述兩個文法樹的不同主要展現在運算符的優先級上。如果按照推導1的文法樹，應該先将a和b相乘，再加上c；而如果按照推導2的文法樹，則應該先把b和c相加，再和a相乘。很明顯，這兩種語義的計算結果是可以不一樣的。我們不想程式設計語言中的同一種表達式有兩種語義，是以有歧義的文法是不适合用在文法分析的。實踐中應該使用沒有歧義的文法來確定同一段程式僅存在唯一一種文法分析樹。比如我們可以修改一下上述文法的産生式，讓運算符具有左結合的特性，并讓乘法一開始就有高于加法的優先級：

F → id

F → ( E )

T → T * F

T → F

E → E + T

E → T

修改文法之後，*号的兩側，不允許直接出現帶+号的表達式，而隻能出現帶括号的表達式和變量名；同時，連續的加法或乘法必須從左側開始運算。這就限制了推導可能進行的方式。在新文法下表達式a * b + c就隻存在一種文法分析樹了：

我們最後用在miniSharp的文法就和這一個非常類似。在實踐當中，我們通常需要仔細觀察和思考所用的文法是否具有歧義。如果有一些文法拿不定主意，我建議大家去參考C# spec，裡面對C#的文法進行極其詳細的定義，我相信大家看過Spec之後會更加了解一門現代的程式設計語言的文法。我也将在後續篇章中介紹一些常見文法結構的設計方法。

在本篇的最後，我想再多介紹一點點上下文無關語言。有些同學可能從剛才開始就想問為何這種語言和文法叫做“上下文無關”呢？其實這裡的“上下文無關”是指文法中的産生式都可以無條件展開為箭頭右側的内容。另外存在一種上下文相關文法，它的産生式都需要在一定條件下才能展開。上下文相關語言要比上下文無關文法複雜得多，而其沒有一種通用的方法可以有效地解析上下文相關語言，是以它也不會用在程式設計語言的設計當中。同學們也許已經意識到，即使是上下文無關文法和語言，也要比正規表達式和正則語言複雜得多。在此我沒有辦法詳細地描述上下文無關語言的性質，但是我可以給感興趣的同學稍微科普一下。就像正規表達式存在一種等價的計算模型——有窮自動機——可以用來解析正則語言一樣，上下文無關文法也存在一種等價的計算模型——下推自動機（Put-Down Automation, PDA）。下推自動機除了一組有限的狀态和狀态轉換以外，還帶有一個無限容量的棧。和有窮自動機不同，下推自動機的狀态并不僅根據輸入字元和目前狀态來進行轉移，還要根據棧頂的字元；而且下推自動機還必須決定何時向棧中壓入或彈出字元。和有窮自動機類似，下推自動機也存在非确定性下推自動機（NPDA）和确定性下推自動機（DPDA）兩種。這兩種下推自動機是不等價的。其中非确定性下推自動機對應于整個上下文無關語言，而确定性下推自動機則對應于上下文無關語言的一個真子集。NPDA所具有的“猜測”能力要比NFA強大得多，以至于我們無法很容易地用計算機來模拟。我們隻能夠模拟DPDA來進行解析。所幸的是，幾乎所有程式設計語言的文法，都是能用一個DPDA所接受的。我們在接下來的篇章中引入的文法分析機制，有些甚至還達不到DPDA的能力，也就是說我們隻能處理上下文無關文法中的一小部分。但即使是這一小部分，也足夠将C#這樣的文法描述出來了。

下一篇中我們将介紹遞歸下降文法分析器的實作方法。希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（七）遞歸下降的文法分析器

上回我們說到文法分析使用的上下文無關語言，以及描述上下文無關文法的産生式、産生式推導和文法分析樹等概念。今天我們就來讨論實際編寫文法分析器的方法。今天介紹的這種方法叫做遞歸下降（recursive descent）法，這是一種适合手寫文法編譯器的方法，且非常簡單。遞歸下降法對語言所用的文法有一些限制，但遞歸下降是現階段主流的文法分析方法，因為它可以由開發人員高度控制，在提供錯誤資訊方面也很有優勢。就連微軟C#官方的編譯器也是手寫而成的遞歸下降文法分析器。

使用遞歸下降法編寫文法分析器無需任何類庫，編寫簡單的分析器時甚至連前面學習的詞法分析庫都無需使用。我們來看一個例子：現在有一種表示二叉樹的字元串表達式，它的文法是：

N → a ( N, N )

N → ε

其中終結符a表示任意一個英文字母，ε表示空。這個文法的含義是，二叉樹的節點要麼是空，要麼是一個字母開頭，并帶有一對括号，括号中逗号左邊是這個節點的左兒子，逗号右邊是這個節點的右兒子。例如字元串A(B(,C(,)),D(,))就表示這樣一棵二叉樹：

注意，文法規定節點即使沒有兒子（兒子是空），括号和逗号也是不可省略的，是以隻有一個節點的話也要寫成A(,)。現在我們要寫一個解析器，輸入這種字元串，然後在記憶體中建立起這棵二叉樹。其中記憶體中的二叉樹是用下面這樣的類來表示的：

class Node
{
    public Node LeftChild { get; private set; }
    public Node RightChild { get; private set; }
    public char Label { get; private set; }

    public Node(char label, Node left, Node right)
    {
        Label = label;
        LeftChild = left;
        RightChild = right;
    }
}

這是一道微軟面試題，曾經難倒了不少參加面試的候選人。不知在座各位是否對寫出這段程式有信心呢？不少參選者想到了要用棧，或者用遞歸，去尋找逗号的位置将字元串拆解開來等等方法。但是若是使用遞歸下降法，這個程式寫起來非常容易。我們來看看編寫遞歸下降文法分析器的一般步驟：

使用一個索引來記錄目前掃描的位置。通常将它做成一個整數字段。
為每個非終結符編寫一個方法。
如果一個非終結符有超過一個的産生式，則在這個方法中對采用哪個産生式進行分支預測。
處理單一産生式時，遇到正确終結符則将第一步建立的掃描索引位置向前移動；如遇到非終結符則調用第二步中建立的相應方法。
如果需要産生解析的結果（比如本例中的二叉樹），在方法傳回之前将它構造出來。

我們馬上來試驗一下。首先建立一個類，然後存放一個索引變量來儲存目前掃描位置。然後要為每一個非終結符建立一個方法，我們的文法中隻有一個非終結符N，是以隻需建立一個方法：

class BinaryTreeParser
{
    private string m_inputString;
    private int m_index;

    //初始化輸入字元串和索引的構造函數，略

    Node ParseNode()
    {
        
    }
}

回到剛才的産生式，我們看到非終結符N有兩個産生式，是以在ParseNode方法的一開始我們必須做出分支預測。分支預測的方法是超前檢視（look ahead）。就是說我們先“偷窺”目前位置前方的字元，然後判斷應該用哪個産生式繼續分析。非終結符N的兩個産生式其中一個會産生a(N, N)這個的結構，而另一個則直接産生空字元串。那現在知道，起碼有一種可能就是會遇到一個字母，這時候應該采用N → a(N, N)這個産生式繼續分析。那麼什麼時候應該采用N → ε進行分析呢？我們觀察産生式右側所有出現N的地方，倘若N是空字元串，那麼N後面的字元就會直接出現，也就是逗号和右括号。于是這就是我們的分支預測：

如果超前檢視遇到英文字母，預測分支N → a(N, N)
如果超前檢視遇到逗号、右括号預測分支N → ε

轉化成代碼就是這樣：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)繼續分析
    }
    else if (lookAheadChar == \',\' || lookAheadChar == \')\' )
    {
        //采用N → ε繼續分析
    }
    else
    {
        throw new Exception("文法錯誤");
    }
}

接下來我們分别來看兩個分支怎麼處理。先來看N → ε，這種情況下非終結符是個空字元串，是以我們不需要移動目前索引，直接傳回null表示空節點。再來看N → a(N, N) 分支，倘若輸入的字元串沒有任何文法錯誤，那就應該依次遇到字母、左括号、N、逗号、N右括号。根據上面的規則，凡是遇到終結符，就移動目前索引，直接向前掃描；而要是遇到非終結符，就遞歸調用相應節點的方法。是以（不考慮文法錯誤）的完整方法代碼如下：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)繼續分析
        char label = m_inputString[m_index++]; //解析字母
        m_index++; //解析左括号，因為不需要使用它的值，是以直接跳過

        Node left = ParseNode(); //非終結符N，遞歸調用

        m_index++; //解析逗号，跳過

        Node right = ParseNode(); //非終結符N，遞歸調用

        m_index++; //解析右括号，跳過

        return new Node(label, left, right);
    }
    else if (lookAheadChar == \',\' || lookAheadChar == \')\')
    {
        //采用N → ε繼續分析
        //無需消耗輸入字元，直接傳回null
        return null;
    }
    else
    {
        throw new Exception("文法錯誤");
    }
}

因為存在文法限制，是以一旦我們完成了分支預測，就能清楚地知道下一個字元或非終結符一定是什麼，無需再進行任何判斷（除非要進行文法錯誤檢查）。是以根本就不需要尋找逗号在什麼位置，我們解析到逗号時，逗号一定就在那，這種感覺是不是很棒？隻需要寥寥幾行代碼就已經寫出了一個完整的Parser。大家感興趣可以繼續補全一些輔助代碼，然後用真正的字元串輸入試驗一下，是否工作正常。前面假設輸入字元串的文法是正确的，但真實世界的程式總會寫錯，是以編譯器需要能夠幫助檢查文法錯誤。在上述程式中加入文法錯誤檢查非常容易，隻要驗證每個位置的字元，是否真的等于産生式中規定的終結符就可以了。這就留給大家做個練習吧。

上面我們采用的分支預測法是“人肉觀察法”，編譯原理書裡一般都有一些計算FIRST集合或FOLLOW集合的算法，可以算出一個産生式可能開頭的字元，這樣就可以用自動的方法寫出分支預測，進而實作遞歸下降文法分析器的自動化生成。ANTLR就是用這種原理實作的一個著名工具。有興趣的同學可以去看編譯原理書。其實我覺得“人肉觀察法”在實踐中并不困難，因為程式設計語言的文法都特别有規律，而且我們天天用程式設計語言寫代碼，都很有經驗了。

下面我們要研究一下遞歸下降法對文法有什麼限制。首先，我們必須要通過超前檢視進行分支預測。支援遞歸下降的文法，必須能通過從左往右超前檢視k個字元決定采用哪一個産生式。我們把這樣的文法稱作LL(k)文法。這個名字中第一個L表示從左往右掃描字元串，這一點可以從我們的index變量從0開始遞增的特性看出來；而第二個L表示最左推導，想必大家還記得上一篇介紹的最左推導的例子。大家可以用調試器跟蹤一遍遞歸下降文法分析器的分析過程，就能很容易地感受到它的确是最左推導的（總是先展開目前句型最左邊的非終結符）。最後括号中的k表示需要超前檢視k個字元。如果在每個非終結符的解析方法開頭超前檢視k個字元不能決定采用哪個産生式，那這個文法就不能用遞歸下降的方法來解析。比如下面的文法：

F → id

F → ( E )

E → F * F

E → F / F

當我們編寫非終結符E的解析方法時，需要在兩個E産生式中進行分支預測。然而兩個E産生式都以F開頭，而且F本身又可能是任意長的表達式，無論超前檢視多少字元，都無法判定到底應該用乘号的産生式還是除号的産生式。遇到這種情況，我們可以用提取左公因式的方法，将它轉化為LL(k)的文法：

F → id

F → ( E )

G → * F

G → / F

E → FG

我們将一個左公因式F提取出來，然後将剩下的部分做成一個新的産生式G。在解析G的時候，很容易進行分支預測。而解析E的時候則無需再進行分支預測了。在實踐中，提取左公因式不僅可以将文法轉化為LL(k)型，還能有助于減少重複的解析，提高性能。

下面我們來看LL(k)文法的第二個重要的限制——不支援左遞歸。所謂左遞歸，就是産生式産生的第一個符号有可能是該産生式本身的非終結符。下面的文法是一個直截了當的左遞歸例子：

F → id

E → E + F

E → F

這個表達式類似于我們上篇末尾得到的無歧義二進制運算符的文法。但這個文法存在左遞歸：E産生的第一個符号就是E本身。我們想像一下，如果在編寫E的遞歸下降解析函數時，直接在函數的開頭遞歸調用自己，輸入字元串完全沒有消耗，這種遞歸調用就會變成一種死循環。是以，左遞歸是必須要消除的文法結構。解決的方法通常是将左遞歸轉化為等價的右遞歸形式：

F → id

E → FG

G → + FG

G → ε

大家應該牢牢記住這個例子，這不僅僅是個例子，更是解除大部分左遞歸的萬能公式！我們将要在編寫miniSharp文法分析器的時候一次又一次地用到這種變換。

由于LL(k)文法不能帶有左遞歸和左公因式，很多常見的文法轉化成LL(k)之後顯得不是那麼優雅。有許多程式員更喜歡使用LR(k)文法的文法分析器。LR代表從左到右掃描和最右推導。LR型的文法允許左遞歸和左公因式，但是并不能用于遞歸下降的文法分析器，而是要用移進-歸約型的文法分析器，或者叫自底向上的文法分析器來分析。我個人認為LR型文法分析器的原理非常優雅和精妙，但是限于本篇的定位我不準備介紹它。我想任何一本編譯原理書裡都有詳細介紹。當然如果未來我的VBF庫支援了LR型文法分析器，我也許會追加一些特别篇，誰知道呢？

希望大家看了今天這篇文章之後，都能用遞歸下降法寫出一些LL(k)文法的文法分析器來。下一篇我将介紹使用C#和VB中神奇的Linq文法來“組合”出文法分析器來，敬請期待！

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（八）用Linq編寫解析器組合子

上回我們說到手寫遞歸下降文法分析器。手寫遞歸下降的方式是目前很多編譯器采用的方式，如果你想寫一個商業品質的編譯器，這是首選的方法。但是，一個完善的遞歸下降解析器需要的代碼量也不少，如果要進行錯誤報告、錯誤恢複等等那代碼量就更大了。作為懶人，我們有時想要一些小型語言的解析器，最好寫起來像直接寫文法的産生式一樣，最好連錯誤報告和錯誤恢複也一并自動解決，可能嗎？在過去很長一段時間，人們采用的方法是使用解析器生成器（parser generator）。因為不管是LL遞歸下降解析還是LR的移進歸約解析，都可以很容易地用計算機來生成所需的規則。這樣的著名工具有yacc、ANTLR等。他們的特點是要用一種專門的文法格式來編寫文法産生式，然後經過一個翻譯程式生成解析器的代碼。在函數式語言發展起來之後，有些人發現函數式語言的抽象能力非常強，甚至能夠直接用函數式語言的代碼來表達文法的産生式，并将解析器“組合”出來，這稱作解析器組合子（parser combinator）。如今C#和VB語言也具有函數式語言相當的特征，特别是還有Linq助陣，以至于在C#和VB中也能享受組合子帶來的方式。今天我們就來看看怎麼做解析器的組合子。這一篇文字描述可能比較模糊，大家一定要認真地看代碼，動手實驗。

解析器組合子的基本思想是“組合”，首先我們要定義一些最基本的産生式作為基礎組合子，然後通過組合的方式拼裝出最終的解析器來。回想一下正規表達式的定義，它有兩個基本表達式要素——空表達式和字元表達式，以及三個基本運算——并、連接配接和克林閉包。用基本運算連接配接基本表達式，就能組成任何正規表達式。解析器組合子也需要定義兩個基本的産生式和兩個基本運算。

首先是産生空字元的産生式：

G → ε

這個産生式不産生任何單詞，換句話說在解析的時候，不解析任何單詞就能成功解析出一個G。是以這個産生式的解析器永遠都能解析成功。

接下來是産生一個單詞t的産生式：

G → t

産生式産生一個特定單詞t，表示在解析的時候，如果遇到單詞t，則成功解析出一個G，而遇到其他單詞則會解析失敗。

再來定義兩個基本運算。首先是連接配接運算：

G → X Y

産生式先産生X再産生Y，表示在解析的時候先成功解析X，再成功解析Y，就能成功解析出一個G。

接下來是并運算：

G → X

G → Y

這表示，G既可以産生X也可以産生Y。在解析時無論成功解析X還是Y，都能成功解析出一個G。以上四種基本産生式嵌套使用，就能表示任何上下文無關文法。

下面定義解析器函數的原型委托：

public delegate IResult<T> ParserFunc<out T>(ForkableScanner scanner);

public interface IResult<out T>
{
    T Value { get; }
    ForkableScanner ReturnedScanner { get; }
}

public class Result<T> : IResult<T>
{
    public T Value { get; private set; }
    public ForkableScanner ReturnedScanner { get; private set; }

    public Result(T value, ForkableScanner returnedScanner)
    {
        Value = value;
        ReturnedScanner = returnedScanner;
    }
}

這并不是VBF.Compilers.Parsers.Combinators庫最後采用的Parser函數原型，但它非常适合第一次接觸解析器組合子的同學們了解。先看第一行委托的結構，它接受一個ForkableScanner作為參數，然後傳回一個IResult<T>類型。首先什麼是ForkableScanner呢？我們在詞法分析篇定義的Scanner類隻能不斷地向前Read，而在函數式程式設計風格中，我們需要一個無副作用的Scanner。簡而言之，任何一個個ForkableScanner可以随時“Fork”成兩個ForkableScanner，而這兩個Scanner任何一個向前掃描，都不會影響另外一個，而且他們各自掃描都回得到同樣的單詞流。這都是為了處理上述“并”運算的解析器，并運算需要兩個分支能夠互不影響地單獨進行。接下來是傳回類型IResult<T>，定義成接口是為了能夠加上.NET 4泛型協變的“out”關鍵字。實際類型Result<T>包含一個解析結果T和成功解析之後傳回的Scanner，代表餘下的輸入流。如果傳回的整個Result對象為null，則表示解析失敗。後面所有解析器組合子最終都是為了生成這樣一個委托的對象，一旦生成了這個對象，就可以馬上拿來解析了。

有了解析器函數原型，下面就開始一樣一樣地定義基礎組合子。所謂組合子其實都是一些靜态方法（本例中這些靜态方法都定義在Parsers靜态類中）、傳回類型就是上面的解析器委托。由于傳回類型也是委托，是以這些組合子實際上都是一些高階函數（傳回函數的函數）。在我們的代碼中常常是一個lambda表達式。較少使用lambda表達是的同學第一次看下面的代碼可能會略微感到頭暈，隻需要稍微休息一下再重新看即可……

首先是空産生式G → ε，它的組合子是：

public static ParserFunc<T> Succeed<T>(T result)
{
    return scanner => new Result<T>(result, scanner);
}

這個組合子接受一個參數，表示其解析結果。正如前面所介紹，由Succeed組合子生成的解析器，永遠都會成功解析，而且會将設定的結果傳回。

第二種是接受一個單詞的的産生式G → t，我們将它的組合子定義成一個擴充方法：

public static ParserFunc<Lexeme> AsParser(this Token token)
{
    return scanner =>
    {
        var lexeme = scanner.Read();
        if (lexeme.TokenIndex == token.Index)
        {
            return new Result<Lexeme>(lexeme, scanner);
        }
        else
        {
            return null;
        }
    };
}

注意這個組合子生成的解析器是Lexeme（詞素）類型的，詞素對象是我們在詞法分析階段定義的，裡面包含了詞素的類型和具體字元串。這個組合子接受一個Token作為參數，而傳回的解析器從輸入的Scanner中讀取下一個詞素，如果該詞素的單詞類型與傳入的Token相比對，就報告解析成功，否則解析失敗。

第三種是兩個文法的連接配接G → X Y。我們需要定義一個組合子，接受兩個已經存在的ParserFunc函數，傳回一個新的ParserFunc，先後調用兩個傳入的ParserFunc：

public static ParserFunc<Tuple<T1, T2>> Concat<T1, T2>(this ParserFunc<T1> parser1, ParserFunc<T2> parser2)
{

    return scanner =>
    {
        var result1 = parser1(scanner);

        if (result1 == null) return null;

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<Tuple<T1, T2>>(Tuple.Create(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

注意我們傳回的ParserFunc結果類型是Tuple<T1, T2>，因為結果中需要同時包含T1和T2。

用這種方式定義的連接配接運算組合子，在實踐中非常難用。因為我們的文法常常要包含不止兩個符号連接配接的情形。假如我們的産生式是G → X Y Z，那麼必須寫成 X.Concat(Y.Concat(Z))，而它的傳回類型是Tuple<T1, Tuple<T2, T3>>，如果要取得結果中的Z，隻能寫r.Item2.Item2。實際上miniSharp這樣的語言，文法中出現7-8個符号連接配接也不是什麼稀奇的事情，而如果都用這個組合子的話，Tuple嵌套會複雜到把人的眼睛都搞暈掉。是以這時我們想到了——Linq。Linq的“組合子”中，有一種叫SelectMany，他給我們帶來了這種文法糖：

List<int> la = new List<int>() { 1, 2, 3 };
List<string> lb = new List<string>() { "a", "b", "c" };

var r = from a in la
        from b in lb
        select a + b;

它實際可以翻譯成：

var r = la.SelectMany(a => lb.SelectMany(b => a + b));

也就是說，連續from語句，其實是SelectMany擴充方法的嵌套調用。這種調用方法有把lambda嵌套“打平”的功能，非常類似于單子風格中的Bind運算。實際上C#和VB允許在任何自定義類型上擴充SelectMany方法，然後就允許用Linq文法的from去調用。有些人非常鄙視文法糖，但這個文法糖卻是無法替代的，這是C#版解析器組合子關鍵中的關鍵！由此就可以将連接配接運算定義成一個SelectMany組合子：

public static ParserFunc<TResult> SelectMany<T1, T2, TResult>(this ParserFunc<T1> parser,
    Func<T1, ParserFunc<T2>> parserSelector, Func<T1, T2, TResult> resultSelector)
{

    return scanner =>
    {
        var result1 = parser(scanner);

        if (result1 == null) return null;

        var parser2 = parserSelector(result1.Value);

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<TResult>(resultSelector(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

這個神奇的SelectMany組合子不但消除了嵌套Tuple帶來的混亂，還允許我們用一個自定義的select語句生成連接配接運算的結果，這在生成文法樹的時候尤為友善。我們一會再看例子，先繼續看最後一種基本組合子。

最後一種基本組合子是并運算。并運算要求産生式産生兩種可能的分支。對應到解析器組合子上，連接配接運算也要接受兩個現成的解析器作為參數，但是選擇哪一個呢？這裡我們沒有辦法做分支預測，是以隻好采取嘗試的辦法。有一種嘗試的方法就是先試用第一個解析器，如果失敗了，再試用第二個，這是一種類似深度優先搜尋的辦法：

public static ParserFunc<T> Union<T>(this ParserFunc<T> parser1, ParserFunc<T> parser2)
{
    return scanner =>
    {
        var scanner1 = scanner;
        var scanner2 = scanner.Fork();

        var result1 = parser1(scanner1);
        if (result1 != null)
        {

            return result1;
        }

        var result2 = parser2(scanner2);

        return result2;
    };
}

僅僅使用以上四個組合子函數，就可以來寫Parser了！是否還半信半疑呢？我們就來寫上一次寫過的二叉樹字元串表示的文法分析器。忘記的同學建議打開上一篇看看。我們把文法再抄一遍：

N → a ( N, N )

N → ε

這裡面涉及的單詞包括字母、左右括号和逗号，我們都用詞法分析篇的方法将他們定義出來。然後再用解析器組合子組合出上述文法的解析器。完整的代碼如下：

Lexicon binaryTreeSyntax = new Lexicon();
LexerState lex = binaryTreeSyntax.DefaultLexer;

//定義詞法
Token LEFTPH = lex.DefineToken(RE.Symbol(\'(\'));
Token RIGHTPH = lex.DefineToken(RE.Symbol(\')\'));
Token COMMA = lex.DefineToken(RE.Symbol(\',\'));
Token LETTER = lex.DefineToken(RE.Range(\'a\',\'z\') | RE.Range(\'A\',\'Z\'));

//定義文法
ParserFunc<Node> NodeParser = null;
NodeParser = 
    (from a in LETTER.AsParser()
     from _1 in LEFTPH.AsParser()
     from left in NodeParser
     from _2 in COMMA.AsParser()
     from right in NodeParser
     from _3 in RIGHTPH.AsParser()
     select new Node(a.Value[0], left, right))
    .Union(Parsers.Succeed<Node>(null));


//運作部分
ForkableScannerBuilder builder = 
    new ForkableScannerBuilder(binaryTreeSyntax.CreateScannerInfo());

string source = "A(B(,),C(,))";
SourceReader sr = new SourceReader(
    new StringReader(source));

ForkableScanner scanner = builder.Create(sr);

var tree = NodeParser(scanner);

重點來看“定義文法”部分，我們來看看産生式都是如何轉變為組合子調用的。首先，N → ε轉化為了一句Parsers.Succeed調用，代表總能解析成功，而且不消耗輸入單詞的解析器。然後是N → a ( N, N )，連續的連接配接轉化為一連串Linq的from子句。而其中出現了終結符的地方，則通過AsParser擴充方法将Token轉化為Parser。最後再用一個Union組合子将兩個N産生式組合到一起，中間我們還看到了用select子句友善地構造想要的解析結果能力。再一次，贊歎SelectMany的神奇力量！初看起來，Linq用來寫文法感覺怪怪的，但是習慣了之後，可以非常快速地将各種産生式以Linq語句的方式表達出來。

解析器組合子最大的優點就是無論實作還是使用都非常簡潔，高度展現了函數式程式設計的優勢。但它最大的缺點是難以調試。倘若大家用解析器組合子組合出來的解析器有錯誤，無法獲得想要的解析結果，那可就麻煩了。大家可以試試用Visual Studio的調試器跟蹤一下解析器組合子，會發現它的跳轉非常頻繁，而且根本看不出目前在幹什麼（因為運作時已經生成了Lambda函數，無法獲得組合子傳入的參數），也無法看出下一步會運作什麼。是以，采用解析器組合子唯一確定正确的做法，就是編寫足夠的測試用例。

還有一個重要的問題要解決——文法錯誤。大家可以試一試輸入一個不符合文法的字元串，比如去掉一個括号，看看會是什麼結果？答案是直接傳回null——和一開始的設定一樣。無法知道錯誤出在了哪裡。作為程式設計語言的解析器，不僅應該能報告錯誤出現的位置，而且還應該能自動進行某種錯誤恢複，這樣就可以繼續完成解析，進而獲得所有的文法錯誤，而不僅僅是頭一個。這個功能非常重要，但我們今天設計的解析器組合子結構卻非常不擅長進行錯誤報告和恢複。比如說Union組合子，幹脆就是通過解析錯誤來判斷要不要采用這個分支，如果每個分支都錯了，它又如何決定報告哪條分支的錯誤呢？可以設定一些規則，但是我們想要更好、更智能的錯誤報告和恢複功能。這就留到下一篇，正式介紹VBF庫中采用的CPS風格解析器組合子了。敬請期待！

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（九）CPS風格的解析器組合子

上回我們用函數式程式設計的方法，結合Linq文法，建立了一套解析器組合子方案，并能成功解析自定義文法的輸入字元串。但是，上次做成的解析器組合子有個重要的功能沒有完成——錯誤報告。作為程式設計語言的文法分析器，不能在遇到文法錯誤的時候簡單地傳回null，那樣程式員就很難修複代碼中的文法錯誤。我們需要的是準确報告文法錯誤的位置，更進一步，是程式中所有的文法錯誤，而不僅僅是頭一個。後者要求解析器具有錯誤恢複的能力，即在遇到文法錯誤之後，還能恢複到正常狀态繼續解析。錯誤恢複不僅僅可以用在檢測出所有的文法錯誤，還可以在存在文法錯誤的時候仍然提供有意義的解析結果，進而用于IDE的智能感覺和重構等功能。手寫的遞歸下降文法分析器可以很容易地加入錯誤恢複，但需要針對每一處錯誤手工編寫代碼來恢複。像C#官方編譯器，給出的文法錯誤資訊非常全面、精确、智能，全都是手工編寫的功勞。又回到我們是懶人這個殘酷的事實，能不能在讓解析器組合子生成的解析器自動具有錯誤恢複能力呢？

首先來看上一個版本的四個基本組合子：空産生式的Succeed組合子，token産生式的AsParser組合子，連接配接運算産生式的SelectMany組合子和并運算産生式的Union組合子。首先Succeed是不會解析失敗的，是以它沒有必要進行錯誤恢複。現在來看AsParser組合子，它的邏輯是讀取下一個詞素，如果詞素的單詞類型群組合子的參數比對則解析成功，否則解析失敗。代碼如下：

public static ParserFunc<Lexeme> AsParser(this Token token)
{
    return scanner =>
    {
        var lexeme = scanner.Read();
        if (lexeme.TokenIndex == token.Index)
        {
            return new Result<Lexeme>(lexeme, scanner);
        }
        else
        {
            return null;
        }
    };
}

如果要對失敗的情形進行錯誤恢複，有兩種可行的選擇：1、假裝要解析的Token存在，繼續解析（這種做法相當于在原位置插入了一個單詞）；2、跳過不比對的單詞，重新進行解析（這種做法相當于删除了一個單詞）。如果漏寫一個分号或者括号，插入型錯誤恢複就能有效地恢複錯誤，如果是多寫了一個關鍵字或辨別符造成的錯誤，删除型錯誤恢複就能有效地恢複。但問題是，我們怎麼能在組合子的代碼中判斷出哪種錯誤恢複更有效呢？最優政策是讓兩種錯誤恢複的狀态都繼續解析到末尾，然後看哪種恢複狀态整體文法錯誤最少。但是，隻要有一個字元解析失敗，就要分支成兩個完整解析，那麼錯誤一旦多起來，這個分支的龐大程度将使得錯誤恢複無法進行。更何況，錯誤并不僅僅出現在真正的文法錯誤上，我們還要用錯誤來判斷“并”運算組合子的分支問題。請看上一版本Union組合子的代碼：

public static ParserFunc<T> Union<T>(this ParserFunc<T> parser1, ParserFunc<T> parser2)
{
    return scanner =>
    {
        var scanner1 = scanner;
        var scanner2 = scanner.Fork();

        var result1 = parser1(scanner1);
        if (result1 != null)
        {

            return result1;
        }

        var result2 = parser2(scanner2);

        return result2;
    };
}

在Union中，我們先試驗第一個parser1能否解析成功，如果失敗才解析parser2。如果解析器有自動錯誤恢複的功能，那麼我們就無法用這種方式判斷了，因為兩條分支遇到錯誤之後都會繼續進行下去。我們可以讓兩條分支都解析到底，然後挑錯誤較少的分支作為正式解析結果。但同上所述，這種做法的分支多得難以置信，效率上決定我們不能采用。

為了避免效率問題，我們需要一種“廣度優先”的處理方案。在遇到錯誤時産生的“插入”和“删除”兩條分支，要同時進行，但要一步一步地進行。這裡所謂的一“步”，就是指AsParser組合子讀取一個詞素。我們看到四種基本組合子中，隻有AsParser組合子會用scanner來真正讀取詞素，其他組合子最終也是要調用到AsParser組合子來進行解析的。我們讓兩個可能的分支都向前解析一步，然後看是否其中一條分支的結果比另外一條更好。所謂更好，就是一條分支沒有進一步遇到錯誤，而另外一條分支遇到了錯誤。如果兩條分支都沒有遇到錯誤，或者都遇到了錯誤，我們就再向前推進一步，直到某一步比另外一步更好為止。Union組合子也可以采用同樣的政策處理。這是一種貪心算法的政策，我們所得到的結果未必是文法錯誤最少的解析結果，但它的效率是可以接受的。

那麼怎麼進行“廣度優先”推進呢？我們上次引入的組合子，目前的組合子無法知道下一個要運作的組合子是什麼，更無法控制下一個組合子隻向前解析一步。為了達到目的，我們要引入一種新的組合子函數原型，稱作CPS（Continuation Pass-in Style）風格的組合子。不知道大家有多少人聽說過CPS，這在函數式程式設計界是一種廣為應用的模式，在.NET世界裡其實也有采用。.NET 4.0引入的Task Parallel Library庫中的Task類，就是一個典型的CPS設計範例。我舉一個簡單的例子來介紹一下CPS。如果有兩個函數A和B，需要按順序調用，用傳統方式程式設計很簡單，就是直接調用：

void A()
{
    Console.WriteLine("A");
}

void B()
{
    Console.WriteLine("B");
}

void Run()
{
    A();
    B();
}

而如果采用CPS，則是把B傳遞給A，這時我們稱B是A的continuation，或者future。

void A(Action future)
{
    Console.WriteLine("A");
    future();
}

void B()
{
    Console.WriteLine("B");
}

void Run()
{
    A(B);
}

乍一看這也不能實作什麼特别的事情，但其實是很有用的。A獲得了自己的future之後可以自行決定如何運作它。比如可以異步地運作。這樣我們就在Run()方法中，用一種容易了解的方式，建構出了一條異步調用序列。.NET 4.0的Task Parallel Library正是這樣的風格，每個Task類通過ContinueWith方法接受自己的future。而我們的函數式解析其組合子，也可以用這種方式，讓每個Parser函數接受一個future，并自行決定如何調用future。這裡最關鍵的思想是實作延遲調用future，進而實作“廣度優先”的單步解析效果。首先來看看新的Parser類原型（警告，這一篇裡采用的函數式技巧比上一篇還要難懂得多，如果看了之後發生頭暈，嗜睡等症狀，請休息之後重新看……）：

public delegate Result<T> ParserFunc<T>(ForkableScanner scanner, ParserContext context);
public delegate ParserFunc<TFuture> Future<T, TFuture>(T value);

public abstract class Parser<T>
{
    public abstract ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future);
}

ParserFunc方法和上一篇非常類似，但是多了一個ParserContext方法。我們會用這個對象來儲存一些錯誤報告的資訊。再來是Future函數的定義，Future傳回的類型是一個ParserFunc委托對象；Future的參數T，則是用來讓每一個組合子生成的Parser，将自己的解析結果T傳給它自己的Future用的。注意這次多了一個Parser<T>抽象類，它代替ParserFunc成為組合子的生成對象。它之是以不能聲明成一個委托，是因為它的BuildParser方法要接受一個額外的泛型類型參數TFuture。接下來每一個解析器組合子都需要繼承自Parser<T>，并實作它的BuildParser方法。下面我們就來看一看新的CPS型解析器組合子怎麼定義。

首先還是G → ε的組合子，它永遠都能解析成功，是以，它的邏輯是生成一個ParserFunc，将預設的解析結果傳遞給自己的Future:

public class SucceedParser<T> : Parser<T>
{
    public T Value { get; private set; }

    public SucceedParser(T value)
    {
        Value = value;
    }
    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future)
    {
        return (scanner, context) => future(Value)(scanner, context);
    }
}

這是第一次實踐CPS風格，大家一定要注意觀察它與上一次傳統風格解析器組合子的不同。最關鍵的一點，就是傳回的ParserFunc，必須要調用BuildParser傳進來的future函數，傳遞自己的解析結果。

接下來就是重頭戲G → t，我們要在這個單詞解析器組合子中加入期待已久的錯誤報告和錯誤恢複功能，請看代碼：

public class TokenParser : Parser<Lexeme>
{
    public Token ExpectedToken { get; private set; }
    public string MissingCorrection { get; private set; }

    public TokenParser(Token expected)
    {
        ExpectedToken = expected;
        MissingCorrection = expected.ToString();
    }


    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<Lexeme, TFuture> future)
    {
        ParserFunc<TFuture> scan = null;
        scan = (scanner, context) =>
        {
            var s1 = scanner.Fork();

            var l = scanner.Read();

            int tokenIndex;
            tokenIndex = l.TokenIndex;

            if (tokenIndex == ExpectedToken.Index)
            {
                var r = context.StepResult(0, () => future(l)(scanner, context));
                return r;
            }
            else
            {
                Lexeme correctionLexeme = l.GetErrorCorrectionLexeme(ExpectedToken.Index, MissingCorrection);
                ErrorCorrection insertCorrection = new InsertedErrorCorrection(ExpectedToken.ToString(), correctionLexeme.Span);

                if (l.IsEndOfStream)
                {
                    scanner.Join(s1);
                    return context.StepResult(1, () => future(correctionLexeme)(scanner, context), insertCorrection); //插入
                }
                else
                {
                    ErrorCorrection deleteCorrection = new DeletedErrorCorrection(l);
                    return context.ChooseBest(context.StepResult(1, () => future(correctionLexeme)(s1, context), insertCorrection), //插入
                        context.StepResult(1, () => scan(scanner, context), deleteCorrection)); //删除
                }
            }
        };

        return scan;
    }
}

大緻描述下來就是生成這樣一個ParserFunc：首先通過Scanner讀取下一個詞素，并判斷它是否是期待的單詞。如果是，則調用context.StepResult(0, …)方法（稍後解釋）；如果不是，則判斷是否遇到的輸入流的末尾，如果是末尾，則隻嘗試“插入”修複方案（因為無法删除“流末尾”單詞），如果不是末尾則使用context.ChooseBest方法，嘗試插入和删除兩種修複方案。context.StepResult方法就是産生延遲執行future的關鍵。它的第一個參數表示該結果的“代價”，0表示這是一個成功解析的結果；1表示是經過錯誤恢複的結果。第二個參數則是一個延遲執行的委托，這個委托隻會在我們需要将解析器“推進一步”的時候才會執行，我們将future函數的調用放在這裡并做成延遲執行的方式，就是要等待廣度優先一步一步地向前解析時才執行下一步的操作。那麼這個context.ChooseBest函數到底是如何實作的呢？請看代碼：

private Result<T> ChooseBest<T>(Result<T> result1, Result<T> result2, int correctionDepth)
{
    if (result1.Type == ResultType.Stop)
    {
        return result1;
    }
    if (result2.Type == ResultType.Stop)
    {
        return result2;
    }

    var step1 = (StepResult<T>)result1;
    var step2 = (StepResult<T>)result2;

    if (step1.Cost < step2.Cost)
    {
        return step1;
    }
    else if (step1.Cost > step2.Cost)
    {
        return step2;
    }
    else
    {
return new StepResult<T>(Math.Max(step1.Cost, step2.Cost), 
            () => ChooseBest(step1.NextResult, step2.NextResult, correctionDepth + 1), null);
    }
}

ChooseBest方法要比較兩個Result的代價，并選取代價較小的分支。如果代價一樣，則通過延遲計算的方法将比較推至下一輪。我們到處采用延遲計算的手段，以至于整個單詞流都輸入之後，解析可能仍然沒有結束！是以Result類有一個集中取得每一步結果的功能，在單詞流輸入完畢後還要繼續驅動這些延遲計算，直到拿到最終的解析結果。

接下來是表示連接配接運算G → X Y的SelectMany組合子。具體方法是将傳入的future作為Y的future，再将Y的Parser作為X的future，以此将兩者連接配接起來：

public class ConcatenationParser<T1, T2, TR> : Parser<TR>
{
    public Parser<T1> ParserLeft { get; private set; }
    public Func<T1, Parser<T2>> ParserRightSelector { get; private set; }
    public Func<T1, T2, TR> Selector { get; private set; }

    public ConcatenationParser(Parser<T1> parserLeft, Func<T1, Parser<T2>> parserRightSelector, Func<T1, T2, TR> selector)
    {
        CodeContract.RequiresArgumentNotNull(parserLeft, "parserLeft");
        CodeContract.RequiresArgumentNotNull(parserRightSelector, "parserRightSelector");
        CodeContract.RequiresArgumentNotNull(selector, "selector");

        ParserLeft = parserLeft;
        ParserRightSelector = parserRightSelector;
        Selector = selector;
    }

    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<TR, TFuture> future)
    {
        return (scanner, context) => 
            ParserLeft.BuildParser(
                left => ParserRightSelector(left).BuildParser(
                    right => future(Selector(left, right))))(scanner, context);
    }
}

最後的并運算，則是廣度優先同時實驗兩個傳入的Parser，即直接用ChooseBest方法選取繼續執行的Parser：

public class AlternationParser<T> : Parser<T>
{
    public Parser<T> Parser1 { get; private set; }
    public Parser<T> Parser2 { get; private set; }

    public AlternationParser(Parser<T> parser1, Parser<T> parser2)
    {
        CodeContract.RequiresArgumentNotNull(parser1, "parser1");
        CodeContract.RequiresArgumentNotNull(parser2, "parser2");

        Parser1 = parser1;
        Parser2 = parser2;
    }

    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future)
    {
        return (scanner, context) =>
        {
            var s1 = scanner;
            var s2 = scanner.Fork();

            return context.ChooseBest(Parser1.BuildParser(future)(s1, context), Parser2.BuildParser(future)(s2, context));
        };
    }
}

如果大家還不能很清晰地了解上述CPS風格解析器組合子的原理，也不要擔心。我也是花了整整兩個星期時間反複看論文才理清所有細節的。而且我貼的也是簡化的代碼，并不完整。大家可以下載下傳VBF庫的源代碼來仔細研究。當然，如果對Haskell不恐懼的話，看原始的論文也不錯。從這裡下載下傳論文（點右上方Download下面的PDF圖示）：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7601

最後，我們像上一篇傳統解析器組合子那樣，為每種組合子聲明一個便于使用的靜态函數或者擴充方法。注意，在上述四種基本組合子外，CPS組合子如要正常工作，需要一個特殊的組合子——EndOfStreamParser，它類似于TokenParser但錯誤恢複的時候從不嘗試插入。這裡略過它的實作，直接來看輔助函數的定義：

public static class Parsers
{
    public static Parser<Lexeme> AsParser(this Token token)
    {
        CodeContract.RequiresArgumentNotNull(token, "token");

        return new TokenParser(token);
    }

    public static Parser<Lexeme> Eos()
    {
        return new EndOfStreamParser();
    }

    public static Parser<T> Succeed<T>(T value)
    {
        return new SucceedParser<T>(value);
    }

    public static Parser<TResult> SelectMany<T1, T2, TResult>(this Parser<T1> parser, Func<T1, Parser<T2>> parserSelector, 
        Func<T1, T2, TResult> resultSelector）
    {
        CodeContract.RequiresArgumentNotNull(parser, "parser");
        CodeContract.RequiresArgumentNotNull(parserSelector, "parserSelector");
        CodeContract.RequiresArgumentNotNull(resultSelector, "resultSelector");

        return new ConcatenationParser<T1, T2, TResult>(parser, parserSelector, resultSelector);
    }

    public static Parser<T> Union<T>(this Parser<T> parser1, Parser<T> parser2)
    {
        CodeContract.RequiresArgumentNotNull(parser1, "parser1");
        CodeContract.RequiresArgumentNotNull(parser2, "parser2");

        return new AlternationParser<T>(parser1, parser2);
    }
}

這樣，我們就能和上一篇一樣用Linq的文法來組合Parser了。最後我們還需要一個驅動延遲計算的類：

public class ParserRunner<T>
{
    public ParserContext Context { get; private set; }
    private ParserFunc<T> m_runner;

    public ParserRunner(Parser<T> parser, ParserContext context)
    {
        CodeContract.RequiresArgumentNotNull(parser, "parser");
        CodeContract.RequiresArgumentNotNull(context, "context");

        m_runner = parser.BuildParser(FinalFuture);
        Debug.Assert(m_runner != null);
        Context = context;
    }

    public T Run(ForkableScanner scanner)
    {
        var result = m_runner(scanner, Context);
        return result.GetResult(Context);
    }

    private ParserFunc<T> FinalFuture(T value)
    {
        return (scanner, context) => context.StopResult(value);
    }
}

這個類裡我們定義了整個解析器最終的一個future——它産生令所有分支判斷停止的StopResult。這裡最關鍵的是利用result.GetResult虛方法推進廣度優先的分支選取，并且收集這條路線上所有的文法錯誤。我們所有的文法錯誤就隻有兩種：“丢失某單詞”（采用了插入方式錯誤恢複）和“發現了未預期的某單詞”（采用了删除方式錯誤恢複）。

下面的例子示範了真正的VBF.Compilers.Parsers.Combinators.dll庫的用法。真正的VBF庫除了定義基本組合子之外還定義了許許多多的重載和擴充函數，基本實作了EBNF的所有功能（而且還可以很容易地繼續無限擴充）。用VBF庫時Linq語句可以直接在Token上使用，而無需到處使用AsParser擴充方法。此外還有大量的代碼，限于邏輯無法全部在部落格中展現，大家如想了解最好的方法還是直接下載下傳我的代碼觀看和試用。

class Node
{
    public Node LeftChild { get; private set; }
    public Node RightChild { get; private set; }
    public char Label { get; private set; }

    public Node(char label, Node left, Node right)
    {
        Label = label;
        LeftChild = left;
        RightChild = right;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Lexicon binaryTreeSyntax = new Lexicon();
        LexerState lex = binaryTreeSyntax.DefaultLexer;

        //定義詞法
        Token LEFTPH = lex.DefineToken(RE.Symbol(\'(\'));
        Token RIGHTPH = lex.DefineToken(RE.Symbol(\')\'));
        Token COMMA = lex.DefineToken(RE.Symbol(\',\'));
        Token LETTER = lex.DefineToken(RE.Range(\'a\', \'z\') | RE.Range(\'A\', \'Z\'));

        //定義文法
        ParserReference<Node> NodeParser = new ParserReference<Node>();
        NodeParser.Reference =
            (from a in LETTER
             from _1 in LEFTPH
             from left in NodeParser
             from _2 in COMMA
             from right in NodeParser
             from _3 in RIGHTPH
             select new Node(a.Value[0], left, right))
            | Parsers.Succeed<Node>(null);

        var builder = new ForkableScannerBuilder(binaryTreeSyntax.CreateScannerInfo());

        string source = "A(B(,),C(,))";
        SourceReader sr = new SourceReader(
            new StringReader(source));


        ForkableScanner scanner = builder.Create(sr);
        CompilationErrorManager errorManager = new CompilationErrorManager();

        ParserContext context = new ParserContext(errorManager, 0, 1);
        context.DefineDefaultCompilationErrorInfo(0);

        var runner = new ParserRunner<Node>(NodeParser.SuffixedBy(Parsers.Eos()), context);
        var result = runner.Run(scanner);

        foreach (var error in errorManager.Errors.OrderBy(e => e.ErrorPosition.StartLocation.CharIndex))
        {
            Console.WriteLine(error.ToString());
        }
    }
}

注意from語句已經可以直接使用Token類型，Union操作也可以用“|”運算符代替。由于廣度優先分支判斷的緣故，整個文法在用于解析之前，必須在後面連接配接一個EndOfStream，代表解析到檔案末尾才算結束。最後的代碼還示範了如何将解析錯誤列印出來。大家可以将輸入字元串故意改錯，看看是否能夠檢測出來。還可以試試錯誤太多太離譜時的性能下降現象。

在下一篇，我們将正式用這套解析器組合子實作miniSharp語言的文法分析器，并且還會接觸到VBF庫擴充組合子的各種用法。敬請期待！

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（十）miniSharp文法分析器

經過前面四篇的鋪墊，我們終于擁有了編寫文法分析器的強大工具，現在可以正式開發一門程式設計語言的文法分析器了。我們先來定義miniSharp的文法規則，然後根據LL文法的特點進行一些調整，最後借助解析器組合子生成完整的文法分析器。

miniSharp語言是C#的一個小子集，然而它仍然具有一門完整程式設計語言的所有要素，而且仍然是一種面向對象的語言。我們把miniSharp的文法分成三類——聲明結構、語句和表達式。聲明結構就是類、方法、字段的聲明。語句就是諸如if-else、while這樣特定含義的指令。而表達式則是表示一種有運算結果的結構，如二進制運算符表達式、函數調用表達式等。C#中指派也是一種表達式，但miniSharp為了簡化後續代碼生成，将指派當成一種語句。

首先來定義聲明結構的文法。為了簡化語義分析，我們規定程式中第一個類必須是一個靜态類，靜态類中隻能有一個靜态方法Main——這是整個miniSharp唯一允許的靜态方法。在靜态類之後可以定義多個普通類，普通類之間可以繼承。下面定義文法的産生式采用了擴充寫法，支援類似克林閉包的*符号。G → X* 代表G → ε; G → H; H → XG。文法中的藍色字代表終結符（詞法分析獲得的單詞）

Program	→	MainClass ClassDecl*
MainClass	→	static class ID { public static void Main (string[] ID) { Statement+ } }
ClassDecl	→	class ID { FieldDecl* MethodDecl* }
→	class ID : ID { FieldDecl* MethodDecl* }
FieldDecl	→	Type ID;
MethodDecl	→	public Type ID (FormalList) { Statement* return Exp ; }
FormalList	→	Type ID FormalRest*
→	ε
FormalRest	→	, Type ID
Type	→	int[]
→	bool
→	int
→	ID

語句部分我們将要定義語句塊和六種語句。其中if-else語句的else部分是不能省略的。while語句不支援break。剩下四種分别是調用Console.WriteLine的語句、指派語句、數組元素指派語句和變量聲明語句。

Statement	→	{ Statement* }
→	if ( Exp ) Statement else Statement
→	while ( Exp ) Statement
→	System.Console.WriteLine( Exp )
→	ID = Exp ;
→	ID [ Exp ] = Exp ;
→	Type ID ;

表達式部分我們将要定義二進制、一進制、數組長度、數組通路、字面常量、變量、this引用、new運算、方法調用等多種表達式。

Exp	→	Exp op Exp
→	Exp[ Exp ]
→	Exp .Length
→	Exp .ID ( ExpList )
→	INTEGER_LITERAL
→	true
→	false
→	ID
→	this
→	new int [ Exp ]
→	new ID ()
→	! Exp
→	( Exp )
ExpList	→	Exp ExpRest*
→	ε
ExpRest	→	, Exp

其中二進制運算表達式的op是+、-、*、/、>、<、==、&&和||之一。為了簡單起見我們這裡的二進制運算表達式文法是有歧義而且沒有正确定義優先級的。按照C#的語言規範，運算符的優先級關系如下（隻提取了miniSharp支援的部分）：

1	(Exp) new this 變量常量方法調用屬性通路數組通路
2	!
3	* /
4	+ -
5	< > ==
6	&&
7	\|\|

有些文法分析器就是使用有歧義的二進制運算符文法，在遇到歧義時使用預定義的運算符優先級來解決沖突。現在的文法分析器傾向于直接使用無歧義的文法。下面的文法就是經過精心安排的運算符文法，消除了歧義并使得運算符具有左結合和優先級的差別：

BasicExp	→	括号、new、this、變量、常量、方法調用、屬性通路、數組通路
Factor	→	BasicExp
→	! Factor
Term	→	Factor
→	Term op Factor 其中 op 是 * /
Comparand	→	Term
→	Comparand op Term 其中 op 是 + -
Comparison	→	Comparand
→	Comparison op Comparand 其中 op 是 < > ==
Logical	→	Comparison
→	Logical && Comparison
Exp	→	Logical
→	Exp \|\| Logical

這樣我們就定義了miniSharp的完整文法。注意，上述文法仍然存在一些左公因式和左遞歸的現象。我們用的解析器組合子因為獨特的廣度優先分支判斷方式，其支援的文法實際上已經超越了遞歸下降文法分析器的LL(k)文法，稱作LL(∞)的文法，這種文法非常強大，可描述所有确定性下推自動機DPDA接受的語言。但是，它仍然不允許文法存在左遞歸，而左公因式也會大大降低解析器的效率。是以消除左遞歸和盡量避免左公因式仍然是真正實作文法分析器時需要着重考慮的任務。

現代語言的文法分析器通常都是将源代碼翻譯成一棵抽象文法樹（Abstract Syntax Tree，AST）。後續的語義分析可以在抽象文法樹上繼續進行。我們在文法分析篇（六）介紹過“文法分析樹”，它是一種在文法推導過程中建立起來的樹狀資料結構。那麼什麼是抽象文法樹呢？其實就是經過簡化和抽象的文法分析樹。在完整的文法分析樹中每個推導過程的終結符都包含在文法樹内，而且每個非終結符都是不同的節點類型。實際上，如果僅僅是要做編譯器的話，很多終結符（如關鍵字、各種标點符号）是無需出現在文法樹裡的；而前面表達式文法中的Factor、Term也實際上沒有必要區分為兩種不同的類型，可以将其抽象為BinaryExpression類型。這樣簡化、抽象之後的文法樹，更加利于後續語義分析和代碼生成。使用.NET裡的面向對象語言來實作文法樹，最常見的做法就是用組合模式，将文法樹做成一顆對象樹，每種抽象文法對應一個節點類。下圖就是miniSharp的抽象文法樹的所有類。

節選其中一個文法樹節點展示一下，比如大家熟悉的IfElse語句的文法樹節點類：

public class IfElse : Statement
{
    public Expression Condition { get; private set; }
    public Statement TruePart { get; private set; }
    public Statement FalsePart { get; private set; }
    public SourceSpan IfSpan { get; private set; }
    public SourceSpan ElseSpan { get; private set; }

    public IfElse(Expression cond, Statement truePart, Statement falsePart, SourceSpan ifSpan, SourceSpan elseSpan)
    {
        Condition = cond;
        TruePart = truePart;
        FalsePart = falsePart;
        IfSpan = ifSpan;
        ElseSpan = elseSpan;
    }

    public override T Accept<T>(IAstVisitor<T> visitor)
    {
        return visitor.VisitIfElse(this);
    }
}

它的結構非常簡單，裡面儲存了所有作為子節點成分的字段，例如IfElse是由一個Condition表達式和TruePart、FalsePart兩個語句組成。另外我們還多儲存了兩個SourceSpan，分别是if語句中“if”關鍵字和“else”關鍵字出現的源代碼位置（多少行，多少列）。儲存位置是為了後續語義分析中提供錯誤資訊的位置。比如if的條件表達式必須是個bool類型的表達式，但文法分析階段無法做出類型驗證，而到了語義分析階段分析出了語義錯誤，仍然需要向編譯器使用者提供錯誤的位置，這些SourceSpan就可以派上用場。

注意節點類最後還實作了一個Accept方法，用來支援文法樹的Visitor模式。我們在語義分析階段和代碼生成階段，需要一次又一次地周遊抽象文法樹。為了簡化文法樹的通路，我們聲明一個IAstVisitor<T>接口作為文法樹的Visitor，後續過程需要周遊文法樹時，就實作這一接口即可。實際上這個接口有一個預設實作——AstVisitor類，允許隻重寫一部分成員。

有了Ast，下面我們就開始編寫miniSharp的文法分析器。在本系列的第五篇（miniSharp語言的詞法分析器）中我們已經用VBF詞法分析庫定義了miniSharp的詞法，生成了一些Token對象。那麼接下來就隻要使用Linq文法的解析器組合子，根據本篇開頭定義的文法進行組合，并适時使用select語句生成文法樹節點的對象即可。比如，文法最開始的Program和MainClass的寫法如下：

PProgram.Reference = // MainClass ClassDecl*
    from main in PMainClass
    from classes in PClassDecl.Many()
    select new Program(main, classes);

PMainClass.Reference = // static class id { public static void Main(string[] id) { statement }}
    from _static1 in K_STATIC
    from _class in K_CLASS
    from className in ID
    from _1 in LEFT_BR
    from _public in K_PUBLIC
    from _static2 in K_STATIC
    from _void in K_VOID
    from _main in K_MAIN
    from _2 in LEFT_PH
    from _string in K_STRING
    from _3 in LEFT_BK
    from _4 in RIGHT_BK
    from arg in ID
    from _5 in RIGHT_PH
    from _6 in LEFT_BR
    from statements in PStatement.Many1()
    from _7 in RIGHT_BR
    from _8 in RIGHT_BR
    select new MainClass(className, arg, statements);

這代碼是如此的直白以至于沒什麼可解釋的。唯一要注意的是PProgram.Reference這個用法，這裡PProgram是ParserReference<T>類的執行個體。這個類允許先直接new出來，然後再用.Reference = XXX的方式為其指定文法規則。這樣就允許一個Parser組合子先使用，後定義（比如上面例子中的PMainClass就先在PProgram的文法定義中使用了，然後下面才定義其文法）。因為文法中的非終結符常常出現遞歸引用，用ParserReference這個類可以大大簡化我們的工作，不用關心Parser的聲明先後順序問題。

我們重點來看一些需要特殊技巧的例子。首先是聲明方法形式參數的文法，采用了FormalList → Type ID FormalRest*這樣的定義方法，這是避免左遞歸的技巧。但是這樣一來，方法的第一個參數就和其他的參數分别定義在兩個文法當中。我們希望生成的抽象文法樹不區分第一個參數和其餘參數，是以可以在生成文法樹時采用一點點小技巧來辦到：

var paramFormal =
    from paramType in PType
    from paramName in ID
    select new Formal(paramType, paramName);

PFormalList.Reference = // Type id FormalRest* | <empty>
    (from first in paramFormal
     from rest in PFormalRest.Many()
     select new[] { first }.Concat(rest).ToArray()) |
    Parsers.Succeed(new Formal[0]);

PFormalRest.Reference = // , Type id
    paramFormal.PrefixedBy(COMMA.AsParser());

另外注意擴充的産生式“X*”在VBF解析器組合子庫中可以直接使用X.Many()的方式實作。VBF中還定義了數個這種友善的擴充組合子。

最後要注意的是二進制運算符的分析器。我們前面寫出的無歧義符合優先級的二進制運算符文法仍然是左遞歸的，用于解析器組合子時必須像上面的FormalList那樣改成右遞歸的。但是這些運算符都是左結合的，我們不想讓生成的抽象文法樹也變成右遞歸的形态。是以，這裡我們需要用（傳統）Linq的Aggregate擴充方法來處理一下生成的文法樹：

var termRest =
    from op in (ASTERISK.AsParser() | SLASH.AsParser())
    from factor in PFactor
    select new { Op = op, Right = factor };

PTerm.Reference = // term * factor | factor
    from factor in PFactor
    from rest in termRest.Many()
    select rest.Aggregate(factor, (f, r) => new Binary(r.Op, f, r.Right));

var comparandRest =
    from op in (PLUS.AsParser() | MINUS.AsParser())
    from term in PTerm
    select new { Op = op, Right = term };

PComparand.Reference = // comparand + term | term
    from term in PTerm
    from rest in comparandRest.Many()
    select rest.Aggregate(term, (t, r) => new Binary(r.Op, t, r.Right));


var comparisonRest =
    from op in (LESS.AsParser() | GREATER.AsParser() | EQUAL.AsParser())
    from comparand in PComparand
    select new { Op = op, Right = comparand };

PComparison.Reference = // comparison < comparand | comparand
    from comparand in PComparand
    from rest in comparisonRest.Many()
    select rest.Aggregate(comparand, (c, r) => new Binary(r.Op, c, r.Right));

除此之外，剩下的文法翻譯成組合子基本上都是水到渠成的工作了。完整的代碼全部都在MiniSharpParser.cs中，大家可以自行下載下傳閱讀。經過小小的努力，我們終于能将miniSharp的源代碼轉換為抽象文法樹了，接下來我們就要進入下一個編譯器重要的階段——語義分析。敬請期待下一篇！

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（十一）語義分析

上回我們已經用VBF的Parsers.Combinators庫生成了miniSharp的文法分析器，并且能夠将miniSharp的源代碼翻譯成抽象文法樹（AST）。這一回我們要繼續進行下一步——語義分析。就目前大家接觸的程式設計語言，如C#、VB、C++來說，語義分析是編譯器前端最複雜的部分。因為這些程式設計語言的語義都非常複雜。語義分析不像之前詞法分析、文法分析那樣，有一些特定的工具來幫助。這一部分通常都是要純手工寫代碼來完成。我們的miniSharp語義因為已經高度簡化，它的語義分析可以說比C#要容易一個數量級。我們隻會在標明方法重載的時候見識一下C#複雜語義的冰山一角。

所謂程式設計語言語義，就是這段代碼實際的含義。程式設計語言的代碼必須有絕對明确的含義，這樣人們才能讓程式做自己想做的事情。比如最簡單的一行代碼：a = 1; 它的語義是“将32位整型常量存儲到變量a中”。首先我們對“1”有明确的定義，它是32位有符号整型字面量，這裡“32位有符号整型”就是表達式“1”的類型。其次，這句話成為合法的程式設計語言，32位整型常量必須能夠隐式轉換為a的類型。假設a就是int型變量，那麼這條語句就直接将1存儲到a所在記憶體裡。如果a是浮點數類型的，那麼這句話就隐含着将整型常量1轉換為浮點類型的步驟。在語義分析中，類型檢查是貫穿始終的一個步驟。像miniSharp這樣的靜态類型語言，類型檢查通常要做到：

判定每一個表達式的聲明類型
判定每一個字段、形式參數、變量聲明的類型
判斷每一次指派、傳參數時，是否存在合法的隐式類型轉換
判斷一進制和二進制運算符左右兩側的類型是否合法（比如+不就不能在bool和int之間進行）
将所有要發生的隐式類型轉換明确化

要進行以上操作，需要一個表存儲所有已知的類型。如果引用了外部程式集，則也需要将外部程式集中的類型資訊放到表中。類型資訊包括類型的名字、父類（如果有的話）、成員以及互相隐式轉換的規則。我們用如下的類來表示一個miniSharp自定義類型：

public class CodeClassType : TypeBase
{
    public bool IsStatic { get; set; }
    public CodeClassType BaseType { get; set; }
    public Collection<Method> Methods { get; private set; }
    public Collection<Method> StaticMethods { get; private set; }
    public VariableCollection<Field> Fields { get; private set; }

    public CodeClassType()
    {
        Methods = new Collection<Method>();
        StaticMethods = new Collection<Method>();
        Fields = new VariableCollection<Field>();
    }

    public override bool IsAssignableFrom(TypeBase type)
    {
        CodeClassType otherClassType = type as CodeClassType;

        if (otherClassType == null)
        {
            return false;
        }

        if (otherClassType == this)
        {
            return true;
        }
        else
        {
            return IsAssignableFrom(otherClassType.BaseType);
        }
    }

}

miniSharp不支援顯式類型轉換，而唯一支援的隐式類型轉換是子類引用到父類引用的轉換。

除了自定義類型之外，我們還需要表示數組類型和基元類型（int和bool），簡陋地如下處理：

public class PrimaryType : TypeBase
{
    public static readonly PrimaryType Int = new PrimaryType() { Name = "int" };
    public static readonly PrimaryType Boolean = new PrimaryType() { Name = "bool" };
    public static readonly PrimaryType String = new PrimaryType() { Name = "string" };
    public static readonly PrimaryType Void = new PrimaryType() { Name = "void" };

    public static readonly PrimaryType Unknown = new PrimaryType() { Name = null };

    public override bool IsAssignableFrom(TypeBase type)
    {
        if (this == type)
        {
            return true;
        }
        else
        {
            return false;
        }

    }
}

public class ArrayType : TypeBase
{
    public TypeBase ElementType { get; set; }

    public static readonly ArrayType IntArray = new ArrayType() { Name = "int[]", ElementType = PrimaryType.Int };
    public static readonly ArrayType StrArray = new ArrayType() { Name = "string[]", ElementType = PrimaryType.String };

    public override bool IsAssignableFrom(TypeBase type)
    {
        CodeClassType elementClassType = ElementType as CodeClassType;
        ArrayType arrayType = type as ArrayType;

        if (elementClassType != null && arrayType != null)
        {
            return elementClassType.IsAssignableFrom(arrayType.ElementType);
        }

        return false;
    }
}

實際上C#會将int和bool直接映射到System.Int32以及System.Boolean結構體。我們的miniSharp不僅僅要翻譯成托管代碼，是以并沒有采用這個規定，但在生成IL的時候仍然做這樣的特殊處理。最後因為miniSharp并不支援引用外部程式集，是以我也沒有将類型表獨立出來，而是将類型資訊存儲在每個表示class的文法樹節點上，以友善語義分析時通路。

語義分析的第二個主要任務是找到所有辨別符的定義。辨別符在miniSharp裡主要有：類名、字段名、方法名、參數名和本地變量名。遇到每個名稱，我們必須解析出辨別符表示的類、方法或字段的定義。比如下面這段代碼：

class MyClass
{
    int a;

    public int Foo()
    {
        int a;
        a = 1;
        if (this.a > 0)
        {
            return this.a;
        }
        else
        {
            return a;
        }
    }
}

有一個字段叫a，在過程Foo中又定義了一個同名局部變量a。那麼過程内的局部變量a就會覆寫字段的a，這句話的意思是辨別符“a”在Foo中将表示局部變量，而不是同名字段。在語義分析裡，我們遇到每一個可能代表變量的辨別符時，都要按照一套預先設定的規則來尋找其定義。比如按照如下順序：

搜尋目前的本地符号表，其中包括目前作用域中定義的本地變量和方法參數
搜尋目前類的字段

如果類的字段不僅僅是private的話，如果類還允許定義屬性的話，這裡的規則還要多好幾條。所幸miniSharp隻用以上兩條就夠了。我們看看怎麼表示本地符号表。

public class VariableCollection<T> : KeyedCollection<string, T> where T : VariableInfo
{
    private Stack<HashSet<string>> m_levelStack;
    public int m_Levels;

    public VariableCollection()
    {
        m_Levels = 0;
        m_levelStack = new Stack<HashSet<string>>();
    }

    protected override string GetKeyForItem(T item)
    {
        return item.Name;
    }

    public void PushLevel()
    {
        m_levelStack.Push(new HashSet<string>());
        m_Levels++;
    }

    public void PopLevel()
    {
        if (m_Levels == 0)
        {
            throw new InvalidOperationException();
        }

        var keysInLevel = m_levelStack.Pop();
        m_Levels--;

        foreach (var key in keysInLevel)
        {
            Remove(key);
        }
    }

    protected override void InsertItem(int index, T item)
    {
        base.InsertItem(index, item);

        if (m_Levels > 0)
        {
            var keysInLevel = m_levelStack.Peek();
            keysInLevel.Add(GetKeyForItem(item));
        }


    }
}

為了簡便處理這裡所用的資料結構都比較粗糙。但基本思想是使用一個Stack，在進入一個新的作用域（大括号包圍的語句塊）時壓入一個新的HashSet，儲存這一作用域内聲明的變量。當作用域結束時彈出一個HashSet，這個作用域内的變量就從表裡删除了。是以，miniSharp允許兩個不互相嵌套的語句塊内定義同名變量，但不允許在同一個方法内的語句塊内覆寫語句塊外定義的變量或形式參數。

接下來我們要讨論方法重載選取的問題。這是miniSharp中唯一一個稍微有些複雜性的語義。miniSharp允許同一個類多個方法具有相同的方法名，隻要他們的形式參數表的類型不完全一樣即可。而判斷一個方法調用表達式到底調用的是哪個方法，一共分為以下幾個步驟。

第一步，找到目前類中所有簽名相符的方法。miniSharp和C#一樣，目前類中的方法具有比父類更高的優先級。而VB則采取目前類和父類相同優先級（使用Overloads關鍵字時）。是以miniSharp也要先在目前類中搜尋合适的候選。第二個條件是簽名相符，它的定義是方法調用的表達式與候選方法的名稱相同，參數清單長度一緻，并且方法調用的表達式清單中的每一個表達式的類型，都能隐式轉換成候選方法參數表中對應位置參數的類型。稍微形式化一下，就是方法F(T1, T2, T3,…,Tn)是調用表達式C(E1, E2, E3,… Em)的簽名相符候選方法的條件是F.Name = C，m = n并且對所有i從1到n滿足Ti.IsAssignableFrom(typeof(Ei))。
第二步，所有簽名相符的候選方法中，找到一個最佳候選。如果有兩個候選方法P(P1, P2,…,Pn)和Q(Q1, Q2,…,Qn)，那麼我們說P比Q更佳當且僅當：P的每一個參數類型都比Q的相應參數類型更好或至少一樣好，同時Q的每一個參數類型都不比P的相應參數類型更好。如果P和Q各自有一些參數類型比對方更好，那麼就視為P和Q條件一緻，無法做出判斷（有歧義）。
調用表達式清單項E所對應的候選方法參數類型TP比TQ更好意味着：TP與typeof(E)相等但TQ與typeof(E)不相等；或者TQ.IsAssignableFrom(TP)，這意味着TP比TQ更“具體”一些。如果TP和TQ之間無法互相隐式轉換，或者兩者是相同的類型，則視為無法區分。
如果在目前類中沒有符合條件的候選，則對父類重複以上步驟。

真正C#的方法重載判斷大體上也是這個步驟，但還要更加複雜得多。因為C#還有param數組型參數，可選參數，命名參數，泛型方法等文法。這裡C#的Spec整整寫了好幾頁紙來描述完整的規則。初看起來這段規則轉換成代碼很難寫，是以我采用了一種取巧的方法：定義一個比較兩個候選參數好壞的Comparer類，然後用Order By的方式對候選參數進行排序。Comparer類如下：

public class MethodOverloadingComparer : IComparer<Method>
{
    private IList<Expression> m_expressionList;

    public MethodOverloadingComparer(IList<Expression> expressions)
    {
        Debug.Assert(expressions != null);
        m_expressionList = expressions;
    }

    public int Compare(Method x, Method y)
    {
        //step 1. find one with better conversion.
        int lastComparisonResult = 0;
        for (int i = 0; i < m_expressionList.Count; i++)
        {
            int result = CompareConversion(x.Parameters[i].Type, y.Parameters[i].Type, m_expressionList[i]);

            if (lastComparisonResult < 0 && result > 0 || lastComparisonResult > 0 && result < 0)
            {
                //none is better
                return 0;
            }
            else if (result != 0)
            {
                lastComparisonResult = result;
            }
        }

        return lastComparisonResult;
    }

    private int CompareConversion(TypeBase leftTarget, TypeBase rightTarget, Expression source)
    {
        if (leftTarget == rightTarget)
        {
            //same type, no better one
            return 0;
        }
        else if (leftTarget == source.ExpressionType && rightTarget != source.ExpressionType)
        {
            //left is better;
            return -1;
        }
        else if (leftTarget != source.ExpressionType && rightTarget == source.ExpressionType)
        {
            //right is better;
            return 1;
        }
        else
        {
            if (leftTarget.IsAssignableFrom(rightTarget))
            {
                //right is more specific
                return 1;
            }
            else if(rightTarget.IsAssignableFrom(leftTarget))
            {
                //left is more specific
                return -1;
            }
            else
            {
                //both are bad
                return 0;
            }
        }
    }
}

最後，我們要将這一系列步驟組合到一起。由于miniSharp的類可以以任何順序定義，一個類中的方法也可以以任何順序定義，調用時并不受任何限制。是以我們無法隻用一次抽象文法樹的周遊來完成語義分析。我采用的做法是分成三次周遊，前兩次分别對類的生命和成員的聲明進行解析并建構符号表（類型和成員），第三次再對方法體進行解析。這樣就可以友善地處理不同順序定義的問題。總的來說，三次周遊的任務是：

第一遍：掃描所有class定義，檢查有無重名的情況。
第二遍：檢查類的基類是否存在，檢測是否循環繼承；檢查所有字段的類型以及是否重名；檢查所有方法參數和傳回值的類型以及是否重複定義（簽名完全一緻的情況）。
第三遍：檢查所有方法體中語句和表達式的語義。

因為上一次抽象文法樹的設計已經采用了Visitor模式，是以以上三個階段的語義分析可以分别寫成三個Visitor來進行處理。語義分析子產品同時還要報告所有語義錯誤。下面我給出第一階段的Visitor實作供大家參考：

public class TypeDeclResolver : AstVisitor
{
    private TypeCollection m_types;
    private CompilationErrorManager m_errorManager;

    private const int c_SE_TypeNameDuplicates = 301;
    
    public void DefineErrors()
    {
        m_errorManager.DefineError(c_SE_TypeNameDuplicates, 0, CompilationStage.SemanticAnalysis,
            "The program has already defined a type named \'{0}\'.");
    }

    public TypeDeclResolver(CompilationErrorManager errorManager)
    {
        m_errorManager = errorManager;
        m_types = new TypeCollection();
    }

    public override AstNode VisitProgram(Program ast)
    {
        Visit(ast.MainClass);

        foreach (var cd in ast.Classes)
        {
            Visit(cd);
        }

        return ast;
    }

    public override AstNode VisitMainClass(MainClass ast)
    {
        //main class must be the first class.
        Debug.Assert(m_types.Count == 0);
        var name = ast.Name.Value;

        var mainclassType = new CodeClassType() { Name = name, IsStatic = true };

        m_types.Add(mainclassType);
        ast.Type = mainclassType;

        return ast;
    }

    public override AstNode VisitClassDecl(ClassDecl ast)
    {
        var name = ast.Name.Value;

        if (m_types.Contains(name))
        {
            m_errorManager.AddError(c_SE_TypeNameDuplicates, ast.Name.Span, name);
            return ast;
        }

        var classType = new CodeClassType() { Name = name };

        m_types.Add(classType);
        ast.Type = classType;

        return ast;
    }

    public TypeCollection Types
    {
        get { return m_types; }
    }

}

其中的ErrorManager類是與詞法、文法分析階段共享的文法錯誤管理類，可以友善地随時定義和儲存編譯錯誤。為了減少語義分析的負擔，我們規定隻有文法分析階段沒有錯誤才進行語義分析，而且語義分析的三個階段任何一步有文法錯誤都可以不再繼續執行分析。

第二個階段和第三個階段的代碼較長，我就不貼在這裡了，大家可以下載下傳我的代碼自行觀看。在此我隻貼一個比較有代表性的Call表達式解析過程，友善大家了解上述方法重載的邏輯（但我還沒有仔細進行過測試，是以不保證這段代碼完全沒有bug）

public override AstNode VisitCall(Call ast)
{
    // step 1. resolve each argument
    foreach (var argument in ast.Arguments)
    {
        Visit(argument);
    }

    //step 2. resolve object
    Visit(ast.Target);

    CodeClassType targetType = ast.Target.ExpressionType as CodeClassType;

    if (targetType == null)
    {
        m_errorManager.AddError(c_SE_MethodMissing, ast.Method.MethodName.Span, ast.Method.MethodName.Value);
        ast.ExpressionType = PrimaryType.Unknown;
        return ast;
    }

    //step 3. resolve method
    ResolveMethod(ast, targetType);

    //step 4. TODO: add type conversion node to arg implicit conversions

    return ast;
}

private void ResolveMethod(Call ast, CodeClassType targetType)
{
    if (targetType == null)
    {
        m_errorManager.AddError(c_SE_MethodMissing, ast.Method.MethodName.Span, ast.Method.MethodName.Value);
        ast.ExpressionType = PrimaryType.Unknown;

        return;
    }

    // step 1: collect candidates from current type
    var candidates = (from m in targetType.Methods
                      where String.Equals(m.Name, ast.Method.MethodName.Value, StringComparison.InvariantCulture) 
                      && m.Parameters.Count == ast.Arguments.Count
                      select m).ToArray();

    if (candidates.Length == 0)
    {
        ResolveMethod(ast, targetType.BaseType);
        return;
    }

    // step 2: remove unqualifed candidates
    List<Method> qualifiedCandidates = new List<Method>();
    foreach (var candidate in candidates)
    {
        bool isQualified = true;
        for (int i = 0; i < candidate.Parameters.Count; i++)
        {
            if (!candidate.Parameters[i].Type.IsAssignableFrom(ast.Arguments[i].ExpressionType))
            {
                isQualified = false;
                break;
            }
        }

        if (isQualified) qualifiedCandidates.Add(candidate);
    }

    if (qualifiedCandidates.Count == 0)
    {
        ResolveMethod(ast, targetType.BaseType);
        return;
    }

    // step 3: choose a "best" one
    if (qualifiedCandidates.Count > 1)
    {
        var comparer = new MethodOverloadingComparer(ast.Arguments);
        qualifiedCandidates.Sort(comparer);

        var firstCandidate = qualifiedCandidates[0];
        var secondCandidate = qualifiedCandidates[1];

        if (comparer.Compare(firstCandidate, secondCandidate) < 0)
        {
            //choose first as the best one
            ast.Method.MethodInfo = firstCandidate;
            ast.ExpressionType = firstCandidate.ReturnType;
        }
        else
        {
            //ambiguous between first & second
            m_errorManager.AddError(c_SE_MethodAmbiguous, ast.Method.MethodName.Span, 
                firstCandidate.GetSignatureString(), secondCandidate.GetSignatureString());
            ast.ExpressionType = PrimaryType.Unknown;
        }
    }
    else
    {
        ast.Method.MethodInfo = qualifiedCandidates[0];
        ast.ExpressionType = qualifiedCandidates[0].ReturnType;
    }
}

經過完善的語義分析，我們就得到了一個具有完整類型資訊，并且沒有語義錯誤的AST。下一階段我們就可以開始為程式設計語言生成代碼了。首先我們将從生成CIL開始，做一個和C#類似的托管語言。之後我們将深入代碼生成的各項技術，親自動手生成目标機器的代碼。敬請期待下一篇！

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！

自己動手開發編譯器（十二）生成托管代碼

前一階段我們完成了編譯器中的重要階段——語義分析。現在，程式中的每一個變量和類型都有其正确的定義；每一個表達式和語句的類型都是合法的；每一處方法調用都選擇了正确的方法定義。現在即将進入下一個階段——代碼生成。代碼生成的最終目的，是生成能在目标機器上運作的機器碼，或者可以和其他庫連結在一起的可重定向對象。代碼生成，和這一階段的各個優化手段，統稱為編譯器的後端。目前大部分編譯器，在代碼生成時，都傾向于先将前段解析的結果轉化成一種中間表示，再将中間表示翻譯成最終的機器碼。比如Java語言會翻譯成JVM bytecode，C#語言會翻譯成CIL，再經由各自的虛拟機執行；IE9的javascript也會先翻譯成一種bytecode，再由解釋器執行或者進行JIT翻譯；即使靜态編譯的語言如C++，也存在先翻譯成中間語言，再翻譯成最終機器碼的過程。中間表示也不一定非得是一種bytecode，我們在文法分析階段生成的抽象文法樹（AST）就是一種很常用的中間表示。.NET 3.5引入的Expression Tree正是采用AST作為中間表示的動态語言運作庫。那為什麼這種做法非常流行呢？因為翻譯中中間語言有如下好處：

使用中間語言可以良好地将編譯器的前端和後端拆分開，使得兩部分可以相對獨立地進行。
同一種中間語言可以由多種不同的源語言編譯而來，而又可以針對多種不同的目标機器生成代碼。CLR的CIL就是這一特點的典型代表。
有許多優化可以直接針對中間語言進行，這樣優化的結果就可以應用到不同的目标平台。

我們這次動手編寫編譯器，自然也少不了中間語言這一步。為了達到親手實踐的目的，我們将會自己定義中間語言，但是那樣的話想要把編譯出的程式運作起來就還需要很多工作。為了提前體驗運作目标代碼的成就感，同時驗證編譯器前端的正确性，我們這次先将miniSharp編譯成CLR的中間語言——CIL（Common IL，MSIL），并且就使用.NET自帶的Reflection.Emit庫來做。

首先來了解一下CIL的特點。CIL是一種bytecode，在.NET的程式集裡他是二進制方式存在的。我們常常見到的是用ILDASM或者ILSpy反彙編而成的彙編形态。例如這一段：

.method public hidebysig newslot

instance int32 ComputeFac (

int32 num

) cil managed

{

// Method begins at RVA 0x2050

// Code size 30 (0x1e)

.maxstack 6

.locals init (

[0] int32

)

IL_0000: ldarg.1

IL_0001: ldc.i4.1

IL_0002: clt

IL_0004: brfalse IL_0010

IL_0009: ldc.i4.1

IL_000a: stloc.0

IL_000b: br IL_001c

IL_0010: ldarg.1

IL_0011: ldarg.0

IL_0012: ldarg.1

IL_0013: ldc.i4.1

IL_0014: sub

IL_0015: call instance int32 Fac::ComputeFac(int32)

IL_001a: mul

IL_001b: stloc.0

IL_001c: ldloc.0

IL_001d: ret

} // end of method Fac::ComputeFac

和機器語言相比，CIL是一種高度抽象的中間語言。程式集裡有非常豐富的中繼資料，可以直接對應到源代碼裡的類和方法。而CIL僅僅用于描述方法體的邏輯。CIL較少反應出運作時真正發生在CPU上的事情，而更多地與源代碼中的語句和表達式接近。是以我們說CIL是一種相當進階的中間語言。CIL是一種棧式機。要注意的是，這裡的“棧”與運作時的記憶體堆和棧的“棧”沒有任何關系。CIL的棧是一個運算棧（evaluation stack），它在運作時實際是不存在的，但我們必須要在了解CIL運作過程時想象它存在。運算棧在CIL中的作用是儲存運算的中間結果，這與寄存器機的寄存器有些類型。CIL的每一條指令都隻能對運算棧頂進行操作。

看上面的IL代碼，第一行ldarg.1指令的作用是将1号實參加載到運算棧的棧頂上，第二條ldc.i4.1指令是将32位整型常量1壓入運算棧。注意“ldc.i4.1”是一條指令，它是不帶參數的。IL中有許多這種縮短格式的指令，以消除或減少指令參數，進而減少目标代碼的體積。經過這兩條指令後，運算棧中有兩個值：棧頂是32位常量1，其下面是方法的1号參數值。這時遇到指令clt，這條指令會将運算棧先後彈出兩個值，并比較它們的大小，如果後彈出的值小于先彈出的值，則将32位整數“1”壓入運算棧，反之則将“0”壓入運算棧。假設該方法第一個實參傳的是“0”，以上過程如圖所示：

執行指令

運算棧

空

ldarg.1

壓入參數值0

ldc.i4.1

壓入常數1

clt

彈出1

彈出0

比較0 < 1，是以壓入1

接下來的brfalse指令又會彈出運算棧頂的值，并根據這個值決定是否要進行跳轉。以此類推，即可了解每條指令的作用。任何一條IL指令總會将一些值壓入棧；或者從棧中彈出一些值；或者先彈出一些值，再壓入一些值。這些不同的動作稱為這條指令的棧轉換行為。每條指令都有固定的棧轉換行為，隻要了解了棧轉換行為，就等于完全了解一條IL指令。

MSDN中OpCodes類的幫助中詳細介紹了每一條指令的棧轉換規則。當我們需要了解CIL指令的含義時，這個幫助就是最好的資料。簡單了解了CIL與運算棧之後，大部分指令的行為都是很好了解的。我這裡稍微解釋一下某些特殊的規則。

在CIL指令表當中大家會看到許多指令有多個版本。比如ldloc指令用于将局部變量加載到運算棧頂。這個指令就有ldloc、ldloc.s、ldloc.0、ldloc.1等不同的版本。這其中的ldloc是該指令的長版本，其他指令則是短版本。因為CIL是bytecode，是以這些指令在程式集中都是一個或兩個位元組的代碼。ldloc長版本指令自身編碼為兩個位元組（FE 06），而且它需要一個uint16（兩位元組）的參數，是以它一共需要占四個位元組的空間。我們知道一個方法很少有65536這麼多個本地變量，很多也就是1-2個，有十幾個的已經算是非常多了。是以都用這麼長的指令非常浪費。短版本ldloc.s自身編碼隻有一個位元組（11），而且它的參數是uint8（一個位元組），該指令隻占2個位元組的空間。但是ldloc.s隻能加載索引在0-255範圍内的本地變量。最後，針對最常用的頭4個本地變量，還有四個最短版本。比如ldloc.0，僅占一個位元組的編碼（06）沒有參數。我們在生成代碼的時候需要根據通路本地變量的索引來選取不同的指令：

private void EmitLoadLocal(int locIndex)
{
    switch (locIndex)
    {
        case 0:
            m_ilgen.Emit(OpCodes.Ldloc_0);
            break;
        case 1:
            m_ilgen.Emit(OpCodes.Ldloc_1);
            break;
        case 2:
            m_ilgen.Emit(OpCodes.Ldloc_2);
            break;
        case 3:
            m_ilgen.Emit(OpCodes.Ldloc_3);
            break;
        default:
            if (locIndex <= 255)
            {
                m_ilgen.Emit(OpCodes.Ldloc_S, (byte)locIndex);
            }
            else
            {
                m_ilgen.Emit(OpCodes.Ldloc, (short)locIndex);
            }
            break;
    }
}

下面我們就開始為miniSharp語言編寫CIL代碼生成器。和語義分析階段類似，我們隻需要編寫一個AST的Visitor實作即可。要注意，我們不僅需要生成方法的IL代碼，還需要生成程式集、子產品、類、方法、構造函數、字段等定義。Reflection.Emit為這些結構提供了各類Builder類型，使用非常友善，但必須注意一些規則：

為了生成exe，程式集入口的PEFileKind應當是ConsoleApplication（預設是Dll）。
每個類對應一個TypeBuilder，生成一個類之後必須調用其CreateType方法真正生成類型。一個類CreateType之前，它的父類必須已經CreateType過才行。是以要按照繼承順序建立各個類。
TypeBuilder上也有Type類的所有方法，如GetConstructor、GetMethod之類，但隻有當TypeBuilder調用過CreateType之後這些方法才能使用。是以我們必須自己儲存未完成類型的成員資訊。

下面的代碼展示了按照類繼承順序生成各類的代碼：

public override AstNode VisitProgram(Program ast)
{
    List<ClassDecl> classesInHierarchyOrder = new List<ClassDecl>();

    var topBaseClasses = from c in ast.Classes where c.BaseClass.Type == null select c;
    classesInHierarchyOrder.AddRange(topBaseClasses);

    while (classesInHierarchyOrder.Count < ast.Classes.Count)
    {
        foreach (var c in ast.Classes)
        {
            foreach (var b in classesInHierarchyOrder.ToArray())
            {
                if (c.BaseClass.Type == b.Type)
                {
                    classesInHierarchyOrder.Add(c);
                }
            }
        }
    }

    foreach (var c in classesInHierarchyOrder)
    {
        Visit(c);
    }

    Visit(ast.MainClass);

    return ast;
}

下面展示MainClass的生成方法。這裡用了一個技巧，即static class = abstract + sealed。

public override AstNode VisitMainClass(MainClass ast)
{
    m_currentType = m_module.DefineType(
        ast.Type.Name, TypeAttributes.Class | TypeAttributes.Abstract | TypeAttributes.Sealed);
    m_currentMethod = m_currentType.DefineMethod(
        "Main", MethodAttributes.Public | MethodAttributes.Static, typeof(void), new[] { typeof(string[]) });

    m_ilgen = m_currentMethod.GetILGenerator();

    foreach (var s in ast.Statements)
    {
        Visit(s);
    }

    m_ilgen.Emit(OpCodes.Ret);

    m_currentType.CreateType();
    m_mainMethod = m_currentMethod;
    return ast;
}

搞定類和方法之後，就開始要生成方法體的代碼了。這一部分最主要的翻譯對象是語句和表達式，有一個要注意的規則：

表達式執行之後，該表達式的結果應當壓入運算棧。
語句執行後，運算棧應當被清空。

如果不滿足上述規則，生成的代碼就很有可能是錯的，要非常小心。下面展示兩個最基本的語句——if else和while的生成方法。

public override AstNode VisitIfElse(IfElse ast)
{
    var ifBlock = m_ilgen.DefineLabel();
    var elseBlock = m_ilgen.DefineLabel();
    var endif = m_ilgen.DefineLabel();

    Visit(ast.Condition);
    //the e-stack should have a bool value
    m_ilgen.Emit(OpCodes.Brfalse, elseBlock);

    //if block
    m_ilgen.MarkLabel(ifBlock);
    Visit(ast.TruePart);
    m_ilgen.Emit(OpCodes.Br, endif);

    //elseblock
    m_ilgen.MarkLabel(elseBlock);
    Visit(ast.FalsePart);

    //after if
    m_ilgen.MarkLabel(endif);

    return ast;
}

public override AstNode VisitWhile(While ast)
{
    var beforeWhile = m_ilgen.DefineLabel();
    var afterWhile = m_ilgen.DefineLabel();

    m_ilgen.MarkLabel(beforeWhile);

    Visit(ast.Condition);
    //the e-stack should have a bool value
    m_ilgen.Emit(OpCodes.Brfalse, afterWhile);

    Visit(ast.LoopBody);

    m_ilgen.Emit(OpCodes.Br, beforeWhile);
    m_ilgen.MarkLabel(afterWhile);

    return ast;
}

這裡if語句采用的是brfalse指令。實際上CIL中有許多條件分支語句，如blt、bge等等，可直接翻譯if ( a > b )這樣的結構，效率更高。此次我采用偷懶的做法，全都用clt, cgt這樣的有傳回值的指令來計算大于小于等比較運算，但後統一用brfalse來執行條件跳轉。上面這段代碼還展示了Label在Emit API中的使用方法。翻譯指派語句和數組指派語句時要注意，為本地變量、本地參數或類的字段指派時采用的指令和棧轉換動作均有所不同，需要分别考慮。比如ldfld之前必須先将目标對象壓棧，如果是this的話應該用ldarg.0指令（執行個體方法預設第0個參數是this引用）

再來示範兩個基本表達式的翻譯，二進制運算符和方法調用：

public override AstNode VisitBinary(Binary ast)
{
    //push operands
    Visit(ast.Left);
    Visit(ast.Right);

    switch (ast.Operator)
    {
        case BinaryOperator.Add:
            m_ilgen.Emit(OpCodes.Add);
            break;
        case BinaryOperator.Substract:
            m_ilgen.Emit(OpCodes.Sub);
            break;
        case BinaryOperator.Multiply:
            m_ilgen.Emit(OpCodes.Mul);
            break;
        case BinaryOperator.Divide:
            m_ilgen.Emit(OpCodes.Div);
            break;
        case BinaryOperator.Less:
            m_ilgen.Emit(OpCodes.Clt);
            break;
        case BinaryOperator.Greater:
            m_ilgen.Emit(OpCodes.Cgt);
            break;
        case BinaryOperator.Equal:
            m_ilgen.Emit(OpCodes.Ceq);
            break;
        case BinaryOperator.LogicalAnd:
            m_ilgen.Emit(OpCodes.And);
            break;
        case BinaryOperator.LogicalOr:
            m_ilgen.Emit(OpCodes.Or);
            break;
        default:
            m_ilgen.Emit(OpCodes.Pop);
            m_ilgen.Emit(OpCodes.Pop);
            m_ilgen.Emit(OpCodes.Ldc_I4_0);
            break;
    }
    return ast;
}

public override AstNode VisitCall(Call ast)
{
    var methodRInfo = GetClrMethod(ast.Method.MethodInfo);

    //push target object
    Visit(ast.Target);

    //push arguments
    foreach (var arg in ast.Arguments)
    {
        Visit(arg);
    }

    m_ilgen.EmitCall(OpCodes.Call, methodRInfo, null);

    return ast;
}

注意這裡翻譯&&和||運算符時沒有生成“短路”操作，是以與C#的語義稍有不同。如果要支援短路也非常容易，大家可以親自實驗一下。翻譯二進制運算符時，如果語義分析正确無誤，不應該進入default分支。是以在此隻進行一種錯誤處理的邏輯，它仍然要保持運算棧的平衡。翻譯方法調用時，應當先将方法的目标對象壓棧，然後從左到右依次壓入每個實參，最後調用call指令完成調用。

所有的TypeBuilder都調用CreateType之後，最後調用AssemblyBuilder.Save方法，就可以将目标程式集寫入磁盤了！

public void Create(Ast.AstNode ast, string url)
{
    Visit(ast);

    Debug.Assert(m_assembly != null);

    m_assembly.SetEntryPoint(m_mainMethod, PEFileKinds.ConsoleApplication);
    m_assembly.Save(url);
}

現在終于可以試試看了，我們來編譯一段miniSharp代碼試試：（階乘計算）

static class 程式入口
{
    //中文注釋
    public static void Main(string[] args)
    {
        Fac o;
        o = new Fac();
        System.Console.WriteLine(o.ComputeFac(8));
    }
}

class Fac
{
    public int ComputeFac(int num)
    {
        int num_aux;
        if (num < 1)
            num_aux = 1;
        else
            num_aux = num * (this.ComputeFac(num - 1));

        return num_aux;
    }
}

生成的程式集：

運作結果：

看到自己的編譯器正确地編譯源代碼，是否覺得很有成就感呢？如果隻想做一個托管程式設計語言，那麼生成CIL就是最後一步了。但是CLR幫我們做的實在太多了，不能滿足我們的求知欲。是以，下一階段我們将親手實作從中間語言到目标機器代碼的編譯器後端部分。從下一篇開始本系列的間隔時間會變得比較長而且不确定，因為我自己也需要一邊學習一邊實踐。

希望大家繼續關注我的VBF項目：https://github.com/Ninputer/VBF 和我的微網誌：http://weibo.com/ninputer 多謝大家支援！