第一章：编译器的黎明 The Dawn of Compilers

第一章：编译器的黎明

黎明前的计算荒原

> "The navy's new compiler is 2,000 times faster than hand-coding... It's not science fiction—it's the IBM 704." — *John Backus, describing FORTRAN to skeptical engineers, 1957*

想象一下1954年的计算机实验室。那是一个充斥着真空管嗡鸣声、磁带机咔嗒声和打孔卡片沙沙声的世界。在IBM位于纽约州的实验室里，一群年轻的研究人员正在从事一项在当时看来近乎疯狂的工程——他们试图让机器自己理解人类的计算意图，而无需人类逐一告诉电子管应该如何导通或截止。这群人将要完成的工作，将彻底改变人类与机器对话的方式，并在此后七十余年间持续塑造着整个软件产业的形态。

在那个人类刚刚学会让机器执行指令不久的时代，编程本身就是一种高度专业化、近乎手工艺性质的活动。程序员们——当时更常被称为"计算员"(computer)——需要用极其原始的语言与硬件直接对话。每一台计算机都有自己独特的指令集，而程序则是这些指令的线性序列，被手工转换为打孔卡片或磁带上的物理模式。一个简单的矩阵乘法程序可能需要数千行指令，而程序员必须精确地记住每一个寄存器的用途、每一条指令的时序要求。这种工作方式的低效是显而易见的——人类大量的时间和精力被消耗在机器能够更高效完成的中介任务上。

正是在这样的背景下，一个革命性的想法在IBM的走廊里悄然萌芽：如果能够让程序员用接近人类数学表达的方式描述问题，然后让机器自动完成将这些表达式翻译为机器指令的繁琐工作，那将会怎样？这个想法的提出者和实践者们并不知道，他们正在开启的不仅是一个新的技术领域，更是一场深刻改变人类文明进程的认知革命。

FORTRAN的诞生：一段传奇的序章

约翰·巴科斯与团队

1954年的一个秋日，IBM启动了一个内部代号为"Speedcoding"的实验项目。这个项目的负责人是年仅29岁的约翰·巴科斯(John Warner Backus)，一位身材瘦削、眼神锐利的数学家。巴科斯在哥伦比亚大学完成了数学硕士学位后加入IBM，原本以为自己会从事纯粹的数学研究，却意外地被计算机科学的可能性所吸引。他后来回忆说，加入IBM是因为"听说这里有台可以自动计算的东西"。

巴科斯的团队最初只有五名成员：他自己负责整体设计和算法规划，Irving Ziller负责子程序调用机制，Richard Goldberg负责输入输出和格式处理，Sheldon Best负责内存管理，而Harlan Herrick则负责编写测试程序。这些名字在计算机史上或许不如巴科斯那样广为人知，但他们每一个人都为这个后来被证明具有里程碑意义的项目做出了不可或缺的技术贡献。

项目最初的目标相当务实：IBM需要为即将推出的704大型计算机开发一套能够显著提升编程效率的系统。当时的计算机使用成本极高——704计算机每小时的机时费用约为数百美元（按购买力折算相当于今天的数千美元），而一个复杂的科学计算程序可能需要数周甚至数月的开发时间。任何能够缩短开发周期、减少程序错误的工具都意味着巨大的商业价值。

但巴科斯和他的团队很快就意识到，他们正在从事的工作远不止是开发一套"更快的汇编语言"。他们真正要做的是彻底重新定义人类与计算机的关系——让计算机学会理解人类用数学语言表达的计算意图，而不是让人类去迁就机器的低级指令系统。

FORTRAN I：革命性的设计理念

经过三年的开发和数月的测试，IBM于1957年4月正式发布了FORTRAN（Formula Translation的缩写）编译器。这是世界上第一个高级编程语言及其配套编译器，其影响怎么强调都不为过。

FORTRAN的设计哲学可以概括为：用数学公式的自然形式表达计算过程，让编译器负责将其转换为高效的机器代码。这个看似简单的想法在当时却面临着巨大的技术挑战。编译器需要解决一个看似不可能完成的任务：分析人类用近似数学语法书写的表达式，理解其中的计算意图，然后生成能够正确执行这些计算的机器指令序列。

现代读者看到FORTRAN代码可能会觉得它相当原始。让我们来看一个经典的例子：

```fortran PROGRAM HELLO WRITE(6,100) 100 FORMAT(13H HELLO, WORLD) STOP END ```

这段代码会输出"Hello, World"。其中`13H`表示后续有13个字符，而`WRITE`和`FORMAT`语句负责处理输入输出。尽管以今天的标准来看这相当繁琐，但它已经比同等的机器码程序简洁了数十倍。

