完成中间代码生成

最晚突发灵感，一口气写代码生成写到凌晨 5 点。睡了一觉，逃了一天课，下午又接着写，终于完成了这个 "Simple Compiler"。说实话，写这个编译器花的时间最多的不在代码生成，但确实感到代码生成的技术含量是最高的，也难怪每一本讲编译的书在代码生成上的章节是最长的。想想 2 个月前的暑假时还认为写编译器是一项不可能在短时间完成的任务，而现在基本上对编译器的流程有了一个大致的了解和实践，真的还是应了那句老话：“没有什么是学不会的。”

这个编译器，词法分析方面主要参照了《编译原理与实践》(Compiler Construction Principles and Practice) 里的那个 TINY Compiler 处理方法和技巧，构造 DFA，分状态处理输入字符。语法分析就是纯正的 LL(1)。

语义分析和中间代码生成这个阶段就不像前两个阶段那样有一个公式可以套。可以说，每个语言都有不同的、属于自己的分析方法，所以这个部分我更多的参照了教科书里面的方法。虽然说先根据语法分析的结果生成语法树，再根据语法树生成代码会简单一些，但这样会增加代码，降低效率，而且在某些情况下不适用，同时因为我的语法分析是 LL(1)，所以我还是选择在不改变语法的情况下直接在语法分析中间添加语义分析的代码。

具体技术上，主要是使用“回填”技术。为了解决如何延后修改已经生成的代码的问题，我设立了一个四元式的数组，把生成的中间代码写进去，在 backpatch 函数中修改相应四元式。在分析完了所有程序后，用 emit 函数将四元式输出到控制台上。

其实，虽然感觉在实际编写代码上的时间并不是很多，但平时一直都在看关于编译的书，也正是有这些积累，才能够有比较清晰的思路来完成它。还要感谢那些前辈们宝贵的智慧和经验，没有他们，编译还是 Mission Impossible。

《编译原理》，Compilers: Principles, Techniques, and Tools，龙书
《编译原理与实践》，Compiler Construction Principles and Practice
《可变目标C编译器——设计与实现》，A Retargetable C Compiler: Design and Implementation，lcc
《编译器构造：C语言描述》，Crafting a compiler with C

Visual Studio 2005 试用

昨天从网上下载到了 Visual Studio 2005 Professional Edition 的 RTM 版，马上试着安装。遇到的第一个问题是，VS2005 需要 Windows XP SP2，我还是 SP1。在 Aaron Stebne 的 Blog 找到了没有 SP2 也能安装 VS2005 的方法。因为 setup.exe /NO_BSLN_CHECK 简单，也没仔细看就尝试。结果总是在安装 MSI 的时候出错。没办法，改了注册表重试，一切顺利。（根据 Aaron Stebne 的说法，VS2005 并没有使用 SP2 的特性，微软的这一限制只是为了推广 SP2，所以即使没 SP2 也不会对使用造成任何不同）

试用了一下，嗯，界面不错，但是和 2003 比起来，改变还是不大，主要是 Dock 上有点变化。2005 似乎很强调网络功能，从 Start Page 到 Search，都提供并推荐使用线上服务，而菜单中更是加入了 Community 选项，看来微软认为 2005 要把所有的程序员通过网络联系起来吧。

功能上，乍一看还真么什么新东西，只多了个 Call Browser 和 Code Definition Window。C++ 工程属性页加入了 Manifest Tool 和 XML Document Generator 两个，默认选项变了一些。现在，编译错误不再在 Task List 里面显示了，而是一个独立的 Error List，这样对经常使用 Task List 的人来说可能更方便一些了。其他的都大同小异。

