什么语言最适合写编译器/解释器?

Lisp? C? Python?
关注者
299
被浏览
38949
即便题主说“写解释器/编译器”,其实解释器与编译器各自都可以从简单到复杂、在各种不同的场景下有不同的最合适的实现。就这么泛泛地问很难引出泛用的好答案…

以解释器为例,要尽量跨平台而且性能还过得去,同时还不要依赖太多外部的东西的话,那么C通常是不二之选,因为在各种平台上通常都能找到(至少基本上)符合规范的C编译器和运行时库,只要按照规范来写C的话在各种平台上都能编译运行。经典案例是C写的Lua。
然而如果要把解释器写得短小精悍,极可能榨干解释执行的性能的话,那么在每个平台上用汇编写就是最好的选择。这样可以最大程度利用平台上的寄存器(例如说可以用CPU的栈指针寄存器来表示解释器的栈顶指针,这样就可以把解释器栈混合到native栈上,有可能减少一层间接访问,提高性能);同时还便于精确地安排代码布局,把常用逻辑对齐、集中在一起,而把不那么常用的逻辑或者复杂的逻辑安排在别的地方。直接写汇编也行,或者自己用自己想选用的语言(例如C++)实现一个汇编器库然后使用这个库来生成机器码也行,但最核心的概念是“手写汇编”。

编译器的话,其实编译器中有好些不同的方面,分别有些不同的需求以及对应的用起来顺手的语言。
例如说词法分析常常可以用正则表达式来表达,语法分析常常可以用某种context-free grammar(CFG)或parsing expression grammar(PEG)的DSL来表达,然后tree pattern也可以写DSL来表达。指令选择如果选用BURS(bottom-up rewrite system)系的做法,那也常常会有自己的DSL。

要说核心需求,编译器其实常常要做三种事情:
  • 模式匹配(pattern matching),
  • 代码形式的转换(transformation),
  • 然后还有根据一些给定条件来求解(可以是constraint solving)。
前两者用有algebraic data types(ADT)的语言的话会比较方便,因为这些语言常常会对ADT有配套的模式匹配语言结构,在遍历和转换编译器的内部数据结构时会非常方便。
最后那点的话,有时候会有人用Datalog来做…也是种很方便的做法。

还有一些有趣的话题。例如说有些写编译器的人会比较喜欢用有自动内存管理(可以是GC,不过不一定…)的语言来写。因为编译的主流程本来就要很多麻烦事,如果要迁就手动内存管理来写的话,要么代码会有点难看,要么要自己投入一些开发成本去写一套适合自己使用场景的基类/分配器啊啥的来处理。
结果有些编译器就干脆把自己的临时数据全用一个arena分配器来分配,换句话说说只管分配不管释放,等到一个编译任务结束的时候再一口气整个arena一起扔掉。这放在静态编译器场景里可能还OK(但规模一大也常常不OK…),放在动态编译器里的话就可能不合适。

最后…要是非要挑一种语言来写整个编译器的话,我现在可能会选Rust吧(站队
OCaml / F#我也很喜欢的。
但最终能用啥,咱也未必有控制权。现在工作写的编译器就是用C++实现的,没得选啊。