如何通过DFA转换表构建自己的编译器扫描器（四步法）？

本文共计3919个文字，预计阅读时间需要16分钟。

我们介绍了两种有穷自动机模型——确定性有穷自动机（DFA）和非确定性有穷自动机（NFA），以及从正规表达式经过NFA最终转化为DFA的算法。一些同学表示，理解NFA到DFA的转换过程仍有难度。

上回我们介绍了两种有穷自动机模型——确定性有穷自动机DFA和非确定性有穷自动机，以及从正则表达式经过NFA最终转化为DFA的算法。有些同学表示还是难以理解NFA到底怎么转化为DFA。所以本篇开头时我想再多举一个例子，看看NFA转化为DFA之后到底是什么样。首先我们看下面的NFA，它是从一组词法分析所用的正则表达式转换而来的。这个NFA合并了IF、ID、NUM、error这四个单词的NFA。因此，它的四个接受状态分别代表遇到了四种不同的单词。

用上一篇学到的方法，我们需要求出一个DFA，它的每个状态都是NFA状态集合的一个子集。首先我们要定义任何状态的ε-闭包，之所以叫ε-闭包，是因为它对ε转换而言是封闭的，也就是说ε-闭包内任何状态，经过ε转换之后，都还是闭包内的一个状态。接下来，从初始状态ε-闭包开始，我们要计算输入任何一种字符后，NFA所能转换到的下一个状态集合。这一步的公式是：

其中那个U型的符号，表示：对NFA状态集合d中的任何状态s，求出s在遇到符号c之后所能达到的所有状态组成的集合，再把所有这种集合求并集。最后，再对这个集合求出ε-闭包。我很难找出一种更简单的描述方式，简而言之就是要计算出NFA状态集合d，在输入符号c之后，所能达到的一切状态的新集合。而这个集合，就会变成DFA的一个状态，这个状态是从d，沿着一条标有c的边达到的。我们首先求出初始状态的ε-闭包作为DFA的初始状态，然后，我们要反复从当前已知的NFA状态集合出发，计算输入任意字符后所能达到的新状态集合，直到不能再找出新的NFA状态集合为止。