说说问题。第一，设置、界面、习惯变了，虽然不大，但还是不爽。当然，这是可以预料的。第二，Visual Assist X 的 10.1.1301 版不能用在 2005 里面，10.1.1418 版又因为试用期已过，无法再用，所以现在写代码都有些没信心。第三，Start Page 里面的 Recent Projects 没用！我打开了无数次 Solution，但那里面永远都是空的。修改设置里面的值，可以看到空白变长变短。进到注册表里面，发现 ProjectMRUList 是空的。不知这个问题该怎么解决。第三，有很多功能在这个版本里面没有包含，如 Code Profiling 等，毕竟是 Professional 版。还是很期待 Team Suite 版，也不知什么时候才能得到。

另外，调试功能好像也有一点问题。经常下了断点，按下了 "Start Debugging" 按钮，也停在了断点处，居然 Debug 工具栏的所有按钮都是灰色的，但菜单里面的选项又可以用。而且，在这种情况下过不了多久就会弹出一个 "Stop Debugging" 窗口。停止重新运行后又恢复了正常。有些怀疑这个 RTM 版的真实身份。

总的来说，目前对 2005 没有失望，但也没什么值得兴奋的地方。

Glenn Gould 诞辰 73 周年

总觉得把“诞辰”这个词用在古尔德身上不太合适（一般感觉都是那些优秀而先进的共产党员们才配得上这个伟大而光荣的词的），但这是事实：古尔德已逝。至今，古尔德仍然是我最习惯的诠释巴赫的音乐家。

初识编译器设计

最近终于开始自己动手写编译器了。老师给了一个名为 SIMPLE 的语言，叫我们写一个词法分析和语法分析。我是用 C++ 写的，刚刚把语法分析做出来了，总的来说还是有点心得的。

词法方面更多的还是参照了《编译原理与实践 (Compiler Construction Principles and Practice, Kenneth C. Louden) 》的 TINY Compiler，原因主要还是因为对编译器不熟，现在有比较成熟的方法，先拿来再说。分析的方法还是先在纸上构造出相应的 DFA，然后用一个 switch 语句选择各种状态分别处理。实际编写的时候，还是发现了很多和 TINY 不同的地方，所以自己也在他的基础上进行了修改。

我们的 SIMPLE 语言比 TINY 要复杂很多（Simple > Tiny ?），所以语法分析方面，相应的函数也多了很多。语言是符合 LL(1) 文法的，所以用的还是递归下降分析法（后来发现，其实还是有一个表达式不符合 LL(1)，不过找到了解决办法）。因为有一个非终结符的两个候选式的 First 集合有交集，所以一时想不到该怎么去选择候选式。后来发现，可以用以下办法解决这个问题：将两个候选式 First 集合的交集抽出来，如果一个候选式可以推出另一个候选式（前者比后者大），那么在遇到交集里的终结符时，选择大的候选式。其他的非交集部分则选择各自候选式。举个例子：

abc → id | | id relation id | arith_exp relation arith_exp

arith_exp 是算术表达式，可以是 id + id，也可以是 id，还可以是 id + num，等等。可以看出，由于 arith_exp 和 id 的 First 集合具有交集 id，如果当前符号是 id，则不知道应该选择哪一个候选式。因为 arith_exp 可以推出 id，所以我把上式改成了

abc → arith_exp [relation arith_exp]

因为如果满足了 id，则一定满足 arith_exp，反之如果满足 arith_exp，不一定满足 id。事实上，上面的例子只是一个简化了的表达式，实际中还要考虑一些其他因素，不过总的思路就是这样了。当然，最好的方法还是仔细的设计标准的 LL(1) 文法，这也算是一点教训吧。

“海顿”和古尔德

今天坐飞机回到广州。一路上一直在听古尔德弹的那三首“海顿”奏鸣曲，也不知这是我第几次重听她们了。昨晚没睡好，飞机上一直昏昏沉沉的。伴着古尔德的琴声，我脑中迷迷糊糊的出现了一个场景：古尔德坐在那他那把矮矮的椅子上，随随便便地穿了一件衬衫，弓着腰伏在钢琴上用手指敲击着键盘，嘴巴还不停地随着哼唱着。这无疑是标准的古尔德弹钢琴的姿态，但是当那时耳朵里响起第三第二乐章的那个忧伤淡淡的 e 小调时，我突然感到一阵难以言喻的快乐。

