Alfred V. Aho & Jeffrey D. Ullman：他们写下的"龙书"训练了几代程序员，让编译器从黑魔法变成系统科学

图灵奖第五十五届（2020）| Alfred V. Aho & Jeffrey D. Ullman：他们写下的”龙书”训练了几代程序员，让编译器从黑魔法变成系统科学

一句话概括：当所有人都在用编译器时，很少有人真正理解编译器是如何工作的——Aho和Ullman不仅发明了编译技术的核心算法，更用传奇教材《编译原理》（龙书）将复杂的编译理论变成可学习、可实践的系统知识，奠定了现代编程语言实现的理论基础和工程方法。

🏆 获奖简介

Alfred Vaino Aho（阿尔弗雷德·瓦伊诺·阿霍，1941-）和Jeffrey David Ullman（杰弗里·戴维·厄尔曼，1942-）是编译器理论与实践的奠基人，算法与数据库理论的先驱。

Alfred V. Aho：

出生时间：1941年8月9日
出生地点：加拿大安大略省蒂明斯
主要成就：
- AWK编程语言联合发明者（A代表Aho）
- egrep（扩展正则表达式搜索）的算法设计者
- 编译器优化算法（如数据流分析）的先驱
- LR语法分析理论的重要贡献者
教育背景：
- 1963年：多伦多大学工程物理学士
- 1965年：普林斯顿大学电气工程硕士
- 1967年：普林斯顿大学电气工程/计算机科学博士

Jeffrey D. Ullman：

出生时间：1942年11月22日
出生地点：美国纽约市
主要成就：
- 数据库理论奠基人之一（关系数据库理论、数据挖掘）
- 形式语言与自动机理论的系统化
- 编译器优化和程序分析理论
- 算法分析方法论的推广
教育背景：
- 1963年：哥伦比亚大学工程学士
- 1966年：普林斯顿大学电气工程博士
获奖年份：2020年（共同获奖）
获奖原因：对编程语言实现的基础算法和理论的根本性贡献

为什么他们是第五十五位？ 1960年代，编译器还是少数专家掌握的”黑魔法”，每种新语言都需要从零开始设计编译器。Aho和Ullman在贝尔实验室和斯坦福大学的合作中，系统化了编译器的设计方法——从词法分析的正则表达式到语法分析的LR算法，从语义分析的属性文法到代码优化的数据流分析。他们的《编译原理》（1977年红龙书，1986年绿龙书，2006年紫龙书）成为全球计算机科学教育的圣经，训练了数百万程序员。更重要的是，他们的理论不只停留在纸面：AWK语言、egrep工具、YACC解析器生成器都是他们思想的实际产物。从C/C++到Java，从Python到Rust，今天所有编程语言的实现都建立在他们奠定的理论和工程框架之上。

🚀 Alfred Aho的重大贡献

1. AWK语言：文本处理的瑞士军刀

背景（1977年）：

问题：Unix用户需要处理文本文件（日志、数据表）
现状：
- sed：面向行的流编辑器，功能有限
- shell脚本：语法笨拙，不适合复杂逻辑
- C语言：对简单任务来说太重量级
需求：一种专门用于”模式扫描与处理”的语言

AWK的诞生（Aho, Weinberger, Kernighan）：

核心设计理念：

模式 { 动作 }

对输入的每一行，检查是否匹配”模式”
如果匹配，执行”动作”
自动处理文件读取、行分割、字段提取

经典示例：

示例1：计算文件各列的和

# 文件 data.txt:
# Alice 85 90
# Bob 78 92
# Carol 95 88

# 计算每人总分
awk '{print $1, $2+$3}' data.txt
# 输出：
# Alice 175
# Bob 170
# Carol 183

示例2：日志分析

# 统计HTTP状态码
awk '$9 == 404 {count++} END {print count}' access.log

# 计算平均响应时间
awk '{sum += $NF; count++} END {print sum/count}' response_times.txt

语言特性：

自动字段分割：$1, $2, $3... 自动按空格分割
关联数组：count["error"]++（比C数组灵活）
内置变量：NR（行号）、NF（字段数）、FS（字段分隔符）
正则匹配：/pattern/ {action}

