第一个 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属于C1C1属于C用C0开发出C1语言的编译器。在C1的基础上设计C语言的又一个子集C2语言C2语言比C1复杂但是仍然不是完整的C语言开发出C2语言的编译器……如此直到CNCN已经足够强大了这时候就足够开发出完整的C语言编译器的实现了。至于这里的N是多少这取决于你的目标语言这里是C语言的复杂程度和程序员的编程能力——简单地说如果到了某个子集阶段可以很方便地利用现有功能实现C语言时那么你就找到N了。下面的图说明了这个抽象过程那么这种大胆的子集简化的方法是怎么实现的又有什么理论依据呢先介绍一个概念“自编译”Self-Compile也就是对于某些具有明显自举性质的强类型所谓强类型就是程序中的每个变量必须声明类型后才能使用比如C语言相反有些脚本语言则根本没有类型这一说法编程语言可以借助它们的一个有限小子集通过有限次数的递推来实现对它们自身的表述这样的语言有C、Pascal、Ada等等至于为什么可以自编译可以参见清华大学出版社的《编译原理》书中实现了一个Pascal的子集的编译器。总之已经有计算机科学家证明了C语言理论上是可以通过上面说的CVM的方法实现完整的编译器的那么实际上是怎样做到简化的呢这张图是不是有点熟悉对了就是在讲虚拟机的时候见到过不过这里是CVMC Language Virtual Machine每种语言都是在每个虚拟层上可以独立实现编译的并且除了C语言外每一层的输出都将作为下一层的输入最后一层的输出就是应用程序了这和滚雪球是一个道理。用手汇编语言把一小把雪结合在一起一点点地滚下去就形成了一个大雪球这大概就是所谓的0生11生CC生万物吧下面是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生11生CC生万物实在巧妙活动推荐 AWS Summit AWS技术峰会2015上海