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

想搞正则表达式解析器好久了。前面由于一些基础设施没准备好，没法开始动手。现在 xlLib 里头准备的差不多了，可以着手实施了。

在做这件事之前，读了好几遍 @vczh 的文章《构造可配置词法分析器》《构造正则表达式引擎》（http://www.cppblog.com/vczh/archive/2008/05/22/50763.html），给了很大的帮助和启发，在这里表示感谢。（虽然到现在为止还没有完全读懂。）

编译原理理论上的东西我了解的还不是很多。正则表达式在文本解析中有着特殊的作用，特殊之一是，它的每个词法单元都是单个字符（转义的除外），因此词法分析阶段需要做的工作仅仅是转义、识别单个字符。

本文我们实现以下功能：
 词法分析
 语法分析
 操作符“|”的支持
 小括号“()”的支持（仅用于改变优先级）

词法分析
我们定义一个 Token 结构来描述一个词法单元：

enum TokenType
{
    TT_Eof,
    TT_VerticalBar,     // |
    TT_OpenParen,       // (
    TT_CloseParen,      // )
    TT_OrdinaryChar
};

struct Token
{
    TokenType type;
    Char ch;
    size_t length;

    Token(TokenType type = TT_OrdinaryChar, Char ch = 0, size_t length = 1)
        : ch(ch), type(type), length(length)
    {

    }
};

其中 TokenType 表示哪种类型，除了普通字符外，我们支持的单词类型有竖线、左小括号、右小括号，EOF 严格的说并不属于单词，但这里我们需要一种表示单词读尽的方法。ch 表示这个 Token 的字符，length 表示这个 Token 的字符个数，一般来说是 1，如果碰到转义的，那就不是 1。之所以要记录长度，是因为有时候试探性地多读了一个 Token 后，需要回退回去。

整个词法分析就由下面这一个函数去做：

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;
    default:
        break;
    }

    return Token(type, ch);
}

其中 m_strRegExp 是要解析的表达式，m_nCurrentPosition 是当前位置。

我们的转义定义是，从前往后读，反斜杠 \ 后面的一个字符，转义为该字符本身。反斜杠后面跟任何字符，都是合法的。如果反斜杠出现在最后一个位置，那么容错处理，视为反斜杠这个字符。其余未经转义的，除了我们已定义功能的“|”“(”“)”外，都作为普通字符处理。目前这样的转义处理，不支持 \d、\uXXXX 之类的写法，这些以后再考虑。

顺便再写一个回退用的函数：

void Backward(const Token &token)
{
    m_nCurrentPosition -= token.length;
}

语法分析
文法介绍
按照本文开头定义的，我们的“正则表达式”的语法可以用以下的 EBNF 文法描述：

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

（大概这个意思，不知道写得规不规范）
“|”的优先级最低，整个表达式（Expr）首先被第一级竖线分割成各个版本不带竖线的子式（ExprNoOr）。
每个 ExprNoOr，被括号分分隔，括号外面的是不带括号（当然也不带竖线）的子式（ExprNoGroup），括号的里面，视为一个完整的表达式（Expr）。整个 ExprNoOr，由若干个 ExprNoGroup 或者带括号的表达式连接构成。注意这里有个递归定义。到目前为止，所有的子式将终结于 ExprNoGroup。
ExprNoGroup 定义为由若干个普通字符（不含“|”“(”“)”）组成的字符串。

状态机
这个，完整的叫做“非确定有限状态机”（NFA），理论上的东西我目前不是很精确地了解，以后总结。现在把代码实现中所需要的预备知识和算法讲一下。

举个例子，对于符合我们前面定义的正则表达式“abc”，我们可以用一下的NFA 表示：

匹配字符串的时候，我们从起始状态S 开始，依次用每个字符区尝试匹配每一条边，如果最后走到结束状态E，说明匹配成功。

再例如“(a|b)c”，它的NFA 表示如下：

又例如“a|ab”，它的NFA 表示如下：

这时，一个状态后面可能有不止一条边满足某个字符的通过条件，匹配的时候可能需要进行回溯操作。

另外，由于一下代码实现实现上的原因，“a|bc”可能被弄成下面这个样子：

跟刚才的相比，多了一条“ε边”。ε边是一条可以不消耗字符直接通过的边。

具有ε边的 NFA 叫做 ε-NFA。

好了，上面介绍了我们在本文定义的正则表达式语法中可能涉及到的状态机的样子。操作符“|”会导致状态机产生支路；括号改变优先级，体现在支路的位置不同。

我们使用一个图结构（xl::Graph）表示状态机，图的简单实现见：
http://xllib.codeplex.com/SourceControl/changeset/view/16803#160588

节点的数据结构定义如下：

struct Node
{
public:
    Node() : m_nIdentify(++ms_nCounter)
    {

    }

    int m_nIdentify;

    static int ms_nCounter;
};

__declspec(selectany) int Node::ms_nCounter = 0;

没有特别的数据，只带一个类实例计数，以区分不同的实例。

边的数据结构定义如下：

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(chE

补充：软件开发 , C++ ,