影响：

Unix哲学：“做一件事并做好”的典范
数据科学前身：在pandas出现前的数据清洗工具
持续使用：40年后仍然是Linux系统的标配工具

2. egrep与正则表达式算法

挑战（1970年代初）：

Ken Thompson的grep使用回溯算法，复杂模式性能差
需要支持扩展正则表达式（如 (a|b)*c）

Aho的贡献：

Thompson NFA构造的高效实现
DFA最小化算法：减少状态数
Aho-Corasick算法（1975，与Margaret Corasick合作）：
- 问题：在文本中同时搜索多个模式（如病毒扫描）
- 解决：构建所有模式的Trie树 + 失败链接
- 性能：O(n + m + z)，n=文本长度，m=模式总长度，z=匹配数

算法示例（Aho-Corasick）：

模式集合：{he, she, his, hers}
文本：ushers

1. 构建Trie:
        root
       /    \
      h      s
     / \      \
    e   i      h
   /     \      \
  r       s      e
 /
s

2. 添加失败链接：
   当在"she"的"e"处失配时，跳转到"he"的"e"

3. 扫描文本：
   在"ushers"中找到"she"和"he"和"hers"

应用：

病毒扫描：同时匹配数千个病毒签名
网络入侵检测：Snort等IDS系统
生物信息学：DNA序列多模式匹配

3. 编译器优化的数据流分析

贡献（1970年代）：

可用表达式分析（Available Expressions）：

目的：识别可以复用的计算
例子：

x = a + b;
y = c + d;
z = a + b;  // 可以复用x的结果

Aho的算法：

构建程序的控制流图（CFG）
迭代计算每个基本块的：
- GEN：本块生成的表达式
- KILL：本块失效的表达式
- IN：进入本块时可用的表达式
- OUT：离开本块时可用的表达式
直到达到不动点

到达定值分析（Reaching Definitions）：

目的：确定变量的可能取值来源
用途：死代码消除、常量传播

工程实践：这些算法今天是所有优化编译器（GCC、LLVM、JVM）的核心组件。

4. LR语法分析理论

背景：

LL分析（自顶向下）：简单但表达力有限
LR分析（自底向上）：理论由Donald Knuth提出，但状态机庞大

Aho的贡献：

LALR（Look-Ahead LR）算法：
- 合并LR(1)的相似状态，大幅减少状态数
- 保持大部分LR(1)的能力
- 实用到可以手工实现

YACC（Yet Another Compiler Compiler）：

Stephen C. Johnson基于Aho和Ullman的理论开发
Aho提供算法指导
语法文件示例：

%token NUMBER
%%
expr: expr '+' term   { $$ = $1 + $3; }
    | term            { $$ = $1; }
    ;
term: term '*' factor { $$ = $1 * $3; }
    | factor          { $$ = $1; }
    ;
factor: NUMBER        { $$ = $1; }
      | '(' expr ')'  { $$ = $2; }
      ;

影响：

Bison（GNU YACC）：今天仍广泛使用
思想传承：ANTLR、Parser Combinator等现代工具

🚀 Jeffrey Ullman的重大贡献

1. 形式语言与自动机理论的系统化

教材《形式语言与自动机理论导论》（1979）：

覆盖内容：

正则语言与有限自动机：
- 正则表达式 ↔ NFA ↔ DFA的等价性
- 泵引理（Pumping Lemma）：证明某语言不是正则的
上下文无关语言与下推自动机：
- BNF范式定义语法
- 下推自动机（PDA）的非确定性
图灵机与可计算性：
- 停机问题的不可判定性
- 归约（Reduction）技术

教学方法：

递进式讲解：从简单到复杂，层层深入
严格证明+直观例子：理论与实践结合
习题设计：从基础到挑战，巩固理解

影响：

成为全球大学”形式语言”课程的标准教材
奠定了编译器前端（词法、语法分析）的理论基础

2. 数据库理论的奠基工作

虽然图灵奖主要表彰编译器贡献，但Ullman在数据库领域同样卓越：

关系数据库理论：

