RE转换为NFA：Thompson算法

RE转换为NFA：Thompson算法

词法分析器生成器接受RE作为输入，并将RE转换为NFA，再将NFA转换为DFA，进一步处理得到词法分析器代码。

Thompson算法思想

它是一个递归算法：

考虑下面正则表达式的基本形式：

前面两种形式是基本形式，可以直接构造NFA：

后面三种是递归形式：

例子

(a|b)*abb