【Linux·基础篇】Shell 基础|正则表达式:从神经元模型到多流派并存(三)

前情提要：在往期文章《【Linux·基础篇】Shell 基础｜正则表达式：从神经元模型到多流派并存（二）》的结尾，我们提到克莱尼的数学符号在纸面上沉睡了许多年。它需要一个既懂数学、又需要处理文本的人来唤醒。1968 年，这个人出现了。他没有发明新的数学，只是做了一件工程师最擅长的事——把已有的理论变成真正能运行的工具。而这一步，将彻底改变正则表达式的命运。

一、1968：从纸面到代码——汤普逊与 QED

在“正则事件”被提出十几年后，克莱尼的数学符号才第一次被真正“运行”起来。

1968 年，贝尔实验室的工程师肯尼斯·蓝·汤普逊（Kenneth Lane Thompson）¹正在使用一款名为 QED（quick editor）的文本编辑器。他在一次学术阅读中接触到了克莱尼的论文，立刻意识到：这套数学符号正是他一直在寻找的文本模式匹配语法。

汤普逊动手实现了这个想法。他在 QED 编辑器中加入了一个功能：用户输入正则表达式，编辑器就能在文本中查找匹配的行。更令人惊叹的是他采用的实现技术——他将正则表达式实时编译成 IBM 7094 计算机的机器码，然后高速执行搜索。²这在当时是非常前沿的即时编译（just-in-time compilation，JIT）技术，比 Java 虚拟机中的 JIT 编译器早了二十多年。

汤普逊使用的核心算法，被称为汤普逊构造法（Thompson's construction algorithm）。它的思路是把正则表达式转换成一种叫做“非确定性有限自动机”（nondeterministic finite automata，NFA）的数学结构，然后模拟执行。³这个算法至今仍是许多高效正则引擎的理论基础。

【注 1】肯尼斯·莱恩·汤普逊（Kenneth Lane Thompson，1943—），小名肯·汤普逊（Ken Thompson），美国计算机科学家，Unix 操作系统的主要设计者，B 语言（C 语言前身）的创造者。1968 年，他首次将正则表达式实现为软件，在 QED 编辑器中加入了正则搜索功能，并发明了汤普逊构造法；此后编写了 Unix 标准编辑器 ed，1973 年从中提取出独立的 grep 命令。他与丹尼斯·麦卡利斯泰尔·里奇（Dennis MacAlistair Ritchie）共同获得 1983 年图灵奖。

【注 2】Thompson, K., "Regular Expression Search Algorithm", Communications of the ACM, Vol. 11, No. 6, June 1968, pp. 419-422.

【注 3】汤普逊构造法的核心思想：将正则表达式的每个基本元素（单个字符、连接、选择、星号）分别翻译成一个小型的状态机片段，然后像搭积木一样把这些片段拼接起来，形成完整的状态机。由于“选择”和“重复”操作会引入分叉节点（允许一个状态同时指向多个可能的下一个状态），这种状态机属于非确定性有限自动机（NFA）。汤普逊的方法之所以高效，是因为它在模拟 NFA 时同时跟踪所有可能的状态，而不是像回溯算法那样逐个尝试，从而保证了匹配时间与输入长度成正比（线性时间），不会出现性能爆炸。

二、结语：走向世界的序曲

QED 编辑器让正则表达式第一次在真正的计算机上运行起来。但汤普逊或许没有意识到，他刚刚完成的工作，很快将随着一个全新操作系统的诞生而走向世界。

此番炼器手札，炉火尚未全熄。若道友观之有趣，或可暂留此间，结一尘缘。待下回开炉铸器，新得感悟，必先与同道分享。