从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

2023-10-28 12:37:22

文章目录

查阅相关链接

编译原理（网易云课堂 中科大 编译原理）

前引

各位好 笔者在写完了 上一篇 从正则表达式Regex转抽象语法树AST后 继续写第二篇AST转NFA了 ^^

前提说一下 这部分难度个人认为是这几个步骤中最简单的 因为是递归生成 但是同样也是有很多的实现细节需要注意 这里的简单只是相对的 哈哈 那话不多说 笔者继续往下面写了

从零开始自制实现正则引擎（二）

下面部分 仅限于学习完了词法分析的hxd 并且能够自己画出来AST转NFA的图 这部分难度相对没有那么高 但也没有那么简单 需要自己理解 如何利用Thompson 算法递归生成ε-NFA 这部分自己动手画一下图 自己再把各种连接状态图画一下 应该就能写出来了 我在写正则引擎的第二天 就把AST->NFA 和绝大部分NFA->DFA写出来了 所以这部分相对真没有那么难

1、Thompson Algorithm 递归实现

写到这里 不得不说两句 epsilon 存在的原因 为什么会有epsilon存在呢 其实状态图里面可以省去这些不吞掉字符的空节点 但是存在的原因 是因为有了这些空节点 才会有100来行 能够递归生成NFA的优雅递归算法 这些空节点很完美的让这个递归变得十分优雅 如果不存在 那么节点的合并 指针的交换会让我们生成最后这个NFA树特别恼人 我体会的最深的地方就是 选择部分的生成 如果没有空节点 我都想不到怎么去递归的生成 - - 这部分先说到这里

我们下面直接对Thompson Algorithm五种情况分别用代码来分析一下

1、ε 与 char 节点生成（示例讲解）

从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

这两种情况可以合并的原因是 两个节点生成的方式完全一样 除了有一个是不消化字符 有一个需要 所以我们把这两个情况作为一样的看待

1、ε 与 char 节点生成（代码实现）

对 你没有看错 就只有一行 就把两种情况解决了 很简单

void epsilon_char_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
void NFA::epsilon_char_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    start->value = node->value;
}

2、concat 节点生成（示例讲解）

从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

其实还是很简单的 就是把两个节点中间插入两个节点 头节点 和 倒数第二节点分别放入两个字符 或者递归的去形成里面的节点情况即可

2、concat 节点生成（代码实现）

这里就是按照上面的图片写的 最后两行就是去递归的生成 那两个节点间的情况 没别的了 还是很easy的

void concat_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
void NFA::concat_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();

    start->edge1 = n1;
    n1->edge1 = n2;
    n2->edge1 = end;

    build(start,n1,node->left);
    build(n2,end,node->right);
}

3、select 节点生成（示例讲解）

从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

这里的话 也不难 多生成四个节点 看图即可 然后中间的话 递归的生成即可

3、select 节点生成（代码实现）

void select_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
void NFA::select_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();
    NFA_node* n1_next = new NFA_node(),*n2_next = new NFA_node();

    start->edge1 = n1;
    start->edge2 = n2;
    n1->edge1 = n1_next;
    n2->edge1 = n2_next;
    n1_next->edge1 = end;
    n2_next->edge1 = end;

    build(n1,n1_next,node->left);
    build(n2,n2_next,node->right);
}

4、e-closure 节点生成（示例讲解）

从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

这里的话 稍微复杂一点 主要在于有一个回旋的指针 我默认的把回旋指针放到了edge1那里 不仅是方便后面的重复遍历 而且也方便后面的节点收集 看图即可 下面就放代码了

4、e-closure 节点生成（代码实现）

void NFA::closure_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();

    start->edge1 = n1;
    start->edge2 = end;
    n1->edge1 = n2;
    n2->edge1 = n1;
    n2->edge2 = end;
    n2->closure_node = true;

    build(n1,n2,node->left);
}

2、代码实现

这部分相对简单 而且上面对应每一种情况 我都详细的把代码给出来了 所以就不多做介绍了 下面直接放代码了

1、NFA_node.h

#ifndef NFA_NODE_H
#define NFA_NODE_H

#include "global.h"
#include <unordered_map>


class NFA_node
{
    private:
        char value;
        enum states state;
        NFA_node* edge1;
        NFA_node* edge2;
        int id;            // node_id For converting to DFA conveniently
        bool closure_node;  // for print_NFA_routine

        friend class NFA;
        friend class DFA_node;
        friend class DFA;
    public:
        NFA_node(char value = 0,enum states init_state = UNACCEPTABLE,    \
                 NFA_node* e1 = nullptr,NFA_node* e2 = nullptr,int id = 0,bool closure_node = false):
                 value(value),state(init_state),edge1(e1),edge2(e2),id(id),closure_node(closure_node)   {}
        ~NFA_node()         {}

        void Print_NFA(NFA_node* end,string& str);
        void Get_Id(unordered_map<NFA_node*,int>& map,NFA_node* end,int& id_max);
        void delete_node();
};



