随笔-89  评论-944  文章-0  trackbacks-0

引言

这篇我们要实现的是中括号表达式。

 

一个中括号里写上任意数目的字符,表示匹配这些字符中的任何一个。比如“[abc]”匹配abc。中括号里除了单个字符,也可以写字符区间,比如“[a-c]”就表示从ac的所有字符,这里“ac”是指内码连续的一系列字符,包含首尾的ac。综合起来说,中括号里面可以放任意个字符或者字符区间,匹配所填字符或字符区间内的任意一个字符。比如“[acd-f]”可以匹配acdef这五个字符。

 

还有一种否定的形式,在中括号最前面写一个“^”,其余部分不变,这用于匹配除了所描述的字符集合之外的所有字符。也就是取所表述的字符集合的补集的意思,既然有补集,便有全集,全集是正则表达式所支持的普通字符的全体。

 

不管肯定形式还是否定形式,中括号表达式都表示了一种字符集合。

 

语法分析

文法介绍

我们用 EBNF 文法描述集合表达式:

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

首尾是中括号,中括号里面开头可能有“^”,接下来是若干个字符或者字符区间。

 

中括号表达式的优先级很高,比小括号还要高。上一篇我们的整个正则表达式文法是:

Expr        -> ExprNoOr { "|" ExprNoOr }

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

ExprNoGroup -> { OrdinaryChar }

 

由于中括号表达式的增加,ExprNoGroup 不再是那么简单了。现在文法要改为:

Expr             -> ExprNoOr { "|" ExprNoOr }

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

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

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

ExprNoCollection -> { OrdinaryChar }

 

ExprNoCollection 取代了之前的ExprNoGroup,而ExprNoGroup 的结构变得和 ExprNoOr 类似,新增的ExprCollection用于描述中括号之内的文法。

 

状态机

回顾一下我们之前对状态机的边的数据结构定义:

 

struct Edge

{

    Edge()

        : m_bEpsilon(true), m_chBegin(0), m_chEnd(0)

    {

           

    }

 

    Edge(Char ch)

        : m_bEpsilon(false), m_chBegin(ch), m_chEnd(ch)

    {

 

    }

 

    Edge(Char chBegin, Char chEnd)

        : m_bEpsilon(false), m_chBegin(chBegin), m_chEnd(chEnd)

    {

 

    }

 

    bool Match(Char ch)

    {

        if (m_bEpsilon)

        {

            return false;

        }

 

        return (ch >= m_chBegin && ch <= m_chEnd);

    }

 

    bool bEpsilon;

    Char chBegin;

    Char chEnd;

};

 

该数据结构可以支持表示一个区间。比如表达式“a[1-358]b”,它的状态机结构为:

 

clip_image001[4]

其中 1-3 占用一条边。

 

在考虑否定的形式,将刚才的表达式修改成“a[^1-358]b”,状态机能保持类似结构吗?是否可以给边增加一个属性,表示“处于否定状态”呢?

 

clip_image002[4]

如上图,加入橘黄色的边表示“否定边”,那么,如何进行匹配检验呢?假设到了1号状态后,后续字符是“5”,走第一条边“1-3”,通过!这显然与期望不一致,我们希望“5”被阻挡,因为“[^1-358]”中不包含“5”。原因是,我们之前状态机的同一节点的后续各条边之间是逻辑或关系,只要有一条通过即可,而引入“否定边”后,我们需要对这些边做逻辑与操作,只有每条边都通过才行。这样,可以考虑将并联改成串联:

 

clip_image003[4]

 

