自動(dòng)機(jī)
關(guān)于自動(dòng)機(jī)的說明，這里不不再?gòu)?fù)述，請(qǐng)到http://zh.wikipedia.org/wiki/自動(dòng)機(jī)查看。
表達(dá)式
首先，我們規(guī)定表達(dá)式中只允許輸入Char_Type和String_Type類型的字符。
template <typename Char_Type, typename String_Type>
class Rule
{
};
ε-NFA的狀態(tài)
對(duì)于一個(gè)狀態(tài)來說，我們并不需要知道他的任何信息
在上面的代碼中，為了調(diào)試方便，我為其加入了idx域，并為每個(gè)狀態(tài)分配了一個(gè)唯一的ID。
struct EpsilonNFA_State
{
#ifdef _DEBUG
uint idx;
EpsilonNFA_State()
{
idx = inc();
}
static uint inc()
{
static uint i = 0;
return i++;
}
#else
EpsilonNFA_State() {}
#endif
};
ε-NFA的邊
ε-NFA中的邊都是有向的。對(duì)于任意一條邊來說，最重要的是他的兩個(gè)端點(diǎn)是誰以及這條邊所對(duì)應(yīng)的字符集（若這條邊不是ε邊）。
struct EpsilonNFA_Edge
{
struct
{
Char_Type char_value;
String_Type string_value;
}data;
enum Edge_Type
{
TUnknown = 0,
TNot = 1,
TChar = 2,
TString = 4,
TEpsilon = 8
};
uchar edge_type;
EpsilonNFA_State* pFrom;
EpsilonNFA_State* pTo;
EpsilonNFA_Edge(EpsilonNFA_State* pFrom, EpsilonNFA_State* pTo) : edge_type(TEpsilon), pFrom(pFrom), pTo(pTo) {}
EpsilonNFA_Edge(const Char_Type& x, EpsilonNFA_State* pFrom, EpsilonNFA_State* pTo) : edge_type(TChar), pFrom(pFrom), pTo(pTo)
{
data.char_value = x;
}
EpsilonNFA_Edge(const String_Type& x, EpsilonNFA_State* pFrom, EpsilonNFA_State* pTo) : edge_type(TString), pFrom(pFrom), pTo(pTo)
{
data.string_value = x;
}
inline void negate()
{
edge_type ^= TNot;
}
inline const bool isNot()const
{
return (edge_type & TNot) == TNot;
}
inline const bool isEpsilon()const
{
return (edge_type & TEpsilon) == TEpsilon;
}
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 (isEpsilon()) return TEpsilon;
else if (isChar()) return TChar;
else if (isString()) return TString;
else return TUnknown;
}
};
有了以上兩個(gè)結(jié)構(gòu)之后，我們?yōu)镽ule添加三個(gè)成員變量
EpsilonNFA_State *pEpsilonStart, *pEpsilonEnd;
hashmap<EpsilonNFA_State*, vector<EpsilonNFA_Edge>, _hash> epsilonNFA_Edges;
pEpsilonStart和pEpsilonEnd分別表示這條表達(dá)式所對(duì)應(yīng)狀態(tài)機(jī)的start和end狀態(tài)，epsilonNFA_Edges則是以某個(gè)狀態(tài)作為key，從這個(gè)狀態(tài)到達(dá)另一個(gè)狀態(tài)所經(jīng)過的邊作為value的hash表。
生成狀態(tài)機(jī)
終于到了正題，首先，我們把所有的關(guān)系分為串聯(lián)關(guān)系、并聯(lián)關(guān)系、可選關(guān)系、0次及以上的重復(fù)關(guān)系、至少1次以上的重復(fù)關(guān)系和取反關(guān)系。下面分別介紹每種關(guān)系的ε-NFA如何來生成。（下文中若沒有指出連接邊的類型則是ε邊）
字符集
正如上文所說，字符集包括Char_Type和String_Type類型的字符，應(yīng)此生成字符集的狀態(tài)機(jī)就比較簡(jiǎn)單了，只需創(chuàng)建出兩個(gè)狀態(tài)，然后通過一條經(jīng)過這個(gè)字符集的邊將這兩個(gè)狀態(tài)按照某個(gè)方向連接，最后將一個(gè)狀態(tài)標(biāo)記為start狀態(tài)，另一個(gè)狀態(tài)標(biāo)記為end狀態(tài)即可。
Rule(const Char_Type& x, Context& context) : pDFAStart(NULL), context(context)
{
pEpsilonStart = EpsilonNFA_State_Alloc::allocate();
construct(pEpsilonStart);
pEpsilonEnd = EpsilonNFA_State_Alloc::allocate();
construct(pEpsilonEnd);
epsilonNFA_Edges[pEpsilonStart].push_back(EpsilonNFA_Edge(x, pEpsilonStart, pEpsilonEnd));
context.epsilonNFA_States.insert(pEpsilonStart);
context.epsilonNFA_States.insert(pEpsilonEnd);
}
Rule(const String_Type& x, Context& context) : pDFAStart(NULL), context(context)
{
pEpsilonStart = EpsilonNFA_State_Alloc::allocate();
construct(pEpsilonStart);
pEpsilonEnd = EpsilonNFA_State_Alloc::allocate();
construct(pEpsilonEnd);
epsilonNFA_Edges[pEpsilonStart].push_back(EpsilonNFA_Edge(x, pEpsilonStart, pEpsilonEnd));
context.epsilonNFA_States.insert(pEpsilonStart);
context.epsilonNFA_States.insert(pEpsilonEnd);
}
串聯(lián)關(guān)系
串聯(lián)關(guān)系中，只需要將前一個(gè)狀態(tài)機(jī)的end狀態(tài)通過ε邊連接到另一個(gè)狀態(tài)機(jī)的start狀態(tài)，最后將前一個(gè)狀態(tài)的start狀態(tài)標(biāo)記為新狀態(tài)機(jī)的start狀態(tài)，后一個(gè)狀態(tài)機(jī)的end狀態(tài)標(biāo)記為新狀態(tài)機(jī)的end狀態(tài)即可。
self operator+(const self& x)
{
self a = cloneEpsilonNFA(*this), b = cloneEpsilonNFA(x);
copyEpsilonNFA_Edges(b, a);
a.epsilonNFA_Edges[a.pEpsilonEnd].push_back(EpsilonNFA_Edge(a.pEpsilonEnd, b.pEpsilonStart));
a.pEpsilonEnd = b.pEpsilonEnd;
return a;
}
并聯(lián)關(guān)系
并聯(lián)關(guān)系中，需要分別新建一個(gè)start和end狀態(tài)做為新狀態(tài)機(jī)的start和end狀態(tài)，然后將新生成的start狀態(tài)分別連接到原狀態(tài)機(jī)的start狀態(tài)，原狀態(tài)機(jī)的end狀態(tài)連接到新生成的end狀態(tài)即可。
self operator|(const self& x)
{
self a = cloneEpsilonNFA(*this), b = cloneEpsilonNFA(x);
copyEpsilonNFA_Edges(b, a);
EpsilonNFA_State* _pStart = EpsilonNFA_State_Alloc::allocate();
construct(_pStart);
EpsilonNFA_State* _pEnd = EpsilonNFA_State_Alloc::allocate();
construct(_pEnd);
context.epsilonNFA_States.insert(_pStart);
context.epsilonNFA_States.insert(_pEnd);
a.epsilonNFA_Edges[_pStart].push_back(EpsilonNFA_Edge(_pStart, a.pEpsilonStart));
a.epsilonNFA_Edges[_pStart].push_back(EpsilonNFA_Edge(_pStart, b.pEpsilonStart));
a.epsilonNFA_Edges[a.pEpsilonEnd].push_back(EpsilonNFA_Edge(a.pEpsilonEnd, _pEnd));
a.epsilonNFA_Edges[b.pEpsilonEnd].push_back(EpsilonNFA_Edge(b.pEpsilonEnd, _pEnd));
a.pEpsilonStart = _pStart;
a.pEpsilonEnd = _pEnd;
return a;
}
重復(fù)關(guān)系
在正則表達(dá)式中存在形如(a)+和(a)*的兩種重復(fù)關(guān)系，對(duì)于這兩種重復(fù)關(guān)系，生成的狀態(tài)機(jī)的區(qū)別僅在于end狀態(tài)對(duì)于一次以上的重復(fù)，只需要給原狀態(tài)機(jī)添加一條從end狀態(tài)到start狀態(tài)的ε邊即可。而對(duì)于零次以上的重復(fù)，不光需要添加ε邊，同時(shí)需要將新狀態(tài)機(jī)的end狀態(tài)標(biāo)記為start狀態(tài)，因?yàn)榱愦沃貜?fù)時(shí)不需要經(jīng)過任意邊既可被接受。
self operator*()
{
self a = cloneEpsilonNFA(*this);
a.epsilonNFA_Edges.insert(EpsilonNFA_Edge(a.pEpsilonEnd, a.pEpsilonStart));
a.pEpsilonEnd = a.pEpsilonStart;
return a;
}
self operator+()
{
self a = cloneEpsilonNFA(*this);
a.epsilonNFA_Edges[a.pEpsilonEnd].push_back(EpsilonNFA_Edge(a.pEpsilonEnd, a.pEpsilonStart));
return a;
}
上面這三種是最基本的生成方法，通過以上這三種生成方法已足夠應(yīng)付多數(shù)的表達(dá)式。
一些拓展
下面來看看一些拓展形式的狀態(tài)機(jī)是如何生成的。
可選關(guān)系
在可選關(guān)系中，只需要給原狀態(tài)機(jī)添加一條從start狀態(tài)到end狀態(tài)的ε邊即可。由于ε-NFA只允許有一個(gè)start和end狀態(tài)的關(guān)系，應(yīng)此當(dāng)條件不成立時(shí)從start狀態(tài)就可直接通過ε邊到達(dá)end狀態(tài)。
inline self opt()
{
self a = cloneEpsilonNFA(*this);
a.epsilonNFA_Edges[a.pEpsilonStart].push_back(EpsilonNFA_Edge(a.pEpsilonStart, a.pEpsilonEnd));
return a;
}
取反關(guān)系
由于我們只處理Char_Type和String_Type類型的字符集，應(yīng)此對(duì)于取反我們只需要將當(dāng)前狀態(tài)機(jī)內(nèi)所有類型為TChar或TString類型的邊取一下反即可（需要注意的是可能存在負(fù)負(fù)得正的情況，既取偶數(shù)次反等于沒取反）
self operator!()
{
self a = cloneEpsilonNFA(*this);
for (typename hashmap<EpsilonNFA_State*, vector<EpsilonNFA_Edge>, _hash>::iterator i = a.epsilonNFA_Edges.begin(), m = a.epsilonNFA_Edges.end(); i != m; ++i)
{
for (typename vector<EpsilonNFA_Edge>::iterator j = i->second.begin(), n = i->second.end(); j != n; ++j)
{
if (j->isChar() || j->isString()) j->negate();
}
}
return a;
}
Char-Char關(guān)系
所謂的char-char關(guān)系就是正則表達(dá)式中的[a-z]表達(dá)式。其實(shí)這是一種并聯(lián)關(guān)系的拓展，由兩個(gè)原始狀態(tài)機(jī)拓展到了N個(gè)，生成方法也類似。
self operator-(const self& x)
{
self a = cloneEpsilonNFA(*this);
if (epsilonNFA_Edges.size() == 1 && x.epsilonNFA_Edges.size() == 1 &&
epsilonNFA_Edges.begin()->second.size() == 1 && x.epsilonNFA_Edges.begin()->second.size() == 1 &&
epsilonNFA_Edges.begin()->second.begin()->edge_type == EpsilonNFA_Edge::TChar && x.epsilonNFA_Edges.begin()->second.begin()->edge_type == EpsilonNFA_Edge::TChar)
{
EpsilonNFA_State* _pStart = EpsilonNFA_State_Alloc::allocate();
construct(_pStart);
EpsilonNFA_State* _pEnd = EpsilonNFA_State_Alloc::allocate();
construct(_pEnd);
context.epsilonNFA_States.insert(_pStart);
context.epsilonNFA_States.insert(_pEnd);
a.epsilonNFA_Edges[_pStart].push_back(EpsilonNFA_Edge(_pStart, a.pEpsilonStart));
a.epsilonNFA_Edges[a.pEpsilonEnd].push_back(EpsilonNFA_Edge(a.pEpsilonEnd, _pEnd));
const Char_Type chStart = epsilonNFA_Edges.begin()->second.begin()->data.char_value;
const Char_Type chEnd = x.epsilonNFA_Edges.begin()->second.begin()->data.char_value;
for (Char_Type ch = chStart + 1; ch < chEnd; ++ch)
{
self y(ch, context);
copyEpsilonNFA_Edges(y, a);
a.epsilonNFA_Edges[_pStart].push_back(EpsilonNFA_Edge(_pStart, y.pEpsilonStart));
a.epsilonNFA_Edges[y.pEpsilonEnd].push_back(EpsilonNFA_Edge(y.pEpsilonEnd, _pEnd));
}
self b = cloneEpsilonNFA(x);
copyEpsilonNFA_Edges(b, a);
a.epsilonNFA_Edges[_pStart].push_back(EpsilonNFA_Edge(_pStart, b.pEpsilonStart));
a.epsilonNFA_Edges[b.pEpsilonEnd].push_back(EpsilonNFA_Edge(b.pEpsilonEnd, _pEnd));
a.pEpsilonStart = _pStart;
a.pEpsilonEnd = _pEnd;
}
else
{
throw error<string>("doesn't support", __FILE__, __LINE__);
}
return a;
}
尾聲
讓我們來編寫一個(gè)函數(shù)來打印出整個(gè)生成后的狀態(tài)機(jī)。
void printEpsilonNFA()
{
printf("-------- ε- NFA Start --------\n");
for (typename hashmap<EpsilonNFA_State*, vector<EpsilonNFA_Edge>, _hash>::const_iterator i = epsilonNFA_Edges.begin(), m = epsilonNFA_Edges.end(); i != m; ++i)
{
for (typename vector<EpsilonNFA_Edge>::const_iterator j = i->second.begin(), n = i->second.end(); j != n; ++j)
{
printf("%03d -> %03d", j->pFrom->idx, j->pTo->idx);
switch (j->edgeType())
{
case EpsilonNFA_Edge::TEpsilon:
printf("(ε)");
break;
case EpsilonNFA_Edge::TChar:
printf("(%c)", j->data.char_value);
break;
case EpsilonNFA_Edge::TString:
printf("(%s)", j->data.string_value.c_str());
break;
default:
break;
}
if (j->isNot()) printf("(not)");
printf("\n");
}
}
printf("start: %03d -> end: %03d\n", pEpsilonStart->idx, pEpsilonEnd->idx);
printf("--------- ε- NFA 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));
#ifdef _DEBUG
result.printEpsilonNFA();
#endif
可打印出如下內(nèi)容
最后形成形如下圖的狀態(tài)機(jī)
完整的代碼可到http://code.google.com/p/qlanguage下載。
posted on 2013-02-15 20:29
lwch 閱讀(2891)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
QLanguage