引导编译器所需的语言功能的最小子集是什么？ [已关闭]

Question

一种语言（受 C 启发）作为一种可用于为整个语言编写编译器的子语言，绝对必要的核心特性是什么？

Answer 1

您需要一个

while

循环、

if

、一个 true 整型变量，以及一种读写文件的方法。就是这样。 （实际上，文件读写部分是很好的，但不是绝对必要的——你只需要它来将信息输入和输出程序。如果你可以读写文件，那么你就不需要不再需要整数变量，因为您可以使用该文件作为临时存储。）

while

、

if

和一个整数变量是图灵完备的，即它可以计算任何图灵可计算的函数。编译器是图灵可计算的函数。无法接受任何输入或产生任何输出的编译器非常无聊，因此您需要有一种方法来读取一些输入并写入一些输出。

Answer 2

您可以定义由 20 行奇数行组成的可引导元编译器来执行此操作。 MetaII 编译器 是一个特别好的例子 ，来自 1963 年。 我在 1970 年代就以 MetaII 作为基础引导了更大的编译器。

这些元编译器需要能够解析元编译器描述（尤其是它们自己的描述，因此可以进行引导），该描述定义了 EBNF 语法（测试输入字符串、扫描下一个标记等）和一组生成器操作（输出文字）字符串，输出最后扫描的令牌，输出生成的标签）。您几乎可以用任何语言实现一个库，以任何过程语言通常只需几百行即可实现对此的支持。

这是 MetaII 的自我描述，直接摘自原始论文： 。
是的，这就是整个该死的事情。 （为真正积极主动的读者进行练习：您可以简化最小的支持指令集和此描述）。

这里有一个关于如何在 JavaScript 中构建/理解这个 gem 的精彩教程：MetaII 教程。

20 世纪 80 年代圣克鲁斯分校的研究生道格·米歇尔斯 (Doug Michels) 将这一点发挥到了极致。如果将语言标记编码为单个字符，则可以定义一个以 80 个字符进行自我描述的可引导元编译器。如果你想查看详细信息，你必须从圣克鲁斯拿到论文。

Answer 3

有两种方法可以解释您的问题：作为理论计算机科学问题；并且，作为一个实际的工程问题。

已经有一个倾向于理论答案的答案。所以，我会更加注重实际。

我认为您需要整数、指针、变量、if 语句、循环语句和函数。正如另一篇文章指出的那样，您需要某种方式从文件中读取以编译源代码并写入文件以保存生成的程序集或目标代码。

我建议你研究一下 Small C 编译器。它是 C 子集的编译器，能够自行编译。如果您查看 Small C 的 Wikipedia 页面，您会看到已经出版了一些有关编译器的书籍。虽然这些书已经绝版，但您也许可以找到一本可用的二手书。