并联改串联是刚刚写到这里的时候想到的。下午在写代码的时候想到的是另一个方案——对集合求补集。“[^1-358]”等价于“[*-046-79-#]”,其中我暂时用“*”表示第一个字符(U+0000),用“#”表示最后一个字符(U+FFFF)。这样,状态机的形式为:

 

clip_image004[4]

 

(现在觉得串联的形式更美了。本文先按补集方案做,串联方案因为匹配的时候只有第一条边可以消耗字符,后续的边不能消耗字符了,不是很方便处理,再想想。)

 

集合运算

集合运算一开始是由于需要求补集才引入的。如果不求补集,可以不用,无非重复的边多一些。如表达式“[1-54-6]”,那么可能需要一条“1-5”的边,一条“4-6”的边,引入集合运算后,可以合为一条“1-6”边。

 

对于否定形式的“[^1-54-6]”,则必须进行集合运算了:先将两个区间并为“1-6”,再求补,得到“*-0”和“7-#”。也可以先对每个区间求补,最后求交集。

 

首先是区间的概念。代码见:

http://xllib.codeplex.com/SourceControl/changeset/view/16818#270866

 

相关函数简要介绍如下:

 

template <typename T>

struct Interval

{

    T left;             // 左端点

    T right;            // 右端点

    bool bIncludeLeft;  // 是否包含左端点

    bool bIncludeRight; // 是否包含右端点

 

    // 一系列构造函数等

    Interval();

    Interval(T left, T right, bool bIncludeLeft = true, bool bIncludeRight = true);

    Interval(const Interval &that);

    ~Interval();

 

    // 一系列运算符

    Interval &operator = (const Interval &that);

    bool operator == (const Interval &that) const;

    bool operator != (const Interval &that) const;

    bool operator < (const Interval &that) const;

    bool operator > (const Interval &that) const;

    bool operator <= (const Interval &that) const;

    bool operator >= (const Interval &that) const;

 

    // 是否为空集

    bool IsEmpty() const;

    //是否包含某元素

    bool Contains(const T &v) const;

    // 是否包含某区间(子集)

    bool Contains(const Interval &that) const;

    // 是否被某区间包含(超集)

    bool ContainedBy(const Interval &that) const;

    // 求交集

    Interval Intersection(const Interval &that) const;

    // 是否相交

    bool HasIntersectionWith(const Interval &that) const;

    // 是否相连

    bool Touched(const Interval &that) const;

    // 求相连两集合的并集

    Interval UnionTouched(const Interval &that) const;

    // 求并集(不管是否相连)

    Set<Interval> Union(const Interval &that) const;

    // 去除一个区间(差集)

    Set<Interval> Exclude(const Interval &that) const;

    // 变成闭区间

    Interval CloseInterval(const T step);

};

 

其中,两个 bool 变量表示两个端点的开闭。

 

大小比较,空集永远等于空集,两集合的大小先看左端点再看右端点,左端点相同时闭的比开的小,右端点相同时开的比闭的小。

 

“相连”的概念是指,有交集,或者其中一个的左端点等于另一个的右端点,两点一开一闭。UnionTouched,是指两个区间可以并成一个区间的时候,求并了之后的结果,如果不能并为一个区间,那么返回自己。Union 就是普遍意义的区间并,可能会并成2个间断的区间。

 

Exclude 是差集的概念,一个区间对另一个区间求差集,可能会断裂成2个区间。补集运算就不再搞一个了,一个集合对全集求补,相当于全集对它求差。

 

最后一个,表示把开区间变成闭区间,其中带有一点离散化的概念,需要知道离散化的步长(粒度)。如果左端点是开的,那么CloseInterval操作就是把左端点加上step,并改为闭的;右端点也类似,只是要减去step而不是加上。

 

从上面几个运算来看,求交和求“相连并”这两个运算对于区间是封闭的,求并、求差都不封闭。

 

有了区间,我们再鼓捣出一个区间集:

http://xllib.codeplex.com/SourceControl/changeset/view/16818#270871

 

template <typename T>

class IntervalSet

{

    typedef Interval<T> IntervalType;

    Set<IntervalType> m_setIntervals;   // 保存区间集

 

    // 构造和析构

    IntervalSet()

    IntervalSet(const IntervalSet &that)

    ~IntervalSet()

 

    // 一系列运算符

    IntervalSet &operator = (const IntervalSet &that)

    bool operator == (IntervalSet &that) const

    bool operator != (IntervalSet &that) const

 

    // 取出区间集里的区间

    Set<IntervalType> GetIntervals()

 

    // 是否为空集

    bool IsEmpty() const

 

    // 对单个区间作交、并、差

    void Intersect(const IntervalType &interval)

    void Union(const IntervalType &interval)

    void Exclude(const IntervalType &interval)

 

    // 对区间集求交、并、差

    IntervalSet Intersection(const IntervalSet &that) const

    IntervalSet Union(const IntervalSet &that) const

    IntervalSet Exclude(const IntervalSet &that) const

 

    // 变成闭区间集

    void MakeClose(const T &step)

};

 

相关概念类似,不再做过多解释了。

 

到了这里,我们可以表达任意集合了,区间、单点(左右端点相同的闭区间),以及它们的任意并,都可以表达了。

 

下面,我们走出集合运算,把目光重新聚集到正则表达式解析上来。

 

代码实现

由于文法改变,我们需要修改Token定义和LookAhead,以便增加新的语法元素“[”“]”“^”“-”,然后修改 ExprNoGroup,并增加ExprCollectionExprNoCollection

 

TokenLookAhead的变化很简单:

 

enum TokenType

{

    TT_Eof,

    TT_VerticalBar,     // |

    TT_OpenParen,       // (

    TT_CloseParen,      // )

    TT_OpenBracket,     // [

    TT_CloseBracket,    // ]

    TT_Hyphen,          // -

    TT_Caret,           // ^

    TT_OrdinaryChar

};

 

Token LookAhead()

{

    if (m_nCurrentPosition >= m_strRegExp.Length())

    {

        return Token(TT_Eof, 0, 0);

    }

 

    Char ch = m_strRegExp[m_nCurrentPosition++];

    TokenType type = TT_OrdinaryChar;

 

    if (ch == L'\\')

    {

        if (m_nCurrentPosition < m_strRegExp.Length())

        {

            return Token(TT_OrdinaryChar, m_strRegExp[m_nCurrentPosition++], 2);

        }

    }

 

    switch (ch)

    {

    case L'|':

        type = TT_VerticalBar;

        break;

    case L'(':

        type = TT_OpenParen;

        break;

    case L')':

        type = TT_CloseParen;

        break;

    case L'[':

        type = TT_OpenBracket;

        break;

    case L']':

        type = TT_CloseBracket;

        break;

    case L'-':

        type = TT_Hyphen;

        break;

    case L'^':

        type = TT_Caret;

        break;

    default:

        break;

    }

 

    return Token(type, ch);

}

 

上面,各Token之间是按照优先级从低到高排列的。

 

因为现在ExprNoCollection承担了原先ExprNoGroup的作用——接受普通字符,因此只要抄原先ExprNoGroup的代码即可:

 

StateMachine::NodePtr ParseExprNoCollection(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;

}

 

接下来是ExprNoGroup

 

StateMachine::NodePtr ParseExprNoGroup(StateMachine::NodePtr pNode)

{

    StateMachine::NodePtr pCurrent = pNode;

 

    while (true)

    {

        pCurrent = ParseExprNoCollection(pCurrent);

 

        if (pCurrent == nullptr)

        {

            return nullptr;

        }

 

        Token token = LookAhead();

 

        if (token.type != TT_OpenBracket)

        {

            Backward(token);

            return pCurrent;

        }

 

        pCurrent = ParseExprCollection(pCurrent);

 

        if (pCurrent == nullptr)

        {

            return nullptr;

        }

 

        token = LookAhead();

 

        if (token.type != TT_CloseBracket)

        {

            return nullptr;

        }

    }

 

    return nullptr;

}

 

对照文法

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

 

我们可以发现,它和ExprNoOr写法很像。当然像了,它俩文法就很像,所以实现相像是必然的。

 

最后我们来看 ExprCollection

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

 

我先贴一半的代码:

 

StateMachine::NodePtr ParseExprCollection(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;

    }

 

这是一个大的循环,同时处理“^”“-”和普通字符。其中“^”必须在第一个字符处出现,否则视为不合法。“-”必须在bInHyphenfalsebAcceptHyphentrue的时候出现,否则也视为不合法。

 

遇到第一个“^”,将bOpposite置为true,表示整个中括号表达式是否定的。遇到“-”,将bInHyphen设上,待下个字符到来时,与前一个字符共同组合成区间。

 

上面这个大循环的结果是区间集is以及标识bOpposite。接下来是使用得到的区间集进行必要的运算,并生成状态机:

 

    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;

}

 

