隨筆檔案

實現正則表達式的想法很早就有，各種原因導致沒有做，最近花了點時間先實現了幾個簡單的正則語法，分別是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]這種字符區(qū)間表示法，我們可以用最簡單原始的方法轉換，就是把區(qū)間中的每個字符都轉化成相應的一條邊（NFA中的邊），這樣一來會導致字符區(qū)間越大，對應邊的數量會越多，使得對應的NFA也越大。因此，我們需要構造區(qū)間字符集合來減少邊的數量。

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

那么我們希望對應的字符集合是這樣：[a-a] [b-d] [e-e] [f-w] [x-z]

這需要構造一個字符集，每次插入一個區(qū)間的時候，把新插入的區(qū)間與已存在的區(qū)間進行分割，初始時已存在的區(qū)間集為空，那么正則表達式a[x-z]|[a-z]*e的劃分步驟如下：

已存在區(qū)間集合{}，插入[a-a]，得到{[a-a]}

已存在區(qū)間集合{[a-a]}，插入[x-z]，得到{[a-a], [x-z]}

已存在區(qū)間集合{[a-a], [x-z]}，插入[a-z]，得到{[a-a], [b-w], [x-z]}

已存在區(qū)間集合{[a-a], [b-w], [x-z]}，插入[e-e]，得到{[a-a], [b-d], [e-e], [f-w], [x-z]}

這個區(qū)間構造完成了之后，還需要在后面轉換成NFA邊的時候，根據字符區(qū)間查詢出在這個集合中，由哪幾個區(qū)間構成，比如：

查詢區(qū)間[a-a]，得到[a-a]

查詢區(qū)間[x-z]，得到[x-z]

查詢區(qū)間[a-z]，得到區(qū)間[a-a] [b-d] [e-e] [f-w] [x-z]

在轉換成NFA時，集合中的每個區(qū)間都對應一條邊，這樣相對于每個字符對應一條邊，邊的數量不會太多。

有了這么一個集合構造的類之后，把正則的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了。