什么是可以编译自身的*概念*最小*编译器*？

本着这个问题的精神,我想问一个类似的问题,但是关于编译器,而不是解释器.

什么是可以编译自己的代码的概念上最小的编译器？

当我说"概念上最小"时,我的意思是它只使用非常基本的概念并从那里构建,而不是它包含非常短的代码.为什么这是一个重要的区别的一个例子是OTCC是一个非常小的C编译器,它很小,因为它被混淆,不一定是因为它在概念上很简单(它也可能在概念上很简单,但我不知道;它被混淆了).

我还想补充一点,以下也可能是一个非常概念上的小程序,但实际上并没有告诉我们发生了什么,所以它并不是我正在寻找的:

(writefile argv[2] (generate (parse (readfile argv[1]))))

我真正想要的是一种语言:

图灵完成.

能够编译自己.

我对此感兴趣因为

这将是一个有趣的案例研究和

它可以作为引导编译器的起点.

如果它不存在,我可能只是自己写.:)

我不是很清楚"概念上最小的"是什么意思.大概你对Lambda演算中的最小图灵机或表示不感兴趣？如果你在谈论物理编译器实现,那么你真的在谈论生成机器代码指令的编译器.正如Anthony Mills的评论所提到的,TCC是相关的.应该具有实际应用的另一个有趣的讨论是从头开始编写的自举编译器的详细描述.

有一段时间在comp.compilers新闻组上有一个有趣的讨论值得一试.

您没有说目标机器是什么,或者编译器是否必须存在或只是想象.

在想象的世界里,我会说约翰麦卡锡的元叶LISP翻译的改编将非常接近.您可能还想看看John Reynold的论文" 高阶语言的定义解释器",虽然密集是一种简单的模型.

在现实世界中,我打赌Chez Scheme,但遗憾的是本机代码编译器是专有的封闭源代码.不过,你可以从学习翻译中学习.另一个值得研究的系统是Oberon编译器,它被设计为由一个人构建和理解,并且非常干净.

[我知道这是一个非常晚的条目,但我认为这是非常相关的].

我所知道的最小的自编译器是Val Schorre的1963 MetaII编译器.是的,从十九六三.(该页面上有关于该主题的技术论文的链接).如果您喜欢编译器,请运行以获取此文件; 它是一种气体,只有10页.

这不是理论; 这很实用.他的论文提供了编译器源代码(大约20-30行IIRC),元编译机器的描述,以及一个元编译程序处理源代码并重新生成完全相同的元编译程序.你可以在1-2天内自己复制这个结果非常有趣,如果不介意实现metamachine的令人难以置信的代码.[我在1970年通过这样做学会了从本文构建编译器].或者,您可以使用MetaII上的现代教程,它使用JavaScript预先构建它.

一旦运行了这个元编译器,就可以轻松地扩展语法和元机器,以引导到具有更多功能的大型元编译器,和/或为实际应用程序生成编译器.(我在70年代早期以这种方式构建了一个类似于BASIC编译器的Pascal).

你可以采取另一种方式:你可以开始解决问题,看看你可以删除多少,仍然能够提升到MetaII级别.我这样做了一次,并设法摆脱了大约30%而没有失去能力甚至很多表现力; 它下降到大约20行文本,显然是一个更简单的元机器.

一位名叫道格·米歇尔斯的聪明人,很久以前与20世纪80年代(Unix供应商)Santa Cruz Operation联系,告诉我他已经走得更远,并将元编译器的自我描述减少到极少数字符.我从未见过这项工作,所以我不知道他到底有多远.

[编辑]挖掘,挖掘,挖掘......发现这个宝石(在Linkedin上):

达特茅斯兼职教授Bill McKeeman说:

道格是我的本科生; 他的高级论文作业很简单:编写最短,可扩展,自编译的编译器.前端需要27个字符 ; 整个事情花了63.这一切都适合一张IBM卡.他公布了结果.

挖掘,挖掘,挖掘更多:这似乎是道格的27个特征论文.参见图2.通过"前端",McKeeman显然意味着"只是解析器"; 该论文包含更大的完整翻译.

你不能让编译器这个小,除非他们是 "在概念上简单的".