決定把Vczh Library++3.0的項目的主要工程升級到VC++ 2010。新的VC++智能提示變得無敵順暢，無論我怎么模板怎么宏亂嵌套，結果都是正確的。娃哈哈。不過反正語法是兼容的，使用Vczh Library++3.0的也無法直接使用那個單元測試用的工程文件，所以我想影響應該不大。

跟老外聊天果然是不流利啊，就算英文可以看文章寫wiki，說起話來還是不夠爽。特別是非美帝且非天朝的人說起英語，口音跟天朝有一拼，就互相聽不懂了。

四個星期。第一個周末去了批發市場買名牌，當然我只是看，同事在買。第二個周末去了看郁金香展，拍了些圖。第三個星期去了Orcas島（這個M$產品的code name就是喜歡用這些湖啊島啊山啊……）等到山頂，那個比上海北京都好得多的空氣讓我們可以直接用眼睛看到加拿大的山。第四個星期同事出去玩，我就在寫代碼了。還是寫代碼爽啊，游山玩水什么的都是浮云。當然戰利品是有的，帶了一盒明信片，還有人體工學鍵盤鼠標。M$賣給自己人還要打5折，壓榨了我們的剩余價值應該送個才對，后來打聽到了，美帝的人要鍵盤是不用錢的，天朝的人就得自己花錢了，雖然打折……

Vczh Library++的C囧（NativeX，拿C改了點語法，當中間語言用，功能基本沒有減少）編譯器一直在重構。昨天晚上終于做了一個功能，可以把二進制格式的assembly轉成文本文件供查閱了。雖然做了點代碼生成的優化，不過其實還是不夠好。接下來就是慢慢看文本文件里面記錄的指令集，慢慢想辦法優化輸出的指令了。給C囧語言加上點泛型的想法開始成型了，雖然這主要是為了高級語言編譯到低級的C囧語言所做的準備，不過還是有點麻煩。Vczh Library++的最終目的就是提供本地強類型語言、垃圾收集的面向對象強類型語言和動態語言三種語言的編譯器和一些輔助類，讓這三種語言可以編譯到相同的assembly，互相調用，并且提供大量工具可以讓用戶們基于這三種語言的編譯器輕松開發出自己的語言。最后只要把最低級的C囧語言的JIT給做了，就等于所有語言同時享受JIT帶來的好處。革命尚未成功，同志仍需努力。