FORTRAN编译器的工作过程包含了我们今天所知的编译器架构中几乎所有的核心要素：

1. 词法分析：将源代码的字符流转换为标记(token)序列 2. 语法分析：将标记序列组织成抽象语法树 3. 语义分析：理解表达式的类型和含义 4. 代码生成：将分析结果转换为目标机器代码

这个时期的编译器虽然简陋，但已经确立了一种影响深远的范式：源代码到机器代码的转换应该由程序自动完成，而不是由程序员手工完成。

一个改变游戏规则的赌注

关于FORTRAN的诞生，有一个经常被忽视但至关重要的背景：这是一个商业赌注。

IBM高层最初对这个项目持怀疑态度。1954年，当巴科斯向IBM总裁小托马斯·沃森(Thomas J. Watson Jr.)汇报项目计划时，他坦率地承认自己无法保证编译器能够产生足够高效的代码。这是一个冒险的承诺——如果编译器生成的代码运行速度远低于手工优化的汇编代码，那么整个项目就会成为笑柄。

但巴科斯有一个关键的洞察：他观察到，即使是最熟练的程序员手工编写的汇编代码，也有相当一部分时间浪费在次要任务上——管理循环、存储中间结果、跟踪跳转地址。编译器虽然可能无法在每个细节上都超越人类专家，但它可以系统性地消除大量人为错误，并且能够在整个代码库中保持一致的质量。更重要的是，如果编译器能够生成"足够好"的代码——即使比最优解慢20%到30%——那么因为开发时间的大幅缩短，整个项目的效率仍然是革命性的。

后来的事实证明了巴科斯的判断。1958年，一项对当时实际使用中的FORTRAN程序的调查发现，编译器生成的代码平均只比最优手写汇编代码慢约5%到10%。考虑到开发时间的巨大节省，这完全在可接受的范围内。对于某些特定类型的程序，编译器甚至能够生成比大多数程序员手写代码更快的输出，因为它可以进行全局优化，而人类程序员往往难以在头脑中同时追踪如此大量的细节。

格雷丝·霍珀：编译技术的先驱

从海军军官到计算机先驱

如果说约翰·巴科斯是高级语言的缔造者，那么格雷丝·霍珀(Grace Brewster Murray Hopper)则是计算机编程语言的另一位奠基人。她的故事同样充满了远见卓识、坚定信念和对未来的惊人预判。

霍珀1906年出生于纽约曼哈顿，她的父亲是一名精算师，母亲是一位数学教师。在家庭氛围的熏陶下，她从小就对数学和机械产生了浓厚兴趣。1928年，她从瓦萨学院数学系毕业，此后在耶鲁大学继续深造并于1930年获得硕士学位。1934年，她成为耶鲁大学历史上第三位获得数学博士学位的女性。

1943年，37岁的霍珀做出了一个在当时看来颇为大胆的决定：加入美国海军预备役部队。当时正值第二次世界大战，海军急需各类专业人员。霍珀被分配到哈佛大学计算实验室，在霍华德·艾肯(Howard Aiken)的指导下工作。艾肯是早期机电计算设备的先驱，他设计的马克一号(Mark I)是世界上最早的通用自动计算设备之一。

正是在哈佛期间，霍珀第一次接触到了计算机科学——当时还没有这个名称。在艾肯的实验室里，霍珀成为了马克一号的主要程序员之一，为海军计算弹道数据和编制射表。她后来回忆说，正是在那些日日夜夜编程的经历中，她意识到"程序员不应该一辈子都用来写程序"。

编译思想的萌芽

战后，霍珀继续在哈佛和私企从事计算机相关工作。1949年，她加入埃克特-莫奇利计算机公司(Eckert-Mauchly Computer Corporation)，这家公司正在开发世界上第一台商业计算机UNIVAC I。正是在这里，她开始发展后来被称为"编译"的思想雏形。

霍珀观察到，程序员们反复编写相似的代码模式——循环结构、条件分支、算术运算。这不仅效率低下，而且容易出错。她开始思考：如果能够为这些常用模式创建标准化的"快捷方式"，让程序员使用更加接近人类语言的方式编程，然后由计算机自动将这些快捷方式"翻译"为机器指令，那将会怎样？

这个想法在今天看来理所当然，但在1950年代初，它代表着一种全新的思维方式。当时的计算机科学家们普遍认为，编译器是一个"不可能存在"的东西——编译过程涉及的自然语言理解问题被广泛认为是一个尚未解决的难题。霍珀后来说，当她向同事们描述自己的计划时，经常得到这样的反应："你疯了吗？计算机只能做你告诉它做的事，不能做你想让它做的事。"

