Home | 2013-09-01

正则表达式实现(二)

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

生成epsilon-NFA

epsilon-NFA是包含epsilon边(空边)的NFA,把简单正则表达式转换成epsilon-NFA的方法如下:

正则表达式:ab 对应的epsilon-NFA是:

concat

正则表达式:a|b对应的epsilon-NFA是:

alternation

正则表达式:a* 对应的epsilon-NFA是:

closure

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