解析正则表达式（一）概要 - c++编程基础

r 产生的新节点 pCurrent，第二次（以及第三次、第四次……） ParseExprNoOr 产生的新节点 pNewNode，都用一条ε边连接到 pCurrent。

接下来是 ParseExprNoOr：

StateMachine::NodePtr ParseExprNoOr(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = pNode;

while (true)
{
pCurrent = ParseExprNoGroup(pCurrent);

if (pCurrent == nullptr)
{
return nullptr;
}

Token token = LookAhead();

if (token.type != TT_OpenParen)
{
Backward(token);
return pCurrent;
}

pCurrent = ParseExpr(pCurrent);

if (pCurrent == nullptr)
{
return nullptr;
}

token = LookAhead();

if (token.type != TT_CloseParen)
{
return nullptr;
}
}

return nullptr;
}

它跟文法中写的形式上稍稍有点不一样。文法中是“ExprNoGroup { "(" Expr ")" ExprNoGroup }”，而现在好像是“{ ExprNoGroup "(" Expr ")" }”。其实是一样的，循环的退出点是某一次 ParseExprNoGroup 之后读到的不是“(”，要不要重复取决于“(”有没有出现。

以下是 ParseExprNoGroup，也是本文的解析终点：

StateMachine::NodePtr ParseExprNoGroup(StateMachine::NodePtr pNode)
{
StateMachine::NodePtr pCurrent = pNode;

while (true)
{
Token token = LookAhead();

if (token.type != TT_OrdinaryChar)
{
Backward(token);
return pCurrent;
}

pCurrent = AddNormalNode(pCurrent, token.ch);

if (pCurrent == nullptr)
{
return nullptr;
}
}

return nullptr;
}

它只认普通字符，有的话把它加入状态机。

至此，我们的语法分析已经做完了，最终得到一个ε-NFA。之后我们使用这个ε-NFA来匹配字符串。

匹配检验
相对于语法分析，匹配就比较简单了。我们现在要做的工作是：已知一个正则表达式对应的ε-NFA，给出一个字符串，判定该字符串是否符合正则表达式的描述。

由于我们现在直接使用ε-NFA，所以可能需要回溯，因此，简单起见写成如下递归形式：

bool Match(const String &s)
{

return Match(s, 0, m_pBegin);
}

bool Match(const String &s, int i, StateMachine::NodePtr pNode)
{
if (pNode == m_pEnd)
{
if (i < s.Length())
{
return false;
}

return true;
}

for (auto it = pNode->arrNext.Begin(); it != pNode->arrNext.End(); ++it)
{
if (Match(s, i, *it))
{
return true;
}
}

return false;
}

bool Match(const String &s, int i, StateMachine::EdgePtr pEdge)
{
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);
}
else
{
return Match(s, i, pEdge->pNext);
}
}

第一个 Match 是入口。第二个 Match 是针对某个节点，它遍历该节点的所有后续的边，如果从某一条边解析后续字符串成功，就结束，否则继续尝试下一条边。第三个 Match 是针对某条边的，如果能通过这条边，就继续到下个节点。这里有个对ε边的特殊处理，如果是ε边，i 没有加一，直接到下个节点。

上述过程是一个深度优先的搜索过程，如果能走到最后的节点，且字符串也刚刚走到最后，算匹配成功。

单元测试
先做一些常规的测试：

XL_TEST_CASE()
{
RegExp r;
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"()|()"));
XL_TEST_ASSERT(!r.Parse(L"("));
XL_TEST_ASSERT(!r.Parse(L")"));
}

XL_TEST_CASE()
{
RegExp r;

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

XL_TEST_ASSERT(r.Parse(L"a"));
XL_TEST_ASSERT(r.Match(L"a"));
XL_TEST_ASSERT(!r.Match(L"ab"));
XL_TEST_ASSERT(!r.Match(L"b"));

XL_TEST_ASSERT

解析正则表达式（一）概要 (三)