一是贝多芬写这几首奏鸣曲时不过才 25 岁左右，那时的他和 52 岁的他比起来确实太年轻了，而那时的作品和“锤子键”等晚期作品比起来同样是太稚嫩了。但是简单就是美，我认为，“海顿”胜就胜在她的天真，她的纯洁，她的洛可可。

二是我似乎又找到我喜欢古尔德的新的原因。在刚才那一幕里面，任何一个不认识他的人肯定会觉得这人的举动十分可笑，但这正是因为古尔德全身心地投入到钢琴中，完全忘记了外在的这个世界。其实，我觉得很少有人比古尔德更爱钢琴，更爱音乐。我们知道，平时晚上一时兴起，就要通过电话和朋友聊上几小时的音乐。古尔德一生未婚，对于他来说，可能钢琴的地位已经取代了那个可能的妻子。他对待钢琴演奏就像母亲对待婴儿一般疼爱。另一方面，古尔德是一个很孩子气的人，天真，淘气，任性，纯洁，这些特点我觉得他都有。对待他喜欢的曲子，比如这三首“海顿”奏鸣曲，他常常会弹得很慢，慢慢得享受，慢慢得陶醉，就像孩子们总喜欢在沙滩上多呆一会儿。而对待他不喜欢但又不得不演奏的曲子，他就像孩子一样任性，以最快的速度敷衍过去，就像我小时候对待不喜欢吃但大人们逼着吃的菜。我喜欢的就是古尔德那孩子般纯洁的对音乐的爱。

变长文件管理器

这段时间做了一个变长文件管理器（类似 WinRAR，可以把多个文件装进一个文件）。原本是学校的作业，但是我也算是认真对待了的。做的过程中遇到了很多比较抽象的问题，解决过程中也确实领悟到不少有用的编程思想，看来计算机科学这玩意儿还是要多动手写才会有提高，光看书还是不够的。（程序源码和客户端放在后面，有兴趣可以去下载）

记录文件的格式类似于FAT文件系统，采用簇作为存储单位，这样比较方便对文件进行操作。虽然这次程序引入了读取参数配置，压缩文件这些原来没有涉及过的方面，但是最终还是就一个 exe。原本觉得应该把管理器的类库做成一个 DLL，供客户端来调用，但是尝试后还是发现要把所有类库用的 .h 文件倒入到客户端那边去，而我又习惯在 .h 写类的实现，所以太麻烦，只好作罢。看来以后还是要改一改编写习惯。

这次写的过程中遇到一个问题，至今也没有想到解决办法。我本想做一个类似数据库的结构，用 Struct 模拟表中的字段，Struct 的成员变量类型相当于字段类型。用链表模拟整个表，链表传入的模版就是之间声明的 Struct，这样一个链表就可以存储任意多个具有相同成员类型的数据了，在这一点上还是很像数据库的。问题是，一个数据库可以容纳任意多的表，并且每个表的结构可以不同，这一点如何用模版实现呢？最开始想到的还是用一个链表来模拟数据库，用链表来保存链表。但是这是不行的，因为模拟表的链表本身就是模版了，都具有不同的模版类型，而链表只能存储相同类型的数据。想来想去，只能用类似 .NET 中 ArrayList 的方法，把模拟表的链表转化成类似 Object 的基类，使其具有相同类型。

那么如何在 C++ 里面模拟“所有类型具有共同基类”呢？我想到的是自己写一个 Object 类：

class MyObject
{
void* dataPtr;
int size;
}

dataPtr 保存数据所在的内存地址，size 保存数据大小。装箱时，要同时传入数据本身和数据所占字节数。然后 Object 到内存中分配一个 size 大小的空间，保存数据，并记录内存地址；拆箱时，将 void* 转化成需要的类型的指针，返回值即可。

