汤普森构造法 汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机NFA的算法算法得到的NFA可以在编程中用于匹配一个正则表达式这也是正则表达式引擎实现的基本思路之一 正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式在诸如文本编辑器的高级查找和替换以及许多编程语言中人们都习惯使用正则表达式来表示字符串的匹配模式然而当计算机执行匹配程序时NFA却是更加适合的一种格式因此汤普森构造法有着重要的应用价值它实际上可以视作正则表达式到NFA的一个编译器而从理论角度上来说该算法实际上是正则表达式和NFA等价性证明的一部分事实上这两种表述形式本质上都对应着相同的语言即正则语言 在应用中算法得到的NFA可以再次通过幂集构造和最小化的过程得到一个对应的最简的确定有限状态自动机DFA进而用于匹配正则表达式但是有些情况下也会直接使用对应的NFA