今天來(lái)說(shuō)一下智能提示的初步想法。智能提示需要解決的問(wèn)題有兩個(gè)。第一個(gè)是迅速知道光標(biāo)位置在與編輯中的代碼相對(duì)應(yīng)的抽象語(yǔ)法樹(shù)中的位置。第二個(gè)是把當(dāng)前用戶(hù)可以輸入的東西顯示出來(lái)并且提供輸入的便利。第一個(gè)問(wèn)題里面有兩個(gè)小問(wèn)題，包括用你能達(dá)到的最快速度分析代碼全文組成語(yǔ)法樹(shù)并產(chǎn)生scope表，以及智能地在用戶(hù)輸入東西的時(shí)候臨時(shí)對(duì)輸入的那一小塊（如何確定塊的區(qū)域，這個(gè)根據(jù)不同的語(yǔ)言以及編輯的不同位置可能需要不同的算法）進(jìn)行重新分析產(chǎn)生一棵小樹(shù)。我們總是可以在全文分析沒(méi)結(jié)束之前，使用上一次全文分析產(chǎn)生的scope表以及這棵小樹(shù)來(lái)得到超過(guò)99%正確率的上下文。
那么今天要說(shuō)的就是如何用C#進(jìn)行高效的全文分析。我們知道全用LALR的話不僅難開(kāi)發(fā)而且代碼難調(diào)試難測(cè)試難修改，因此就算了。最好調(diào)試的代碼是什么呢，顯然是遞歸下降法寫(xiě)出來(lái)的。其實(shí)代碼本來(lái)沒(méi)多少層，所以遞歸下降最多也就遞歸十幾層，也不會(huì)太多，總的來(lái)說(shuō)性能還是可以接受的。但是每來(lái)一個(gè)語(yǔ)言就用一次遞歸下降還是很慘的。好在.net自帶C#編譯器，我們可以使用parser combinator來(lái)生成。關(guān)于什么是combinator，可以參考
這里。至于什么是parser combinator，我曾經(jīng)用C++
實(shí)現(xiàn)了一個(gè)。
Parser combinator的好處是我們可以在C#里面把文法直接表達(dá)出來(lái)，然后變成一個(gè)語(yǔ)法分析器。不過(guò)直接執(zhí)行combinator，性能會(huì)受到很大影響。怎么樣才能把性能降低到跟手寫(xiě)的差不多呢？.NET給了我們?nèi)N武器，分別是CodeDom、Emit和Linq Expression。我比較傾向于CodeDom，CodeDom可以讓我們寫(xiě)C#來(lái)拼出一顆巨大的代表一個(gè)C#程序的語(yǔ)法樹(shù)，然后用自帶的.net編譯器去編譯成dll或者cs文件。因此這個(gè)C#的parser combinator的目的就是要讓我們用最美妙的語(yǔ)法來(lái)拼出目標(biāo)語(yǔ)言的文法，最后根據(jù)文發(fā)來(lái)產(chǎn)生一份C#語(yǔ)法分析器的代碼。我們可以每次運(yùn)行的時(shí)候都編譯出一個(gè)內(nèi)存的dll，或者直接產(chǎn)生一個(gè)cs文件然后拖進(jìn)我們的工程。
我目前可能會(huì)采取前一種方法：也就是用parser combinator來(lái)產(chǎn)生文法樹(shù)，然后我提供一個(gè)函數(shù)來(lái)把它轉(zhuǎn)換成一份對(duì)應(yīng)的C#遞歸下降語(yǔ)法分析器的代碼（跟yacc很像哈，雖然他用的是LALR），最后編譯它。因此只需要在IDE第一次打開(kāi)某個(gè)語(yǔ)言的代碼文件的時(shí)候編譯出這個(gè)語(yǔ)法分析器，在IDE關(guān)掉之前就都可以用了。
那語(yǔ)法分析器要產(chǎn)生什么語(yǔ)法樹(shù)呢？這個(gè)還是要我們自己來(lái)解決的。不過(guò)我采取了一種比較偷懶的方法。我先寫(xiě)了一個(gè)語(yǔ)法樹(shù)的基類(lèi)（
vlpp.codeplex.com后Candidate\CodeBoxControl\CodeBoxControl\CodeProvider\*.cs），然后只要你給我一個(gè)這樣子的虛類(lèi)：
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>()來(lái)獲得相應(yīng)的實(shí)現(xiàn)了。至于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 }
因此當(dāng)你往AddNode.Left賦值的時(shí)候，也就是等于在寫(xiě)CodeNode.Nodes["Left"]，這就是Create<T>所提供的實(shí)現(xiàn)了。當(dāng)然寫(xiě)進(jìn)去了之后ParentNode和Scope屬性就會(huì)立刻有效了。這種方法還是可以剩下你不少時(shí)間的。
今天就說(shuō)到這里了，然后我就得去開(kāi)發(fā)那個(gè)C#的parser combinator并且想好一個(gè)單元測(cè)試的對(duì)策（這也是一種練習(xí)哈），然后再繼續(xù)寫(xiě)博客了。不過(guò)中秋節(jié)那一整個(gè)星期都要回家辦點(diǎn)事情所以估計(jì)會(huì)暫停。
posted on 2010-09-17 08:43
陳梓瀚(vczh) 閱讀(7423)
評(píng)論(5) 編輯 收藏 引用 所屬分類(lèi):
開(kāi)發(fā)自己的IDE