離上一篇已經(jīng)有近兩個(gè)月的時(shí)間了，這段時(shí)間事情煩（多），導(dǎo)致沒(méi)心情寫，現(xiàn)在爭(zhēng)取補(bǔ)上。
生成epsilon-NFA
epsilon-NFA是包含epsilon邊（空邊）的NFA，把簡(jiǎn)單正則表達(dá)式轉(zhuǎn)換成epsilon-NFA的方法如下：
正則表達(dá)式：”ab” 對(duì)應(yīng)的epsilon-NFA是：
正則表達(dá)式：”a|b”對(duì)應(yīng)的epsilon-NFA是：
正則表達(dá)式：”a*” 對(duì)應(yīng)的epsilon-NFA是：
這是最基本的3種正則表達(dá)式的NFA表示，其中a*在實(shí)際的正則表達(dá)式實(shí)現(xiàn)中通常生成的epsilon-NFA不是這樣的，因?yàn)橛邢旅孢@些正則表達(dá)式存在：
a{m} 重復(fù)a，m次
a{m,n} 重復(fù)a，m到n次
a{m,} 重復(fù)a，至少m次
a+ 重復(fù)a，至少1次
a? 重復(fù)a，0次或1次
所以對(duì)于a*表示重復(fù)至少0次的實(shí)現(xiàn)可以跟上面這些正則表達(dá)式采用相同方法的實(shí)現(xiàn)。
按照這些生成規(guī)則就可以把正則表達(dá)式轉(zhuǎn)換成epsilon-NFA，我代碼中即把這些生成規(guī)則實(shí)現(xiàn)成一個(gè)AST的visitor。
epsilon-NFA subset construction to DFA
在生成了epsilon-NFA之后，通常會(huì)有很多epsilon的邊存在，也會(huì)有很多無(wú)用的state存在，所以通常需要把epsilon邊消除并合并state，這個(gè)過(guò)程采用的算法是subset construction，如下：
subset construction:
start_subset <- epsilon_extend(start_state) // 把start_state通過(guò)epsilon擴(kuò)展得到起始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) // 對(duì)subset中的每個(gè)state通過(guò)edge所到達(dá)的state的epsilon邊擴(kuò)展得到next_subset
if (!subsets.exist(next_subset)) // 如果next_subset不存在于subsets中，則把這個(gè)next_subset加入到work_list中
work_list.push_back(next_subset)
map[subset, edge] = next_subset // 構(gòu)建subset到next_subset的邊映射
subsets.merge({next_subset}) // 把next_subset合并到subsets
}
}
delta:
next_subset <- { } // 初始化next_subset為空集合
for state in subset
{
// 取出next_state并將它通過(guò)epsilon邊擴(kuò)展得到的subset合并到next_subset中
next_state <- map[state, edge]
if (next_state)
next_subset.merge(epsilon_extend(next_state))
}
這里面使用了epsilon_extend，它是把一個(gè)state的所有epsilon邊能到達(dá)的state構(gòu)成一個(gè)集合，比如上面正則表達(dá)式a*對(duì)應(yīng)的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 }
對(duì)于一個(gè)epsilon-NFA來(lái)說(shuō)，每個(gè)state的epsilon_extend是固定的，因此可以對(duì)epsilon-NFA中的每個(gè)state都求出epsilon_extend并保存下來(lái)，算法如下：
epsilon_extend_construct:
work_list <- { }
// 為每個(gè)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通過(guò)epsilon所能到達(dá)的state的epsilon_extend
// 合并到當(dāng)前state的epsilon_extend
for next_state in map[state, epsilon]
state_epsilon_extend.merge(epsilon_extend(next_state))
// 如果當(dāng)前state的epsilon_extend變化了之后
// 把所有通過(guò)邊epsilon到達(dá)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通過(guò)subset construction構(gòu)造成完之后，并把構(gòu)造的subsets中的subset轉(zhuǎn)換成DFA中的state，再把NFA中除epsilon邊之外的所有邊都轉(zhuǎn)換成DFA的邊，這樣就把DFA構(gòu)造完成。
DFA minimization
從NFA構(gòu)造完成DFA之后，這時(shí)的狀態(tài)數(shù)量一般不是最少的，為了減少最終生成的狀態(tài)機(jī)的狀態(tài)數(shù)量，通常會(huì)對(duì)DFA的state進(jìn)行最小化構(gòu)造，這個(gè)算法具體如下：
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拆分成兩個(gè)subset，那就把新拆分出來(lái)的
// 兩個(gè)subset合并到state_sets里面，并break繼續(xù)work_list中取出下一個(gè)
// 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是把一個(gè)state_set按edge劃分成兩個(gè)subset，即對(duì)于state_set中的每一個(gè)state都通過(guò)這條邊edge到達(dá)的state屬于不同的state_set時(shí)就把state_set拆分成兩個(gè)subset。首先把第一個(gè)state劃分到subset1中，從第二個(gè)state開始通過(guò)邊edge到達(dá)的state所屬的state_set和第一個(gè)state通過(guò)邊edge到達(dá)的state所屬的state_set為同一個(gè)的時(shí)候，把這個(gè)state劃分到subset1中，否則劃分到subset2中。
這個(gè)算法就這樣依次把最初的兩個(gè)state_set（accept的state組成的set和非accept的state組成的set）劃分到不能再劃分為止，此時(shí)就把能合并的state都合并到了同一個(gè)state_set中，這時(shí)只需要把每個(gè)state_set轉(zhuǎn)換成最終狀態(tài)機(jī)中的state，即可完成DFA的最小化構(gòu)造并轉(zhuǎn)換成狀態(tài)機(jī)。得到狀態(tài)機(jī)之后，就可以使用狀態(tài)機(jī)進(jìn)行字符匹配了。