随笔档案

实现正则表达式的想法很早就有，各种原因导致没有做，最近花了点时间先实现了几个简单的正则语法，分别是concatenation、alternation和closure，其他语法及metacharacter等有时间了有想法了之后再扩展。

这三种基本的语法分别是对应这样的：

concatenation: abc    表示匹配字符串abc

alternation: abc|def   表示匹配字符串abc或者def

closure: a*               表示匹配零个到多个a构成的字符串

我们知道正则表达式最终需要转换成自动机才能用来匹配字符串，我实现的正则通过如下几个步骤把正则表达式转换成自动机：

正则表达式->Parse成AST->生成边（字符）集合->生成NFA->NFA subset construction->转换成DFA->DFA minimization

最后用DFA minimization之后构造的自动机来匹配字符串。

正则语法的分析

一个正则表达式写出来，要让这个正则表达式匹配字符串等操作之前，我们先需要从正则表达式中提取需要的信息并在正则语法错误的时候提示错误，这个过程自然少不了parser。一个parser通常是从一个lexer里面获取一个token，而正则表达式的token都是字符，那么lexer不需要做任何的分词操作，只需要简单的把字符返回给parser即可。

那三种基本的正则语法对应的BNF为：

这个parser分析了正则表达式之后产生AST，AST的node类型为：

class ASTNode
{
public:
    ACCEPT_VISITOR() = 0;
    virtual ~ASTNode() { }
};
 
class CharNode : public ASTNode
{
public:
    explicit CharNode(int c) : c_(c) { }
 
    ACCEPT_VISITOR();
 
    int c_;
};
 
class CharRangeNode : public ASTNode
{
public:
    struct Range
    {
        int first_;
        int last_;

        explicit Range(int first = 0, int last = 0)
            : first_(first), last_(last)
        {
        }
    };

    CharRangeNode() { }

    void AddRange(int first, int last)
    {
        ranges_.push_back(Range(first, last));
    }
 
    void AddChar(int c)
    {
        chars_.push_back(c);
    }
 
    ACCEPT_VISITOR();
 
    std::vector<Range> ranges_;
    std::vector<int> chars_;
};
 
class ConcatenationNode : public ASTNode
{
public:
    void AddNode(std::unique_ptr<ASTNode> node)
    {
        nodes_.push_back(std::move(node));
    }
 
    ACCEPT_VISITOR();
 
    std::vector<std::unique_ptr<ASTNode>> nodes_;
};
 
class AlternationNode : public ASTNode
{
public:
    void AddNode(std::unique_ptr<ASTNode> node)
    {
        nodes_.push_back(std::move(node));
    }
 
    ACCEPT_VISITOR();
 
    std::vector<std::unique_ptr<ASTNode>> nodes_;
};
 
class ClosureNode : public ASTNode
{
public:
    explicit ClosureNode(std::unique_ptr<ASTNode> node)
        : node_(std::move(node))
    {
    }
 
    ACCEPT_VISITOR();
 
    std::unique_ptr<ASTNode> node_;
};

其中ASTNode作为AST的基类，并提供接口实现Visitor模式访问ASTNode类型。

字符（边）集的构造

AST构造好了之后，需要把AST转换成NFA。语法中有[a-zA-Z0-9]这种字符区间表示法，我们可以用最简单原始的方法转换，就是把区间中的每个字符都转化成相应的一条边（NFA中的边），这样一来会导致字符区间越大，对应边的数量会越多，使得对应的NFA也越大。因此，我们需要构造区间字符集合来减少边的数量。

比如正则表达式是：a[x-z]|[a-z]*e

那么我们希望对应的字符集合是这样：[a-a] [b-d] [e-e] [f-w] [x-z]

这需要构造一个字符集，每次插入一个区间的时候，把新插入的区间与已存在的区间进行分割，初始时已存在的区间集为空，那么正则表达式a[x-z]|[a-z]*e的划分步骤如下：

已存在区间集合{}，插入[a-a]，得到{[a-a]}

已存在区间集合{[a-a]}，插入[x-z]，得到{[a-a], [x-z]}

已存在区间集合{[a-a], [x-z]}，插入[a-z]，得到{[a-a], [b-w], [x-z]}

已存在区间集合{[a-a], [b-w], [x-z]}，插入[e-e]，得到{[a-a], [b-d], [e-e], [f-w], [x-z]}

这个区间构造完成了之后，还需要在后面转换成NFA边的时候，根据字符区间查询出在这个集合中，由哪几个区间构成，比如：

查询区间[a-a]，得到[a-a]

查询区间[x-z]，得到[x-z]

查询区间[a-z]，得到区间[a-a] [b-d] [e-e] [f-w] [x-z]

在转换成NFA时，集合中的每个区间都对应一条边，这样相对于每个字符对应一条边，边的数量不会太多。

有了这么一个集合构造的类之后，把正则的AST中的字符信息提取出来构造出这么个集合即可，这样只需要写个visitor就完成了：

class EdgeSetConstructorVisitor : public Visitor
{
public:
    explicit EdgeSetConstructorVisitor(EdgeSet *edge_set)
        : edge_set_(edge_set)
    {
    }
 
    EdgeSetConstructorVisitor(const EdgeSetConstructorVisitor &) = delete;
    void operator = (const EdgeSetConstructorVisitor &) = delete;
 
    VISIT_NODE(CharNode);
    VISIT_NODE(CharRangeNode);
    VISIT_NODE(ConcatenationNode);
    VISIT_NODE(AlternationNode);
    VISIT_NODE(ClosureNode);

private:
    EdgeSet *edge_set_;
};

边集合构造完成之后，下一步就是生成NFA了。