编译器是怎么写出来的,怎么自己写一个编译器

首页 > 实用技巧 > 作者:YD1662023-05-29 22:45:24

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

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

编译器是怎么写出来的,怎么自己写一个编译器(1)

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

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

编译器是怎么写出来的,怎么自己写一个编译器(2)

还是让我们回顾一下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了。下面的图说明了这个抽象过程:

编译器是怎么写出来的,怎么自己写一个编译器(3)

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

下面是 C99 的关键字:

编译器是怎么写出来的,怎么自己写一个编译器(4)

首页 123下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.