论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

Compiling a Compiler

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:37:50

CIS 85
穆信成

    UNIX是以C语言写成的。使用C语言的其中一个优点是造成了UNIX的可携性。
另一方面,工作站的销售对象是需要大量计算的工程师、科学家等等;因此不同
於PC,在工作站级以上的电脑上,compiler是一项附在作业系统中的基本配备。
UNIX系统中必定附有C compiler。既然要保持可携性, UNIX系统里面所附的的C
compiler也得和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 :<换行码>Figure1<TAB的码>A 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的原文。
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058