摘要: 今天我终于实现了伟大的智能提示了，真是浑身上下都在发光啊。这次智能提示的代码可以在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起来非常有信心。

    最近一两个星期都在纠结如何实现一个简单的上下文有关的智能提示功能（至少按个"."会有个列表什么的）。这个明天再写了，今天只有一点点头绪，还没完全成型。