正则表达式实现（二）

离上一篇已经有近两个月的时间了，这段时间事情烦（多），导致没心情写，现在争取补上。

生成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_state通过epsilon扩展得到起始subset
start_subset <- epsilon_extend(start_state)
// 初始化subsets
subsets <- { start_subset }
// 初始化work_list
work_list <- subsets
while (!work_list.empty())
{
    subset <- work_list.pop_front()
    // 取出NFA中的每条边
    for edge in epsilon-NFA
    {
        // 对subset中的每个state通过edge所到达的
        // state的epsilon边扩展得到next_subset
        next_subset <- delta(subset, edge)

        // 如果next_subset不存在于subsets中，
        // 则把这个next_subset加入到work_list中
        if (!subsets.exist(next_subset))
            work_list.push_back(next_subset)

        // 构建subset到next_subset的边映射
        map[subset, edge] = next_subset

        // 把next_subset合并到subsets
        subsets.merge({next_subset})
    }
}

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(pre_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的最小化构造并转换成状态机。得到状态机之后，就可以使用状态机进行字符匹配了。