自動機
關于自動機的說明，這里不不再復述，請到http://zh.wikipedia.org/wiki/自動機查看。
表達式
首先，我們規定表達式中只允許輸入Char_Type和String_Type類型的字符。
template <typename Char_Type, typename String_Type>
class Rule
{
};
ε-NFA的狀態
對于一個狀態來說，我們并不需要知道他的任何信息
在上面的代碼中，為了調試方便，我為其加入了idx域，并為每個狀態分配了一個唯一的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中的邊都是有向的。對于任意一條邊來說，最重要的是他的兩個端點是誰以及這條邊所對應的字符集（若這條邊不是ε邊）。
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;
}
};
有了以上兩個結構之后，我們為Rule添加三個成員變量
EpsilonNFA_State *pEpsilonStart, *pEpsilonEnd;
hashmap<EpsilonNFA_State*, vector<EpsilonNFA_Edge>, _hash> epsilonNFA_Edges;
pEpsilonStart和pEpsilonEnd分別表示這條表達式所對應狀態機的start和end狀態，epsilonNFA_Edges則是以某個狀態作為key，從這個狀態到達另一個狀態所經過的邊作為value的hash表。
生成狀態機
終于到了正題，首先，我們把所有的關系分為串聯關系、并聯關系、可選關系、0次及以上的重復關系、至少1次以上的重復關系和取反關系。下面分別介紹每種關系的ε-NFA如何來生成。（下文中若沒有指出連接邊的類型則是ε邊）
字符集
正如上文所說，字符集包括Char_Type和String_Type類型的字符，應此生成字符集的狀態機就比較簡單了，只需創建出兩個狀態，然后通過一條經過這個字符集的邊將這兩個狀態按照某個方向連接，最后將一個狀態標記為start狀態，另一個狀態標記為end狀態即可。
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);
}
串聯關系
串聯關系中，只需要將前一個狀態機的end狀態通過ε邊連接到另一個狀態機的start狀態，最后將前一個狀態的start狀態標記為新狀態機的start狀態，后一個狀態機的end狀態標記為新狀態機的end狀態即可。
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;
}
并聯關系
并聯關系中，需要分別新建一個start和end狀態做為新狀態機的start和end狀態，然后將新生成的start狀態分別連接到原狀態機的start狀態，原狀態機的end狀態連接到新生成的end狀態即可。
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;
}
重復關系
在正則表達式中存在形如(a)+和(a)*的兩種重復關系，對于這兩種重復關系，生成的狀態機的區別僅在于end狀態對于一次以上的重復，只需要給原狀態機添加一條從end狀態到start狀態的ε邊即可。而對于零次以上的重復，不光需要添加ε邊，同時需要將新狀態機的end狀態標記為start狀態，因為零次重復時不需要經過任意邊既可被接受。
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;
}
上面這三種是最基本的生成方法，通過以上這三種生成方法已足夠應付多數的表達式。
一些拓展
下面來看看一些拓展形式的狀態機是如何生成的。
可選關系
在可選關系中，只需要給原狀態機添加一條從start狀態到end狀態的ε邊即可。由于ε-NFA只允許有一個start和end狀態的關系，應此當條件不成立時從start狀態就可直接通過ε邊到達end狀態。
inline self opt()
{
self a = cloneEpsilonNFA(*this);
a.epsilonNFA_Edges[a.pEpsilonStart].push_back(EpsilonNFA_Edge(a.pEpsilonStart, a.pEpsilonEnd));
return a;
}
取反關系
由于我們只處理Char_Type和String_Type類型的字符集，應此對于取反我們只需要將當前狀態機內所有類型為TChar或TString類型的邊取一下反即可（需要注意的是可能存在負負得正的情況，既取偶數次反等于沒取反）
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關系
所謂的char-char關系就是正則表達式中的[a-z]表達式。其實這是一種并聯關系的拓展，由兩個原始狀態機拓展到了N個，生成方法也類似。
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;
}
尾聲
讓我們來編寫一個函數來打印出整個生成后的狀態機。
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");
}
最后我們來編寫一些測試代碼來試試生成效果如何
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
可打印出如下內容
最后形成形如下圖的狀態機
完整的代碼可到http://code.google.com/p/qlanguage下載。
posted on 2013-02-15 20:29
lwch 閱讀(2959)
評論(3) 編輯 收藏 引用 所屬分類:
QLanguage