函数依赖（Functional Dependencies）：
- 定义：X → Y 表示X决定Y
- 例：学号 → 姓名（学号确定则姓名确定）
范式理论（Normal Forms）：
- 1NF、2NF、3NF、BCNF的形式化定义
- 消除数据冗余和异常的方法
Armstrong公理：
- 从已知函数依赖推导新依赖的推理规则

查询优化：

关系代数等价变换：
- 投影下推：π(σ(R)) vs σ(π(R))
- 连接交换律：R ⋈ S = S ⋈ R
代价模型：估计查询执行时间
动态规划：找到最优执行计划

影响：

Oracle、PostgreSQL等数据库的查询优化器基于这些理论
Ullman的学生包括多位数据库领域的领军人物

3. 数据挖掘的早期工作

贡献（1990年代）：

MapReduce的理论先驱：
- 研究大规模数据的分布式处理
- 影响了Google的MapReduce设计
关联规则挖掘：
- “啤酒与尿布”问题的算法基础
- A Priori算法的理论分析

4. 算法教育的推广

《数据结构与算法》系列教材（与Aho、Hopcroft合著）：

特点：

实用算法：排序、搜索、图算法
复杂度分析：O(n log n)的严格推导
伪代码：语言无关，易于理解

教学理念：

算法不是”魔法”，是可以系统学习的技能
从问题出发，而非算法堆砌
证明正确性与分析效率同样重要

🚀 两人的共同贡献：龙书

《编译原理》（Compilers: Principles, Techniques, and Tools）

历史：

1977年：第一版（红龙书），Aho & Ullman
1986年：第二版（绿龙书），Aho, Sethi, Ullman
2006年：第三版（紫龙书），Aho, Lam, Sethi, Ullman

为什么叫”龙书”？

封面是一幅中世纪骑士屠龙图，象征”程序员征服复杂编译器”的旅程。

内容架构（以紫龙书为例）：

前端（Front End）：

1. 词法分析（Lexical Analysis）

输入：源代码字符流
```
int x = 42;
```

输出：词法单元流

<TYPE, int> <ID, "x"> <ASSIGN> <NUM, 42> <SEMICOLON>

技术：
- 正则表达式 → NFA → DFA
- LEX/Flex工具的原理

2. 语法分析（Syntax Analysis）

输入：词法单元流
输出：抽象语法树（AST）
```
     =
    / \
   x   42
```
技术：
- 上下文无关文法（CFG）
- LL、LR、LALR算法
- YACC/Bison工具的原理

3. 语义分析（Semantic Analysis）

任务：
- 类型检查：int x = "hello"; → 错误
- 符号表管理：变量作用域
- 语法制导翻译（Syntax-Directed Translation）
技术：
- 属性文法（Attribute Grammars）
- S属性（综合属性）、L属性（继承属性）

中端（Middle End）：

4. 中间代码生成

三地址码（Three-Address Code）：

t1 = a * b
t2 = c + d
t3 = t1 - t2
x = t3

控制流图（CFG）：基本块 + 边

5. 代码优化

局部优化：
- 公共子表达式消除
- 常量折叠：x = 2 + 3 → x = 5
- 死代码消除
全局优化：
- 数据流分析
- 循环优化：循环不变量外提、强度削弱
高级优化：
- 内联函数
- 循环展开

后端（Back End）：

6. 目标代码生成

指令选择：三地址码 → 机器指令
寄存器分配：
- 图着色算法
- 活性分析（Liveness Analysis）
指令调度：重排指令利用流水线

7. 运行时环境

内存布局：栈、堆、静态区
函数调用：活动记录（Activation Record）
垃圾回收：标记-清除、分代回收

龙书的教学价值

为什么是”圣经”：

系统性：覆盖编译器全流程，不留空白
理论+实践：
- 理论：算法证明、复杂度分析
- 实践：伪代码、实例分析
渐进式：从简单语言到复杂特性（面向对象、并发）
工具链：介绍LEX、YACC等实用工具

学习曲线：

挑战：内容密集，数学证明较多
收获：深刻理解编程语言如何”运作”
适用：
- 编译器开发者：必读
- 语言设计者：理解实现代价
- 普通程序员：理解性能优化原理