理论上要实现还是不难，但实际中这种转换很难办到。首先，C++ 对运行时动态类型转换支持并不好。比如，假设有 MyObject a = 1 ，如何实现 int b = a 呢？MyObject 怎么知道要把 void* 转换成 int* 呢？难道 int b = a.Convert(int) ，或者 int b = a.Convert("int") ？这些都不可能，C++ 不支持传入一个类型，更不可能根据字符串转换数据类型（C++ 之提供了一个动态获得类型的方法 type_id）。其次，C++ 中各种数据类型多种多样，很难只用一个 void* 一概而论。比如，要实现字符串 char* 怎么办？要实现 STL List 怎么办？

当然，要解决这些问题也不是绝对没有办法。如果 C++ 的标准就由我来制定，C++ 的所有代码就由我来写，那我完全可以自己写这个 Object，自己实现 Object 对所有类型的转换。可能有人会说，这根本不是一个办法的办法。其实，.NET 就做到了这一点，Java 就做到了这一点，我想关键还在于它们都是由一个公司开发出来的，语言的耦合度自然就比 C++ 大。耦合度大，语言确实失去了一定的自由度，但也确实更加方便。也是到现在，我才真正体会到 C# 原来是那么方便强大的一个语言。

现在再回想起初中时刚开始接触编程的那个时候，在看看现在的自己，发现自己确实在成长，曾经觉得要不可及的那些 C 语言代码，现在只是当作工具来用了。说来现在感觉自己又进入了一个新的高度，不再是原来的桌面应用程序，不再是 Flash 和 ASP，而是编译器，操作系统，文件系统，更多原理级的东西，更接近数学。当然，这也只是一个新的开始，在这条路上还有很长要去走，还有很多高度要去翻越。

变长文件管理器 RecordManager

假期结束

整个八月没有来写新的日志，总觉得有一些想记的东西，但又总是不知道从何下笔。

暑期的的生活还是那么有规律，我还是一个不喜欢外出的人。这个暑假其实也没干什么事，前半段用来上 TOEFL 了，后半段主要在做学校的数据结构作业。怎么说呢，其实这个假期觉得自己还是有一些新的认识，有一些改变，但是要具体说是什么又说不清了，总之，自己清楚。

请几天，在加拿大读书的表哥回来了，到我家来了 2 天。出去快 3 年了，感觉他还是老样子，应该有的性格和习惯都还在，不该有的东西还是没有。原本想在加拿大读书，接触的大多都是外国人，在兴趣爱好上和语言习惯上应该都会和以前不同了吧，结果他还是很流利、“很地道”的成都话，喜欢的除了上网聊天就是聚会结交。这些没什么不好，如果他不是这样我反而会认不出他了呢。但是从这里我发现，出国并不能从根本上改变一个人。

上次和 Alex 谈到这个问题的时候就觉得，其实现在很多人出国仅仅是赶时髦，随大流，绝大多数人对出国的目的并不明确，甚至抱有幻想。很多人认为出国留学就是为了移民，就认为出了国，成了老美，那我这一辈子，我的子子孙孙以后就可以享尽荣华富贵，就好像在国外就有金子等着中国人去捡，这一点我在新东方上课的时候就很有感受。是的，不可否认在国外，很多环境因素比国内要好，医疗，福利，人口，公共设施，等等。但是对于一个中国人来说，能不能融入别人的国家才是最重要的，文化差异，这不是一两天就可以消除的。其次，为什么会想国外就有金子等着中国人去捡呢？难道说我在国内都没有能力、找不到好工作，在国外还能去把别人踢开自己当老板？人在任何社会里受到的待遇都是公平的，就像在美国赚美元一样，赚的是美元，花的也是美元啊。我觉得，出国留学为的就是学习到更新更丰富的专业知识，是否留在国外，那得看当时情况。如果仅仅为出国而出国，那我是绝不愿意做的。