但霍珀没有被这些质疑吓退。1952年，她和她的团队开发出了世界上第一个编译器——A-0系统（A代表"自动"(Automatic)，0表示它是该系列的第一个）。这个编译器接受用近似英语的符号语言编写的程序，并将其转换为机器代码。虽然以今天的标准来看，它更像是一个汇编系统而非现代意义上的编译器，但它首次证明了"程序可以写程序"这一革命性概念。

FLOW-MATIC与COBOL的诞生

A-0系统的成功让霍珀看到了更大的可能性。她开始思考：为什么编程语言必须是数学式的？为什么不能让计算机理解更加接近自然英语的表达方式？

1955年，霍珀开始开发一种新的编程语言——FLOW-MATIC（也称为B-0）。这是一种专门用于商业数据处理的高级语言，其设计目标是用接近英语的语法描述数据处理流程。FLOW-MATIC允许程序员使用类似"IF EMP-NAME IS GREATER THAN 'S' GO TO SUBROUTINE 3"这样的语句，这比当时的其他编程语言要直观得多。

但FLOW-MATIC面临一个根本性的问题：它只能在UNIVAC计算机上运行，而IBM的机器占据了更大的市场份额。霍珀意识到，如果要真正推广高级语言的概念，必须得到行业标准的支持。

1959年，在五角大楼（美国国防部）的资助下，一个被称为CODASYL（数据系统语言委员会）的委员会成立，负责开发一种通用的商业编程语言。霍珀作为技术顾问积极参与了这个过程，她成功地将FLOW-MATIC的许多设计理念融入了新的语言中。

最终诞生的COBOL（Common Business-Oriented Language的缩写）成为了商业数据处理领域的标准语言。直到今天，COBOL系统仍在全球各大金融机构的核心系统中运行——据估计，全世界每天有超过3万亿美元的交易是通过COBOL程序处理的。2019年，当美国多个州的失业保险系统因新冠疫情而崩溃时，政府不得不紧急召集懂COBOL的程序员来修复系统，这也从侧面说明了COBOL持久的影响力。

霍珀晚年时经常被问及她最自豪的成就是什么。她的回答始终如一："我希望未来的人们能够用近似英语的语言与计算机对话，而不必学习机器的语言。"这个愿景，她用一生的时间去推动它实现。

编译技术的演进：从笨拙到优雅

早期编译器：手工艺术的年代

FORTRAN和FLOW-MATIC开创了编译器的先河，但这些早期编译器的设计在很大程度上依赖于" hacks"和特殊情况处理。以FORTRAN为例，其编译器采用了今天看来相当粗糙的技术：

第一代FORTRAN编译器几乎没有做语法分析。它使用一种"扫描-匹配"(scan-and-match)的方法：读取源代码，识别已知的模式，然后直接生成相应的机器代码。这种方法虽然简单，但极易出错——一个小小的语法错误可能导致编译器生成完全错误的目标代码，甚至可能导致编译器本身崩溃。

此外，早期编译器几乎没有做任何优化。它们基本上是"逐句翻译"：读取一个语句，生成相应的机器代码，然后继续下一个语句。这种方法无法发现跨越语句边界的优化机会。例如，考虑以下代码：

```fortran X = A + B + C + D ```

一个简单的编译器可能会生成如下的机器代码序列： 1. 将A加载到寄存器 2. 加上B 3. 加上C 4. 加上D 5. 存储结果到X

但实际上，如果编译器能够分析整个表达式，它可以采用更高效的策略，例如使用多个寄存器并行执行加法，或者重新排列操作顺序以最小化寄存器压力。

早期编译器还有一个重要局限：它们几乎不进行任何类型检查。FORTRAN允许程序中的变量在不同位置使用不同的类型，而不进行任何警告或错误提示。这导致了许多难以发现的程序错误，这些错误直到运行时才会暴露出来。

语法分析革命：LL和LR分析器的诞生

1960年代，编译技术进入了一个新的发展阶段。计算机科学家们开始意识到，编译器不仅仅是一种实用工具，它本身就是一个深刻的理论研究对象。形式语言理论、图灵机理论、自动机理论——这些看似抽象的数学工具在编译器的设计中找到了实际的用武之地。

1961年，约翰·巴科斯的另一位同事——IBM的彼得·纳瑟(Peter Naur)——提出了一个重要的概念：使用巴科斯-纳瑟范式(BNF)来形式化描述编程语言的语法。BNF是一种上下文无关文法的表示方法，它使用递归规则来描述语言的语法结构。例如，FORTRAN的算术表达式可以用BNF描述为：

``` <expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term> <term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor> <factor> ::= <number> | "(" <expression> ")" | <variable> ```

BNF的出现标志着编译器设计从"经验技巧"向"系统理论"的转变。它让语言设计者能够精确地定义语言的语法规则，也为编译器编写者提供了明确的目标——只要实现能够正确识别这种语法的分析器，就能正确解析用该语言编写的程序。