龙书的实际影响

教育：

全球500+所大学将其作为编译原理课程教材
培养了数百万理解编译器的程序员

工业：

GCC（GNU Compiler Collection）：直接应用龙书算法
LLVM：现代编译器基础设施，继承龙书思想
JVM JIT：Java虚拟机的即时编译器
V8（JavaScript引擎）：动态语言的优化编译

语言设计：

Go：快速编译的秘诀在于简化语法分析
Rust：借用检查器（Borrow Checker）= 数据流分析的应用
TypeScript：类型推导基于属性文法理论

🌍 对世界的深远影响

编程语言的繁荣

1970年代：

编译器是稀缺资源，新语言难以推广

1980-2000年代：

龙书+工具链降低了编译器开发门槛
语言爆炸：C++、Java、Python、Ruby、PHP…

2000年代至今：

领域特定语言（DSL）：SQL方言、Shader语言、配置语言
新范式：函数式（Haskell、Scala）、并发（Erlang、Go）
实验语言：研究者可以快速实现原型验证想法

软件工程的标准化

静态分析工具：

Lint：代码风格检查
Coverity：安全漏洞检测
基础：都是编译器技术的延伸（AST分析、数据流分析）

IDE智能功能：

代码补全：语法分析 + 类型推导
重构：符号表 + AST变换
跳转定义：符号解析

性能优化的理论基础

编译器优化：

循环向量化：SIMD指令
自动并行化：依赖分析
全程序优化（LTO）：跨文件内联

JIT编译：

热点代码：运行时分析 + 动态编译
去优化（Deoptimization）：优化假设失效时回退

启示： Aho和Ullman的理论让”性能优化”从”黑魔法”变成”科学方法”。

🏆 获奖理由（通俗版）

ACM官方表彰：“对编程语言实现的基础算法和理论的深远贡献。”

更通俗的理解：

Alfred Aho证明：文本处理、模式匹配、代码优化可以有高效且优雅的算法。他让程序员不仅”会用工具”，更”理解工具”。

Jeffrey Ullman证明：编译器、数据库、算法是可以系统教授的学科，而非天才的专利。他让知识从象牙塔走向大众。

两人共同：将编译器从”巫师的黑魔法”变成”工程师的标准工具”，让每个学计算机的学生都能理解程序如何从源代码变成机器码。没有他们，就没有今天编程语言的繁荣和软件工程的标准化。

👤 个人生平与传奇

Alfred V. Aho（1941-）

成长背景：

芬兰裔加拿大人：父母从芬兰移民到加拿大安大略省
早期兴趣：数学和物理，多伦多大学学习工程物理
转向计算机：普林斯顿读研期间被计算机科学吸引

贝尔实验室岁月（1967-1991）：

黄金时代：与Ken Thompson、Dennis Ritchie、Brian Kernighan共事
Unix工具链：参与egrep、AWK、YACC的开发
理论研究：编译器优化、算法设计

学术生涯（1995-至今）：

哥伦比亚大学：计算机科学教授
继续写作：更新龙书、发表论文
教学奖：ACM Karl V. Karlstrom Outstanding Educator Award

性格特点：

谦逊：将AWK的成功归功于团队
实用主义：理论必须能解决真实问题
教育热情：认为”教学是知识的最终测试”

趣闻：

AWK中的”A”虽然代表Aho，但他坚持按字母顺序排列作者名（Aho, Weinberger, Kernighan），避免争论

Jeffrey D. Ullman（1942-）

早年经历：

纽约出生：成长于知识分子家庭
哥伦比亚大学：本科工程，1963年毕业
普林斯顿博士：1966年获电气工程博士（当时CS还未独立成系）

学术生涯：

普林斯顿（1966-1979）：早期教职，与Aho合作编写红龙书
斯坦福（1979-至今）：
- 计算机科学教授
- 培养大批博士，包括多位图灵奖得主的学生
- 数据库、数据挖掘、Web搜索的研究

教学哲学：

清晰至上：复杂理论用简单语言解释
“填鸭”反对者：强调理解而非记忆
开放资源：支持教材配套材料免费公开