对了，前天得到一个 Gmail 帐号 crendking@gmail.com，不过还是不打算用，比较现在都两个邮箱了，够用了。最近 Google 炒的好像比较热，很多言论预测 Google 要取代 Microsoft 成为新一代的业界霸主。我倒不偏向哪一方，其实我对两家都比较喜欢的，只是我觉得 Microsoft 能走到今天这步绝对不是吹的，要扳倒它绝不是一天两天的事。愿两家各自走好吧。

明天就要回广州了，下一年的学习生活可能会非常紧张，总算现在已经是养足了精神。

求大数的阶乘

昨天看到博客园的一篇文章《10000的阶乘的算法(大数的阶乘)》，自己也想了一下，写了一个 C# 版的。程序也比原文的要简单。

原文中，数组大小 M = log10^1+log10^2+log10^3...+log10^n，好像不对。我觉得应该是 M = log10(1) + log10(2) + ... + log10(n)，log10(1) 表示以10为底数、1为真数的对数。可能我们表达的是一个意思，只是写法不同而已（不过我还是觉得10^3 = 1000，log10^3 = 3，这样明显不对嘛）。

程序：

using System;

namespace Factorial
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
int n, M, carry = 0, t1;
double t2 = 0;
bool display = false;
int[] result;

Console.Write("Input the number you want to factorial: ");
n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("");

for (int i = 1; i <= n; i++)
t2 += Math.Log(i, 10);
M = (int)Math.Ceiling(t2);

result = new int[M];
result[0] = 1;

for (int i = 1; i <= n; i++)
for (int j = 0; j < M; j++)
{
t1 = result[j] * i + carry;
result[j] = t1 % 10;
carry = (t1 - result[j]) / 10;
}

Console.WriteLine("The result is: ");
for (int i = M - 1; i >= 0; i--)
{
if (result[i] != 0 && !display)
display = true;
if (display)
Console.Write(result[i]);
}

Console.ReadLine();
}
}
}

用 Windows XP 自带的计算器验算了一下，1000! 应该是没问题的，但算 10000! 确实算不出来，要等很久。原文的那个程序也是要等很久，而 Windows 自带计算器只等了 1 秒钟左右。我想，要不然是 Calc 省略了后面的位数，要不然是 Calc 有更好的算法。

小程序，轻松一下。:-)

平淡的日子

