自動機(jī)

關(guān)于自動機(jī)的說明，這里不不再復(fù)述，請到http://zh.wikipedia.org/wiki/自動機(jī)查看。

表達(dá)式

首先，我們規(guī)定表達(dá)式中只允許輸入Char_Type和String_Type類型的字符。

template <typename Char_Type, typename String_Type>
class Rule
{
};

ε-NFA的狀態(tài)

對于一個狀態(tài)來說，我們并不需要知道他的任何信息

在上面的代碼中，為了調(diào)試方便，我為其加入了idx域，并為每個狀態(tài)分配了一個唯一的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中的邊都是有向的。對于任意一條邊來說，最重要的是他的兩個端點是誰以及這條邊所對應(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;
}
};

有了以上兩個結(jié)構(gòu)之后，我們?yōu)镽ule添加三個成員變量

EpsilonNFA_State *pEpsilonStart, *pEpsilonEnd;
hashmap<EpsilonNFA_State*, vector<EpsilonNFA_Edge>, _hash> epsilonNFA_Edges;

pEpsilonStart和pEpsilonEnd分別表示這條表達(dá)式所對應(yīng)狀態(tài)機(jī)的start和end狀態(tài)，epsilonNFA_Edges則是以某個狀態(tài)作為key，從這個狀態(tài)到達(dá)另一個狀態(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ī)就比較簡單了，只需創(chuàng)建出兩個狀態(tài)，然后通過一條經(jīng)過這個字符集的邊將這兩個狀態(tài)按照某個方向連接，最后將一個狀態(tài)標(biāo)記為start狀態(tài)，另一個狀態(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)系中，只需要將前一個狀態(tài)機(jī)的end狀態(tài)通過ε邊連接到另一個狀態(tài)機(jī)的start狀態(tài)，最后將前一個狀態(tài)的start狀態(tài)標(biāo)記為新狀態(tài)機(jī)的start狀態(tài)，后一個狀態(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)系中，需要分別新建一個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)系，對于這兩種重復(fù)關(guān)系，生成的狀態(tài)機(jī)的區(qū)別僅在于end狀態(tài)對于一次以上的重復(fù)，只需要給原狀態(tài)機(jī)添加一條從end狀態(tài)到start狀態(tài)的ε邊即可。而對于零次以上的重復(fù)，不光需要添加ε邊，同時需要將新狀態(tài)機(jī)的end狀態(tài)標(biāo)記為start狀態(tài)，因為零次重復(fù)時不需要經(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只允許有一個start和end狀態(tài)的關(guān)系，應(yīng)此當(dāng)條件不成立時從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)此對于取反我們只需要將當(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á)式。其實這是一種并聯(lián)關(guān)系的拓展，由兩個原始狀態(tài)機(jī)拓展到了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;
}

尾聲

讓我們來編寫一個函數(shù)來打印出整個生成后的狀態(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");
}

最后我們來編寫一些測試代碼來試試生成效果如何

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) 評論(3) 編輯收藏引用所屬分類: QLanguage

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: QParserGenerator的文法文件介紹 QParserGenerator代碼分析二(A fix&An example) QParserGenerator代碼分析一(生成LALR1 DFA) 詞法分析器2(ε-NFA到DFA的轉(zhuǎn)換) 詞法分析器1(正則表達(dá)式到ε-NFA的轉(zhuǎn)換) 修復(fù)了一個關(guān)于CParser_Input的Bug QLanguage的AST QLanguage基本語法 ESEngine_Demo5 ESEngine_Demo4

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

自動機(jī)

表達(dá)式

ε-NFA的狀態(tài)

ε-NFA的邊

生成狀態(tài)機(jī)

字符集

串聯(lián)關(guān)系

并聯(lián)關(guān)系

重復(fù)關(guān)系

一些拓展

可選關(guān)系

取反關(guān)系

Char-Char關(guān)系

尾聲

常用鏈接

留言簿(2)

隨筆分類(92)

隨筆檔案(91)

相冊

Blogs

Projects

Redis

Websites

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