xiiregexbuilder

 1#ifndef NFA_H
 2#define NFA_H
 3
 4#include <vector>
 5#include <set>
 6#include <map>
 7#include <memory>
 8#include "parser.h"
 9
10struct NFAState {
11    int id;
12    bool isAccept;
13    std::map<unsigned char, std::set<int>> transitions;
14    explicit NFAState(int id, bool isAccept = false) : id(id), isAccept(isAccept) {}
15};
16
17class NFA {
18public:
19    int regexIndex;
20    int startStateId;
21    std::map<int, NFAState> states;
22
23    explicit NFA(int idx) : regexIndex(idx), startStateId(-1) {}
24    void addState(int id, bool isAccept = false);
25    void addTransition(int fromId, unsigned char c, int toId);
26    bool simulate(const std::string& input) const;
27};
28
29class NFABuilder {
30public:
31    static int globalStateCounter;
32    static std::unique_ptr<NFA> build(ASTNode* root, int regexIdx);
33
34private:
35    static void linearize(ASTNode* node, int& posCounter, std::map<int, std::set<unsigned char>>& posToChars, std::set<int>& dotPositions);
36    static void computeNullableFirstLast(ASTNode* node);
37    static void computeFollowpos(ASTNode* node, std::map<int, std::set<int>>& followpos);
38};
39
40#endif // NFA_H