EDIT (2025-12-09): 添加了算法的生成的NFA节点与转移数量的结论的说明.

简要介绍

正则表达式Regex可以转换到NFA，然后可以直接模拟NFA或将所得NFA转换到DFA再模拟。这样就是一个完整的正则匹配引擎了。

参考博文

本文是词法分析系列第三篇文章，主要介绍从regex转换到NFA的方法。关于如何模拟运行NFA请参考下面两篇文章：

1. 直接模拟NFA：NFA的模拟运行
2. 先将NFA转换到DFA再模拟：NFA到DFA的转换算法
3. 将正则表达式转换到NFA(本文)

算法!

这个算法又被称为McNaughton-Yamada-Thompson Algorithm （好长的名字！）

INPUT: 在字符集Σ定义的正则表达式r

OUTPUT: 该正则r对应的NFA N , N 能接受 L(r) (L(x): Language of x)

算法流程:

1. 解析(拆分)输入的正则表达式r成多个不包含操作符的子表达式。

2. 按下面的方法逐个转换1)得到的子表达式转换到子NFA：

   • 如果表达式是ϵ：直接生成ϵ转移

     graph LR;
   	s(((Start))) --ϵ--> f(((f)))
   

   • 否则是在字符集Σ有定义的表达式a

     graph LR;
   	s(((Start))) --a--> f(((f)))
   

3. 按下面的方法将得到的子NFA根据子表达式之间的操作符连接起来：

   • r = s|t:

     graph LR;
   	start(((start))) --ϵ--> s{{"N(s)"}}
   	start(((start))) --ϵ--> t{{"N(t)"}}
   	s{{"N(s)"}} --ϵ--> fin(((f)))
   	t{{"N(t)"}} --ϵ--> fin(((f)))
   

   • r=st:

     graph LR;
   	start(((start))) --ϵ--> s{{"N(s)"}}
   	s{{"N(s)"}} --ϵ--> t{{"N(t)"}}
   	t{{"N(t)"}} --ϵ--> fin(((f)))
   

   • r = s*:

      graph LR;
      	start(((start))) --ϵ--> fin(((f)))
       start(((start))) --ϵ--> s{{"N(s)"}} --ϵ--> s{{"N(s)"}}
       s{{"N(s)"}} --ϵ--> fin(((f)))
   

   • r = (s): N(r) = N(s).

不太能理解为啥流程图能生成出这个样子。。上述图片去就参考Wiki好了

算法的一个重要推论

从上面我门可以很清晰的观察到, 在处理每一个操作符和操作数时(比如说,s|t, s和t是操作数, |是操作符), 我们至多创建两个新的状态 (Start和f),4个新的转移.

因此我们可以很轻易的得出一下结论(敲黑板):

仅由McNaughton-Yamada-Thompson Algorithm算法将正则表达式r转换到的NFA至多有2|r|个状态节点,4|r|个转移.

注: |r|其实就是r中操作符与操作数的数量之和.

E.O.F Ciallo～(∠・ω< )⌒★