« 游戏的优化——不仅仅是帧速率 | 返回首页 | C++ exception 的问题 »

编译器实现有感

脚本虚拟机前段时间就已经做好,如果没有跑在上面的语言,光有虚拟机没太大意义。所以脚本编译器一早就开始做了。中间因为去上海参加 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

哈哈,我们好像啊,不过我将来会比你更牛

正在看编译原理方面的书籍,也想实践一个C语言的编译器.可奈何数学基础太差,感觉书上的理论太抽象了.遂打算从手写开始...

偶也写了一下类似编译器的东西,用的是高级语言,不过是用来解释规则的,有时间思考写组有意思的规则完成一个人类好用的语言。

你这叫哪门子编译器啊?还差着十万八千里呢!年轻人不要情绪化!

可能楼主能牛吧,但这样的编译器我不敢用

毕业设计自选了C编译器实现。不过整个学校居然连一个搞编译的导师都没有。。。不得不说,高中时候没努力,出来混,迟早要还的。。

嗯,编译原理的书分成几遍扫描是有原因的,更主要的是为了教学的需要,把一个复杂的问题分成几个简单的问题,逐一解决。当然你也可以不那么做,但是前提是要了解基本的原理,要不然,代码写的越多错的越多,翻来翻去,推倒又推倒一大段时间过去了,还没有可用的东西出来,和你差不多水平的人对你的辛苦付出倒是可以理解,要是碰到一个不懂技术的上司,可能会以为你工作没效率。嗯,编译器是可以把遍数减少的,比如取消前端宏展开,捂端代码优化。事实上商业版本中间几个遍也可是合成一个的。这好比七层网络协议栈,那只是教学的需要,真正在用的往往是去繁就简,就没有那么多层给你看到。

楼主不要不懂装懂!

看到头都晕了,真是佩服,我何时才能有这样的水平啊.

用语言实现自己是不难

但是这个语言的效率就难了


实现语言的人不是人人都能做到把效率提上去

当然了借鉴剽窃一些技术走别人的路自然难度就小些

让语言可以自己实现自己不是什么难事,只要是图灵完备的语言都具备这个能力。

你要注意你的到底是语言还是api

私人认为如果不能自己写自己的不能算是通用语言,嵌入式语言很大程度上说其实就是某个语言写的api而已,那和写编译器其实是2回事。

用汇编写编译器其实是个愚蠢的事并不是什么技术高超或者大牛的显现。

编译器用词法分析变成中间语言,这些中间语言的特点是没有副作用。特定的语言没有控制流。设计这些中间语言本身就是一种思想和见地。

人的大脑做机械的事你是永远比不过计算机的,这才是那些人的聪明之处。你思维还没到那个境地

为什么每个新语言都要用自己实现自己。这才隐含了重要的东西

很多人实现的其实是一个api,其实并不是语言。你这个api语言一旦定性再扩充就不兼容了或者性能也达到了顶点

用高级语言写之后可以转换成某种特定的内部语言,这种内部语言有某种特性可以自动全局分析而且无损,这才是关键

用汇编语言,可以说这个编译器出来的代码肯定性能很差。汇编在宏观尺度上没办法考语言避免副作用

1

如果只实现一个嵌在静态资源页面中的脚本功能,不支持函数调用,需要实现哪些东西?

不是吧,没有BNF,你怎么知道自己实现了什么?

回云风:

你所说的运算符先后顺序,是否指的是,运算符号的优先级处理。

例如:
a+b*c,parse的结果为:(a+b)*c或者a+(b*c)?

(似乎这样讨论下去,会变成版聊)

下面那个大哥,我看见你在我的流言本上的牢骚了。从时间看,你在这里发完评论马上就去留言了,不知道怎么得出评论几天都不放行的结论的。
如果你不想每次发评论都接受审核,可以申请一个帐号。在留言的地方就有申请的连接。

ps. 处理表达式优先级其实是个很简单的工作。我是别的都写好了以后,用了不到一个小时加上的。
私以为,最复杂的是处理运算次序,是从右往左还是从左往右。以及区分左值和右值。

偶也写过一个脚本语言,跟Java Script差不多,把自己喜欢的语言特性都加入进去,例如Lambda表达式的支持,var list = [1, 2, 3, 4]之类的功能。

我最初也是自己实现了一个Parser之后才学习相关的理论知识的。至今,我还是喜欢使用手写的递归下降算法,虽然也会用antlr、javacc。

手工写parser,比较麻烦的是表达式的解释,其中的表达式优先级问题,最开始玩的时候,可能理不清头绪。

我会思考这个改变对未来可能的影响,如果可以有更好的扩展性和可读性,以及让代码和结构更加简单的话,我一定会重写。特别是结构简单,我认为更简单的结构可以有更稳定而且更高效率的程序。

如果你写程序的时候已经有了一部分代码,这时候你发现有更优雅的实现方式,但是要推翻很多已有的代码。得到的好处是实现更灵活,用起来更好用,减少了部分重复代码,而实现的功能区别不大,效率甚至可能比原来丑陋的实现还要低一点,这时候你会选择重构吗?

个人认为,编译原理里面分析出来的那些词法分析、语法分析、语法树等概念还是非常有用的。决定不是因为他们老了脑子不好使才想出来的方法。我想莽撞的写代码是一定会碰到问题的。而且用lex&yacc分析的方法也只需要扫描一次。有的编译器需要扫描多次是因为有不同的功能,比如C语言的宏展开。我就是用lex&yacc作的,刚开始写C语言格式的表达式和函数调用的时候只需要分析一次,而且很快。在自己写的虚拟机上执行也很完美。不过我在写class的时候发现一次分析已经不够用了,我现在的编译器就进行了三次分析。至于实现语言,我是选择用C,不过,用什么语言并不是关键,C和C++一样可以实现很复杂的功能。

我在半年前也实现过一个编译器,当时正好是学编译原理课程。
我实现的是一个自己扩展过的PL/0语言的编译器,语言的文法很简单,而且是使用Lex&Yacc制作的,和你这个比起来就没有技术含量了。
当然,当时我也不知道如何去编译成可执行的代码,因为不了解EXE文件结构,还有就是Intelx86指令集,所以也就只将程序编译成为自己定义的一种中间代码,所以后来自己也就搞了一个虚拟机来解释执行,这个跟你的方法差不多。不过我解决的问题的规模小得多,在虚拟机中,也没有实现类似Java/.net的自动垃圾回收机制(gc),毕竟一个PL/0语言用不上这个。
编译原理以及编译器构造技术,的确是高深而又有趣的。

RockCarry

佩服啊!
真想"瞻仰"一下...

真乃实践狂人也!其实编译原理就是很多人做编译器的经验之谈,先写BNF思路会清晰很多。羡慕你上中学就可以听这些课,编译前端我觉得也没有什么,就是后端的代码优化,符号表算法和定义优秀的虚拟机比较棘手!
估计你连抽象语法树都没生成,全部递归下降,对代码控制的能力算是很强了。PS:其实用c写也挺好,c也能写出重用性很好的程序,效率也很高,不在乎语言在乎用语言的人

哈哈,这样写会教会初学者地:)

Post a comment

非这个主题相关的留言请到:留言本