首先,如果是否定形式的,对整个区间集求一个补,然后搞成闭区间。肯定形式略过这一步。不管肯定形式还是否定形式,如果最后是空集,我现在处理为直接返回当前节点。

 

如果得到非空的区间集,对其中每个区间生成一条边,连到新节点,就可以了。代码到这里为止。

 

单元测试

跟上一篇一样,弄点常规测试用例:

 

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"[1-3a]"));

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

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

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

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

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

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

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

 

    XL_TEST_ASSERT(r.Parse(L"[^1-3a]"));

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

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

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

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

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

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

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

}

 

嗯,再回顾一下上一篇我们写的匹配0255的正则表达式:

 

1.         一位数:(0|1|2|3|4|5|6|7|8|9)

2.         两位数:(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)

3.         三位数:

a)         0199(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)

b)         2002492(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)

c)         25025525(0|1|2|3|4|5)

 

我们现在可以来简化一下了:

1.         一位数:[0-9]

2.         两位数:[0-9][0-9]

3.         三位数:

a)         0199[01][0-9][0-9]

b)         2002492[0-4][0-9]

c)         25025525[0-5]

 

合起来就是“[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]”,比上一篇短多了。使用和之前同样的测试用例进行测试:

 

XL_TEST_CASE()

{

    RegExp r;

 

    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"0"));

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

 

