Thompson construction：把 regex 编译成 NFA
一个正则表达式描述一种语言，而 NFA 是一台能跑的机器。Thompson construction 把两者接上：给每种 regex 算子配一块标准「积木」——一小段带 ε 边、有唯一入口和唯一出口的 NFA 片段——再照 regex 的结构把积木拼起来。因为每块都只有一个入口一个出口，拼接始终只有一种操作：「把上一块的出口用 ε 边接到下一块的入口」。NFA 与 ε 边的概念见 NFA 一页。
四块积木（其余算子是它们的变体）：
-
字面
a：两个 state，一条读a的边。 -
连接
AB:A 的出口 —ε→ B 的入口。 -
或
A|B：新入口 ε 分叉进 A、B；两者出口再 ε 汇到新出口。 -
闭包
A*：新入口既能 ε 跳过整块、又能进 A;A 的出口能 ε 绕回重来，也能 ε 收尾。
本页支持 | * + ? 与括号；相邻即连接。先把 regex 转成 postfix（后缀式）消掉括号与优先级，再按 postfix 逐个 token 把片段拼起来。
这台 NFA 可以直接运行——用 NFA 一页的 subset simulation。拼完后在下面试几个输入，看它接受 / 拒绝是否符合 regex 语义。注意 Thompson NFA 满是 ε 边、state 数量约是 regex 长度的两倍：它不追求小，只追求「机械可拼、结构对应」。要获得更高效的机器，可用 subset construction 一页的算法把它转成 DFA。