摘要: 今天我終于實現了偉大的智能提示了，真是渾身上下都在發光啊。這次智能提示的代碼可以在Vczh Library+ 3.0的頁面上看到。我使用了上一篇文章所提到的技術，在用戶輸入文字的時候，通過迅速獲得“當前編輯語句”的語法樹，再加上舊的“當前編輯語句”的作用域對象，來判斷用戶究竟處于整份代碼的什么地方，最后給出正確的提示。
  閱讀全文     隔了兩個星期才更新，主要是因為之前有一個星期我拿來做了一個Ribbon的DEMO，將來打算用Ribbon來做IDE。另一個原因是這次去的的重大突破消耗了我整整一個星期的時間來完成，好久沒有遇到這么困難的問題了……

    這次主要解決的問題有兩個。第一個是如何從文法生成一個可以對付殘缺不全的代碼的語法分析器，當然這個已經被很多論文研究過無數遍了，我就不詳細解釋了。第二個是如何高效的進行分析。我們知道當代碼高達10000行的時候，語法分析再怎么快也得花上幾秒鐘時間（C#寫的，已經很快了，何況這段代碼是生成的……）的。但是用戶在按下“->”的時候根本來不及等你這么幾秒，所以我想到了一個方法。

    用戶寫代碼的時候總是會陷入思考的，這個時候后臺的全文分析會跟上來，然后標記出“當前編輯語句”部分。如果你接下來快速輸入，我除了再次啟動后臺的全文分析之外，我還會針對用戶的輸入來修改“當前編輯語句”的字符串然后針對這小小的幾行代碼用語法分析產生一個語句列表。這樣的話UI線程里面的語法分析就快到可以忽略了，而且每隔幾秒鐘后臺的全文分析就會趕上然后替換最新結果。這樣可以保證你在打代碼的時候有99%的概率我的語義分析可以正常工作。就算不能工作，也就是產生不出那個下拉列表，一般來說，這種情況只有那些打字的APM超過500的人才會碰到，正常人是不會碰到的……

    介紹了原理之后，我就來貼張圖了。不過在我這個Demo里面你真的輸入10000行代碼還是會感覺到延遲的，那是因為我為了調試，在Tree里面每次都會產生一顆平均十幾萬行的文本表示的全文語法樹，Windows的那個文本框性能太爛了……

    就貼幾張圖好了，首先是輸入object，然后輸入->，最后輸入member;。寫到->的時候已經出現了NativeXPointerMemberExpression了，下拉列表的所有信息已經完全出來了，哇哈哈。




     摘要:     使用了上一篇文章的方法，我已經用C#把NativeX語言的語法分析器寫出來了。而且最近把代碼文件重構了一遍，刪除掉了原來的實驗性工程，轉而重新設計了一個比較合理的工程結構，當然還是提交到了Vczh Library++ 3.0的頁面上去了。現在先來看一看給IDE使用的文法哈。現在語法分析器已經有兩套了，一套是C++寫的用于開發NativeX的編譯器的，...  閱讀全文      摘要:     在詞法分析器生成器寫完之后，就要做語法分析器的生成器了。今天完成了生成器的第一個版本。這個語法分析器生成器所做的事情就是從一個C#寫的文法產生出C#寫的該文法對應的語法分析器。在寫文法的時候你需要提供每一個文法的返回類型，以及指定每一個屬性究竟對應著文法的哪一段。為了方便，我提供了預定義的列表文法和左遞歸文法。當然我們知道手寫遞歸下降分析器都是有套路的，用人寫...  閱讀全文      摘要:     詞法分析器生成器終于做好了，因此我又畫了一個狀態機然后生成了一個詞法分析器，因此開始研究IDE的智能提示的技術了。智能提示的技術有幾個要點，第一個是無論怎么慢都不能妨礙你打字，第二個是崩潰了也不能讓IDE關掉，要重啟分析器。因此我做了一個小實驗。首先我將NativeX語言的著色器跟詞法分析器都做好了，因此我要做的事情就是在你打字的時候，用另外一個線程進行詞法分...  閱讀全文      摘要:     休息了大半個月，沒寫自己的代碼了。國慶過了，再不為自己寫寫代碼就有負罪感了。這篇文章所提到的所有工具的代碼都可以在Vczh Library++ 3.0的頁面找到。上一篇文章提到了一個狀態機繪圖工具，直到最近我終于把他的第一個部分給做好了。現在可以畫圖之后產生一個可以供這里所描述的高亮控件所使用的著色器了。第一步我們要使用TokenizerBuilder繪制一個...  閱讀全文     接著上一篇的話題。開發智能提示首要的問題就是開發一個高性能的語法分析器。一個高性能的語法分析器總是包含一個高性能的詞法分析器的。本系列的第一篇已經提到了用C#和狀態機寫著色器對10萬行代碼進行著色只需要半秒。鑒于我們大部分的程序文件都只是幾千行，因此用相同的技術開發的詞法分析器顯然可以在幾十毫秒內完成對文件的分析，從而再也不需要擔心詞法分析器的性能問題了。

    著色器的狀態機一般都比詞法分析器的狀態機簡單，因為我們總是使用一個顏色來表達一些類型的記號（譬如操作符、數字和名字一般都用同樣的顏色——黑色）。因此我們每當支持一種新語言或者當語言升級的修改IDE的時候，總是要同時修改兩個狀態機。手寫狀態機是很容易出錯的，就如同手寫語法分析器也很容易出錯一樣。語法分析器的解決辦法是讓你給文法來生成語法分析器的代碼，因此詞法分析器和著色器也使用類似的方法：給狀態機生成代碼。

    目前這個狀態機只做了一半：只能畫狀態，暫時還不能指定顏色或者記號類型。當然添加一個指定顏色的功能是很簡單的，不過我還需要想一想如何用圖像來表達，讓狀態機顯得更清晰。今天做了一個晚上搞定了狀態機的編輯程序，如圖所示：

    接下來就可以開發兩個功能，第一個是生成著色器的代碼，第二個是生成詞法分析器的代碼。這樣就可以避免因為程序寫錯從而省下一大堆調試的時間了。     今天來說一下智能提示的初步想法。智能提示需要解決的問題有兩個。第一個是迅速知道光標位置在與編輯中的代碼相對應的抽象語法樹中的位置。第二個是把當前用戶可以輸入的東西顯示出來并且提供輸入的便利。第一個問題里面有兩個小問題，包括用你能達到的最快速度分析代碼全文組成語法樹并產生scope表，以及智能地在用戶輸入東西的時候臨時對輸入的那一小塊（如何確定塊的區域，這個根據不同的語言以及編輯的不同位置可能需要不同的算法）進行重新分析產生一棵小樹。我們總是可以在全文分析沒結束之前，使用上一次全文分析產生的scope表以及這棵小樹來得到超過99%正確率的上下文。

    那么今天要說的就是如何用C#進行高效的全文分析。我們知道全用LALR的話不僅難開發而且代碼難調試難測試難修改，因此就算了。最好調試的代碼是什么呢，顯然是遞歸下降法寫出來的。其實代碼本來沒多少層，所以遞歸下降最多也就遞歸十幾層，也不會太多，總的來說性能還是可以接受的。但是每來一個語言就用一次遞歸下降還是很慘的。好在.net自帶C#編譯器，我們可以使用parser combinator來生成。關于什么是combinator，可以參考這里。至于什么是parser combinator，我曾經用C++實現了一個。

    Parser combinator的好處是我們可以在C#里面把文法直接表達出來，然后變成一個語法分析器。不過直接執行combinator，性能會受到很大影響。怎么樣才能把性能降低到跟手寫的差不多呢？.NET給了我們三種武器，分別是CodeDom、Emit和Linq Expression。我比較傾向于CodeDom，CodeDom可以讓我們寫C#來拼出一顆巨大的代表一個C#程序的語法樹，然后用自帶的.net編譯器去編譯成dll或者cs文件。因此這個C#的parser combinator的目的就是要讓我們用最美妙的語法來拼出目標語言的文法，最后根據文發來產生一份C#語法分析器的代碼。我們可以每次運行的時候都編譯出一個內存的dll，或者直接產生一個cs文件然后拖進我們的工程。

    我目前可能會采取前一種方法：也就是用parser combinator來產生文法樹，然后我提供一個函數來把它轉換成一份對應的C#遞歸下降語法分析器的代碼（跟yacc很像哈，雖然他用的是LALR），最后編譯它。因此只需要在IDE第一次打開某個語言的代碼文件的時候編譯出這個語法分析器，在IDE關掉之前就都可以用了。

    那語法分析器要產生什么語法樹呢？這個還是要我們自己來解決的。不過我采取了一種比較偷懶的方法。我先寫了一個語法樹的基類（vlpp.codeplex.com后Candidate\CodeBoxControl\CodeBoxControl\CodeProvider\*.cs），然后只要你給我一個這樣子的虛類：

    那么你就可以用CodeNode.Create<AddNode>()或者CodeNode.Create<NumberNode>()來獲得相應的實現了。至于CodeNode的聲明是這樣的：

    因此當你往AddNode.Left賦值的時候，也就是等于在寫CodeNode.Nodes["Left"]，這就是Create<T>所提供的實現了。當然寫進去了之后ParentNode和Scope屬性就會立刻有效了。這種方法還是可以剩下你不少時間的。

    今天就說到這里了，然后我就得去開發那個C#的parser combinator并且想好一個單元測試的對策（這也是一種練習哈），然后再繼續寫博客了。不過中秋節那一整個星期都要回家辦點事情所以估計會暫停。     今天先放圖哈。智能完成已經開始做試驗了不過距離能看還差很遠，所以今天先繼續談一下著色的事情。

    這就是我暫時實現的所有功能了。首先著色算法可以外掛，其次左邊那個邊欄（大小和繪制均可以訂制）操作他的時候會發生什么事情也是外掛的。著色器與“斷點變紅”是分離在兩個不同的插件接口里面的，原因上一篇文章說過了。你們可能還會注意到那個灰色的框框。那個框框的確是會被編輯器當成一個整體來對待，不過我絕對還沒有實現折疊。因為在我的設計里面，如何進行折疊應該是插件的事情，控件本身只要處理好怎么編輯和顯示就行了。還有一個比較難發現的就是，我這玩意兒也是支持輸入法的，輸入法的窗口會跟隨光標移動……

    在開發這個東西的時候我嘗試了兩種新方法。第一種是MVC。MVC開發高亮還真是容易啊，不僅文字緩存部分（C#也是可以精確控制內存的哈）可以獨立出來，連編輯操作（各種按鍵鼠標組合）其實也可以不做在控件里面。這樣有什么好處呢，當然是可以進行高強度的單元測試了哈。第二種就是GUI自動化，光對類進行單元測試還是不夠的，Visual Studio 2010為.net單元測試工程提供了一個Coded UI Test框架可以給我啟動一個獨立的外部程序（MFC寫的也行，WinForm寫的也行，WPF寫的也行，網頁都行）然后操作上面的各種控件最后拿到控件里面的信息。不過可惜的是我的文本框并沒有按照Windows的UI Automation標準來實現（從而讓盲人也能使用這個控件），因此只能進行鍵盤和鼠標的操作，至于我繪制的東西是什么則需要其他方法。C#跨進程怎么做最方便呢？當然是Windows Communication Foundation了哈。為了寫足夠的單元測試是要不惜一切D。不過顯然WCF的服務不可能做在控件里，因此我的solution下面暫時就有控件工程、測試工程和被測試的“獨立程序”工程了。

    有了GUI自動化測試，我在進行重構的時候，就可以放心的修改代碼，然后執行測試程序，去外面喝杯茶。過個幾分鐘測試工程就會跟我報告一共掛掉了多少個case，只要修好就行了。這種方法杜絕了絕大多數由粗心引起的bug。如果你在公司使用類似技術來對付你的代碼的話可以有效減少工作時間，從而讓公司可以榨取更多價值。

    操作的組合還是比較麻煩的。為了全套支持，我特地操作了一下Visual Studio 2010的文本框，然后對一些我看不順眼的行為經過修改之后，現在已經可以實現{LEFT, RIGHT, UP, DOWN, HOME, END, PAGEUP, PAGEDOWN, ENTER, BACKSPACE, DELETE}×{null, CONTROL, SHIFT, CONTROL+SHIFT}共44種操作方法。加上鼠標，突破半百。這么復雜的東西，如果沒有足夠的單元測試，也沒有足夠的GUI自動化測試的話，隨便改個什么都很有可能發生問題的。所以開發這類程序的時候要十分小心，一定要寫單元測試。

    至于著色應該怎么測試呢？只要有了WCF，就十分簡單了。測試程序發送兩個坐標，WCF服務返回坐標之間所有字符的顏色代號就行了。代號是可以在測試程序跟被測程序之間約定的，所以這種方法就讓測試變得十分簡單了。

    開發這一部分一共花掉我大約四天時間（假設不用上班每天能寫8個小時，累計出來的）。當然平時要上班所以實際花費是要多一倍不止的。其實當我在紙上畫出了上圖C#著色器的狀態機之后，也沒想到實現出來速度這么猛的。雖然著色器使用狀態機來實現已經是速度最快的方法了（經過大學4年寫編譯器的經驗……不過我后來用C++做出了一個能根據正則表達式在內存中產生詞法分析器的，比手寫的更快），不過還是要感嘆一下.net到了4.0還是比起當年的2.0要進步無窮多倍的哈。虛擬機可以在執行的時候才開始產生并優化x86代碼，可以讓程序越跑越快（非騙人，編譯原理小白請自行學習），這還是靜態編譯其所不能達到的。之前還看過channel9上面的視頻講微軟某個研究院在做一個全新的javascript引擎（看起來好像沒有加進IE9beta），就是用了動態的兩階段profile+optimize+codegen的方法，通過為瓶頸代碼使用激進優化方法，從而讓總體的運行和編譯時間的總和降到最低。生成X86什么的還是非常麻煩的，總之我已經被機器碼囧了半年，暫時不想碰JIT了……當然這是遲早要再碰一次的。

    寫到這里就先碎覺了，下一篇開始說之前在糾結的過程中產生的幾個智能完成的方案。遲早都要把它給做出來的。     在寫這篇文章的時候，我正在嘗試自己開發一個我自己認為能拿出去見人的IDE。當然此時此刻我只開展了一點點工作。所以這篇文章沒有什么最終的指導性，而是在記錄我開發IDE的思考過程。當然我覺得之前寫了那么多東西除了開了源之后介紹了我的作品讓大家可以更好的理解并學習以外，其實也沒有什么大的效果（除了幾篇置頂的教程我個人覺得還是有點效果的……）。因此我嘗試做一下改變，把我的思考過程描述出來。一方面我自己可以從一個更高的高度來審視我自己，第二個就是如果你們想從我這里拿走什么，或者想教我什么，請自便哈。

    其實以前并不是沒有開發過IDE，只是那個IDE除了語法高亮以外什么都沒有，因此其實并沒有什么大的用處。個人認為IDE要提供給你的功能有三點：智能提示、集成調試、輔助部署。當然在我眼中最厲害的IDE當屬VisualStudio了，各種功能真是非常人性化，而且也跟我的觀點比較一致：我只是想開發個編譯器然后開發個makefile系統讓別人可以方便一點用我的編譯器而已，為什么我一定要用makefile來組織我的編譯器源代碼啊，一點都不方便（噗

    是個程序員都是這么想的哈。

    IDE還是好東西。前幾天我在vlpp.codeplex.com上面checkin了一份我開發的語法高亮編輯器的雛形（下載后打開Candidate\CodeBoxControl\CodeBoxControl.sln），完全用C#寫。我的Demo也是用的C#，外掛了一個可以分析C#的關鍵字、字符串和注釋的代碼著色器，在我的機器上（雖然我覺得比較強大，不過我的程序也是單核的，因此其實也只有2.7G的頻率）著色一個將近10萬行的程序只需要半秒鐘。其實大家大可不必覺得C#很慢，其實是很快的，慢的是你的內心。

    當然我也做了一點優化，全文著色要半秒，不過其實你在編輯的時候是不需要總是全文著色的。所以我的著色器接口做了一點小限制：
    1、你必須用狀態及實現，而且狀態及的狀態只能用int類型來表達。
    2、著色必須是上下文無關的。

    對于2可能比較難理解。首先C#那個可以檢查出一個ID是不是一個類型然后變色其實根本不是著色器的任務（根據我的設計，你可以在另一個地方臨時更改顏色，也能實現）。其次對于一個給定的任意字符串前綴，其著色效果不能跟前綴之后的任何字符有關系。

    因此我只需要記下每一行的末尾著色器當時的狀態，就可以從任意位置開始到任意位置結束進行部分著色了。因此這里就有很多的優化空間。有了這些優化之后，我用我的Demo編輯一個將近10萬行的C#文件的時候，那個運行在UI線程里面的著色算法絲毫沒有讓我覺得有延遲，只有在少數情況下（瞬間貼了好幾萬行代碼，然后按ctrl+end跳到全文最后，我不得不對你貼進去的東西立刻著色）才會讓你感覺到有小于半秒鐘的延遲。所以我覺得這個設計已經可以達到我的要求了，因為我自己寫的代碼一般單個文件都沒有超過1萬行，所以偶爾給我一個小于0.05秒的延遲其實也是無所謂的……

    為什么可以進行優化呢。你可以想一下，如果我正在對某一行進行編輯，而且這一行后面的代碼都已經被著色過了，那么如果你的改動都沒有讓行末尾的著色器狀態發生變化，那么這一行后面的所有字符都不需要更改他的著色，因此我就可以只對你當前編輯的一行進行著色（唯一修改的其實也就只有那種多行注釋，你一般也不會寫很多這種多行注釋的，都用的單行……）。一百來個字符的著色基本上可以忽略，因此無論你的文件有多大，其實著色速度是跟你平均每行的長度有關系，只有在極少數情況下才會跟你的行數有關系。這個時候你可以看到著色器兩個限制的強大威力了吧。

    那么，當我們對一行代碼進行斷點的時候，代碼顏色的修改是如何做的呢？為了這個東西去影響著色器那個強到可以忽略的效率實屬殺雞取卵，所以答案就是：外掛一個控制面板接口，讓你可以在顯示某一行的時候臨時修改那一行每個字符顏色。聽起來好像很影響效率，不過我們要相信，一行代碼也就只有那么幾十到一百來個字符，一屏幕的代碼最多也就一兩千個字符。任何語言無論多慢，對一個一兩千那么長的數組賦值，也是奇快無比的，何況是C#這么快的語言……

    因此我們剩下的問題就是如何實現一個可以修改文字顏色的普通文本框了哈。經過我的3此研究，結論就是，不要用RichTextBox，你自己自繪從頭寫一個。第二個結論，凡是GUI最好都別用C++，無論GUI類庫多么好，一個沒有內存管理器就足以讓你覺得很麻煩了，當然對于編譯器本身我還是推薦C++的，因為編譯器雖然算法復雜，不過結構簡單，所有的內存分配都是可以預測的，因此delete起來非常有信心。

    最近一兩個星期都在糾結如何實現一個簡單的上下文有關的智能提示功能（至少按個"."會有個列表什么的）。這個明天再寫了，今天只有一點點頭緒，還沒完全成型。