最近广州还是很热，天一热，人也就懒了，每天的日子也过得很有规律，无非就是写写程序，看看书，订订外卖，睡睡觉。要说因此得到了什么，那只能说，知道了什么样的生活叫做无所事事，叫做没有动力。:(

明天托福班就开课了，总算是一个改变的契机吧，至少能给自己一个出门的理由。人是很容易被麻痹的，除非自己不断提醒自己，要改变，要像自己希望的方向改变。

网络游戏的一点开发经验

以前从没接触过网络游戏方面的编写。前段时间因为课程原因，和班里同学组队写了一个网络游戏，虽然功能上比较简陋，但是麻雀虽小，五脏俱全，网络游戏应该有的几个基本元素都有了，也算是在网络编程上的一次新的尝试了吧。

游戏是用 Java 写的，原因是，我们学那本教材的示例是用 Java 写的。从产生最初的设想，到最后的完成总共是一个半月左右。因为是组队编写，所以在分工合作上就必须十分注意，而且一个月内要完成一个具有界面、网络通讯、游戏逻辑等等内容的软件对于一个没有经验的人来说工作量太大了些。

我们采用的方法是分工-整合，即先通过分析把软件分割成几个技术块，分给组员去研究，等他们把自己那块研究得很透彻了以后，就把自己在那一块的经验、需要注意的地方、一个自己写的典型的示例交给一个整合者。整合者需要较高的程序开发能力，至少要对各个技术块都要有一点了解，并且能够很快从各研究者那里学到东西，然后把各个部分整合起来，完成整个软件。

实际当中，我们分割的技术块有以下几个：

1. 核心算法、逻辑（同时也是整合者）；

2. 界面设计；

3. AWT + Swing；

4. 网络通讯（组播 + 流式 Socket）

5. 安装和分发。

非常有幸的，我担任核心算法的那一块，从自己，也从别人那里学到了很多。

在编写过程中主要遇到了以下几个问题：

1. 各个客户端如何互相识别；

2. 非原子对象如何通过网络传输；

3. 组播的可靠性；

4. 逻辑部分的架构怎么设计，才能保证简洁、有效、少出错。

相应的每个问题的最后解决方案是：

1. 我们考虑了是否使用服务器作为中间人。一种情况就是各个客户端就通过组播传递一个只属于自己的 ID。但是因为组播机制的问题，我们（好像）不能仅仅经由组播组得知组里有多少成员，更不可能收到类似“有新的成员加入组”的消息。经过考虑，我们还是决定使用客户端-服务器模型，有服务器分发 ID，这样，服务器就能分担很多原本在客户端的开销了（特别是使用多线程以后）。

2. 很明显的，用序列化。为了这个，我和一个同学争论了一个晚上，他想用类似网页表单的形式，最后终于说服了他（有现成的技术干嘛不用）。

3. 通过最后的测试，我发现，组播的时序是一个很麻烦的问题，特别是在还有网络延迟的情况。在游戏中，3 个客户端在接收（并发送），1 个客户端在发送（并接收），我怎么保证客户端 A 他先收到客户端 B 接收后发送的消息，还是客户端 C 直接发送的消息？如何保证自己发送的消息自己能最快地接收到？实际情况中，几种可能性都是存在的，也都发生过。我没有找到什么很好的解决办法，只能是增加条件判断。

4. 架构，最难办的东西。就这么一个小游戏，要把它的规则用程序描述出来也是不容易的。更难的是在怎样有效、正确的传递结果，特别是在上面提到的不太可靠的环境下。为了赶时间，我没有花很多时间在设计架构上，还是采用了沿时间的线性编程。事实证明，这简直就是地狱，你将需要非常多的 if, else 放在各个关键点，很多时候为了解决一个匪夷所思的 Bug，又要添加 AND 或者 OR。到最后，逻辑部分变得很冗繁，很复杂，即使有 Bug 也很难找到。这也算是对我偷懒的惩罚吧。

其实对于架构，也想到一种方法，时间表。事前为每一个客户端制作一份时间表，时间表中记录了客户端每一步应该做的事情，这样每个客户端就不需要关心其他客户端发生的步骤，只需要将其他客户端发送的数据接收并正确显示即可。制作和使用时间表并不容易，但是对于复杂流程来说，这会是一个比较好的解决方案，从逻辑上来说，这就是把整个过程式的流程分割了并分发给每个客户端。每个客户端的对应时间表是在一份基本时间表加上以客户端的本地的独特数据（如 ID）作为基础的变化后生成的。我想在以后哪次写类似的软件时有可能会用到这种技术。

另外，以前都是用 C++，C# 的，第一次用 Java，感觉 .NET 确实是从 Java 中汲取了很多好的思想、细节，摒弃了很多麻烦、不实用的东西。两者在语法结构上都很相似，但感觉 C# 更像 C++ 一些。（而正是这许多些微的不同，形成了很多各式各样的争论。）个人来说并不觉得 Java 就比 .NET 差或者落后，只是比较不习惯。还是要看在什么领域里面应用，有些适合 J ，有些时候 N，没有一定的。不过，对于 Java 的图形界面设计，我是深恶痛绝。要想用 AWT 设计出像 .NET 一样整洁清新的“一般”窗体是多么困难的事啊！

还有很多感想，一下子也想不出。以后再说吧。