离上一篇已经有近两个月的时间了，这段时间事情烦（多），导致没心情写，现在争取补上。
生成epsilon-NFA
epsilon-NFA是包含epsilon边（空边）的NFA，把简单正则表达式转换成epsilon-NFA的方法如下：
正则表达式：”ab” 对应的epsilon-NFA是：
正则表达式：”a|b”对应的epsilon-NFA是：
正则表达式：”a*” 对应的epsilon-NFA是：
这是最基本的3种正则表达式的NFA表示，其中a*在实际的正则表达式实现中通常生成的epsilon-NFA不是这样的，因为有下面这些正则表达式存在：
a{m} 重复a，m次
a{m,n} 重复a，m到n次
a{m,} 重复a，至少m次
a+ 重复a，至少1次
a? 重复a，0次或1次
所以对于a*表示重复至少0次的实现可以跟上面这些正则表达式采用相同方法的实现。
按照这些生成规则就可以把正则表达式转换成epsilon-NFA，我代码中即把这些生成规则实现成一个AST的visitor。
epsilon-NFA subset construction to DFA
在生成了epsilon-NFA之后，通常会有很多epsilon的边存在，也会有很多无用的state存在，所以通常需要把epsilon边消除并合并state，这个过程采用的算法是subset construction，如下：
subset construction:
start_subset <- epsilon_extend(start_state) // 把start_state通过epsilon扩展得到起始subset
subsets <- { start_subset } // 初始化subsets
work_list <- subsets // 初始化work_list
while (!work_list.empty())
{
subset <- work_list.pop_front()
for edge in epsilon-NFA // 取出NFA中的每条边
{
next_subset <- delta(subset, edge) // 对subset中的每个state通过edge所到达的state的epsilon边扩展得到next_subset
if (!subsets.exist(next_subset)) // 如果next_subset不存在于subsets中，则把这个next_subset加入到work_list中
work_list.push_back(next_subset)
map[subset, edge] = next_subset // 构建subset到next_subset的边映射
subsets.merge({next_subset}) // 把next_subset合并到subsets
}
}
delta:
next_subset <- { } // 初始化next_subset为空集合
for state in subset
{
// 取出next_state并将它通过epsilon边扩展得到的subset合并到next_subset中
next_state <- map[state, edge]
if (next_state)
next_subset.merge(epsilon_extend(next_state))
}
这里面使用了epsilon_extend，它是把一个state的所有epsilon边能到达的state构成一个集合，比如上面正则表达式a*对应的epsilon-NFA中的所有state的epsilon_extend是：
epsilon_extend(1) –> { 1 }
epsilon_extend(2) –> { 1, 2, 4 }
epsilon_extend(3) –> { 1, 3, 4 }
epsilon_extend(4) –> { 4 }
对于一个epsilon-NFA来说，每个state的epsilon_extend是固定的，因此可以对epsilon-NFA中的每个state都求出epsilon_extend并保存下来，算法如下：
epsilon_extend_construct:
work_list <- { }
// 为每个state初始化epsilon_extend集合
for state in epsilon-NFA
{
epsilon_extend(state) <- { state }
work_list.push_back(state)
}
while (!work_list.empty())
{
state <- work_list.pop_front()
state_epsilon_extend <- epsilon_extend(state)
// 把state通过epsilon所能到达的state的epsilon_extend
// 合并到当前state的epsilon_extend
for next_state in map[state, epsilon]
state_epsilon_extend.merge(epsilon_extend(next_state))
// 如果当前state的epsilon_extend变化了之后
// 把所有通过边epsilon到达state的pre_state都加入到work_list中
if (state_epsilon_extend.has_changed())
{
for pre_state in epsilon_pre(state)
work_list.push_back(state)
}
}
epsilon-NFA通过subset construction构造成完之后，并把构造的subsets中的subset转换成DFA中的state，再把NFA中除epsilon边之外的所有边都转换成DFA的边，这样就把DFA构造完成。
DFA minimization
从NFA构造完成DFA之后，这时的状态数量一般不是最少的，为了减少最终生成的状态机的状态数量，通常会对DFA的state进行最小化构造，这个算法具体如下：
minimization:
// 把所有state划分成accept的state集合和非accept的state集合
state_sets <- { {accept_state(DFA)}, {non_accept_state(DFA)} }
do
{
work_list <- state_sets
old_state_sets_size <- state_sets.size()
state_sets <- { }
for state_set in work_list
{
split_success <- false
for edge in DFA
{
// 如果edge可以把state_set拆分成两个subset，那就把新拆分出来的
// 两个subset合并到state_sets里面，并break继续work_list中取出下一个
// state_set拆分
subset1, subset2, split_success <- split(state_set, edge)
if (split_success)
{
state_sets.merge({subset1, subset2})
break
}
}
if (!split_success)
state_sets.merge({state_set})
}
} while (old_state_sets_size != state_sets.size())
这里面的split是把一个state_set按edge划分成两个subset，即对于state_set中的每一个state都通过这条边edge到达的state属于不同的state_set时就把state_set拆分成两个subset。首先把第一个state划分到subset1中，从第二个state开始通过边edge到达的state所属的state_set和第一个state通过边edge到达的state所属的state_set为同一个的时候，把这个state划分到subset1中，否则划分到subset2中。
这个算法就这样依次把最初的两个state_set（accept的state组成的set和非accept的state组成的set）划分到不能再划分为止，此时就把能合并的state都合并到了同一个state_set中，这时只需要把每个state_set转换成最终状态机中的state，即可完成DFA的最小化构造并转换成状态机。得到状态机之后，就可以使用状态机进行字符匹配了。