表达式
首先，我们规定表达式中只允许输入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;
}
上面这三种是最基本的生成方法，通过以上这三种生成方法已足够应付多数的表达式。
一些拓展
下面来看看一些拓展形式的状态机是如何生成的。
可选关系