明天上飛機，美帝的人民群眾對食物果然還是沒有追求啊，還是天朝好……      摘要: Vczh Library++ 語法分析器開發指南 陳梓瀚   前言 在日常的開發工作中我們總是時不時需要寫一些語法分析器。語法分析器不一定指的是一門語言的編譯器前端，也有可能僅僅是一個自己設計格式的配置文件的讀寫程序，或者是一門用來簡化我們開發的DSL（領域專用語言）。我們可以選擇使用XML，不過因為XML的噪音實在是太多，所以自己寫語法分析器在有些情況下是必要的，特別是那種經常...  閱讀全文     這幾天使用Performance Wizard搞了一下我的那個東西，結果發現瓶頸在一個很不可思議的地方，當然總的原因是因為虛函數調太多了，所以得修改修改。不過還好，還是有不破壞設計的辦法的。

    Performance Wizard是Visual Studio自帶的一個工具。使用的時候很簡單，首先找Analyze -> Launch Performance Wizard...，出來一個向導。第一個頁面選你要做檢查的工程，第二個頁面在Sampling和Instrumentation之間作選擇（我一般選擇后面的），完成了之后就會出來一個叫Performance Explorer的窗口，里面有建立好的性能檢測文件，當然是不保存的，一般來說也不用保存。Performance Explorer的根節點跟你的解決方案同名，右鍵選擇Properties，在Sampling的Sample Event里面選擇Performance Counter，好了大功告成。

    想啟動很簡單，首先將你的編譯指向Release，然后選擇Performance Explorer根節點下面Targets目錄下面的一個跟工程同名的節點，點擊Performance Explorer工具欄上有綠色箭頭的按鈕，然后就開始了。上面的配置將性能分析指到了最精確的一種方法，因此運行的時候慢，而且產生的文件特別大，建議在超級好的機器上使用。不然的話就只好使用Sampling而不是Instrumentation了。這個時候Performance Wizard會編譯你的工程然后執行一直到結束，執行的過程中記錄下很多信息。注意在Vista或以上操作系統，Visual Studio要用管理員權限打開才能正常使用Performance Wizard。

    之后就一直等，完了就會有一張超級詳細的報表出來，這個時候切換到“Call Tree”報表，上面一個火苗樣子的工具欄按鈕按下去就自定尋找性能瓶頸并定位。這個Call Tree就是Call Stack在整個程序執行過程中的變化情況，附加信息非常詳細，非常好用。

    慢慢享受吧，啊哈哈。     今晚在Vczh Library++3.0里面實現了C++調用NativeX腳本函數的單元測試代碼，這個Demo其實是從單元測試里面抽出來的。

    因為代碼可以在這里下載到，所以這里只列出當前版本C++調用NativeX腳本函數的例子。首先我們假設有下面的字符串，然后存放在const WString& code;的變量里面：

    因為NativeX基本上是用來被更加高級的語言做編譯媒介的中間語言，或者拿來寫一點腳本引擎的庫用的，因此語法并沒有設計得十分的簡練。大部分還是從便于分析，并且接近C語言的角度出發。現在的NativeX支持數組、指針、自定義函數和結構體，不過這個Demo為了顯露出本質，就簡單化了，只實現了一個加法函數和減法函數。

    那么假設這段代碼已經保存在變量code里面，那么可以通過下面的方法來調用Add和Sub函數：

    不通過BasicFunctionExecutor而想自己設置返回值指針和自己挨個把參數Push進堆棧也行，其實BasicFunctionExecutor的實現正是調用了這些原始接口來做到的。

    例子就分享到這里了，完整的代碼請去這里下載。     上海什么的完全不能跟西雅圖比啊，西雅圖能見度無敵高，下雨了車開了一個小時玻璃還是干凈的，在上海下雨天開一個小時車那玻璃上全是泥。西雅圖綠化非常好，就像是把城市建在了樹林里面。而且高速公路設計合理，拐彎的時候有斜坡不會一不小心甩出去。而且有些地方還有Stop標記，無論你路上東西多不多，車一定要先完全停止了才能再啟動。

    比較窘的地方就是第一天竟然遇到冰雹了，說來也搞笑西雅圖的云只需要一小塊就呼風喚雨，這一塊云下完了雨也就沒了，加上空氣干凈緯度較高變成了冰雹，而且猛下冰雹的時候旁邊還有太陽，正所謂冰火兩重天也。

    于是今天就跑去Microsoft里面的Company Store參觀了一下XBox，里面展覽Windows 7的幾臺電腦儼然被同志們處理成了網吧。星期一就要去上班了，這幾天寫寫代碼，倒倒時差，吃吃神奇的東西，睡睡覺，兩天就過去了。     因為項目原因去美帝出差，codeplex的速度估計就下降了……之前剛剛把NativeX寫完，但是還剩下最后一個接口沒在Language Provider上實現，因此還有一些Test Case沒寫完。現在把一個NativeX編譯完之后，可以從LanguageAssembly上面反射出NativeX所有的接口。于是在這個基礎之上就可以做ABI了。

    整個項目的大方向是將本地語言、托管強類型語言和托管動態語言有機的結合在一起，因此采取的路線是動態語言編譯成托管語言，然后再編譯成本地語言，在之后編譯成指令集，就可以用虛擬機執行了。指令集還可以做JIT，最終讓CPU直接執行x86的代碼。

    在美帝一兩天安頓好之后，將會做完第一個Language Provider對NativeX的支持，然后優化parser combinator和regular expression lexer，再補充好文檔，然后發布第一個alpha preview binary。當然這個alpha preview binary距離項目的目標是相當遠的，只是做一下將這一整套東西變成dll的試驗。     啊，人生就是不斷地重寫同一個程序。大家看我的博客估計會發現我總是不斷的徘徊在編譯器和界面庫上。這估計是由于一直以來我總是不能把這兩個東西做到我滿意的地步，然后就不斷地重寫，不斷地重構，重構到不行了再重寫。這篇文章講了我之前做編譯器的道路，而這里、這里（這篇文章有一小部分是同學寫我的）和這里可以看成是我做界面庫的道路。

    我學習編程是從VB拖控件開始的，后來又經歷了Delphi，現在工作又用C#，所以平時自己寫什么想堅持C++就變成了一件很糾結的事情。我覺得語言是一種信仰，C++用的爽當然希望他無所不能（其實本來也是。嗯……這句話應該也是信仰）。結果MFC又封裝的太難用，其他的界面庫基本上都沒編輯器，現在C#還有WPF、Silverlight，Adobe還有Flash或者Flex，那C++有啥？啥都沒有。但是我還是想用C++寫漂亮的demo啊，怎么辦呢，沒有只好自己操刀。

    話說回來，我從來就不指望我寫的界面庫能夠充當WPF和Flex這種分量的，只是我自己需要了，就寫一個，反正閑著也是閑著，做了編譯器總要有一些看得見摸得著的demo的。

    第一次做界面庫倒并不是因為C++的緣故，本來是給Delphi做游戲的。大一的時候想移植到C++上面，結果就用OpenGL做了一次。后來為了更方便我封裝了一下WinAPI（其實封裝比自己寫難TM多了）。只是Windows的界面標準過于高級，API又過于靈活。我一直以為在菜單上加個圖標是很容易的，到最后才明白VB也好Delphi也好.NET也好都偷偷替你OwnerDraw了。我一直以為按鈕可以放在一個GroupBox上的，結果竟然XP這個bug沒修，.NET偷偷在Button下面放了一個容器來繞過這個問題。我一直以為API提供了WS_TABSTOP的話就幫我們解決了Tab跳轉焦點的問題，結果WS_TABSTOP竟然是為了我們方便自己實現跳轉焦點而存在的。我一直以為模態窗口是一件很自然的事情，結果不僅沒支持（MessageBox那玩意兒倒支持了），實現起來還不容易。

    而且加上我自己也很喜歡RIA，于是就想著干脆總結之前的經驗，自己做已做好了。搞定了之后還能給編譯器寫個demo還是寫個破IDE什么的，湊合著估計還有點用。

    目前還沒有一個非常詳細的計劃，只是在項目開了一個子文件夾做做實驗。由于觀察到界面庫的Logic Tree和Visual Tree一般來說有明顯結構上的區別，繪圖API可以置換，Hit Test跟Control Style應該捆綁等現象，打算基于這種想法來實踐實踐：

    1：使用Windows API創建窗口和GDI對象，再給出一個跟平臺無關的接口來屏蔽這個實現。其實我不想跨平臺的，只是這樣工程管理起來比較有效罷了。

    2：將控件切割為狀態、顯示位置、風格和排版四個部分。其中控件自己有自己的結構，排版則將控件結構（Logic Tree）映射到一個顯示結構（Visual Tree）并自動維護，顯示位置是用于提供顯示結構功能的一個框架，風格則負責繪制以及做Hit Test從而將用戶輸入的系統消息轉換成邏輯消息（譬如說點擊某個位置 => 點擊滾動條的向上按鈕）。

    3：提供一套Control Combinator。Windows那套嚴格來說不是Combinator，憑什么ListView的條目不能是我自己寫的控件呢？顯然這是他不是Combinator的一個明顯的證據。Combinator就好比我們寫代碼，各種不同的語句組合在一起還是語句，不同的表達式組合在一起還是表達式，而且還有把表達式和語句互相轉換的唯一方法，這就是Combinator了。換個角度來說，這跟WPF的那么多種ItemTemplate還是什么破Template應該是一回事。

    4：為每一種Control提供一個默認的風格。其實這個是必須做的，不然連用都沒法用。

    5：讓控件渲染用的技術、控件風格和控件排版功能可以獨立變化。這是所有RIA的共同特征。

    其實也就這么多了。如果試驗成功的話這個庫將會被合并進Vczh Library++3.0。     其實Vczh Library++3.0提供的parser combinator并不能大量減少語法分析器的代碼量，其實真正降低的是語法分析器的復雜程度。當你想比較快速的完成一個功能的時候，有兩種代碼量差不多的設計，一種實現起來比較難并且調試起來很慘，一種實現起來比較簡單而且基本不用怎么調試，那相對來說肯定會選擇后一種方法了。除非你純粹是想獲得鍛煉。

    使用parser combinator開發語法分析器的時候，你可以直接往C++里面寫EBNF語法，當然語法的具體形式因為受到C++語言本身的限制我做了一點點修改，譬如說A*和A+只好寫成*A和+A，A B只好寫成A + B、A>>B或者A<<B了。空明流產跟我抱怨說boost::spirit編譯速度奇慢（據說要一個多小時，不知道是不是他機器太爛……）而且容易出現C1060 compiler is out of heap space的錯誤，相比之下我在用我自己開發的parser combinator的時候，我一個充滿語法的cpp文件只需要一秒多一點（Thinkpad R61i, Vista Home Basic, 3G內存），而且不會出現C1060這種離譜的錯誤。至少從這個程度上來說，開發boost::spirit的人應該是有很大的C++潔癖癥，才會把好好地一個parser combinator折騰成那個樣子。

    我是用的文法模型是帶類型修飾的文法，從文法的類型只能看出文法最終給你什么數據，而不是文法他本身是怎么寫的。Vczh Library++2.0的parser combinator采用了后面一中的做法，據說boost::spirit也是這么做的，不過奇怪的是舊的parser combinator也沒出現那兩種錯誤，取而代之是VC++經常抱怨我一個表達式的類型簽名超過了4000個字符（囧）。于是Vczh Library++3.0的parser combinator做了一點修改。

    假設你一條文法A的結果是node<input, type>，第二條文法B的結果是node<input, string>，那么A+B的結果就是node<input, pair<type, string>>。這是什么意義呢？我們看表達文法type name semicolon的意思，大概可以理解為他可以接受“int a;”的這種語句。首先由于C++的限制我們替換成type + name + semicolon，其次由于那個semicolon，也就是分號，其實僅僅是語法的要求而不是語法樹的一個必須成分，因此改成type + name << semicolon。這樣的話，這個文法依舊會要求輸入的字符串分別是一個類型、一個名字和一個分號，但是返回的結果就自動把分號給忽略掉了。那么我們如何表示一個同時包含type和name的類型呢？因為文法不可能替你創建一個struct，所以就定義了一個泛型的pair來表達。于是type + name << semicolon的結果類型就是node<input, pair<type, string>>了。這里input代表輸入的記號列表的類型。

    上面是新的parser combinator的做法，舊的parser combinator（據說也是boost::spirit的做法）的類型表示方法比較BT：當你有文法type : node<input, type>，string : node<input, string>和semicolon : node<input, token>的話，那么type + name << semicolon的類型會變成：
    寫成這樣大概就可以理解什么是“文法他本身是怎么寫的”了吧。

    舊的parser combinator的好處是C++為每一個文法生成了一個類型，雖然代碼會膨脹一點但是執行過程會很快，只不過缺點比較多。第一個當然是類型太多VC++編譯器會崩潰（C1060 compiler is out of heap space），第二個是編譯時間過長，第三個是當你的文法比較長的時候，類型簽名可能會超過VC++給你的限制，然后就會出現奇怪的問題。所以我在Vczh Library++3.0的parser combinator就是用了一個新的做法，也就是僅保留文法的結果類型，所以也就不得不引入虛函數了。因為一個文法node<input, type>有非常多種組合可能，在結構上沒辦法表現出來，所以必須使用虛函數。

    在聽了空明流產的抱怨之后，我去搜了一下使用boost::spirit的人的反應，好像都是遇到了那兩個嚴重的問題。幸好我喜歡造車輪，不然的話也許也會深陷地獄了。不過boost::spirit還是提供了解決辦法的，就是把你的長的文法拆開成短的。寫過編譯器的人都會知道，這么做的嚴重后果就是你的分析器變成一團亂麻，根本不知道自己在寫什么，不僅不可能有我上一篇文章描寫的優美結果，更不可能把NativeX的分析器寫成下面這個樣子了：

    啊，簡直就跟EBNF沒什么區別啊。

    當前的進度可以在Vczh Library++3.0的頁面上看到。     昨天剛剛完備了Vczh Library++3.0對于基本的分析器的支持。分析器主要有兩部分組成，第一部分是語法分析器。這個分析器通過程序員直接寫在C++里面的語法來分析一個輸入。第二部分是詞法分析器，這是通過實現一個正則表達式引擎來完成的。為了讓分析其更加靈活，分析器使用模板來寫，輸入只要滿足一定的接口就可以了。Vczh Library++3.0內置字符串輸入、迭代器輸入和列表輸入。于是在單元測試里面就寫了兩段代碼來分析一個四則運算式子，第一個沒有詞法分析器，第二個用了詞法分析器。

    我們先來分析一下四則運算式子的一般做法。總的來說我們會先寫一個不包含左遞歸的文法：

    從EXP開始，我們就可以將一個四則運算式子的結構表達出來了。我們先用Vczh Library++3.0提供的庫，通過直接分析輸入的字符串來拆解一個四則運算式子并將其結果計算出來：

    首先我們需要一個函數，這個函數輸入兩個整數和一個字符（代表操作符）來計算出結果。當然因為分析其本身的要求，操作符和右操作數是一個pair：

    接下來，我們要在C++里面寫一個文法：

    是不是比較直觀捏。現在來解釋一下里面的內容。

    首先對于FACTOR = rgx(L"/d+")[wtoi] | (ch(L'(') >> EXP << ch(L')'));，我們知道這其實就是FACTOR = NUM | ( EXP )。這里rgx是一個正則表達式的輸入檢查，如果輸入的字符串是整數那么就走左邊的，如果輸入的第一個字符是括號就走右邊的。a >> b << c的意思是輸入必須是先a后b后c，然后拋棄a和c的分析結果只留下b。這個很好理解，分析完我們只需要那個EXP不需要兩個括號的。a[b]的意思是把a的分析結果用b函數轉換一下。rgx的結果自然是一個字符串，會告訴你輸入的整數究竟是什么，然后通過函數wtoi將字符串轉換成整數。

    剩下兩條都比較像。我們知道左遞歸的寫法是：TERM = FACTOR | TERM MUL FACTOR，因為我的分析器不能直接支持左遞歸，所以需要一個變換：TERM = FACTOR (MUL FACTOR)*，但是這樣計算函數寫起來會很麻煩，所以我提供了一個lrec組合子將非左遞歸的模式在計算完成之后，重新轉成左遞歸，然后調用那個cal函數。因此cal函數才需要三個參數，如果不用lrec的話，cal將是一個整數，還有一個操作符和整數的列表，寫起來比較麻煩。

    最后就剩下分析了：

    Vczh Library++3.0提供了兩種分析方法，分別對于需要知道詳細的錯誤信息和不需要知道詳細的錯誤信息來做。如果程序員可以假定輸入正確，或者說不需要報告那么詳細的輸入錯誤信息的話，使用第二種方法就行了，一行代碼搞定。

    那么接下來看第二種。第二種我們走傳統道路，先詞法分析后語法分析。詞法分析把輸入分成了5種記號，分別是整數、左括號、右括號、加法和乘法，用正則表達式來描述：

    因此我們的cal函數就要變一變了，同時還要提供一個tval函數將RegexLexer分析出的一個記號RegexToken轉成整數：

    至此剩下的都差不多了。我相信看懂了第一種做法的人可以直接看懂第二種做法，因為只是換了一個輸入類型而已，剩下的內容都是一樣的：

    這里需要注意的是由于lexer.Parse返回的記號里面只保存了wchar_t*，所以變量code有必要存活下來，不然那個指針就會被釋放掉。此法的過程還是比較麻煩的，要多寫四行。這里并沒有過濾空格，如果需要過濾空格的話，用一下linq：


    然后把CopyFrom那行改成：CopyFrom(tokens.Wrap(), lexer.Parser(code)>>Where(DiscardBlank));就完了。linq萬歲！

    至此兩種方法就介紹完了，上面的測試代碼和分析器的源代碼都可以在Vczh Library++3.0找到。