Thompson · regex → NFA

Thompson construction：把 regex 编译成 NFA

一个正则表达式描述一种语言，NFA 是一台能跑的机器，Thompson construction 把两者接上：给每种算子配一块标准积木，即一小段带 ε 边、有唯一入口和唯一出口的 NFA 片段，再照 regex 的结构把积木拼起来。因为每块都只有一个入口一个出口，拼接始终只有一种操作，即把上一块的出口用 ε 边接到下一块的入口。NFA 与 ε 边的定义见 NFA 页。

1 · 四块积木

字面量：两个状态，一条读该字符的边。
连接 AB：A 的出口经 ε 边接到 B 的入口。
选择 A|B：新入口用 ε 边分叉进 A 与 B，两者出口再用 ε 边汇到新出口。
闭包 A*：新入口既能经 ε 边跳过整块，又能进 A；A 的出口能经 ε 边绕回重来，也能经 ε 边收尾。

其余算子是这四块的变体，A+ 展开为 AA*，A? 展开为 A|ε。本页支持 |、*、+、? 与括号，相邻即连接。构造先把 regex 转成 postfix 以消掉括号与优先级，再按 postfix 逐个 token 拼接片段。

图 1-1 · 从 regex 到 postfix 再到 ε-NFA 的逐步拼接。可输入任意 regex，单步观察每个 token 取出栈顶片段、拼成新片段后压回的过程。

2 · 拼出的机器直接可跑

拼完的 NFA 可以直接用 NFA 页的 subset simulation 运行。

图 2-1 · 在上一步拼出的 NFA 上试跑输入串。可输入若干串，对照它的接受与拒绝是否符合 regex 语义。

Thompson NFA 满是 ε 边，状态数约为 regex 长度的两倍。它不追求小，只追求机械可拼且结构与 regex 一一对应；要得到更高效的机器，用 subset construction 页的算法把它转成 DFA。