第一个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了。下面的图说明了这个抽象过程：

这张图是不是有点熟悉?对了，就是在将虚拟机的时候见到过!不过，这里是CVM(CLanguageVirtualMachine)，每种语言都是在每个虚拟层上可以独立实现编译的，并且除了C语言外，每一层的输出都将作为下一层的输入(最后一层的输出就是应用程序了)。这和滚雪球是一个道理。用手(汇编语言)把一小把雪结合在一起，一点点地滚下去就形成了一个大雪球，这大概就是所谓的0生1，1生C，C生万物吧?

那么，这种大胆的子集简化的方法是怎么实现的?又有什么理论依据呢?先介绍一个概念——“自编译”(Self-Compile)，也就是对于某些具有明显自举性质的强类型(所谓强类型就是程序中的每个变量必学声明类型后才能使用，比如C语言，相反有些脚本语言则根本没有类型这一说法)编程语言，可以借助它们的一个有限小子集，通过有限次数的递推来实现对它们自身的表述，这样的语言有C、Pascal、Ada……至于为什么可以自编译，可以参见清华大学出版社的《编译原理》，书中实现了一个Pascal的子集的编译器。总之，已经有CS科学家证明了，C语言理论上是可以通过上面说的CVM的方法实现完整的编译器的。

那么，实际上是怎样做到简化的呢?下面是C99的关键字：

//共37个
auto enum restrict unsigned
break extern return void
case float short volatile
char for signed while
const goto sizeof _Bool
continue if static _Complex
default inline struct _Imaginary
do int switch double long typedef
else register union

//共27个
enum unsigned break return
void case float short char
for signed while goto _Bool
continue if _Complex default
struct _Imaginary do int switch
double long else union

//共18个
enum break return void
case for while goto continue
if default struct do int
switch double else union

break return void case for while
goto continue if default do int
switch double else
//共15个

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

因此，大胆去掉所有结构化关键字，连函数也没有，得到的C0语言关键字如下：

//共5个
break voidgoto int double

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

0生1，1生C，C生万物，实在巧妙!

任何一种语言的第一个编译器肯定是使用其他语言写出来的。那就有一个问题了：第一种语言的第一个编译器是怎么来的呢?哈哈!

原文标题：第一个编译器是怎么来的?

文章出处：【微信公众号：嵌入式ARM】欢迎添加关注!文章转载请注明出处。

审核编辑：汤梓红