随笔-90  评论-947  文章-0  trackbacks-0
解析正则表达式（二）字符集合

引言

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

 

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

 

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

 

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

 

语法分析

文法介绍

我们用 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，并增加ExprCollection、ExprNoCollection。

 

Token和LookAhead的变化很简单：

 

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;

    }

 

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

 

遇到第一个“^”，将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"));

}

 

嗯，再回顾一下上一篇我们写的匹配0到255的正则表达式：

 

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)         0到199：(0|1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)

b)         200到249：2(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9)

c)         250到255：25(0|1|2|3|4|5)

 

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

1.         一位数：[0-9]

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

3.         三位数：

a)         0到199：[01][0-9][0-9]

b)         200到249：2[0-4][0-9]

c)         250到255：25[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 溪流 阅读(2095) 评论(0)  编辑 收藏 引用 所属分类: C++

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


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