随笔-89  评论-944  文章-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

 

首先,我们把由“|”分开的各个部分称为SubExprSubExpr由很多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;

 

    // ...

 

};

 

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

 

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

 

代码实现

代码主要修改是ParsePhrase部分,以及增加的ParseRepeaterParsePhrase目前代码如下:

 

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,作为重复部分的开始,方便之后如果要从状态1pNode)添加不同顺序的ε边(pNodepFrom最多只有两条边,仅用来区分贪婪和非贪婪)。解析完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,应该能通过。然后增加几个对pnPoscase

 

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]”。所有的“|”子式之间,如果有包含关系,或者有部分重叠,使用的时候就需要考虑顺序,这跟贪婪、非贪婪的道理是一样的。

 

然后尝试添加针对新功能的caseIPv4地址由于后面重复是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}”中的mn并不仅仅是1个字符,虽然处理上并不成问题,但这超出了开头提出的“每个词法单元都是单个字符”的愿望。单单为了秉承此美好愿望,也不应该支持。此事我们以后会回过头来处理。

 

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

 

溪流

2012.06.07-2012.06.08

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

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理