xiiregexbuilder

FPGA-Accelerated Regular Expression Matching Engine
git clone https://github.com/maydayv7/xiiregexbuilder

nfa.h (1089B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifndef NFA_H
#define NFA_H

#include <vector>
#include <set>
#include <map>
#include <memory>
#include "parser.h"

struct NFAState {
    int id;
    bool isAccept;
    std::map<unsigned char, std::set<int>> transitions;
    explicit NFAState(int id, bool isAccept = false) : id(id), isAccept(isAccept) {}
};

class NFA {
public:
    int regexIndex;
    int startStateId;
    std::map<int, NFAState> states;

    explicit NFA(int idx) : regexIndex(idx), startStateId(-1) {}
    void addState(int id, bool isAccept = false);
    void addTransition(int fromId, unsigned char c, int toId);
    bool simulate(const std::string& input) const;
};

class NFABuilder {
public:
    static int globalStateCounter;
    static std::unique_ptr<NFA> build(ASTNode* root, int regexIdx);

private:
    static void linearize(ASTNode* node, int& posCounter, std::map<int, std::set<unsigned char>>& posToChars, std::set<int>& dotPositions);
    static void computeNullableFirstLast(ASTNode* node);
    static void computeFollowpos(ASTNode* node, std::map<int, std::set<int>>& followpos);
};

#endif // NFA_H