荣誉：

图灵奖（2020，与Aho共享）
Knuth奖（2000）：理论计算机科学杰出贡献
ACM/IEEE-CS Ken Kennedy奖（2020）：编程语言与编译器

性格特点：

严谨：理论证明一丝不苟
高产：论文、教材、技术报告数量惊人
导师：学生称他”总是有时间讨论问题”

争议：

2011年抗议事件：Ullman曾对以色列-巴勒斯坦问题发表政治观点，引发学生抗议；他本人坚持学术自由和言论自由

两人的合作

初识（1960年代末）：

Aho在贝尔实验室，Ullman在普林斯顿
通过学术会议和共同兴趣结识

合作模式：

分工明确：
- Aho：算法设计、工程实现
- Ullman：理论基础、形式化证明
互补性强：一个偏实践，一个偏理论
长期合作：从1970年代到2000年代，跨越40年

共同著作：

《The Theory of Parsing, Translation, and Compiling》（1972-1973，两卷）
《Principles of Compiler Design》（红龙书，1977）
《Compilers: Principles, Techniques, and Tools》（绿龙书，1986；紫龙书，2006）
《Data Structures and Algorithms》（1983，与Hopcroft合著）
《Foundations of Computer Science》（1992）

友谊：

超越专业合作的终身友谊
互相支持对方的研究和职业发展

💭 为什么他们值得纪念？

1. 他们让编译器从黑魔法变成系统科学

之前（1960年代）：

编译器是少数专家的”艺术”
每种语言重新发明轮子
理论与实践脱节

之后（1970年代起）：

标准化方法：词法→语法→语义→优化→代码生成
理论基础：形式语言、自动机、算法
工具支持：LEX、YACC自动生成编译器组件

影响：降低了编译器开发门槛，促进了编程语言的创新。

2. 他们的教材定义了计算机科学教育

龙书：

全球使用最广泛的编译原理教材
培养了数百万程序员的系统思维

其他教材：

形式语言、算法、数据结构
覆盖计算机科学的多个核心领域

教育理念：

知识应该可传授、可学习、可实践
理论与实践结合

3. 他们的工具今天仍在使用

AWK（1977）：

47年后仍是Linux标配
数据科学的经典工具

egrep算法：

所有正则表达式引擎的基础

YACC思想：

Bison、ANTLR继承

持久性：好的设计超越时代，经久不衰。

4. 他们证明了”理论有用”

常见误解： “理论计算机科学没有实用价值”

Aho和Ullman的反证：

有限自动机：正则表达式引擎、词法分析器
上下文无关文法：语法分析器、XML解析
数据流分析：编译器优化、静态分析工具
图算法：寄存器分配、指令调度

启示：今天看似”纯理论”的研究，可能成为明天的工程基础。

🔍 技术深度：LR语法分析

LR分析器的构造

基本概念：

项（Item）：产生式中带”点”的形式
- 例：E → E • + T（点表示”已识别到这里”）
项集（Item Set）：一组项的集合
状态机：每个项集是一个状态

LR(0)构造算法：

1. 初始项集：S' → •S
2. 闭包操作（Closure）：
   若 A → α•Bβ 在项集中，
   则加入所有 B → •γ

3. 转移操作（Goto）：
   从项集I通过符号X到达的项集：
   Goto(I, X) = Closure({A → αX•β | A → α•Xβ ∈ I})

4. 构造状态机：
   从初始项集开始，不断应用Goto，直到无新状态

LR(1)与LALR(1)：

LR(1)：项带向前看符号，如 [E → E • + T, $]
LALR(1)：合并LR(1)的”核心”相同的状态
- 状态数从数千减少到数百
- 适合手工实现

冲突解决：

移进-归约冲突：优先级和结合性规则
归约-归约冲突：通常是文法二义性，需修改

实例：表达式文法

文法：

E → E + T | T
T → T * F | F
F → (E) | id

LR(0)项集示例（部分）：

I0:
  S' → •E
  E → •E + T
  E → •T
  T → •T * F
  T → •F
  F → •(E)
  F → •id