同样,画一下状态机。这是使用 Graphviz 来画(感谢 yugi.fanxes 推荐),省去不少力气。Dot源代码如下:

 

digraph

{

    rankdir=LR;

    node [shape=circle];

    0 [shape=doublecircle];

    1 [shape=doublecircle];

    0->1 [label="0-9"];

    0->2->3 [label="0-9"];

    3->1 [label=ε];

    0->4 [label="0-1"];

    4->5->6 [label="0-9"];

    6->1 [label=ε];

    0->7 [label=2];

    7->8 [label="0-4"]

    8->9 [label="0-9"];

    9->1 [label=ε];

    0->10 [label=2];

    10->11 [label=5];

    11->12 [label="0-6"]

    12->1 [label=ε];

}

 

状态机:

clip_image006[4]

 

由于边数据结构支持表示字符区间,这次我们使用了这个特性,使得状态机简化了很多。

 

相应的,IPv4地址的表示也可以变得更短:

 

XL_TEST_CASE()

{

    RegExp r;

 

    // IPv4 address

    XL_TEST_ASSERT(r.Parse(L"("

                            L"[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]"

                            L").("

                            L"[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]"

                            L").("

                            L"[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]"

                            L").("

                            L"[0-9]|[0-9][0-9]|[01][0-9][0-9]|2[0-4][0-9]|25[0-5]"

                            L")"));

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

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

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

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

}

 

小结

本文在上一篇的基础上,增加了“[”“]”“^”“-”四个符号的处理,支持了字符集合的表达。字符集合的表达还是能带来很大方便的,到目前为止,我们的“正则表达式”功能已经有有点雏形了,可以用来做一些简单的事情了。

 

本文中涉及的实现代码在:

http://xllib.codeplex.com/SourceControl/changeset/view/16849#270275

 

下一篇,将实现“重复”的处理,即“?”“+”“*”这三个符号的解析。

 

溪流

2012.06.03-2012.06.04

 

posted on 2012-06-04 22:19 溪流 阅读(1928) 评论(0)  编辑 收藏 引用 所属分类: C++

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