引言

根据预告，这篇我们对“?”“+”“*”进行处理，实现对重复的支持。“x?”匹配0个或1个“x”，“x+”匹配1到任意个“x”，“x*”匹配0到任意个“x”。

有了重复，就有贪婪模式和非贪婪模式。在贪婪模式下，“x+”匹配“xxxyyy”中的“xxx”；在非贪婪模式下，“x+”匹配“xxxyyy”中的第一个“x”。为了区别两种模式，按照通常的语法，我们在重复控制符号后面加一个“?”表示非贪婪模式，不加默认贪婪模式。现在，有效的语法有“x?”“x??”“x+”“x+?”“x*”“x*?”。

那么，“x”可以是什么呢？重复符号的优先级挺高的，到目前为止，“x”可以是单个字符，也可以是中括号表达是，也可以是小括号括起来的表达式。

下面，我们进行语法分析。

语法分析

文法介绍

还是回顾一下上次的文法：

Expr -> ExprNoOr { "|" ExprNoOr }

ExprNoOr -> ExprNoGroup { "(" Expr ")" ExprNoGroup }

ExprNoGroup -> ExprNoCollection { "[" ExprCollection "]" ExprNoCollection }

ExprCollection -> [ "^" ] { OrdinaryChar | OrdinaryChar "-" OrdinaryChar }

ExprNoCollection -> { OrdinaryChar }

从上面的结构看，重复符号可以加在 ExprNoCollection 的每一个字符后面，也可以加在 ExprNoGroup 里的中括号表达式后面，也可以加在 ExprNoOr 的小括号表达式后面。不过这样看上去有点乱，我们整理一下，换种写法：

Expr -> SubExpr { "|" SubExpr }

SubExpr -> { Phrase }

Phrase -> Word [ Repeater ]

Repeater -> ( "?" | "+" | "*" ) [ "?" ]

Word -> OrdinaryChar | "[" Collection "]" | "(" Expr ")"

Collection -> [ "^" ] { OrdinaryChar | OrdinaryChar "-" OrdinaryChar }

OrdinaryChar -> All ordinary characters

首先，我们把由“|”分开的各个部分称为SubExpr，SubExpr由很多Phrase构成，每个Phrase由一个Word以及可能存在的Repeater构成，Word分为三种，普通字符、中括号表达式、小括号表达式。

首先，不考虑Repeater部分，即：

Phrase -> Word

我们把现有代码调整一下，使得符合文法表述的结构，然后再添加Repeater部分。

结构调整

调整现有代码不详细解释了，纯贴代码（不含Repeater处理哦）：

StateMachine::NodePtr ParseExpr(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pCurrent = ParseSubExpr(pNode);

if (pCurrent == nullptr)

{

return nullptr;

}

while (true)

{

Token token = LookAhead();

if (token.type != TT_VerticalBar)

{

Backward(token);

return pCurrent;

}

StateMachine::NodePtr pNewNode = ParseSubExpr(pNode);

StateMachine::EdgePtr pEdge = NewEdge();

m_spStateMachine->AddEdge(pEdge, pNewNode, pCurrent);

}

return nullptr;

}

StateMachine::NodePtr ParseSubExpr(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pCurrent = pNode;

while (true)

{

StateMachine::NodePtr pNewNode = ParsePhrase(pCurrent);

if (pNewNode == pCurrent || pNewNode == nullptr)

{

return pNewNode;

}

pCurrent = pNewNode;

}

return nullptr;

}

StateMachine::NodePtr ParsePhrase(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pCurrent = ParseWord(pNode);

if (pCurrent == nullptr)

{

return nullptr;

}

// TODO: Parse Repeater

return pCurrent;

}

