NFA状态图设计到很多的空串驱动，无论是刚开始学还是一段时间没看，都会搞不清楚，以此文作为记录
NFA其实核心就是三种状态
r=s|t
r=st
r=s*
方法
其余的所有表达式都是以上三种的集合，所以我们要做的，是两点
1、记清楚三种表达式
2、区别清楚搭配的时候哪个状态和哪个状态是一致的
我们来看例子
r=(s|t)*
这显然是其中两种的组合，括号优先，我们先画括号里面,同时也分析外面
可以发现，下面的0和5作为s|t最外层的始末状态，就是(s|t)最内层的始末状态，所以两者相对应合成一个
再来一个稍难的
( <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ|a)b*
可以看到这是 r=s|t 与r=s的合体
如图所示，本来1状态时初始状态，但是加了括号之后，他成为( <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ|a)的内部初始状态，而不是整个表达式的初始状态
同时6状态作为( <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ|a)的结束状态，是无缝成为b的开始状态的，因为6状态对于b来说是“其他状态的结束状态，或者是b的外部开始状态”，然后通过空串驱动而来，b的核心状态时7和8，9是“b*的外部结束状态”，所以也可作为其他状态的开始状态
总结一下 任何表达式的开始状态和结束状态都可以直接使用 r=s*的开始状态和结束状态
当然了，上式其实是可以化简的，注意到1，2，3，6之间的驱动都是 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ
两者对比如上，由于 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ直接化简，两者也不需要通过 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ驱动来区分，2，4，状态也将省略
接下来是将NFA转换为DFA的过程，需要求出闭包
NFA的状态集对应一个DFA的状态，画表，然后绘制DFA，最后再最小化DFA的状态数量，即可画出一个DFA
这就是词法分析器的核心思想
京公网安备 11010502036488号