计算机文化基础系列常识-图灵奖获奖者介绍连载十四 .pdf

计算机文化基础系列常识-图灵奖获奖者介绍连载（十四）

罗伯特·弗洛伊德

——前后断言法的创始人

历届图灵奖得主基本上都有高学历、高学位，绝大多数有博士头衔。这是可以理解的，

因为创新型人才需要有很好的文化素养，丰富的知识底蕴，因而必须接受良好的教育。但

事情总有例外，1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德

1/7

(RobertW．Floyd)就是一位“自学成才的计算机科学家”(aSelf-TaughtComputer

Scientist)。

弗洛伊德1936年6月8日生于纽约。说他“自学成才”并不是说他没有接受过高等

教育，他是芝加哥大学的毕业生，但学的不是数学或电气工程等与计算机密切相关的专业，

而是文学，1953年获得文学士学位。20世纪50年代初期美国经济不太景气，找工作比

较困难，因学习文学而没有任何专门技能的弗洛伊德在就业上遇到很大麻烦，无奈之中到

西屋电气公司当了二名计算机操作员，在IBM650机房值夜班。我们知道，早期的计算机

都是以批处理方式工作的，计算机操作员的任务就是把程序员编写好的程序在卡片穿孔机

(这是脱机的辅助外部设备)上穿成卡片，然后把卡片叠放在读卡机上输入计算机，以便运

行程序。因此，操作员的工作比较简单，同打字员类似，不需要懂计算机，也不需要懂程

序设计。但弗洛伊德毕竟是一个受过高等教育的人，又是一个有心人，干了一段操作员，

很快对计算机产生了兴趣，决心弄懂它，掌握它，于是他借了有关书籍资料在值班空闲时

间刻苦学习钻研，有问题就虚心向程序员请教。白天不值班，他又回母校去听讲有关课程。

这样，他不但在1958年又获得了理科学士学位，而且逐渐从计算机的门外汉变成计算机

的行家里手。1956年他离开西屋电气公司，到芝加哥的装甲研究基金会(ArmourResearch

Foundation)，开始还是当操作员，后来就当了程序员。1962年他被马萨诸塞州的

ComputerAssociates公司聘为分析员。1965年他应聘成为卡内基

2/7

—梅隆大学的副教授，3年后转至斯坦福大学，1970年被聘任为教授。之所以能这样

快地步步高升，关键就在于弗洛伊德通过勤奋学习和深入研究，在计算机科学的诸多领域：

算法，程序设计语言的逻辑和语义，自动程序综合，自动程序验证，编译器的理论和实现

等方面都作出创造性的贡献。其中包括：1962年，弗洛伊德完成了Algol60编译器的开

发，成功投入使用，这是世界上最早的Algol60编译器之一，而且弗洛伊德在这个编译器

的开发中率先融入了优化的思想，使编译所生成的目标代码占用空间少，运行时间短。弗

洛伊德优化编译的思想对编译器技术的发展产生了深刻的影响。随后，他又对语法分析进

行了系统研究，大家现在熟知的优先文法(precedencegrammar)，限界上下文文法

(boundedcontextgrammar)等都是弗洛伊德在这个时期首先提出来的。优先文法解决了

自底向上的语法分析中的首要任务：如何找到“句柄”，也就是当前需要进行归约的符号串。

弗洛伊德通过对不同的符号定义不同的优先级，解决了这个问题。限界上下文文法则通过

对上下文无关文法G中的两个推导：

*

S→βArβαγ

+

S→δαε

进行比较以确定α是否是δαε的句柄，以及产生方式A→α是否是唯一可进行归约的产

生式。弗洛伊德经过研究，给出其充分必要条件为：β和δ的最后m个符号相同，丁和o

／的最初n个终结符相同。这样一个上下文无关文法G就称为(m，n)限界上下文文法。

在算法方面，弗洛伊德和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序

算法HEAPSORT，这是与英国学者霍尔(C.A.R.Hoare，1980年图灵奖获得者)发明的

QUICKSORT齐名的高效排序算法之一。此外还有直接以弗洛伊德命名的求最短路的算法，

这是弗洛伊德利用动态规划(dynamicprogramming)的原理设计的一个高效算法。