第一个C语言编译器是怎样编写的？

2015-12-01 10:00:28 | 来源：玩转帮会 | 投稿：佚名 | 编辑：小柯

原标题：第一个C语言编译器是怎样编写的？

首先向C语言之父 Dennis Ritchie 致敬！

当今几乎所有的实用的编译器/解释器（以下统称编译器）都是用C语言编写的，有一些语言比如 Clojure, Jython 等是基于 JVM 或者说是用 Java 实现的，IronPython 等是基于 .NET 实现的，但是 Java 和 C# 等本身也要依靠C/C++来实现，等于是间接调用了C。所以衡量某种高级语言的可移植性其实就是在讨论 ANSI/ISO C 的移植性。

C 语言是很低级的语言，很多方面都近似于汇编语言，在《Intel 32 位汇编语言程序设计》一书中，甚至介绍了手工把简单的C语言翻译成汇编的方法。对于编译器这种系统软件，用C语言来编写是很自然不过的，即使是像 Python 这样的高级语言依然在底层依赖于C语言（举 Python 的例子是因为 Intel 的黑客正在尝试让 Python 不需要操作系统就能运行——实际上是免去了 BIOS 上的一次性C代码）。现在的学生，学过编译原理后，只要有点编程能力的都可以实现一个功能简单的类C语言编译器。

可是问题来了，不知道你有没有想过，大家都用C语言或基于C语言的语言来写编译器，那么世界上第一个C语言编译器又是怎么编写的呢？这不是一个“鸡和蛋”的问题……

还是让我们回顾一下C语言历史：1970 年 Tomphson 和 Ritchie 在 BCPL（一种解释型语言）的基础上开发了B语言，1973 年又在B语言的基础上成功开发出了现在的C语言。在C语言被用作系统编程语言之前，Tomphson 也用过B语言编写过操作系统。可见在C语言实现以前，B语言已经可以投入实用了。因此第一个C语言编译器的原型完全可能是用B语言或者混合B语言与 PDP 汇编语言编写的。我们现在都知道，B语言的执行效率比较低，但是如果全部用汇编语言来编写，不仅开发周期长、维护难度大，更可怕的是失去了高级程序设计语言必需的移植性。所以早期的C语言编译器就采取了一个取巧的办法：先用汇编语言编写一个C语言的一个子集的编译器，再通过这个子集去递推完成完整的C语言编译器。详细的过程如下：

先创造一个只有C语言最基本功能的子集，记作 C0 语言，C0 语言已经足够简单了，可以直接用汇编语言编写出 C0 的编译器。依靠 C0 已有的功能，设计比 C0 复杂，但仍然不完整的C语言的又一个子集 C1 语言，其中 C0 属于 C1，C1 属于C，用 C0 开发出 C1 语言的编译器。在 C1 的基础上设计C语言的又一个子集 C2 语言，C2 语言比 C1 复杂，但是仍然不是完整的C语言，开发出 C2 语言的编译器……如此直到 CN，CN 已经足够强大了，这时候就足够开发出完整的C语言编译器的实现了。至于这里的N是多少，这取决于你的目标语言（这里是C语言）的复杂程度和程序员的编程能力——简单地说，如果到了某个子集阶段，可以很方便地利用现有功能实现C语言时，那么你就找到N了。下面的图说明了这个抽象过程：

