随笔-90  评论-947  文章-0  trackbacks-0
解析正则表达式（三）重复

引言

根据预告，这篇我们对“?”“+”“*”进行处理，实现对重复的支持。“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”的状态机，这当然很简单：

 

clip_image001

 

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

 

clip_image002

 

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

 

clip_image003

 

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

 

clip_image004

 

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

 

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

 

clip_image005

 

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

 

clip_image006

 

“ab?c”：

clip_image007

 

可以看出一点规律：

 

节点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”的状态机将是这样的：

 

clip_image008

 

如果是“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 溪流 阅读(1847) 评论(2)  编辑 收藏 引用 所属分类: C++

评论:
# re: 解析正则表达式（三）重复 2012-06-09 00:14 | lwch
呵呵~踩一下..  回复  更多评论
  
# re: 解析正则表达式（三）重复 2012-06-09 00:45 | 溪流
@lwch
多谢捧场~
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 溪流