如何编译一个编译器
穆信成
UNIX是以C语言写成的。使用C语言的其中一个优点是造成了UNIX的可携性。另一方面，工作站的销售对象是需要大量计算的工程师、科学家等等；因此不同於PC，在工作站级以上的电脑上，compiler是一项附在作业系统中的基本配备。UNIX系统中必定附有C compiler。既然要保持可携性， UNIX系统里面所附的的Ccompiler也得和UNIX系统一样，用C写作。
C compiler本身，也是用C写的。当一个语言的compiler 也用该语言本身来写的时候，便会发生一些有趣的事情。也许您会问，既然电脑上面已经有C compiler了，那麽我们要再去compile另一个compiler的source code作什麽？
答案可能是，原有的内建C compiler可能比较简陋或著老旧，因此我们想把新的compiler用旧的compiler编译，然後当成系统内建的compiler用。换句话说，我们就这麽扩充了系统的内建compiler。
Glasgow大学的GRASP计划，也用这样的过程发展他们的Haskell compiler。
Haskell是一个functional language（85级同学记得Programming Language课中提到的functional programming吗？）。Functional programming总是带有较多的学术味而缺乏实用经验。Haskell语言本身仍有不少需要再扩充的空间。GRASP计划用 Haskell 来写Haskell compiler：先从简单的写起， 产生一个最原始的Haskell compiler，然後用这套原始的Haskell语言写一个功能较强的 compiler(把原来的Haskell扩充了），再用第二版的 Haskell 语言写第三版的compiler....。由於都是compiler，因此并不会减低效率。一个好处是，每次扩充语言，接下来立刻用新的语言写compiler，於是我们可以立刻看出新加功能是否有用处？
该怎麽用？如此累积的经验，正可以作Haskell语言以後发展设计的参考。GRASP计划的理想就是″把functional proramming带出实验室″。
UNIX的创造人之一，Ken Thompson，在他的 Turing Award Lecture中，便由这个主题加以发挥，说了一些有趣的故事。C 是一个被拿来写作业系统的语言。写作业系统的人很难忍得住诱惑，不在系统里面装些後门的。想想看，如果我写作业系统时，偷偷在login 的部份加一段程式码，使得全世界的这套作业系统只要看到我的account和密码就让我进去，给我root权限，这该是多爽呀。 但是我不能直接在 login 的 source code 里面这样写，否则一下就被人抓到了（既然source code流通，就是要给人看的呀）。 该怎麽办呢？就从compiler里面动手脚，称作patch1吧：在compiler中多加一道手续， 如果发现被compile的原始程式″疑似″在作login动作，就把它开个漏洞，让我进得去。
但是这样也不见得行得通。Compiler以後也会改版，新版的compiler可能不是我在写。装系统的人也不见得用我的compiler。怎麽办呢？於是我在compiler的source code中作第二次手脚，称作patch2：如果这个compiler觉得在compile的程式″疑似″另一个 compiler 的 source 的话，就加入上面的patch1和这个patch2本身。
好，现在作业系统推出了，CC1 是我写的内建compiler，其中有我动的两个手脚。现在某人在compile UNIX, 不得不用这个compiler。然而CC1 中已经有了patch1，於是一旦compile到login, compile出来的login程式就被动了手脚。只要看到我的名字，就一定让我进系统，给我root权限。
,--------. +-------------+ ,-----------.
| login | | Compiled | | login |
| source |=====>| by CC2 |=====>| Program |
| (clean)| | patch 1作用 | |(受感染了!)|
`--------\ +-------------+ `-----------\
既然 compiler CC1会作怪， 那麽自己写 compiler 总可以了吧？ 然而，C compiler还是得用C写，写好了之後，用谁来compile呢？ 只有用CC1来compile。
CC1发现新写的CC2是一个compiler的source code，於是 patch2 就发挥作用了。CC1会在CC2中也加入patch1和patch2。於是CC2也被″污染″了。
,--------. +-------------+ ,-----------.
| CC2 | | Compiled | | CC2 |
| source |=====>| by CC1 |=====>| Program |
| (clean)| | patch 2作用 | |含 patch1,2|
`--------\ +-------------+ `-----------\
如果再用CC2来compile一个正常的login程式，由於CC2中有了patch1，所以compile出来的login程式也会有後门，让我任意的login；
,--------. +-----------+ ,----------.
| login | | Compiled | | login |
| source |=====>| by CC2 |=====>| Program |
| (clean)| |(patch 1,2)| |(patched!)|
`--------\ +-----------+ `----------\
如果用CC2 compile另一个compiler CC3，由於CC2中已经被加入了 patch2，CC3又会被污染，也就是说CC3这个compiler中还是会有patch1和patch2......如此一来，全世界的每一套UNIX都种下了这个後门，可以让我任意login！
然而这些patch都只在binary档之中出现。CC2的source code一切正常，所以从source code完全看不出有什麽不对劲呢！我们还可以进一步湮灭证据。一旦装好一套系统，公开的CC1 source code中不必有动过手脚的程式码，只要让它被动过手脚的compiler编译就可以了。
有著无辜的包装，事实上内容暗藏玄机的程式，称作″特洛伊木马″。 这个特洛伊木马的故事有趣吗？（注1）
用C语言写C compiler，写出来的程式会是个什麽样子呢？ 举个例子，一个C compiler可能有一段前置处理程式在处理C字串中的溢出字元。比如说，compiler需要把如下的字串：
\"Figure listings :\\nFigure1\\tA Complete Tree\\n.....\"
给转换成：
Figure listings :<换行码>Figure1A Complete.....
这段程式可能看起来像这样（为简单起见，这个程式从标准输入读进原始码，送到标准输出）：
if ((c=getchar())==\\\\)
switch (getchar()) {
case \n\ : putchar(\\\n\); break;
case \t\ : putchar(\\\t\); break;
:
}
else
putchar(c);
好像有点奇怪，是吗？明明用if和switch把溢出字元\\\\以及後面的\n\,\t\,分开了，在putchar的地方又送出\\\n\, \\\t\。如果您见多了用某语言写自己的compiler的情况，对於这种程式段落也就见怪不怪了（注2)。
C语言是个处在大家周遭而不常被注意到的例子。LISP语言只须简单的parser，不分程式和资料，使得用LISP写LISP interpreter的情形更是普遍，也是常用的教材。85级用的PL课本Chezzi & Jazayeri 的functional programming一章中，最後附的LISP程式就是一个LISP interpreter。如果您研究一下，会发现一些感觉挺像上面那个例子的段落。我自己玩了几年的LISP，到头来反倒除了LISP interpreter之外，就不会写其他什麽有用的程式了。这也是一个奇怪的现象呢。
参考资料： ACM Turing Award Lectures :
the first twenty years 1966 to 1985
QA76.24
#
注：1. 原本我以为Ken Thompson只是写写罢了。後来据一些人说，这完全是Ken Thompson 本人干过的真人真事。想像他老远到交大来参加conference, 大摇大摆的走上二楼机房，若无其事地login成root的情况吧。你相不相信呢？
2. 假设旧的compiler CC1并看不懂\\\v\这个控制字元（垂直对齐）， 我们想要有一个具有这个字元的compiler。新compiler CC2的source code可能是这样：
switch (getchar()) {
case \n\ : putchar(\\\n\); break;
case \t\ : putchar(\\\t\); break;
case \v\ : putchar(\\\v\); break;
:
}
但是compiler CC1并没有办法compile这段程式，因为CC1看不懂程式中的\\\v\！这似乎是一个逻辑陷阱，在实际develop的时候得多花手续。详见Ken Thompson的原文。发布人:netbull 来自:中国软件