隨筆檔案

實(shí)現(xiàn)正則表達(dá)式的想法很早就有，各種原因?qū)е聸]有做，最近花了點(diǎn)時(shí)間先實(shí)現(xiàn)了幾個(gè)簡單的正則語法，分別是concatenation、alternation和closure，其他語法及metacharacter等有時(shí)間了有想法了之后再擴(kuò)展。

這三種基本的語法分別是對(duì)應(yīng)這樣的：

concatenation: abc    表示匹配字符串a(chǎn)bc

alternation: abc|def   表示匹配字符串a(chǎn)bc或者def

closure: a*               表示匹配零個(gè)到多個(gè)a構(gòu)成的字符串

我們知道正則表達(dá)式最終需要轉(zhuǎn)換成自動(dòng)機(jī)才能用來匹配字符串，我實(shí)現(xiàn)的正則通過如下幾個(gè)步驟把正則表達(dá)式轉(zhuǎn)換成自動(dòng)機(jī)：

正則表達(dá)式->Parse成AST->生成邊（字符）集合->生成NFA->NFA subset construction->轉(zhuǎn)換成DFA->DFA minimization

最后用DFA minimization之后構(gòu)造的自動(dòng)機(jī)來匹配字符串。

正則語法的分析

一個(gè)正則表達(dá)式寫出來，要讓這個(gè)正則表達(dá)式匹配字符串等操作之前，我們先需要從正則表達(dá)式中提取需要的信息并在正則語法錯(cuò)誤的時(shí)候提示錯(cuò)誤，這個(gè)過程自然少不了parser。一個(gè)parser通常是從一個(gè)lexer里面獲取一個(gè)token，而正則表達(dá)式的token都是字符，那么lexer不需要做任何的分詞操作，只需要簡單的把字符返回給parser即可。

那三種基本的正則語法對(duì)應(yīng)的BNF為：

這個(gè)parser分析了正則表達(dá)式之后產(chǎn)生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的基類，并提供接口實(shí)現(xiàn)Visitor模式訪問ASTNode類型。

字符（邊）集的構(gòu)造

AST構(gòu)造好了之后，需要把AST轉(zhuǎn)換成NFA。語法中有[a-zA-Z0-9]這種字符區(qū)間表示法，我們可以用最簡單原始的方法轉(zhuǎn)換，就是把區(qū)間中的每個(gè)字符都轉(zhuǎn)化成相應(yīng)的一條邊（NFA中的邊），這樣一來會(huì)導(dǎo)致字符區(qū)間越大，對(duì)應(yīng)邊的數(shù)量會(huì)越多，使得對(duì)應(yīng)的NFA也越大。因此，我們需要構(gòu)造區(qū)間字符集合來減少邊的數(shù)量。

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

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

這需要構(gòu)造一個(gè)字符集，每次插入一個(gè)區(qū)間的時(shí)候，把新插入的區(qū)間與已存在的區(qū)間進(jìn)行分割，初始時(shí)已存在的區(qū)間集為空，那么正則表達(dá)式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]}

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

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

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

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

在轉(zhuǎn)換成NFA時(shí)，集合中的每個(gè)區(qū)間都對(duì)應(yīng)一條邊，這樣相對(duì)于每個(gè)字符對(duì)應(yīng)一條邊，邊的數(shù)量不會(huì)太多。

有了這么一個(gè)集合構(gòu)造的類之后，把正則的AST中的字符信息提取出來構(gòu)造出這么個(gè)集合即可，這樣只需要寫個(gè)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_;
};

邊集合構(gòu)造完成之后，下一步就是生成NFA了。