void NFA_node::Print_NFA(NFA_node* end,string& str)
{
    if(!this)   return;

    if(this == end)
    {
        cout << str << "End\n";
        return;
    }

    if(!closure_node && edge1)
    {
        str += (value == 0 ? '-' : value);
        edge1->Print_NFA(end,str);
        str.pop_back();
    }

    if(edge2)
    {
        str += (value == 0 ? '-' : value);
        edge2->Print_NFA(end,str);
        str.pop_back();
    }
}

void NFA_node::Get_Id(unordered_map<NFA_node*,int>& map,NFA_node* end,int& id_max)
{
    if(!this || map.find(this) != map.end() || this == end)
        return;

    map[this] = id_max;
    id = (id_max++);
    if(!closure_node && edge1)   edge1->Get_Id(map,end,id_max);
    if(edge2)                    edge2->Get_Id(map,end,id_max);

    return;
}

void NFA_node::delete_node()
{
    if(!this)   return;
    if(edge1 && !closure_node)   edge1->delete_node();
    if(edge2)                    edge2->delete_node();
    delete this;
}

#endif // NFA_NODE_H

2、NFA.h

#ifndef NFA_H
#define NFA_H

#include "NFA_node.h"

class NFA
{
    private:
        NFA_node* start;
        NFA_node* end;

        int total_nodes;

        friend class DFA;
    public:
        NFA()
        {
            start = new NFA_node();
            end = new NFA_node(0,ACCEPTABLE);
            start->edge1 = end;
        }
        ~NFA()
        {
            if(!start)  return;
            start->delete_node();
        }

        void build_NFA(ASTTree* Tree);
        void build(NFA_node* start,NFA_node* end,ASTTree_node* Tree);
        void epsilon_char_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
        void concat_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
        void select_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
        void closure_build(NFA_node* start,NFA_node* end,ASTTree_node* node);
        void print_NFA_routes();
        void get_all_nodes_id();
};

void NFA::print_NFA_routes()
{
    string str;
    cout << "NFA_Print: \n";
    start->Print_NFA(end,str);
    cout << endl;
}

void NFA::build_NFA(ASTTree* Tree)      // 涉及内存泄露 后面再改
{
    if(!Tree)   return;
    start->delete_node();
    start = new NFA_node();
    end = new NFA_node(0,ACCEPTABLE);
    start->edge1 = end;

    build(start,end,Tree->root);
    get_all_nodes_id();
}

void NFA::build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    if(!node)   return;
    switch(node->kind)
    {
        case EXP_CHR:
        case EXP_EPSILON:
            epsilon_char_build(start,end,node);
            break;
        case EXP_CONCAT:
            concat_build(start,end,node);
            break;
        case EXP_SELECT:
            select_build(start,end,node);
            break;
        case EXP_CLOSURE:
            closure_build(start,end,node);
            break;
        default:
            cout << "NFA_Tree build Error,Unidentified Char\n";
            exit(0);
    }
    return;
}

void NFA::epsilon_char_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    start->value = node->value;
}

void NFA::concat_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();

    start->edge1 = n1;
    n1->edge1 = n2;
    n2->edge1 = end;

    build(start,n1,node->left);
    build(n2,end,node->right);
}

void NFA::select_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();
    NFA_node* n1_next = new NFA_node(),*n2_next = new NFA_node();

    start->edge1 = n1;
    start->edge2 = n2;
    n1->edge1 = n1_next;
    n2->edge1 = n2_next;
    n1_next->edge1 = end;
    n2_next->edge1 = end;

    build(n1,n1_next,node->left);
    build(n2,n2_next,node->right);
}

void NFA::closure_build(NFA_node* start,NFA_node* end,ASTTree_node* node)
{
    NFA_node* n1 = new NFA_node(),*n2 = new NFA_node();

    start->edge1 = n1;
    start->edge2 = end;
    n1->edge1 = n2;
    n2->edge1 = n1;
    n2->edge2 = end;
    n2->closure_node = true;

    build(n1,n2,node->left);
}

void NFA::get_all_nodes_id()
{
    unordered_map<NFA_node*,int> map;
    int id_max = 0;
    start->Get_Id(map,end,id_max);
    end->id = (id_max++);
    total_nodes = id_max;
}

#endif // NFA_H

3、验证NFA生成正确

1、验证结果1（验证正确）

用了一个稍微复杂一点的表达式
ac*|aa|bb|cc 为了调试 我还专门去代码那里把AST NFA输出打开了 - - 其中为了简约 没有输出e-closure闭包的回旋指针 从下面结果 应该可以初步判断是正确的结果了 如果感兴趣的hxd可以自己去画一下图看一下是不是下面的这个结果 那就先写到这里啦 下一篇见 (●’◡’●)
`从零开始自制实现正则引擎（二）---- 抽象语法树AST转化为非确定有限状态自动机NFA

上一篇：2021-10-19


下一篇：免费搭建MC服务器 （一）