【算法】直接由正则表达式构造DFA的算法
首先说一下正则表达式的本质，顾名思义，正则表达式是一种表达式，同算术表达式一样是有基本单元（因子）加上运算符构成的一种运算系统。
算数表达式的因子是 数，而正则表达式的因子是 字符。算术表达式的基本四则运算是 +，-，*，/；而正则表达式的基本运算是 （连接），|（并），*（闭包）。由于连接省略了运算符，不太方便表示，所以以下用 ○ 表示连接。
算术表达式的结果是一个数，而正则表达式的结果是一个字符串。
抽象语法树
我们用抽象语法树来描述一个正则表达式，以便能够直观地看到该正则表达式的结构。关于抽象语法树的知识，需要的话可以另说。
简单的说，抽象语法树就是用 因子 作为叶子节点，而用运算符作为内部节点来连接叶子节点的一种树。
比如，(a|b)*abb的抽象语法树为：
上图中的数字是给字符的编号。该图应该不难看懂，看不懂的可以提出来，篇幅所限，就不多说了。
算法的推导
要构造DFA，则我们必须知道：
（1）开始时可以出现哪些符号，由于符号是有重复的，如上图中的a，而且上图中的a是不等价的，所以只能给它们赋予不同的编号来加以区分，我们也使用编号的集和来表示DFA的一个状态；
（2）接下来可以出现哪些编号；
（3）接下来的接下来可以出现哪些编号；
（4）接下来的接下来的接下来可以出现哪些编号......
（5）最后可以出现哪些编号。
OK，知道了这些，实际上就知道了DFA的所有状态，DFA的状态对应一个编号集和，以下统称 状态。
计算过程
开始状态就是抽象语法的根节点的开始编号集和，结束状态就是根节点的结束编号集和，而中间状态则是紧跟着某个状态的编号集和。
这些信息只需要一次对抽象语法树的遍历就可以求出来了。
以下称开始编号集为firstpos集，结束编号集为lastpos集，用nullable来表示一个节点是否可空，可空的意思就是会产生空串，比如正则表达式 a? 就是可空的，它可以什么都不匹配。还有一个集和是followpos集，它是编号的后跟编号的集和，比如 正则表达式 ab，由于b紧跟在a后面，所以b的编号在 followpos(a) 中。
以下是计算过程。
对于任意节点 n：
（1）如果它是 编号为 i 的叶子节点，那么
nullable(n) = false,
firstpos(n) = {i},
lastpos(n) = {i} ；
（2）如果它是一个 并节点，也就是 n = n1 | n2，那么
nullable(n) = nullable(n1) || nullable(n2)，
firstpos(n) = firstpos(n1) ∪ firstpos(n2)，
lastpos(n) = lastpos(n1) ∪ lastpos(n2)；
（3）如果它是一个 连接节点，也就是 n = n1 n2，那么
nullable(n) = nullable(n1) && nullable(n2)，
firstpos(n) = nullable(n1) ? firstpos(n1) ∪ firstpos(n2) : firstpos(n1)，
lastpos(n) = nullable(n2) ? lastpos(n1) ∪ lastpos(n2) : lastpos(n2)；
（3）如果它是一个 闭包节点，也就是 n = n1 *，那么
nullable(n) = true，
firstpos(n) = firstpos(n1)，
lastpos(n) = lastpos(n1)。
最后是followpos的计算，这个很简单，只有两种情况会使一个编号在另一个编号后面：
（1）如果n是一个连接节点，也就是 n = n1 n2，则
所有 p ∈ lastpos(n1)，有 followpos(p) = followpos(p) ∪ firstpos(n2)；
（2）如果n是一个闭包节点，也就是 n = n1 *，则
所有 p ∈ lastpos(n1)，有 followpos(p) = followpos(p) ∪ firstpos(n1)。
值得指出的是，我们需要的只有 抽象语法树的根节点的 firstpos集 以及 所有编号的follopos集，其他的都是可以舍去的临时信息。
举例分析，上图中，只有 * 节点是可空的；其他信息如下图，节点左边红色的信息是它的firstpos集，右边蓝色的信息是它的lastpos集：
它们的followpos集是：
编号 followpos
1 {1, 2, 3}
2 {1, 2, 3}
3 {4}
4 {5}
5 Φ
构造DFA
我们使用一个状态集Dstates来保存所有的状态（也就是编号集），使用一个表Dtran来表示转换，算法如下：
（1）初始化Dstates，使之只包含未标记的状态 firstpos(n0)，n0是抽象语法的根节点，未标记就是未处理过该状态的转换；
（2）
while(Dstates中存在未标记的状态S)
{
标记S;
for(每个输入符号a)
{
求出 编号集U = S中所有与a对应的编号的followpos集的并集；
if( U 不在 Dstates中)
将U作为未标记的状态加入到Dstates中；
Dtran[S, a] = U;
}
}
举例
上述例子中的开始编号集为 {1，2，3}，对应的DFA的开始状态 0 ，首先将其加入到Dstates中。
接下来，由于它未标记，所以取出它，并分析它的转换，S = {1，2，3}；
标记S；
对于符号a，S中有编号1，3和a对应，并且followpos(1) = {1, 2, 3}, followpos(3) = {4}，则
S在a上的转换 U = followpos(1) ∪ followpos(3) = {1, 2, 3, 4}；
U不在Dstates中，故将U加入Dstates，因此U就是1号状态了。
设置 Dstran[S, a] = U，也就是 Dstran[0, a] = 1。
对于符号b，S中有编号2与其对应，并且followpos(2) = {1, ,2 3}，则S在b上的转换 U = {1, 2, 3}，U已经在Dstates中了，所以不需要加入了，只需要设置 Dtran[S, b] = U，也就是
Dtran[0, b] = 0 就行了。
依次类推可以得出DFA转换表为：
状态 a b 其他
0 1 0
1 1 2
2 1 3
3 1 0 接受
其他说明
（1）抽象语法树是给人看的，实际上并不需要构造出来就可以求出所需的各种集和；
（2）可以给正则表达式连接上一个结束符来表示接受，比如说连接上一个 #，则所有在#上有转换的状态都是接受状态；
（3）参考 《编译原理》第二版（龙书）109页到114页；
（3）还请支持一下，非常感谢！
