编译器实现有感
脚本虚拟机前段时间就已经做好，如果没有跑在上面的语言，光有虚拟机没太大意义。所以脚本编译器一早就开始做了。中间因为去上海参加 C++ 大会，又去了成都做招聘，弄的心力疲惫。这几天才回来，有那么几天去实现。
编译原理的课程大学本科就应该开过吧，我不是科班出身，反正是没正经上过。不过依稀记得自己是学过的，记得是上中学的时候，跑到一个大学上课，老师教的就是编译原理。那个时候 C 语言还没玩转，最熟的是 basic 和 6502 汇编。理解那些东西很有困难。囫囵吞枣的记了一点，算是有点印象，逢人也可以吹吹牛。
记得前段<a href="http://codingnow.com/mailman/listinfo/cpp">我们 C++ 的 maillist</a> 曾经有人说，不是说会写编译器的就很牛，做 UI 的就没水平。每个领域研究下去都有很多东西。俺深以为然也。记得会有人这么觉得，编译器这玩意应当不大好写吧。
这次我不想用什么 yacc/lex ，甚至不想按什么词法分析，语法分析什么的一遍遍扫描，一步步转换。心里无耻的认为，之所以人家要分那么多步骤，是因为年纪大了，脑子不好使，或者需要好多人一起合作，需要把事情硬拆分成独立的步骤，保持编程时的头脑清晰。偶还年轻，脑子里可以同时多装点东西。我自己大脑看代码的时候可不用多遍扫描，顺着读就能读懂，理论上一遍扫描就 OK 了。
据说当年 turbo pascal 的编译器的原作者就很牛，用汇编写的编译器，应该也是一遍扫描的，编译速度超快，几乎不占什么内存。当然了，一遍扫描，内存就只用保留最少的上下文环境，一但处理完就退回去了，对 CPU cache 的命中率也是极有好处的。把几个分析步骤混杂在一起做，更是可以减少重复运算的步骤。唯一的麻烦就是，对程序员是一个挑战。在编程这件事情上，我一向不惧啥挑战的。
一开始很莽撞，连 BNF 都没列，一点头绪都没有，只知道分析过程一定是递归向下的。人家汇编都写了，我这还是 C++ 呢，不是一个重量级的武器嘛。不过写起来，脑子真是一团糨糊啊。我的语言定义是类 C 的，虽然去掉了那些变态的三元操作符，和复杂的指针解析这种东西。左值右值的问题上还是非常复杂。毕竟还是保留了许多从右向左的运算。比如函数调用，就需要先算参数再算函数引用。而函数本身又可以返回函数引用，一次扫描的时候，最麻烦就是从左向右和从右向左的操作混合。因为有回退问题，有些符号在不同的环境下又有不同的意义，既然我想把几个分析步骤一起做了，自然不会产生太多中间数据增加重复运算。这带来很大的设计难度。
比 C 语言增加的是类 lua 的多返回值设计，这个在没有指针类型的时候，可以提高虚拟机的运行效率。否则返回多个值只能借助 table 了。临时 table 会有内存分配的开销，内存分配有可能引起 gc，导致虚拟机在处理完毕后要多一些检查做代码重定位，效率上会打折扣。而我的目的是让我的脚本效率高于 lua，自然这个特性一定要支持了。
可是多返回值的设定引起了函数调用的返回行为根据上下文的不同，lua 里定义了尾调用，只有当函数调用发生在尾部时，才按真实返回值返回。否则强制切成一个返回值。我照搬了这个设定。不过在实现时折磨了我几个晚上。
这周开始写的时候，距离上次 coding 已经过去了两周，导致以前写的大部分代码不可继续。我觉得这种对于我来说高难度的算法，对编写者我自己来说需要一个思维连续的过程，思路一旦出了脑子里的 cache 就很难找回来了。写注释的帮助不大，顶多在代码中留下许多 todo 提醒自己别漏掉什么。连续奋战了几天后，昨天夜里终于小有成绩了。
回过头来看，核心的编译部分，几乎被翻新了3遍。整个过程基本重复这样一个过程，先用很丑陋的代码把有限的功能搭起来。这些代码是非常 buggy 的，只能完成特定的分析，很容易出错，和大量未完成的特性。然后给自己一个大体的思路后，开始重构。每次都选一种比较简单的情况，换一个方法重新编写，确定比上一版好了以后再逐步取消前一版本的功能。函数并不是逐个改写的。因为设计本身是在变化的。原来几个函数交叉做的事情，改了之后可能合并到另几个函数中。最后发现代码逐渐被全部翻新了。非常可喜的是，总的代码量缩减到最多时的 70%，但是完成的特性却增加了不少。慢慢的程序就清晰了，
在那一刻，有一种豁然开朗的感觉。脑子里翁翁的声音没了，心情非常的愉快。很久没有体验这种味道。或许是自己控制代码的技术提高了许多，长期没有遇到这么复杂的程序了。
下面的工作很简单，好象刚刚把表达式解析做了，上百行代码一气喝成，几乎没有出错，立刻可以解析非常复杂的表达式。再此之前，编译器只能分析只带有 table 操作的式子。这两天打算把各种语句控制块加上，感觉一下就能做了。心里已经在想给语言加各种新特性了，锦上添花的事情本就没啥难度，只是看想不想的到的事情了。
能有自己的代码实现想要的东西真好。
ps. 到最后我都没有把 BNF 列出来 (._.!)
Comments
Posted by: Jaeson | (27) December 19, 2023 07:00 PM
Posted by: 8B110 | (26) February 23, 2022 06:43 PM
Posted by: Anonymous | (25) January 18, 2015 12:26 AM
Posted by: maval | (24) August 26, 2013 08:12 AM
Posted by: 蜻蜓 | (23) January 2, 2013 01:09 PM
Posted by: jelo | (22) October 30, 2012 12:19 AM
Posted by: yy | (21) March 13, 2012 02:32 PM
Posted by: davelv | (20) September 24, 2009 09:01 AM
Posted by: 哥俩好 | (19) April 23, 2009 10:01 AM
Posted by: happy | (18) August 9, 2008 04:13 PM
Posted by: longtrue | (17) May 16, 2007 11:34 PM
Posted by: 1 | (16) May 15, 2007 11:41 PM
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (15)
May 15, 2007 08:22 PM
Posted by: 1 | (14) May 15, 2007 07:00 PM
Posted by: 1 | (13) May 15, 2007 06:47 PM
Posted by: AAA | (12) April 29, 2006 02:45 PM
Posted by: AAA | (11) April 24, 2006 03:57 PM
Posted by: 温少 | (10) December 16, 2005 09:56 PM
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (9)
December 16, 2005 12:11 PM
Posted by: 温少 | (8) December 16, 2005 02:16 AM
Posted by: Janhail | (7) December 5, 2005 09:28 AM
Posted by: Atry | (6) December 4, 2005 03:21 PM
Posted by: Janhail | (5) December 3, 2005 05:39 PM
Posted by: RockCarry | (4) December 3, 2005 09:03 AM
Posted by: atxm | (3) December 2, 2005 06:07 PM
Posted by: dawndu | (2) December 1, 2005 05:58 PM
Posted by: error | (1) December 1, 2005 05:37 PM