决定把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找到。