写在前面

从源代码到可执行文件要经历几个过程：

词法分析
语法分析
语义分析
中间代码生成
代码优化

词法分析有点像中文分词，是将输入结构化的第一步：从字符串序列变为词法单元序列，它的输出将作为语法分析的输入。在词法单元中主要涉及到的概念有：

DFA：有穷确定状态机。
NFA：有穷不确定状态机。

确定和不确定的区别在于：当遇到字符的时候状态的变化是不是确定的，下面是一个NFA的例子：

NFA

对于这样一个状态机可以构造出一个转换表如下：

状态	a	b
1	{1,2}	{1}
2		{3}
3

对于DFA来说每个状态上的转换都是确定的，那么其对应的代码的样子如下：

s = s0;
c = nextChar();
while(c != eof){
    s = move(s, c); // 根据状态转换表
    c = nextChar();
}
return s in F ? "yes" : "no";

从代码上来看DFA要比NFA简单不少，那么下面接着来看。

从NFA到DFA

既然DFA看起来要比NFA用起来简单很多，那么如果能将NFA转换为DFA的话问题不就变简单了？

子集构造法是一种比较简单、直观的转化方法，既然在NFA中状态1根据字符a可以到状态1，也可以到状态2，那么如果将状态{1,2}合并看做一个节点，那得到结果不就是DFA了~

从NFA到DFA

在实际操作的时候需要用到三个集合：

ε-closure(s)：从NFA中状态s开始只通过ε得到的状态的集合。
ε-closure(T)：从T中的某个状态s开始只通过ε得到的状态的集合。
move(T, a)：从T中某个状态s开始通过a得到的状态集合。

在NFA上构造完成三个集合之后，那么可以通过如下流程进行转换：

// 在最开始Dstatus中只有ε-closure(s0)一种状态，并未未加标记
while(在Dstatus中有一个未标记的状态T){
    给T加上标记；
    for(每个输入符号a) {
        U = ε-closure(move(T, a));
        if(U 不在Dstates中)
            将U加入到Dstatus中// 不加标记
        Dtran[T, a] = U;// 转换表
    }
}

在实际上DFA和NFA的状态数都是差不多的，但是理论上转换后的DFA可能是原本的NFA状态数的指数级，(a|b)*a(a|b)^(n-1)就是这样一个例子：

DFA状态数为NFA的指数倍

从正则到NFA

很多的词法分析器都是用正则来描述规则，一般正则基本上能搞定所有的需求，而且足够简单。但是在识别输入的字符序列的时候需要用到自动机，那么就需要从正则到NFA or DFA的转换。对于正则的每种行为都有对应的NFA中的转换可以代替：

r=s|t：通过ε实现。
r=st：将s的接受状态和t的初始状态进行合并。
r=s*：将s的接受状态和初始状态相连，从而达到循环的效果。

达到的效果如下：

从正则到NFA

对于(a|b)*a这样的正则按照上面的方法得到的NFA如下：

(a|b)*a对应的NFA

有了这种方法，根据正则的AST就能很容易递归生成NFA。

从正则到DFA

DFA是比较简单的，那么在解析正则的一个思路是正则->NFA->DFA，但是这样做比较麻烦，我们肯定是希望能够直接转换。这里需要四个集合：

nullable(n)：节点n的子表达式中包含空字符串。
firstpos(n)：节点n为根的子表达式中某个串的第一个符号的位置的集合。
lastpos(n)：节点n为根的子表达式中某个串的末一个符号的位置的集合。
followpos(p)：如果L((r)#)中的某个串x=a1..an，使得我们在解释为什么x属于L((r)#)时，可以将x中的某个ai和AST中的位置p匹配，且位置ai+1和位置q匹配，那么q在该集合中。

这样看起来比较难理解，来看一个例子：

集合例子

那么对于框中的根节点来说：

nullable(n)：false。
firstpos(n)：{1,2,3}。
lastpos(n)：{3}。
followpos(1)：{1,2,3}。

这些集合可以递归得到，比如较为麻烦的followpos的计算方法如下：

如果n是一个cat节点，其左右子节点分别为c1、c2，那么对于lastpos(c1)中的每个位置i，firstpos(c2)中的所有位置都在followpos(i)中。
如果n是一个star节点，并且i是lastpos(n)中的一个位置，那么firstpos(n)中所有的位置都在followpos(i)中。

其中关键的followpos其实就是NFA中的状态转换，那么下面的正则到DFA的过程就很容易理解了：

// 构造D的状态集Dstates和D的转换函数Dtran。
初始化Dstates，使之只包含未标记状态firstpos(n0)，其中n0是(r)#的抽象语法树的根节点
while(Dstates中存在未标记状态S){
    标记S；
    for(每个输入符号a){
        令U为S中和a对应的所有位置p的followpos(p)的并集；
        if(U不在Dstates中)
            将U作为未标记的状态加入到Dstates中；
        Dtran[S,a] = U;
    }
}

在实际中DFA确实有优势，但是还有进一步优化的空间，接着往下看。