那么这种大胆的子集简化的方法，是怎么实现的，又有什么理论依据呢？先介绍一个概念，“自编译”Self-Compile，也就是对于某些具有明显自举性质的强类型（所谓强类型就是程序中的每个变量必须声明类型后才能使用，比如C语言，相反有些脚本语言则根本没有类型这一说法）编程语言，可以借助它们的一个有限小子集，通过有限次数的递推来实现对它们自身的表述，这样的语言有 C、Pascal、Ada 等等，至于为什么可以自编译，可以参见清华大学出版社的《编译原理》，书中实现了一个 Pascal 的子集的编译器。总之，已经有计算机科学家证明了，C语言理论上是可以通过上面说的 CVM 的方法实现完整的编译器的，那么实际上是怎样做到简化的呢？这张图是不是有点熟悉？对了就是在讲虚拟机的时候见到过，不过这里是 CVM（C Language virtual Machine），每种语言都是在每个虚拟层上可以独立实现编译的，并且除了C语言外，每一层的输出都将作为下一层的输入（最后一层的输出就是应用程序了），这和滚雪球是一个道理。用手（汇编语言）把一小把雪结合在一起，一点点地滚下去就形成了一个大雪球，这大概就是所谓的 0 生1，1 生C，C生万物吧？

下面是 C99 的关键字：

仔细看看，其实其中有很多关键字是为了帮助编译器进行优化的，还有一些是用来限定变量、函数的作用域、链接性或者生存周期（函数没有）的，这些在编译器实现的早期根本不必加上，于是可以去掉 auto, restrict, extern, Volatile, const, sizeof, static, inline, register, typedef，这样就形成了C的子集，C3 语言，C3 语言的关键字如下：

再想一想，发现 C3 中其实有很多类型和类型修饰符是没有必要一次性都加上去的，比如三种整型，只要实现 int 就行了，因此进一步去掉这些关键词，它们是：unsigned, float, short, char (char 是 int)， signed, _Bool, _Complex， _Imaginary， long，这样就形成了我们的 C2 语言，C2 语言关键字如下：

继续思考，即使是只有 18 个关键字的 C2 语言，依然有很多高级的地方，比如基于基本数据类型的复合数据结构，另外我们的关键字表中是没有写运算符的，在C语言中的复合赋值运算符->、运算符的++、– 等过于灵活的表达方式此时也可以完全删除掉，因此可以去掉的关键字有：enum, struct, union，这样我们可以得到 C1 语言的关键字：

接近完美了，不过最后一步手笔自然要大一点。这个时候数组和指针也要去掉了，另外 C1 语言其实仍然有很大的冗杂度，比如控制循环和分支的都有多种表述方法，其实都可简化成一种，具体的来说，循环语句有 while 循环，do…while 循环和 for 循环，只需要保留 while 循环就够了；分支语句又有 if…{}， if…{}…else, if…{}…else if…， switch，这四种形式，它们都可以通过两个以上的 if…{} 来实现，因此只需要保留 if,…{} 就够了。可是再一想，所谓的分支和循环不过是条件跳转语句罢了，函数调用语句也不过是一个压栈和跳转语句罢了，因此只需要 goto（未限制的 goto）。因此大胆去掉所有结构化关键字，连函数也没有，得到的 C0 语言关键字如下：

只有 5 个关键字，已经完全可以用汇编语言快速的实现了。通过逆向分析我们还原了第一个C语言编译器的编写过程，也感受到了前辈科学家们的智慧和勤劳！我们都不过是巨人肩膀上的灰尘罢了！0 生1，1 生C，C生万物，实在巧妙！

tags：

相关：

教你如何用浏览器管理Docker

Docker 越来越流行了。在一个容器里面而不是虚拟机里运行一个完整的操作系统是一种非常棒的技术和想法。doc

63岁老人自学单片机8年做出机器人：有图有真相

63 岁的李祖臣为实现梦想，8 年前自学单片机、电脑知识，在书店一泡就是一天。8 年后，几百次尝试，老李终于

还在比较JSON和XML？Stop！

本文由玩赚乐(www.banghui.org)– 小峰原创翻译，转载请看清文末的转载要求，欢迎加入技术翻译小组！JSON 还

在Ubuntu15.10上安装IntelGraphics安装器

Intel 最近发布了一个新版本的 Linux Graphics 安装器。在新版本中，将不支持 Ubuntu 15.04，而必须用 Ubun

穿衣搭配喜欢简约风？这个23岁姑娘的博客值得一看