正则表达式的骨相：Thompson 构造法
写
Ken Thompson 在 1968 年的论文里提出了这个算法，核心思路很简单：正则表达式里的每个运算符（连接、选择、Kleene 闭包）都对应一个固定形状的 NFA 模板。你不需要什么全局规划，只需要对抽象语法树做一次后序遍历，把子表达式的 NFA 一块块像拼积木一样粘起来就行。
选择运算
!Thompson NFA construction
这套构造法有一个关键性质：对于长度为 n 的正则表达式，生成的 NFA 状态数最多是 2n。这意味着状态数跟模式长度线性增长，不会爆炸。代价是大量的 ε 转移——NFA 可以在不消耗任何输入的情况下在多个状态间跳动。模拟这种NFA时，你要么维护一个当前状态集合（子集构造法），要么用回溯，后者正是很多早期正则引擎指数级跑炸的根源。
所以下次写正则的时候可以多想一秒：你的模式先变成了一堆带 ε 转移的小 NFA 片段，然后才被引擎拿去跑。Thompson 把一个看似需要全局推理的问题拆成了局部拼接，这才是它最漂亮的地方。
#CS
写
grep -E 'ab+c' file 的时候，你大概不会停下来想这个模式是怎么变成机器能执行的东西的。但这条转换链其实藏着一道极其优雅的编译原理题——从正则表达式到有限自动机，中间那一步叫做 Thompson 构造法。Ken Thompson 在 1968 年的论文里提出了这个算法，核心思路很简单：正则表达式里的每个运算符（连接、选择、Kleene 闭包）都对应一个固定形状的 NFA 模板。你不需要什么全局规划，只需要对抽象语法树做一次后序遍历，把子表达式的 NFA 一块块像拼积木一样粘起来就行。
选择运算
a|b 会生成一个带 ε 转移的分叉入口和汇聚出口；Kleene 闭包 a* 则会生成一个能跳过或循环回到自身的 ε 环路。每块 NFA 都只有一个入口状态和一个出口状态，这让"拼接"操作退化为把前一块的出口和后一块的入口连线——一条边就够了，没有特殊的边界处理。!Thompson NFA construction
这套构造法有一个关键性质：对于长度为 n 的正则表达式，生成的 NFA 状态数最多是 2n。这意味着状态数跟模式长度线性增长，不会爆炸。代价是大量的 ε 转移——NFA 可以在不消耗任何输入的情况下在多个状态间跳动。模拟这种NFA时，你要么维护一个当前状态集合（子集构造法），要么用回溯，后者正是很多早期正则引擎指数级跑炸的根源。
所以下次写正则的时候可以多想一秒：你的模式先变成了一堆带 ε 转移的小 NFA 片段，然后才被引擎拿去跑。Thompson 把一个看似需要全局推理的问题拆成了局部拼接，这才是它最漂亮的地方。
#CS
