今天來說一下智能提示的初步想法。智能提示需要解決的問題有兩個。第一個是迅速知道光標位置在與編輯中的代碼相對應的抽象語法樹中的位置。第二個是把當前用戶可以輸入的東西顯示出來并且提供輸入的便利。第一個問題里面有兩個小問題，包括用你能達到的最快速度分析代碼全文組成語法樹并產生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），然后只要你給我一個這樣子的虛類：
1 public abstract class ExpressionNode : CodeNode
2 {
3 }
4
5 public abstract class NumberNode : ExpressionNode
6 {
7 public int Number { get; set; }
8 }
9
10 public abstract class AddNode : ExpressionNode
11 {
12 public abstract ExpressionNode Left { get; set; }
13 public abstract ExpressionNode Right { get; set; }
14 }
那么你就可以用CodeNode.Create<AddNode>()或者CodeNode.Create<NumberNode>()來獲得相應的實現了。至于CodeNode的聲明是這樣的：
1 public abstract class CodeNode
2 {
3 public virtual TextPosition Start { get; protected internal set; }
4 public virtual TextPosition End { get; protected internal set; }
5 public virtual CodeNode ParentNode { get; protected internal set; }
6 public virtual CodeNodeCollection Nodes { get; private set; }
7 public virtual ICodeScope OwningScope;
8 public virtual ICodeScope Scope;
9
10 public CodeNode();
11
12 public static T Create<T>()
13 where T : CodeNode;
14 }
因此當你往AddNode.Left賦值的時候，也就是等于在寫CodeNode.Nodes["Left"]，這就是Create<T>所提供的實現了。當然寫進去了之后ParentNode和Scope屬性就會立刻有效了。這種方法還是可以剩下你不少時間的。
今天就說到這里了，然后我就得去開發那個C#的parser combinator并且想好一個單元測試的對策（這也是一種練習哈），然后再繼續寫博客了。不過中秋節那一整個星期都要回家辦點事情所以估計會暫停。
posted on 2010-09-17 08:43
陳梓瀚(vczh) 閱讀(7453)
評論(5) 編輯 收藏 引用 所屬分類:
開發自己的IDE