StateMachine::NodePtr ParseWord(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pCurrent = pNode;

Token token = LookAhead();

switch (token.type)

{

case TT_OpenParen:

{

pCurrent = ParseExpr(pCurrent);

if (pCurrent == nullptr)

{

return nullptr;

}

token = LookAhead();

if (token.type != TT_CloseParen)

{

return nullptr;

}

break;

case TT_OpenBracket:

{

pCurrent = ParseCollection(pCurrent);

if (pCurrent == nullptr)

{

return nullptr;

}

token = LookAhead();

if (token.type != TT_CloseBracket)

{

return nullptr;

}

break;

case TT_OrdinaryChar:

{

pCurrent = AddNormalNode(pCurrent, token.ch);

if (pCurrent == nullptr)

{

return nullptr;

}

break;

default:

Backward(token);

return pCurrent;

}

return pCurrent;

}

StateMachine::NodePtr ParseCollection(StateMachine::NodePtr pNode)

{

bool bFirst = true;

bool bInHyphen = false;

bool bAcceptHyphen = false;

Char chLastChar = 0;

bool bOpposite = false;

IntervalSet<Char> is;

bool bContinue = true;

while (bContinue)

{

Token token = LookAhead();

switch (token.type)

{

case TT_Caret:

{

if (!bFirst)

{

return nullptr;

}

else

{

bOpposite = true;

}

break;

case TT_Hyphen:

{

if (bInHyphen || !bAcceptHyphen)

{

return nullptr;

}

else

{

bInHyphen = true;

}

break;

case TT_OrdinaryChar:

{

if (bInHyphen)

{

is.Union(Interval<Char>(chLastChar, token.ch));

bInHyphen = false;

bAcceptHyphen = false;

}

else

{

is.Union(Interval<Char>(token.ch, token.ch));

chLastChar = token.ch;

bAcceptHyphen = true;

}

break;

default:

{

Backward(token);

bContinue = false;

}

break;

}

bFirst = false;

}

if (bOpposite)

{

IntervalSet<Char> u;

u.Union(Interval<Char>(0, -1));

is = u.Exclude(is);

is.MakeClose(1);

}

StateMachine::NodePtr pCurrent = pNode;

if (is.IsEmpty())

{

return pCurrent;

}

pCurrent = NewNode();

Set<Interval<Char>> intervals = is.GetIntervals();

for (auto it = intervals.Begin(); it != intervals.End(); ++it)

{

StateMachine::EdgePtr pEdge = NewEdge(it->left, it->right);

m_spStateMachine->AddEdge(pEdge, pNode, pCurrent);

}

m_spStateMachine->AddNode(pCurrent);

return pCurrent;

}

改完以后，我们考虑怎样添加对重复的支持。

状态机

我们举个简单的例子——构造正则表达式“ab?c”的状态机。

首先不考虑最后的“+”，画出“abc”的状态机，这当然很简单：

状态1后，如果遇到字符b，现在直接指向了节点2，匹配了一次b。如何不匹配b呢？没错，从1直接跳到2，增加ε边：

再来考虑“ab+c”，也很明显，添加从2回到1的ε边：

再结合上面两个，就有了“ab*c”：

……不对！！！两条ε边死循环了！

可以考虑增加一些辅助节点解开这个死结：

同时把前两个也重画。“ab+c”：

“ab?c”：

可以看出一点规律：

节点2是重复单元的开始，节点3是重复单元的结束，中间如果是括，那么可能有很多节点，这些我们都不管，不影响重复的表达。0次开始的，就从节点1向节点4连一条ε边，跳过整个循环部分；1次开始的，就从节点3向节点4连一条ε边；有任意次重复的，从节点3向节点2连一条ε边。

虽然这里使用了超多的ε边，去掉它们会使状态机显得更加简洁。不过为了规律性更强，这些ε边我们都保留。

最后，说说关于贪婪和非贪婪的处理。这部分在@vczh的《构造正则表达式引擎》里也介绍过。它依赖于实现状态机的图的节点指针存储顺序。我们来看一下状态机的节点结构：

template <typename NodeData, typename EdgeData>

struct GraphNode

{

typedef GraphEdge<EdgeData, NodeData> EdgeType;

NodeData tValue;

Array<EdgeType *> arrPrevious;

Array<EdgeType *> arrNext;

// ...

};

其中NodeData和EdgeData是在正则表达式这边传递的节点数据和边数据的结构，图这边有序地保存了流出节点的各条边。而我们在匹配的时候，也是按保存的顺序进行遍历的，谁在前，谁就先得到尝试的机会。

所以，对于“ab?c”和“ab*c”，贪婪和非贪婪取决于流出状态1的两条ε边的顺序，如果是先到状态2，便是贪婪，如果先到状态4，便是非贪婪。对于“ab+c”，取决于流出状态3的两条ε边的顺序，如果是先到状态2，便是贪婪，如果先到状态4，便是非贪婪。

代码实现

代码主要修改是ParsePhrase部分，以及增加的ParseRepeater。ParsePhrase目前代码如下：

StateMachine::NodePtr ParsePhrase(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pCurrent = ParseWord(pNode);

if (pCurrent == nullptr)

{

return nullptr;

}

// TODO: Parse Repeater

return pCurrent;

}

开始部分先改成：

StateMachine::NodePtr ParsePhrase(StateMachine::NodePtr pNode)

{

StateMachine::NodePtr pFrom = NewNode();

StateMachine::NodePtr pCurrent = ParseWord(pFrom);

if (pCurrent == nullptr)

{

delete pFrom;

return nullptr;

}

if (pCurrent == pFrom)

{

delete pFrom;

return pNode;

}

// TODO: Parse Repeater

Repeator r = ParseRepeater();

这里先新建了一个pFrom，也就是上面一节状态机图的节点2，作为重复部分的开始，方便之后如果要从状态1（pNode）添加不同顺序的ε边（pNode到pFrom最多只有两条边，仅用来区分贪婪和非贪婪）。解析完Word后，尝试读入Repeater。

Repeater结构定义如下：

enum RepeatorType

{

RT_None,

RT_ZeroOrOne,

RT_OnePlus,

RT_ZeroPlus

};

struct Repeator

{

RepeatorType type;

bool bGreedy;

Repeator()

: type(RT_None), bGreedy(true)

{

}

};

RT_None表示没有Repeater，后面三种分别是“?”“+”“*”的效果。然后bGreedy表示是否贪婪模式，默认是，如果读到了额外的“?”，就设为非贪婪模式。ParseRepeater代码如下：

Repeator ParseRepeater()

{

Repeator r;

Token token = LookAhead();

switch (token.type)

{

case TT_QuestionMark:

r.type = RT_ZeroOrOne;

break;

case TT_Plus:

r.type = RT_OnePlus;

break;

case TT_Star:

r.type = RT_ZeroPlus;

break;

default:

Backward(token);

break;

}

bool bGreedy = true;

if (r.type != RT_None)

{

token = LookAhead();

if (token.type == TT_QuestionMark)

{

r.bGreedy = false;

}

else

{

Backward(token);

}

return r;

}

其中新增的“?”“+”“*”已经添加到单词定义以及词法分析分析函数了。

最后回到ParsePhrase的后半部分：

Repeator r = ParseRepeater();

switch (r.type)

{

case RT_None:

{

m_spStateMachine->AddNode(pFrom);

StateMachine::EdgePtr pEdge = NewEdge();

m_spStateMachine->AddEdge(pEdge, pNode, pFrom);

}

break;

case RT_ZeroOrOne:

{

m_spStateMachine->AddNode(pFrom);

StateMachine::EdgePtr pEdgeNodeToFrom = NewEdge();

StateMachine::EdgePtr pEdgeNodeToCurrent = NewEdge();

if (r.bGreedy)

{

m_spStateMachine->AddEdge(pEdgeNodeToFrom, pNode, pFrom);

m_spStateMachine->AddEdge(pEdgeNodeToCurrent, pNode, pCurrent);

}

else

{

m_spStateMachine->AddEdge(pEdgeNodeToCurrent, pNode, pCurrent);

m_spStateMachine->AddEdge(pEdgeNodeToFrom, pNode, pFrom);

}

break;

case RT_OnePlus:

{

StateMachine::NodePtr pTo = NewNode();

m_spStateMachine->AddNode(pFrom);

m_spStateMachine->AddNode(pTo);

StateMachine::EdgePtr pEdgeNodeToFrom = NewEdge();

m_spStateMachine->AddEdge(pEdgeNodeToFrom, pNode, pFrom);

StateMachine::EdgePtr pEdgeCurrentToFrom = NewEdge();

StateMachine::EdgePtr pEdgeCurrentToTo = NewEdge();

if (r.bGreedy)

{

m_spStateMachine->AddEdge(pEdgeCurrentToFrom, pCurrent, pFrom);

m_spStateMachine->AddEdge(pEdgeCurrentToTo, pCurrent, pTo);

}

else

{

m_spStateMachine->AddEdge(pEdgeCurrentToTo, pCurrent, pTo);

m_spStateMachine->AddEdge(pEdgeCurrentToFrom, pCurrent, pFrom);

}

pCurrent = pTo;

}

break;

case RT_ZeroPlus:

{

StateMachine::NodePtr pTo = NewNode();

m_spStateMachine->AddNode(pFrom);

m_spStateMachine->AddNode(pTo);

StateMachine::EdgePtr pEdgeCurrentToNode = NewEdge();

m_spStateMachine->AddEdge(pEdgeCurrentToNode, pCurrent, pNode);

StateMachine::EdgePtr pEdgeNodeToFrom = NewEdge();

StateMachine::EdgePtr pEdgeNodeToTo = NewEdge();

if (r.bGreedy)

{

m_spStateMachine->AddEdge(pEdgeNodeToFrom, pNode, pFrom);

m_spStateMachine->AddEdge(pEdgeNodeToTo, pNode, pTo);

}

else

{

m_spStateMachine->AddEdge(pEdgeNodeToTo, pNode, pTo);

m_spStateMachine->AddEdge(pEdgeNodeToFrom, pNode, pFrom);

}

pCurrent = pTo;

}

break;

default:

break;

}

return pCurrent;

}

根据三种不同的Repeater，使用不同的连接方法连状态机节点，bGready影响某两条关键的边的顺序。这里不做过多解释，该解释的都在上一节解释过了。

由于我们引入了贪婪和非贪婪的概念，匹配检验函数Match必然需要支持部分匹配字符串，不然就没法区分两种模式。原先为了方便起见，都是对整个字符串进行匹配的。我们将Match系列函数修改成下面这个样子：

bool Match(const String &s, int *pnPos = nullptr)

{

return Match(s, 0, m_pBegin, pnPos);

}

bool Match(const String &s, int i, StateMachine::NodePtr pNode, int *pnPos = nullptr)

{

if (pNode == m_pEnd)

{

if (pnPos != nullptr)

{

*pnPos = i;

return true;

}

if (i < s.Length())

{

return false;

}

return true;

}

for (auto it = pNode->arrNext.Begin(); it != pNode->arrNext.End(); ++it)

{

if (Match(s, i, *it, pnPos))

{

return true;

}

return false;

}

bool Match(const String &s, int i, StateMachine::EdgePtr pEdge, int *pnPos = nullptr)

{

if (!pEdge->tValue.bEpsilon)

{

if (i >= s.Length())

{

return false;

}

if (!pEdge->tValue.Match(s[i]))

{

return false;

}

return Match(s, i + 1, pEdge->pNext, pnPos);

}

else

{

return Match(s, i, pEdge->pNext, pnPos);

}

新增参数int *pnPos，返回匹配结束后第一个未匹配的字符位置，也就是已匹配的字符数。如果pnPos非空，那么支持部分匹配，返回匹配成功的位置；如果pn为空，还是跟原先一样，进行全字符串匹配。

单元测试

首先跑一下现有的所有case，应该能通过。然后增加几个对pnPos的case：

RegExp r;

int nPos = 0;

XL_TEST_ASSERT(r.Parse(L"[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]"));

XL_TEST_ASSERT(!r.Match(L"256"));

XL_TEST_ASSERT(!r.Match(L"260"));

XL_TEST_ASSERT(!r.Match(L"300"));

XL_TEST_ASSERT(r.Match(L"256", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"260", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"300", &nPos) && nPos == 2);

后三则通不过。原因是0-255的正则表达式在部分匹配的时候有问题。由于正则表达式“[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]”将1位数“[0-9]”放到最前面，使得所有数字都只匹配了第一个就结束了。改正为先写三位数，后写两位数，最后写一位数：“[01][0-9][0-9]|2[0-4][0-9]|25[0-5]|[0-9][0-9]|[0-9]”。所有的“|”子式之间，如果有包含关系，或者有部分重叠，使用的时候就需要考虑顺序，这跟贪婪、非贪婪的道理是一样的。

然后尝试添加针对新功能的case。IPv4地址由于后面重复是3次，本次我们并没有支持计次重复“x{m,n}”，所以没法应用。

写几个土土的case吧：

XL_TEST_CASE()

{

RegExp r;

int nPos = 0;

XL_TEST_ASSERT(!r.Parse(L"?"));

XL_TEST_ASSERT(!r.Parse(L"+"));

XL_TEST_ASSERT(!r.Parse(L"*"));

XL_TEST_ASSERT(!r.Parse(L"??"));

XL_TEST_ASSERT(!r.Parse(L"+?"));

XL_TEST_ASSERT(!r.Parse(L"*?"));

XL_TEST_ASSERT(r.Parse(L"a?"));

XL_TEST_ASSERT(r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(!r.Match(L"aa"));

XL_TEST_ASSERT(r.Match(L"", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Parse(L"a??"));

XL_TEST_ASSERT(r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(!r.Match(L"aa"));

XL_TEST_ASSERT(r.Parse(L"a??"));

XL_TEST_ASSERT(r.Match(L"", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Parse(L"a+"));

XL_TEST_ASSERT(!r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(r.Match(L"aa"));

XL_TEST_ASSERT(r.Match(L"aaa"));

XL_TEST_ASSERT(!r.Match(L"", &nPos));

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"aaa", &nPos) && nPos == 3);

XL_TEST_ASSERT(r.Parse(L"a+?"));

XL_TEST_ASSERT(!r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(r.Match(L"aa"));

XL_TEST_ASSERT(r.Match(L"aaa"));

XL_TEST_ASSERT(!r.Match(L"", &nPos));

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Match(L"aaa", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Parse(L"a*"));

XL_TEST_ASSERT(r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(r.Match(L"aa"));

XL_TEST_ASSERT(r.Match(L"aaa"));

XL_TEST_ASSERT(r.Match(L"", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 1);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"aaa", &nPos) && nPos == 3);

XL_TEST_ASSERT(r.Parse(L"a*?"));

XL_TEST_ASSERT(r.Match(L""));

XL_TEST_ASSERT(r.Match(L"a"));

XL_TEST_ASSERT(r.Match(L"aa"));

XL_TEST_ASSERT(r.Match(L"aaa"));

XL_TEST_ASSERT(r.Match(L"", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"a", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"aa", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Match(L"aaa", &nPos) && nPos == 0);

XL_TEST_ASSERT(r.Parse(L"w1+"));

XL_TEST_ASSERT(!r.Match(L""));

XL_TEST_ASSERT(!r.Match(L"w"));

XL_TEST_ASSERT(r.Match(L"w1"));

XL_TEST_ASSERT(r.Match(L"w11"));

XL_TEST_ASSERT(r.Match(L"w111"));

XL_TEST_ASSERT(r.Match(L"w1111"));

XL_TEST_ASSERT(r.Match(L"w11111"));

XL_TEST_ASSERT(!r.Match(L"", &nPos));

XL_TEST_ASSERT(!r.Match(L"w", &nPos));

XL_TEST_ASSERT(r.Match(L"w1", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"w11", &nPos) && nPos == 3);

XL_TEST_ASSERT(r.Match(L"w111", &nPos) && nPos == 4);

XL_TEST_ASSERT(r.Match(L"w1111", &nPos) && nPos == 5);

XL_TEST_ASSERT(r.Match(L"w11111", &nPos) && nPos == 6);

XL_TEST_ASSERT(r.Parse(L"w1+?"));

XL_TEST_ASSERT(!r.Match(L""));

XL_TEST_ASSERT(!r.Match(L"w"));

XL_TEST_ASSERT(r.Match(L"w1"));

XL_TEST_ASSERT(r.Match(L"w11"));

XL_TEST_ASSERT(r.Match(L"w111"));

XL_TEST_ASSERT(r.Match(L"w1111"));

XL_TEST_ASSERT(r.Match(L"w11111"));

XL_TEST_ASSERT(!r.Match(L"", &nPos));

XL_TEST_ASSERT(!r.Match(L"w", &nPos));

XL_TEST_ASSERT(r.Match(L"w1", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"w11", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"w111", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"w1111", &nPos) && nPos == 2);

XL_TEST_ASSERT(r.Match(L"w11111", &nPos) && nPos == 2);

}

或许可以尝试匹配URL：

XL_TEST_CASE()

{

RegExp r;

XL_TEST_ASSERT(r.Parse(L"http://([a-zA-Z0-9\\-]+.)+[a-zA-Z]+/"));

XL_TEST_ASSERT(r.Match(L"http://streamlet.org/"));

XL_TEST_ASSERT(r.Match(L"http://www.streamlet.org/"));

XL_TEST_ASSERT(r.Match(L"http://www.1-2.streamlet.org/"));

XL_TEST_ASSERT(r.Match(L"http://www.1-2.3-4.streamlet.org/"));

XL_TEST_ASSERT(!r.Match(L"http://org/"));

XL_TEST_ASSERT(!r.Match(L"http://streamlet.o-g/"));

}

小结

这次我们实现了重复，且支持非贪婪模式，使得实用性大大增加了。不过，同样实用的计次重复却没有实现。这是由于以下两方面原因：

第一、计次重复需要复制状态机节点，如“ab{2,5}c”的状态机将是这样的：

如果是“a(…){2,5}c”，中间要复制的玩意儿就多了。目前状态机操作方面还没有支持复制一张子图的功能。

第二，由于“x{m,n}”中的m、n并不仅仅是1个字符，虽然处理上并不成问题，但这超出了开头提出的“每个词法单元都是单个字符”的愿望。单单为了秉承此美好愿望，也不应该支持。此事我们以后会回过头来处理。

通过本篇以及前面两篇，我们得到了一个勉强能用的正则表达式，已实现的语法与市面上的正则表达式是一样的（未实现的当然还是未实现啦）。但是，状态机部分仍然处于原始状态，特别是经过本次的修改，ε边弥漫，极大地影响匹配的效率。下一篇我们将系统了解下ε-NFA、NFA、DFA的概念，然后做一定的优化。

溪流

2012.06.07-2012.06.08

posted on 2012-06-08 23:35 溪流阅读(1871) 评论(2) 编辑收藏引用所属分类: C++

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 建立一个简单干净的 gn+ninja 工具链微软拼音长句模式恢复工具支持Win10 1803 发布个工具，一键恢复Win8/8.1中的微软拼音长句模式（新体验模式）将 Timer 对象化裸写一个进程外 COM 组件让 COM 脱离注册表在 DLL 中加入第二个 COM 类让COM组件可被跨语言调用裸写一个进程内 COM 组件写个含 Windows Media Player 的窗口

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

引言

语法分析

文法介绍

结构调整

状态机

代码实现

单元测试

小结

常用链接

留言簿(21)

随笔分类(124)

随笔档案(90)

我的链接

友情链接

积分与排名

最新随笔

最新评论

阅读排行榜

评论排行榜