I1 (Goto(I0, E)):
  S' → E•
  E → E• + T

I2 (Goto(I0, id)):
  F → id•

分析表构造：

ACTION表：
- ACTION[I, a]：状态I遇到终结符a的动作（移进/归约）
GOTO表：
- GOTO[I, A]：状态I归约为非终结符A后转移的状态

分析过程（输入id + id * id）：

栈                 输入           动作
0                  id+id*id$      shift 2
0 id 2             +id*id$        reduce F→id
0 F 3              +id*id$        reduce T→F
0 T 4              +id*id$        reduce E→T
0 E 1              +id*id$        shift 5
0 E 1 + 5          id*id$         shift 2
...（继续）

🧪 实践意义：如何应用编译器技术

对语言实现者

现代工具链（受Aho和Ullman启发）：

ANTLR：
- 基于LL(*)算法（比LALR更强大）
- 自动生成词法分析器+语法分析器+树遍历器
LLVM：
- 中间表示（IR）：类似三地址码
- 优化Pass：模块化的数据流分析和变换
- 后端：可扩展到多种架构

实现步骤（设计新语言）：

定义语法（BNF范式）
用ANTLR生成解析器
构建AST（抽象语法树）
语义分析（类型检查、符号表）
生成LLVM IR
调用LLVM优化和代码生成

案例：

Swift：使用LLVM后端
Rust：语法分析手工实现，但优化基于LLVM
Julia：JIT编译基于LLVM

对工具开发者

静态分析：

SonarQube：代码质量检查
- 构建AST
- 数据流分析检测空指针、内存泄漏
ESLint：JavaScript Linter
- 语法树遍历
- 规则匹配

IDE功能：

代码补全：
- 部分解析（Incremental Parsing）
- 类型推导
重构：
- AST变换
- 符号重命名（考虑作用域）

对性能优化工程师

理解编译器如何优化代码：

循环展开：

// 原始
for (int i = 0; i < 4; i++)
    a[i] = b[i] + c[i];

// 展开后
a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
a[2] = b[2] + c[2];
a[3] = b[3] + c[3];

内联：消除函数调用开销
向量化：SIMD指令并行计算

编写”编译器友好”的代码：

避免指针别名（影响优化）
使用const、restrict提示编译器
理解内存对齐

📚 延伸阅读

书籍（Aho和Ullman的经典）

《Compilers: Principles, Techniques, and Tools》（紫龙书，2006）
- 编译原理圣经，全面系统
《Introduction to Automata Theory, Languages, and Computation》（2006，第3版）
- 形式语言与自动机，理论基础
《Foundations of Computer Science》（1992）
- 计算机科学导论，覆盖算法、数据结构、理论

工具与实践

Flex & Bison：
- 实现LEX和YACC的开源版本
- 《Flex & Bison》（O’Reilly）实践指南
LLVM：
- 现代编译器基础设施
- 《LLVM Cookbook》、官方文档
ANTLR：
- 《The Definitive ANTLR 4 Reference》

在线资源

Stanford CS143（编译原理课程）：
- 基于龙书的经典课程
Crafting Interpreters（免费在线书）：
- 从零实现解释器，适合初学者
LLVM Tutorial：
- 手把手实现编程语言

历史文献

Aho & Ullman的早期论文：
- 《The Theory of Parsing, Translation, and Compiling》
AWK原始论文（1978）：
- 《Awk — A Pattern Scanning and Processing Language》

🌟 精神遗产

Aho：“优雅的算法是可以解释清楚的算法”

理念：

算法不应是”巫术”，应该能让学生理解
好的设计兼顾理论美和工程实用

AWK的哲学：

专注于一类问题（文本处理）
语法简洁（模式-动作）
自动化繁琐（字段分割、循环）

对今天的启示：

设计工具时，考虑用户的心智模型
专注解决具体问题，而非”大而全”

Ullman：“教育是知识的最终验证”

理念：

如果不能教会学生，说明自己没真正理解
教材应该”自洽”：从基础到高级，逻辑清晰

教学实践：

每个定理都有严格证明
每个算法都有实例演示
习题从简单到挑战，巩固理解