图5.13
至此，对图5.7的状态机应用DFA构造算法的流程就结束了，我们得到了图5.13的DFA，其功能与图5.7的NFA等价。在DFA中，起始状态是0，结束状态是4E。凡是包含了NFA的结束状态的DFA状态都必须是结束状态。
6、使用正则表达式构造词法分析器
判断一个字符串是否属于某规则的算法介绍到这里就结束了。回到我们一开始的问题上，我们需要使用一些规则来吧一个长的字符串断开成记号，然后计算出每一个记号对应的规则。在解决这个问题之前，我们先考察一下能够成功地被词法分析器接受的字符串应该是什么样子的。
假设我们现在有规则A、B、C和D，分别对应于四种记号类型，那么被词法分析器 接受的字符串就是A、B、C和D的任意组合，也就是(A|B|C|D)*。如果规定了输入的字符串不能为空的话，那么被词法分析器接受的字符串就是 (A|B|C|D)+。但是单纯地使用(A|B|C|D)+作为一个规则去应用在输入的字符串的话，我们只能够判断字符串是否是词法分析器能够接受的字符 串。因此我们需要对这个方法进行修改。
首先按照上文的方法，把每一个记号类型对应的规则的正则表达式转换成DFA，然后使用并联的方法将他们组合起来，但是并不使用“重复”。但是这次我们要做一点修改，我们要把新的 DFA 的每一个状态对应的规则的DFA 状态集合记住 。
这里给出一个例子，我们假设需要一个简单语言的词法分析器，规则如下：
I：[a-zA-Z_][a-zA-Z_0-9]*
N：[0-9]+
R：[0-9]+.[0-9]+
O：[=>+-*/|&]
按照规则构造出四个DFA并将它们组合起来：
图6.1
我们构造出了I|N|R|O的DFA，并且标识出了哪些状态包含了原DFA的结 束状态。这样做的一个好处是，当我们把一个字符串放进这样的一个DFA之后，我们就一直等待整个字符串被接受，或者失败。如果字符串被接受的话，我们就把 当前的结束状态记下来。如果失败的话，我们就把这个状态机在分析字符串的时候经过的最后一个结束状态记下来。这个时候，结束状态所代表的原DFA结束状态 的相应记号类型就是我们所需要的信息了。如果得不到任何结束状态的话，输入的字符串就是不背词法分析其接受的。
举个例子，使用上述状态机分析”123.ABC”。
首先从状态0开始，依次经过状态N N N 2，然后宣告失败。最后一个N(结束状态)以及当时被接受的字符串”123”被识别，结果为(N，”123”)。然后从”.ABC”开始，输入第一个记号 就失败了，于是”.”被识别为不可接受字串。最后输入”ABC”，依次经过状态0 1 I I，然后字符串结束并且被接受，于是输出(I，”ABC”)。
为什么我们在构造状态机的时候不使用“重复”呢？因为在每一个记号被识别出的时候，我们都要做一些额外的工作。如果我们使用“重复”来构造词法分析器的状态机，我们将无从知道一个记号被识别出来的确切时间。
算法到这里基本上就结束了，不过还存在一些小问题需要在细节上解决。一般来说我们给出的一些构成词法分析器的规则很少有冲突，不过偶尔会出现两个规则所代表的字符串集合存在交集的情况。有了DFA这个工具，我们可以很轻易地识别出规则冲突。
假如我们的词法分析器有A和B两个状态，那么我们构造词法分析器A|B的时候， 将会得到一些包含DFA(A)和DFA(B)的结束状态的新状态。我们只需要检查这些状态是否具有以下特征，就可以判断A和B的关系。我们假设 DFA(A)为规则A的状态机，DFA(B)为规则B的状态机，DFA(L)为词法分析器A|B的状态机：
1：如果DFA(L)存在一个或多个状态同时包含了DFA(A)和DFA(B)的结束状态，那么A和B所代表的字符串存在交集。
2：如果DFA(L)不存在同时包含了DFA(A)和DFA(B)的结束状态的状态，那么A和B所代表的字符串不存在交集。
3：如果DFA(L)的某些状态包含了DFA(A)的结束状态，并且这些状态都无一例外地包含了DFA(B)的结束状态的话，那么A是B的子集。
4：如果DFA(L)的某些状态包含了DFA(A)的结束状态，但是这些状态并没有无一例外地包含DFA(B)的结束状态的话，那么A不是B的子集。