1965年，约翰·巴科斯的学生唐·克努特(Donald Knuth)开始研究语法分析的高效算法。他注意到，当时存在的自顶向下分析器（如递归下降分析器）在处理某些语法时会遇到困难，而自底向上的分析器虽然更强大，但实现起来也更加复杂。

经过数年的研究，克努特于1965年发表了关于LR(k)分析器的开创性论文。LR(k)分析器是一种自底向上的语法分析器，它能够高效地处理一大类编程语言的语法。LR(k)中的"L"代表从左到右扫描输入，"R"代表最右推导，而"k"表示需要向前看的符号数量。LR(1)分析器——即只需要向前看一个符号的分析器——能够处理绝大多数实际使用的编程语言语法。

与此同时，自顶向下分析技术也在发展。1970年代初期，康奈尔大学的弗兰克·德雷佐(Frank DeRemer)提出了简单LR分析（SLR）和LALR(Look-Ahead LR)分析技术。LALR分析器结合了LR分析器的强大能力和比传统LR分析器更小的状态表，使得构建实用的编译器变得更加容易。

这些技术构成了现代编译器语法分析器的基础。直到今天，我们使用的绝大多数编译器仍然采用LR或LALR分析器来处理源代码的语法结构。

语义分析：理解程序的含义

如果说语法分析是理解程序的"形状"，那么语义分析就是理解程序的"含义"。一个程序不仅要有正确的语法，还必须符合语言规则的语义约束。

语义分析面临的主要挑战包括：

1. 类型检查：确保操作符和操作数的类型兼容。例如，在强类型语言中，将一个整数与一个字符串相加应该是非法的。语义分析器需要追踪每个变量的类型，并在发现类型错误时报告。

2. 作用域分析：确定每个标识符引用的具体定义。例如，当代码中出现变量`x`时，语义分析器需要确定这是哪一个`x`——是全局变量、局部变量还是函数参数。

3. 常量和常量表达式的求值：编译器可以在编译时计算常量表达式的值，从而避免在运行时重复计算。

4. 控制流分析：理解程序中的跳转结构，确保所有跳转目标都是有效的。

1960年代末到1970年代初，编译器研究者们发展出了一系列用于语义分析的技术。其中最重要的包括：

属性文法(Attribute Grammars)：由克努特在1968年提出的一种形式化方法，用于描述编程语言的语义规则。属性文法为语言的每个语法规则附加语义规则，这些规则定义了如何从子表达式的属性计算出父表达式的属性。

一遍扫描与多遍扫描：早期的编译器通常采用多遍扫描的设计——首先扫描源代码建立符号表，然后扫描进行语法分析，再扫描进行语义分析，最后生成目标代码。这种设计虽然清晰，但效率较低。现代编译器越来越多地采用一遍扫描的设计，通过精心设计的数据结构和算法，在一次遍历中完成所有工作。

优化技术：从正确到高效

编译器的优化技术是现代编译器区别于早期编译器的关键特征。优化可以在多个层次上进行：

局部优化作用于单个基本块（即没有跳转入口和出口的连续代码序列）内部。常见的局部优化技术包括：

• **常量折叠**：在编译时计算常量表达式的值。例如，`3 + 5`可以在编译时求值为`8`。
• **代数简化**：利用代数规则简化表达式。例如，`x * 0`简化为`0`，`x + 0`简化为`x`。
• **公共子表达式消除**：如果一个表达式已经被计算过且其操作数没有改变，则重复使用之前的结果。例如，在`a = b + c; d = b + c;`中，`b + c`只计算一次。

循环优化是编译器优化的重点领域，因为程序中的循环往往是执行最频繁的部分。常见的循环优化包括：

• **循环不变代码外提**：将循环中值不变的计算移到循环外部。
• **归纳变量优化**：识别并简化循环中的计数变量。
• **循环展开**：通过复制循环体来减少循环控制的开销。
• **循环合并**：将多个相邻的循环合并为一个循环。

全局优化考虑整个程序的范围，跨越函数边界进行优化。例如：

• **内联展开**：将函数调用替换为函数体，从而消除调用开销并创造更多优化机会。
• **死代码消除**：删除永远不会被执行或结果不会被使用的代码。
• **常量传播**：如果在程序某点上，变量的值是已知的常量，则用常量替换该变量的使用。

1970年代，编译器优化技术取得了重大突破。1977年，弗朗西斯·艾伦(Frances Allen)和约翰·科克(John Cocke)发表了关于程序优化框架的论文，提出了"数据流分析"的形式化方法。数据流分析是一种系统性的技术，用于追踪程序执行过程中