Branch data Line data Source code
1 : : // $Id: NFA.h 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #ifndef nfa_h
6 : : #define nfa_h
7 : :
8 : : #include "RE.h"
9 : : #include "IntSet.h"
10 : :
11 : : class NFA_State;
12 : : class EquivClass;
13 : :
14 : 394056 : declare(PList,NFA_State);
15 : : typedef PList(NFA_State) NFA_state_list;
16 : :
17 : : #define NO_ACCEPT 0
18 : :
19 : : #define NO_UPPER_BOUND -1
20 : :
21 : : #define SYM_BOL 256
22 : : #define SYM_EOL 257
23 : : #define NUM_SYM 258
24 : :
25 : : #define SYM_EPSILON 259
26 : : #define SYM_CCL 260
27 : :
28 : :
29 : : class NFA_State : public BroObj {
30 : : public:
31 : : NFA_State(int sym, EquivClass* ec);
32 : : NFA_State(CCL* ccl);
33 : : ~NFA_State();
34 : :
35 : 68290 : void AddXtion(NFA_State* next_state) { xtions.append(next_state); }
36 : 9318 : NFA_state_list* Transitions() { return &xtions; }
37 : : void AddXtionsTo(NFA_state_list* ns);
38 : :
39 : 444 : void SetAccept(int accept_val) { accept = accept_val; }
40 : 19422 : int Accept() const { return accept; }
41 : :
42 : : // Returns a deep copy of this NFA state and everything it points
43 : : // to. Upon return, each state's marker is set to point to its
44 : : // copy.
45 : : NFA_State* DeepCopy();
46 : :
47 : 32118 : void SetMark(NFA_State* m) { mark = m; }
48 : 14206 : NFA_State* Mark() const { return mark; }
49 : : void ClearMarks();
50 : :
51 : 150975 : int TransSym() const { return sym; }
52 : 18034 : CCL* TransCCL() const { return ccl; }
53 : 370663 : int ID() const { return id; }
54 : :
55 : : NFA_state_list* EpsilonClosure();
56 : :
57 : : void Describe(ODesc* d) const;
58 : : void Dump(FILE* f);
59 : :
60 : : // Recursivly count all the reachable states.
61 : : unsigned int TotalMemoryAllocation() const;
62 : :
63 : : protected:
64 : : int sym; // if SYM_CCL, then use ccl
65 : : CCL* ccl; // if nil, then use sym
66 : : int accept;
67 : : int id; // number that uniquely identifies this state
68 : : NFA_state_list xtions;
69 : : NFA_state_list* epsclosure;
70 : : NFA_State* mark;
71 : : };
72 : :
73 [ + - ][ # # ]: 367 : class EpsilonState : public NFA_State {
74 : : public:
75 : 35723 : EpsilonState() : NFA_State(SYM_EPSILON, 0) { }
76 : : };
77 : :
78 : : class NFA_Machine : public BroObj {
79 : : public:
80 : : NFA_Machine(NFA_State* first, NFA_State* final = 0);
81 : : ~NFA_Machine();
82 : :
83 : 44370 : NFA_State* FirstState() const { return first_state; }
84 : :
85 : : void SetFinalState(NFA_State* final) { final_state = final; }
86 : 19586 : NFA_State* FinalState() const { return final_state; }
87 : :
88 : : void AddAccept(int accept_val);
89 : :
90 : 1699 : void MakeClosure() { MakePositiveClosure(); MakeOptional(); }
91 : : void MakeOptional();
92 : : void MakePositiveClosure();
93 : :
94 : : // re{lower,upper}; upper can be NO_UPPER_BOUND = infinity.
95 : : void MakeRepl(int lower, int upper);
96 : :
97 : 1518 : void MarkBOL() { bol = 1; }
98 : 759 : void MarkEOL() { eol = 1; }
99 : :
100 : : NFA_Machine* DuplicateMachine();
101 : : void LinkCopies(int n);
102 : : void InsertEpsilon();
103 : : void AppendEpsilon();
104 : :
105 : : void AppendState(NFA_State* new_state);
106 : : void AppendMachine(NFA_Machine* new_mach);
107 : :
108 : : void Describe(ODesc* d) const;
109 : : void Dump(FILE* f);
110 : : void DumpStats(FILE* f);
111 : :
112 : 0 : unsigned int MemoryAllocation() const
113 : 0 : { return padded_sizeof(*this) + first_state->TotalMemoryAllocation(); }
114 : :
115 : : protected:
116 : : NFA_State* first_state;
117 : : NFA_State* final_state;
118 : : int bol, eol;
119 : : };
120 : :
121 : : extern NFA_Machine* make_alternate(NFA_Machine* m1, NFA_Machine* m2);
122 : :
123 : : // The epsilon closure is the set of all states reachable by an arbitrary
124 : : // number of epsilon transitions, which themselves do not have epsilon
125 : : // transitions going out, unioned with the set of states which have non-null
126 : : // accepting numbers. "states" is deleted by the call. The return value
127 : : // is the epsilon closure (sorted by state IDs()).
128 : : extern NFA_state_list* epsilon_closure(NFA_state_list* states);
129 : :
130 : : // For sorting NFA states based on their ID fields (decreasing)
131 : : extern int NFA_state_cmp_neg(const void* v1, const void* v2);
132 : :
133 : : #endif
|