接上一篇我們已經(jīng)得到了一個(gè)完整的ε-NFA，下面來說說如何將ε-NFA轉(zhuǎn)換為DFA（確定有限自動(dòng)機(jī)）。
DFA的狀態(tài)
在DFA中，某個(gè)狀態(tài)對(duì)應(yīng)到ε-NFA中的若干狀態(tài)，應(yīng)此我們將會(huì)得到下面這樣的一個(gè)結(jié)構(gòu)。
struct DFA_State
{
set<EpsilonNFA_State*> content;
bool bFlag;
#ifdef _DEBUG
uint idx;
#endif
DFA_State(const set<EpsilonNFA_State*>& x) : content(x), bFlag(false)
{
#ifdef _DEBUG
idx = inc();
#endif
}
inline const bool operator==(const DFA_State& x)const
{
if (&x == this) return true;
return content == x.content;
}
#ifdef _DEBUG
inline uint inc()
{
static uint i = 0;
return i++;
}
#endif
};
可以看到，為了調(diào)試方便我們?cè)诮Y(jié)構(gòu)中定義了狀態(tài)的唯一ID以及對(duì)應(yīng)到ε-NFA狀態(tài)的集合和一個(gè)標(biāo)記位。
DFA的邊
根據(jù)上一篇的經(jīng)驗(yàn)，不難想到DFA的邊應(yīng)該是什么樣的，下面直接給出代碼，不做說明。
struct DFA_Edge
{
struct
{
Char_Type char_value;
String_Type string_value;
}data;
enum Edge_Type
{
TUnknown = 0,
TNot = 1,
TChar = 2,
TString = 4
};
uchar edge_type;
DFA_State* pFrom;
DFA_State* pTo;
DFA_Edge(const Char_Type& x, bool bNot, DFA_State* pFrom, DFA_State* pTo) : pFrom(pFrom), pTo(pTo)
{
data.char_value = x;
edge_type = bNot ? (TChar | TNot) : TChar;
}
DFA_Edge(const String_Type& x, bool bNot, DFA_State* pFrom, DFA_State* pTo) : pFrom(pFrom), pTo(pTo)
{
data.string_value = x;
edge_type = bNot ? (TString | TNot) : TString;
}
inline const bool isNot()const
{
return (edge_type & TNot) == TNot;
}
inline const bool isChar()const
{
return (edge_type & TChar) == TChar;
}
inline const bool isString()const
{
return (edge_type & TString) == TString;
}
const Edge_Type edgeType()const
{
if (isChar()) return TChar;
else if (isString()) return TString;
else return TUnknown;
}
const bool operator<(const DFA_Edge& x)const
{
return (ulong)pFrom + pTo < (ulong)x.pFrom + x.pTo;
}
const bool operator==(const DFA_Edge& x)const
{
return pFrom == x.pFrom && pTo == x.pTo;
}
};
由于DFA中不存在ε邊，應(yīng)此DFA將會(huì)存在若干個(gè)結(jié)束狀態(tài)，但他只有一個(gè)開始狀態(tài)
DFA_State* pDFAStart;
set<DFA_State*> pDFAEnds;
set<DFA_Edge> dfa_Edges;
為了下一步分析的高效，以后可能會(huì)將這里的dfa_Edges同樣修改為hashmap。
至此DFA所要用到的兩個(gè)結(jié)構(gòu)迅速的介紹完了。
子集構(gòu)造算法
通過各種資料，我們不難發(fā)現(xiàn)，從ε-NFA轉(zhuǎn)換到DFA的過程中，最常用就是子集構(gòu)造算法。子集構(gòu)造算法的主要思想是讓DFA的每個(gè)狀態(tài)對(duì)應(yīng)NFA的一個(gè)狀態(tài)集。這個(gè)DFA用它的狀態(tài)去記住NFA在讀輸入符號(hào)后達(dá)到的所有狀態(tài)。（引自編譯原理）其算法如下
輸入：一個(gè)NFA N。
輸出：一個(gè)接受同樣語言的DFA D。
方法：
1.求取ε-NFA初始狀態(tài)的ε閉包作為DFA的起始狀態(tài)，并將這個(gè)狀態(tài)加入集合C中，且它是未標(biāo)記的。同時(shí)記錄它的向后字符集。
2.從集合C中取出一個(gè)未被標(biāo)記的子集T和其對(duì)應(yīng)的字符集，標(biāo)記子集T。
3.使用上一步取出的字符集通過狀態(tài)轉(zhuǎn)移函數(shù)求出轉(zhuǎn)移后的狀態(tài)集M。
4.求取上一步得到的狀態(tài)集M的ε閉包U
5.如果U不在集合C中則將U作為未被標(biāo)記的子集加入C中，同時(shí)記錄它的向后字符集。檢查狀態(tài)U中是否存在NFA中的終結(jié)狀態(tài)，若存在則將狀態(tài)U加入到pDFAEnds中。
重復(fù)2，3，4，5部直至集合C中不存在未被標(biāo)記的狀態(tài)。
ε閉包
ε閉包是指從某個(gè)狀態(tài)起只經(jīng)過ε邊達(dá)到的其他狀態(tài)的集合，同時(shí)這個(gè)狀態(tài)也屬于這個(gè)集合中。其算法如下
輸入：狀態(tài)集k。
輸出：狀態(tài)集U和其所對(duì)應(yīng)的向后字符集。
方法：
1.遍歷狀態(tài)集k中的每個(gè)狀態(tài)k'。
2.若k'不存在于結(jié)果狀態(tài)集U中，將k'插入U(xiǎn)中。
3.建立一個(gè)臨時(shí)集合tmp，并將k'插入其中。
4.從臨時(shí)集合tmp中取出一個(gè)狀態(tài)p。
5.取出所有從p出發(fā)的邊，若這條邊是ε邊，且抵達(dá)狀態(tài)不在結(jié)果狀態(tài)集U中，將抵達(dá)的狀態(tài)分別插入結(jié)果狀態(tài)集U和臨時(shí)集合tmp中。若這條邊是字符集的邊且這條邊所對(duì)應(yīng)的字符不在向后字符集中，則將向后字符插入向后字符集中。
6.將狀態(tài)p從臨時(shí)集合tmp中刪除。
循環(huán)4，5，6部直至tmp中不存在任何狀態(tài)為止。
由于在生成ε-NFA時(shí)不存在只有ε邊的循環(huán)，應(yīng)此這里不會(huì)產(chǎn)生死循環(huán)。下面給出具體的代碼
void epsilonClosure(const set<EpsilonNFA_State*>& k, EpsilonClosureInfo& info)
{
for (typename set<EpsilonNFA_State*>::const_iterator i = k.begin(), m = k.end(); i != m; ++i)
{
info.states.insert(*i);
set<EpsilonNFA_State*> tmp;
tmp.insert(*i);
while (!tmp.empty())
{
EpsilonNFA_State* pState = *tmp.begin();
for (typename vector<EpsilonNFA_Edge>::const_iterator j = epsilonNFA_Edges[pState].begin(), n = epsilonNFA_Edges[pState].end(); j != n; ++j)
{
if (j->isEpsilon())
{
if (info.states.insert(j->pTo).second) tmp.insert(j->pTo);
}
else if (j->isChar()) info.chars.insert(pair<Char_Type, bool>(j->data.char_value, j->isNot()));
else if (j->isString()) info.strings.insert(pair<String_Type, bool>(j->data.string_value, j->isNot()));
}
tmp.erase(pState);
}
}
}
其中用到的EpsilonClosureInfo結(jié)構(gòu)為
struct EpsilonClosureInfo
{
set<EpsilonNFA_State*> states;
set<pair<Char_Type, bool> > chars;
set<pair<String_Type, bool> > strings;
EpsilonClosureInfo() {}
EpsilonClosureInfo(const set<EpsilonNFA_State*>& states,
const set<pair<Char_Type, bool> >& chars,
const set<pair<String_Type, bool> >& strings)
: states(states)
, chars(chars)
, strings(strings) {}
EpsilonClosureInfo(const EpsilonClosureInfo& x)
{
states = x.states;
chars = x.chars;
strings = x.strings;
}
};
需要保存的是狀態(tài)集和向后字符集。
狀態(tài)轉(zhuǎn)移函數(shù)
通過狀態(tài)轉(zhuǎn)移函數(shù)，輸入一個(gè)集合T和一個(gè)字符a將可得到所有通過T中的每一個(gè)狀態(tài)和a邊所能達(dá)到的狀態(tài)的集合。應(yīng)此代碼如下
set<EpsilonNFA_State*> move(const DFA_State& t, const Char_Type& c, bool bNot)
{
set<EpsilonNFA_State*> result;
for (typename set<EpsilonNFA_State*>::const_iterator i = t.content.begin(), m = t.content.end(); i != m; ++i)
{
for (typename vector<EpsilonNFA_Edge>::const_iterator j = epsilonNFA_Edges[*i].begin(), n = epsilonNFA_Edges[*i].end(); j != n; ++j)
{
if (j->isChar() && j->data.char_value == c && j->isNot() == bNot) result.insert(j->pTo);
}
}
return result;
}
set<EpsilonNFA_State*> move(const DFA_State& t, const String_Type& s, bool bNot)
{
set<EpsilonNFA_State*> result;
for (typename set<EpsilonNFA_State*>::const_iterator i = t.content.begin(), m = t.content.end(); i != m; ++i)
{
for (typename vector<EpsilonNFA_Edge>::const_iterator j = epsilonNFA_Edges[*i].begin(), n = epsilonNFA_Edges[*i].end(); j != n; ++j)
{
if (j->isString() && j->data.string_value == s && j->isNot() == bNot) result.insert(j->pTo);
}
}
return result;
}
為了分別支持Char_Type和String_Type的字符我們定義了兩個(gè)move函數(shù)。
最后我們給出子集構(gòu)造算法的代碼
void buildDFA()
{
set<EpsilonNFA_State*> start;
start.insert(pEpsilonStart);
typedef pair<DFA_State*, EpsilonClosureInfo> c_type;
map<size_t, list<c_type> > c;
queue<c_type> c2;
pDFAStart = DFA_State_Alloc::allocate();
EpsilonClosureInfo info;
epsilonClosure(start, info);
construct(pDFAStart, info.states);
c_type ct(pDFAStart, info);
c[info.states.size()].push_back(ct);
c2.push(ct);
if (isEndDFAStatus(pDFAStart)) pDFAEnds.insert(pDFAStart);
context.dfa_States.insert(pDFAStart);
while (!c2.empty())
{
DFA_State* t = c2.front().first;
set<pair<Char_Type, bool> > chars = c2.front().second.chars;
set<pair<String_Type, bool> > strings = c2.front().second.strings;
t->bFlag = true;
for (typename set<pair<Char_Type, bool> >::const_iterator i = chars.begin(), m = chars.end(); i != m; ++i)
{
EpsilonClosureInfo info;
epsilonClosure(move(*t, i->first, i->second), info);
DFA_State* p = getDFAState(info.states, c);
if (p) // 如果這個(gè)狀態(tài)已存在
{
dfa_Edges.insert(DFA_Edge(i->first, i->second, t, p));
}
else
{
DFA_State* pState = DFA_State_Alloc::allocate();
construct(pState, info.states);
context.dfa_States.insert(pState);
if (isEndDFAStatus(pState)) pDFAEnds.insert(pState);
c_type ct(pState, info);
c[info.states.size()].push_back(ct);
c2.push(ct);
dfa_Edges.insert(DFA_Edge(i->first, i->second, t, pState));
}
}
for (typename set<pair<String_Type, bool> >::const_iterator i = strings.begin(), m = strings.end(); i != m; ++i)
{
EpsilonClosureInfo info;
epsilonClosure(move(*t, i->first, i->second), info);
DFA_State* p = getDFAState(info.states, c);
if (p) // 如果這個(gè)狀態(tài)已存在
{
dfa_Edges.insert(DFA_Edge(i->first, i->second, t, p));
}
else
{
DFA_State* pState = DFA_State_Alloc::allocate();
construct(pState, info.states);
context.dfa_States.insert(pState);
if (isEndDFAStatus(pState)) pDFAEnds.insert(pState);
c_type ct(pState, info);
c[info.states.size()].push_back(ct);
c2.push(ct);
dfa_Edges.insert(DFA_Edge(i->first, i->second, t, pState));
}
}
c2.pop();
}
}
尾聲
同樣我們來編寫一個(gè)函數(shù)來打印出DFA。
void printDFA()
{
printf("---------- DFA Start ----------\n");
set<DFA_State*> tmp;
for (typename set<DFA_Edge>::const_iterator i = dfa_Edges.begin(), m = dfa_Edges.end(); i != m; ++i)
{
printf("%03d -> %03d", i->pFrom->idx, i->pTo->idx);
switch (i->edgeType())
{
case DFA_Edge::TChar:
printf("(%c)", i->data.char_value);
break;
case DFA_Edge::TString:
printf("(%s)", i->data.string_value.c_str());
break;
default:
break;
}
if (i->isNot()) printf("(not)");
printf("\n");
tmp.insert(i->pFrom);
tmp.insert(i->pTo);
}
printf("start: %03d -> ends: ", pDFAStart->idx);
for (typename set<DFA_State*>::const_iterator i = pDFAEnds.begin(), m = pDFAEnds.end(); i != m; ++i)
{
printf("%03d ", (*i)->idx);
}
printf("\n");
#if DEBUG_LEVEL == 3
printf("-------------------------------\n");
for (typename set<DFA_State*>::const_iterator i = tmp.begin(), m = tmp.end(); i != m; ++i)
{
printf("State: %03d\n", (*i)->idx);
for (typename set<EpsilonNFA_State*>::const_iterator j = (*i)->content.begin(), n = (*i)->content.end(); j != n; ++j)
{
printf("%03d ", (*j)->idx);
}
printf("\n");
}
#endif
printf("----------- DFA End -----------\n");
}
最后我們加入測(cè)試代碼
Rule_Type::Context context;
Rule_Type a('a', context), b('b', context), d('d', context);
Rule_Type result = (a - d).opt() + (+b | !(a + b));
result.buildDFA();
#ifdef _DEBUG
result.printEpsilonNFA();
result.printDFA();
#endif
可打印出如下內(nèi)容
畫成圖如下
完整的代碼可到http://code.google.com/p/qlanguage下載
posted on 2013-02-23 23:30
lwch 閱讀(2851)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
QLanguage