xiiregexbuilder
FPGA-Accelerated Regular Expression Matching Enginesrc/nfa.cpp (8805B)
1#include "nfa.h"
2#include <iostream>
3#include <algorithm>
4
5// Start at -1 so the first ++globalStateCounter gives 0.
6int NFABuilder::globalStateCounter = -1;
7
8void NFA::addState(int id, bool isAccept) {
9 states.emplace(id, NFAState(id, isAccept));
10}
11
12void NFA::addTransition(int fromId, unsigned char c, int toId) {
13 states.at(fromId).transitions[c].insert(toId);
14}
15
16bool NFA::simulate(const std::string& input) const {
17 std::set<int> activeStates = {startStateId};
18
19 for (unsigned char c : input) {
20 std::set<int> nextStates;
21 for (int stateId : activeStates) {
22 auto& state = states.at(stateId);
23 if (state.transitions.count(c)) {
24 for (int nextId : state.transitions.at(c)) {
25 nextStates.insert(nextId);
26 }
27 }
28 }
29 activeStates = nextStates;
30 if (activeStates.empty()) return false;
31 }
32
33 for (int stateId : activeStates) {
34 if (states.at(stateId).isAccept) return true;
35 }
36 return false;
37}
38
39std::unique_ptr<NFA> NFABuilder::build(ASTNode* root, int regexIdx) {
40 if (!root) return nullptr;
41
42 auto nfa = std::make_unique<NFA>(regexIdx);
43
44 // 1. Linearization (assign positions to symbols)
45 int localPosCounter = 1;
46 std::map<int, std::set<unsigned char>> posToChars;
47 std::set<int> dotPositions;
48 linearize(root, localPosCounter, posToChars, dotPositions);
49 int numPositions = localPosCounter - 1;
50
51 // 2. Compute nullable, firstpos, lastpos
52 computeNullableFirstLast(root);
53
54 // 3. Compute followpos
55 std::map<int, std::set<int>> followpos;
56 for (int i = 1; i <= numPositions; ++i) {
57 followpos[i] = std::set<int>();
58 }
59 computeFollowpos(root, followpos);
60
61 // 4. Build NFA states and transitions
62 // Glushkov states: 0 (initial) + 1..n
63 // We map these to global IDs.
64 // Invariant: after each build(), globalStateCounter equals the highest global ID used.
65
66 int startGlobalId = ++globalStateCounter;
67 nfa->startStateId = startGlobalId;
68 std::map<int, int> localToGlobal;
69 localToGlobal[0] = startGlobalId;
70 nfa->addState(startGlobalId, root->nullable);
71
72 for (int i = 1; i <= numPositions; ++i) {
73 localToGlobal[i] = ++globalStateCounter;
74 bool isAccept = (root->lastpos.find(i) != root->lastpos.end());
75 nfa->addState(localToGlobal[i], isAccept);
76 }
77
78 // Transitions from state 0
79 for (int p : root->firstpos) {
80 if (dotPositions.find(p) != dotPositions.end()) { // DOT
81 for (int val = 32; val <= 126; ++val) {
82 nfa->addTransition(localToGlobal[0], static_cast<unsigned char>(val), localToGlobal[p]);
83 }
84 } else {
85 for (unsigned char c : posToChars[p]) {
86 nfa->addTransition(localToGlobal[0], c, localToGlobal[p]);
87 }
88 }
89 }
90
91 // Transitions from state p > 0
92 for (int p = 1; p <= numPositions; ++p) {
93 for (int q : followpos[p]) {
94 if (dotPositions.find(q) != dotPositions.end()) { // DOT
95 for (int val = 32; val <= 126; ++val) {
96 nfa->addTransition(localToGlobal[p], static_cast<unsigned char>(val), localToGlobal[q]);
97 }
98 } else {
99 for (unsigned char c : posToChars[q]) {
100 nfa->addTransition(localToGlobal[p], c, localToGlobal[q]);
101 }
102 }
103 }
104 }
105
106 return nfa;
107}
108
109void NFABuilder::linearize(ASTNode* node, int& posCounter, std::map<int, std::set<unsigned char>>& posToChars, std::set<int>& dotPositions) {
110 if (!node) return;
111 switch (node->type) {
112 case ASTNodeType::LITERAL: {
113 auto n = static_cast<LiteralNode*>(node);
114 n->position = posCounter++;
115 posToChars[n->position] = {static_cast<unsigned char>(n->value)};
116 break;
117 }
118 case ASTNodeType::DOT: {
119 auto n = static_cast<DotNode*>(node);
120 n->position = posCounter++;
121 dotPositions.insert(n->position);
122 break;
123 }
124 case ASTNodeType::CHAR_CLASS: {
125 auto n = static_cast<CharClassNode*>(node);
126 n->position = posCounter++;
127 posToChars[n->position] = n->characters;
128 break;
129 }
130 case ASTNodeType::CONCATENATION: {
131 auto n = static_cast<ConcatenationNode*>(node);
132 linearize(n->left.get(), posCounter, posToChars, dotPositions);
133 linearize(n->right.get(), posCounter, posToChars, dotPositions);
134 break;
135 }
136 case ASTNodeType::UNION: {
137 auto n = static_cast<UnionNode*>(node);
138 linearize(n->left.get(), posCounter, posToChars, dotPositions);
139 linearize(n->right.get(), posCounter, posToChars, dotPositions);
140 break;
141 }
142 case ASTNodeType::STAR:
143 case ASTNodeType::PLUS:
144 case ASTNodeType::OPTIONAL: {
145 auto n = static_cast<StarNode*>(node);
146 linearize(n->inner.get(), posCounter, posToChars, dotPositions);
147 break;
148 }
149 default: break;
150 }
151}
152
153void NFABuilder::computeNullableFirstLast(ASTNode* node) {
154 if (!node) return;
155 switch (node->type) {
156 case ASTNodeType::LITERAL:
157 case ASTNodeType::DOT:
158 case ASTNodeType::CHAR_CLASS: {
159 node->nullable = false;
160 int pos = -1;
161 if (node->type == ASTNodeType::LITERAL) pos = static_cast<LiteralNode*>(node)->position;
162 else if (node->type == ASTNodeType::DOT) pos = static_cast<DotNode*>(node)->position;
163 else pos = static_cast<CharClassNode*>(node)->position;
164 node->firstpos = {pos};
165 node->lastpos = {pos};
166 break;
167 }
168 case ASTNodeType::CONCATENATION: {
169 auto n = static_cast<ConcatenationNode*>(node);
170 computeNullableFirstLast(n->left.get());
171 computeNullableFirstLast(n->right.get());
172 n->nullable = n->left->nullable && n->right->nullable;
173 n->firstpos = n->left->firstpos;
174 if (n->left->nullable) n->firstpos.insert(n->right->firstpos.begin(), n->right->firstpos.end());
175 n->lastpos = n->right->lastpos;
176 if (n->right->nullable) n->lastpos.insert(n->left->lastpos.begin(), n->left->lastpos.end());
177 break;
178 }
179 case ASTNodeType::UNION: {
180 auto n = static_cast<UnionNode*>(node);
181 computeNullableFirstLast(n->left.get());
182 computeNullableFirstLast(n->right.get());
183 n->nullable = n->left->nullable || n->right->nullable;
184 n->firstpos = n->left->firstpos;
185 n->firstpos.insert(n->right->firstpos.begin(), n->right->firstpos.end());
186 n->lastpos = n->left->lastpos;
187 n->lastpos.insert(n->right->lastpos.begin(), n->right->lastpos.end());
188 break;
189 }
190 case ASTNodeType::STAR:
191 case ASTNodeType::PLUS:
192 case ASTNodeType::OPTIONAL: {
193 auto n = static_cast<StarNode*>(node);
194 computeNullableFirstLast(n->inner.get());
195 n->nullable = (node->type != ASTNodeType::PLUS) || n->inner->nullable;
196 if (node->type == ASTNodeType::STAR || node->type == ASTNodeType::OPTIONAL) n->nullable = true;
197 n->firstpos = n->inner->firstpos;
198 n->lastpos = n->inner->lastpos;
199 break;
200 }
201 default: break;
202 }
203}
204
205void NFABuilder::computeFollowpos(ASTNode* node, std::map<int, std::set<int>>& followpos) {
206 if (!node) return;
207 switch (node->type) {
208 case ASTNodeType::CONCATENATION: {
209 auto n = static_cast<ConcatenationNode*>(node);
210 computeFollowpos(n->left.get(), followpos);
211 computeFollowpos(n->right.get(), followpos);
212 for (int p : n->left->lastpos) followpos[p].insert(n->right->firstpos.begin(), n->right->firstpos.end());
213 break;
214 }
215 case ASTNodeType::STAR:
216 case ASTNodeType::PLUS: {
217 auto n = static_cast<StarNode*>(node);
218 computeFollowpos(n->inner.get(), followpos);
219 for (int p : n->inner->lastpos) followpos[p].insert(n->inner->firstpos.begin(), n->inner->firstpos.end());
220 break;
221 }
222 case ASTNodeType::UNION: {
223 auto n = static_cast<UnionNode*>(node);
224 computeFollowpos(n->left.get(), followpos);
225 computeFollowpos(n->right.get(), followpos);
226 break;
227 }
228 case ASTNodeType::OPTIONAL: {
229 auto n = static_cast<OptionalNode*>(node);
230 computeFollowpos(n->inner.get(), followpos);
231 break;
232 }
233 default: break;
234 }
235}