其等价DFA：
可以看到，DFA的状态都是NFA中状态的集合。
读者可以想象，其实Thompson NFA算法就是在处理其等价的DFA，不是吗？我们知道在匹配算法中，会维护一个clist和nlist，无论是clist还是nlist，不都是一组状态的集合吗？因此，Thompson算法实际上是在运行时动态构造了DFA，也就是，只在需要时构造，而不是一次性就讲NFA构造为DFA。
与其在每一步进行时动态地计算下一步该往哪走，下一步可以去往的状态是哪些，我们可以提早地将这些可能的去向、可能的状态放在缓冲区中。在这一节中，我们将展示一个不到100行的C语言算法来实现这样的操作。
为了实现缓存，我们首先引入新的数据结构来表示DFA的状态： struct DState { List l; DState *next[256]; DState *left; DState *right; }; 一个Dstate结构保存了List结构的副本（比如clist, nlist的副本），next数组保存了输入字符对应的下一个转移状态，比如d->next[c]就是在处理字符c时，d状态会转移的状态。如果d->next[c]是null，那么表示对应的转移状态还没有计算，这时我们调用Nextstate函数来计算其转移状态。 检查正则匹配的函数会重复地跟随d->next[c]的方向转移，在需要时调用nextstate函数来计算下一个状态： int match(DState *start, char *s) { int c; DState *d, *next; d = start; for(; *s; s++){ c = *s & 0xFF; if((next = d->next[c]) == NULL) next = nextstate(d, c); d = next; } return ismatch(&d->l); } 我们使用一个二叉搜索树来保存Dstate，并将list作为节点的键值。为了实现这样一棵二叉搜索树，首先将list作为参数输入，并且对list中的状态进行排序，然后将其作为键值插入二叉树中。dstate函数会返回给定list对应的dstate。（这样做的原因在于，在一些DFA中可能会有回环，遇到回环时我们可以直接在二叉树中找到，并且直接返回） DState* dstate(List *l) { int i; DState **dp, *d; static DState *alldstates; qsort(l->s, l->n, sizeof l->s[0], ptrcmp); /* look in tree for existing DState */ dp = &alldstates; while((d = *dp) != NULL){ i = listcmp(l, &d->l); if(i < 0) dp = &d->left; else if(i > 0) dp = &d->right; else return d; } /* allocate, initialize new DState */ d = malloc(sizeof *d + l->n*sizeof l->s[0]); memset(d, 0, sizeof *d); d->l.s = (State**)(d+1); memmove(d->l.s, l->s, l->n*sizeof l->s[0]); d->l.n = l->n; /* insert in tree */ *dp = d; return d; } nextstate函数调用NFA的step函数，并且返回对应的dstate： DState* nextstate(DState *d, int c) { step(&d->l, c, &l1); return d->next[c] = dstate(&l1); } 在最后，DFA的开始状态也对应与NFA的开始状态集： DState* startdstate(State *start) { return dstate(startlist(start, &l1)); } (就像NFA中的clist和nlist一样，这里的ll也是预先分配空间的list) 我们在运行时动态地构造DFA的状态，而不是一开始就将NFA对应的整个DFA计算出来。尽管一开始就构造DFA可能会匹配得快一些，不过内存消耗以及启动时间比较高。 大家可能会担心这种动态构造DFA的算法会遇到内存瓶颈，不过我们可以在缓存空间过大时直接丢弃整棵二叉树，并重新构造一颗二叉树。这种缓存策略的实现并不困难，只需要不到50行额外的内存管理代码。Source code（grep也使用了限制缓存大小的策略，其大小限制为32个state的大小，这就解释了为什么在n=28的时候，线段发生了一次跳跃，见上图） 由正则表达式转化过来的NFA会不断的计算新的状态集，由于状态集会有重复，这让缓存是值得的。遇到重复的状态时，可以直接从缓存中取出，而不用做多余的计算。真实的基于DFA的算法可以做出更多优化，让算法效率更高。我们将在下一篇文章中讨论。 现实世界中的正则表达式 在现实生产环境中，我们遇到的正则表达式会更复杂，不是我们上述提出的方案能够解决的。在这一节中，我们会讨论一些常见的复杂情况，其他更复杂的情况已超出本文范围。
字符集(character classes)：一个字符集，不论是[0-9]还是\w或事dot(.)，都只是更精确的表示了|操作。字符集可以被翻译为|然后再处理，但是在NFA中引入一个新的操作符会更精确更有效。POSIX将字符集定义为[[:upper:]]，不过其含义取决于上下文，它困难的部分在于搞清楚它的含义，而不是将其编码为NFA。
转移字符：现实开发中，正则表达式需要使用反斜杠\来转移某些操作符。