· 8 years ago · Jun 09, 2018, 05:36 AM
1/*! \file AG_RegEx.cpp
2 \brief implementation of the CAG_RegEx class
3 \author Amer Gerzic
4*/
5
6//#include "stdafx.h"
7//#include "RegExDemo.h"
8#include "AG_RegEx.h"
9
10#ifdef _DEBUG
11#undef THIS_FILE
12static char THIS_FILE[]=__FILE__;
13#define new DEBUG_NEW
14#endif
15
16CAG_RegEx::CAG_RegEx()
17{
18 m_nNextStateID = 0;
19}
20
21CAG_RegEx::~CAG_RegEx()
22{
23 // Clean up all allocated memory
24 CleanUp();
25}
26
27bool CAG_RegEx::SetRegEx(string strRegEx)
28{
29 // 1. Clean up old regular expression
30 CleanUp();
31
32 // 2. Create NFA
33 if(!CreateNFA(strRegEx))
34 return false;
35
36 // 3. Convert to DFA
37 ConvertNFAtoDFA();
38
39 // 4. Reduce DFA
40 ReduceDFA();
41
42 return true;
43}
44
45bool CAG_RegEx::FindFirst(string strText, int &nPos, string &strPattern)
46{
47 // Clean up all pattern states
48 list<CAG_PatternState*>::iterator iter;
49 for(iter=m_PatternList.begin(); iter!=m_PatternList.end(); ++iter)
50 delete *iter;
51 m_PatternList.clear();
52
53 // reset the input text
54 m_strText = strText;
55
56 // Find all patterns
57 if(Find())
58 {
59 nPos = m_vecPos[0];
60 strPattern = m_vecPattern[0];
61 m_nPatternIndex = 0;
62 return true;
63 }
64
65 return false;
66}
67
68bool CAG_RegEx::FindNext(int &nPos, string &strPattern)
69{
70 ++m_nPatternIndex;
71 if(m_nPatternIndex<m_vecPos.size())
72 {
73 nPos = m_vecPos[m_nPatternIndex];
74 strPattern = m_vecPattern[m_nPatternIndex];
75 return true;
76 }
77 return false;
78}
79
80bool CAG_RegEx::Find()
81{
82 bool bRes = false;
83
84 // Clean up for new search
85 m_vecPos.clear();
86 m_vecPattern.clear();
87
88 // if there is no DFA then there is no matching
89 if(m_DFATable.empty())
90 return false;
91
92 // Go through all input charactes
93 for(int i=0; i<m_strText.size(); ++i)
94 {
95 char c = m_strText[i];
96
97 // Check all patterns states
98 list<CAG_PatternState*>::iterator iter;
99 for(iter=m_PatternList.begin(); iter!=m_PatternList.end(); ++iter)
100 {
101 CAG_PatternState *pPatternState = *iter;
102 vector<CAG_State*> Transition; // must be at most one because this is DFA
103 pPatternState->m_pState->GetTransition(c, Transition);
104 if(!Transition.empty())
105 {
106 pPatternState->m_pState = Transition[0];
107 if(Transition[0]->m_bAcceptingState)
108 {
109 m_vecPos.push_back(pPatternState->m_nStartIndex);
110 m_vecPattern.push_back(m_strText.substr(pPatternState->m_nStartIndex,
111 i-pPatternState->m_nStartIndex+1));
112 }
113 }
114 else
115 {
116 // Delete this pattern state
117 iter = m_PatternList.erase(iter);
118 --iter;
119 }
120 }
121
122 // Check it against state 1 of the DFA
123 CAG_State *pState = m_DFATable[0];
124 vector<CAG_State*> Transition; // must be at most one because this is DFA
125 pState->GetTransition(c, Transition);
126 if(!Transition.empty())
127 {
128 CAG_PatternState *pPatternState = new CAG_PatternState();
129 pPatternState->m_nStartIndex = i;
130 pPatternState->m_pState = Transition[0];
131 m_PatternList.push_back(pPatternState);
132
133 // Check is this accepting state
134 if(Transition[0]->m_bAcceptingState)
135 {
136 m_vecPos.push_back(i);
137 string strTemp;
138 strTemp += c;
139 m_vecPattern.push_back(strTemp);
140 }
141 }
142 else
143 {
144 // Check here is the entry state already accepting
145 // because a* for example would accept 0 or many a's
146 // whcih means that any character is actually accepted
147 if(pState->m_bAcceptingState)
148 {
149 m_vecPos.push_back(i);
150 string strTemp;
151 strTemp += c;
152 m_vecPattern.push_back(strTemp);
153 }
154 }
155 }
156
157 return(m_vecPos.size()>0);
158}
159
160bool CAG_RegEx::Eval()
161{
162 // First pop the operator from the stack
163 if(m_OperatorStack.size()>0)
164 {
165 char chOperator = m_OperatorStack.top();
166 m_OperatorStack.pop();
167
168 // Check which operator it is
169 switch(chOperator)
170 {
171 case 42:
172 return Star();
173 break;
174 case 124:
175 return Union();
176 break;
177 case 8:
178 return Concat();
179 break;
180 }
181
182 return false;
183 }
184
185 return false;
186}
187
188bool CAG_RegEx::Concat()
189{
190 // Pop 2 elements
191 FSA_TABLE A, B;
192 if(!Pop(B) || !Pop(A))
193 return false;
194
195 // Now evaluate AB
196 // Basically take the last state from A
197 // and add an epsilon transition to the
198 // first state of B. Store the result into
199 // new NFA_TABLE and push it onto the stack
200 A[A.size()-1]->AddTransition(0, B[0]);
201 A.insert(A.end(), B.begin(), B.end());
202
203 // Push the result onto the stack
204 m_OperandStack.push(A);
205
206 //TRACE("CONCAT\n");
207
208 return true;
209}
210
211bool CAG_RegEx::Star()
212{
213 // Pop 1 element
214 FSA_TABLE A, B;
215 if(!Pop(A))
216 return false;
217
218 // Now evaluate A*
219 // Create 2 new states which will be inserted
220 // at each end of deque. Also take A and make
221 // a epsilon transition from last to the first
222 // state in the queue. Add epsilon transition
223 // between two new states so that the one inserted
224 // at the begin will be the source and the one
225 // inserted at the end will be the destination
226 CAG_State *pStartState = new CAG_State(++m_nNextStateID);
227 CAG_State *pEndState = new CAG_State(++m_nNextStateID);
228 pStartState->AddTransition(0, pEndState);
229
230 // add epsilon transition from start state to the first state of A
231 pStartState->AddTransition(0, A[0]);
232
233 // add epsilon transition from A last state to end state
234 A[A.size()-1]->AddTransition(0, pEndState);
235
236 // From A last to A first state
237 A[A.size()-1]->AddTransition(0, A[0]);
238
239 // construct new DFA and store it onto the stack
240 A.push_back(pEndState);
241 A.push_front(pStartState);
242
243 // Push the result onto the stack
244 m_OperandStack.push(A);
245
246 //TRACE("STAR\n");
247
248 return true;
249}
250
251bool CAG_RegEx::Union()
252{
253 // Pop 2 elements
254 FSA_TABLE A, B;
255 if(!Pop(B) || !Pop(A))
256 return false;
257
258 // Now evaluate A|B
259 // Create 2 new states, a start state and
260 // a end state. Create epsilon transition from
261 // start state to the start states of A and B
262 // Create epsilon transition from the end
263 // states of A and B to the new end state
264 CAG_State *pStartState = new CAG_State(++m_nNextStateID);
265 CAG_State *pEndState = new CAG_State(++m_nNextStateID);
266 pStartState->AddTransition(0, A[0]);
267 pStartState->AddTransition(0, B[0]);
268 A[A.size()-1]->AddTransition(0, pEndState);
269 B[B.size()-1]->AddTransition(0, pEndState);
270
271 // Create new NFA from A
272 B.push_back(pEndState);
273 A.push_front(pStartState);
274 A.insert(A.end(), B.begin(), B.end());
275
276 // Push the result onto the stack
277 m_OperandStack.push(A);
278
279 //TRACE("UNION\n");
280
281 return true;
282}
283
284string CAG_RegEx::ConcatExpand(string strRegEx)
285{
286 string strRes;
287
288 for(int i=0; i<strRegEx.size()-1; ++i)
289 {
290 char cLeft = strRegEx[i];
291 char cRight = strRegEx[i+1];
292 strRes += cLeft;
293 if((IsInput(cLeft)) || (IsRightParanthesis(cLeft)) || (cLeft == '*'))
294 if((IsInput(cRight)) || (IsLeftParanthesis(cRight)))
295 strRes += char(8);
296 }
297 strRes += strRegEx[strRegEx.size()-1];
298
299 return strRes;
300}
301
302bool CAG_RegEx::CreateNFA(string strRegEx)
303{
304 // Parse regular expresion using similar
305 // method to evaluate arithmetic expressions
306 // But first we will detect concatenation and
307 // insert char(8) at the position where
308 // concatenation needs to occur
309 strRegEx = ConcatExpand(strRegEx);
310
311 for(int i=0; i<strRegEx.size(); ++i)
312 {
313 // get the charcter
314 char c = strRegEx[i];
315
316 if(IsInput(c))
317 Push(c);
318 else if(m_OperatorStack.empty())
319 m_OperatorStack.push(c);
320 else if(IsLeftParanthesis(c))
321 m_OperatorStack.push(c);
322 else if(IsRightParanthesis(c))
323 {
324 // Evaluate everyting in paranthesis
325 while(!IsLeftParanthesis(m_OperatorStack.top()))
326 if(!Eval())
327 return false;
328 // Remove left paranthesis after the evaluation
329 m_OperatorStack.pop();
330 }
331 else
332 {
333 while(!m_OperatorStack.empty() && Presedence(c, m_OperatorStack.top()))
334 if(!Eval())
335 return false;
336 m_OperatorStack.push(c);
337 }
338 }
339
340 // Evaluate the rest of operators
341 while(!m_OperatorStack.empty())
342 if(!Eval())
343 return false;
344
345 // Pop the result from the stack
346 if(!Pop(m_NFATable))
347 return false;
348
349 // Last NFA state is always accepting state
350 m_NFATable[m_NFATable.size()-1]->m_bAcceptingState = true;
351
352 return true;
353}
354
355void CAG_RegEx::Push(char chInput)
356{
357 // Create 2 new states on the heap
358 CAG_State *s0 = new CAG_State(++m_nNextStateID);
359 CAG_State *s1 = new CAG_State(++m_nNextStateID);
360
361 // Add the transition from s0->s1 on input character
362 s0->AddTransition(chInput, s1);
363
364 // Create a NFA from these 2 states
365 FSA_TABLE NFATable;
366 NFATable.push_back(s0);
367 NFATable.push_back(s1);
368
369 // push it onto the operand stack
370 m_OperandStack.push(NFATable);
371
372 // Add this character to the input character set
373 m_InputSet.insert(chInput);
374
375 //TRACE("PUSH %s\n", CString(chInput));
376}
377
378bool CAG_RegEx::Pop(FSA_TABLE &NFATable)
379{
380 // If the stack is empty we cannot pop anything
381 if(m_OperandStack.size()>0)
382 {
383 NFATable = m_OperandStack.top();
384 m_OperandStack.pop();
385 return true;
386 }
387
388 return false;
389}
390
391void CAG_RegEx::EpsilonClosure(set<CAG_State*> T, set<CAG_State*> &Res)
392{
393 Res.clear();
394
395 // Initialize result with T because each state
396 // has epsilon closure to itself
397 Res = T;
398
399 // Push all states onto the stack
400 stack<CAG_State*> unprocessedStack;
401 set<CAG_State*>::iterator iter;
402 for(iter=T.begin(); iter!=T.end(); ++iter)
403 unprocessedStack.push(*iter);
404
405 // While the unprocessed stack is not empty
406 while(!unprocessedStack.empty())
407 {
408 // Pop t, the top element from unprocessed stack
409 CAG_State* t = unprocessedStack.top();
410 unprocessedStack.pop();
411
412 // Get all epsilon transition for this state
413 vector<CAG_State*> epsilonStates;
414 t->GetTransition(0, epsilonStates);
415
416 // For each state u with an edge from t to u labeled epsilon
417 for(int i=0; i<epsilonStates.size(); ++i)
418 {
419 CAG_State* u = epsilonStates[i];
420 // if u not in e-closure(T)
421 if(Res.find(u) == Res.end())
422 {
423 Res.insert(u);
424 unprocessedStack.push(u);
425 }
426 }
427 }
428}
429
430void CAG_RegEx::Move(char chInput, set<CAG_State*> T, set<CAG_State*> &Res)
431{
432 Res.clear();
433
434 /* This is very simple since I designed the NFA table
435 structure in a way that we just need to loop through
436 each state in T and recieve the transition on chInput.
437 Then we will put all the results into the set, which
438 will eliminate duplicates automatically for us.
439 */
440 set<CAG_State*>::iterator iter;
441 for(iter=T.begin(); iter!=T.end(); ++iter)
442 {
443 // Get all transition states from this specific
444 // state to other states
445 CAG_State* pState = *iter;
446 vector<CAG_State*> States;
447 pState->GetTransition(chInput, States);
448
449 // Now add these all states to the result
450 // This will eliminate duplicates
451 for(int i=0; i<States.size(); ++i)
452 Res.insert(States[i]);
453 }
454}
455
456void CAG_RegEx::ConvertNFAtoDFA()
457{
458 // Clean up the DFA Table first
459 for(int i=0; i<m_DFATable.size(); ++i)
460 delete m_DFATable[i];
461 m_DFATable.clear();
462
463 // Check is NFA table empty
464 if(m_NFATable.size() == 0)
465 return;
466
467 // Reset the state id for new naming
468 m_nNextStateID = 0;
469
470 // Array of unprocessed DFA states
471 vector<CAG_State*> unmarkedStates;
472
473 // Starting state of DFA is epsilon closure of
474 // starting state of NFA state (set of states)
475 set<CAG_State*> DFAStartStateSet;
476 set<CAG_State*> NFAStartStateSet;
477 NFAStartStateSet.insert(m_NFATable[0]);
478 EpsilonClosure(NFAStartStateSet, DFAStartStateSet);
479
480 // Create new DFA State (start state) from the NFA states
481 CAG_State *DFAStartState = new CAG_State(DFAStartStateSet, ++m_nNextStateID);
482
483 // Add the start state to the DFA
484 m_DFATable.push_back(DFAStartState);
485
486 // Add the starting state to set of unprocessed DFA states
487 unmarkedStates.push_back(DFAStartState);
488 while(!unmarkedStates.empty())
489 {
490 // process an unprocessed state
491 CAG_State* processingDFAState = unmarkedStates[unmarkedStates.size()-1];
492 unmarkedStates.pop_back();
493
494 // for each input signal a
495 set<char>::iterator iter;
496 for(iter=m_InputSet.begin(); iter!=m_InputSet.end(); ++iter)
497 {
498 set<CAG_State*> MoveRes, EpsilonClosureRes;
499 Move(*iter, processingDFAState->GetNFAState(), MoveRes);
500 EpsilonClosure(MoveRes, EpsilonClosureRes);
501
502 // Check is the resulting set (EpsilonClosureSet) in the
503 // set of DFA states (is any DFA state already constructed
504 // from this set of NFA states) or in pseudocode:
505 // is U in D-States already (U = EpsilonClosureSet)
506 bool bFound = false;
507 CAG_State *s = NULL;
508 for(i=0; i<m_DFATable.size(); ++i)
509 {
510 s = m_DFATable[i];
511 if(s->GetNFAState() == EpsilonClosureRes)
512 {
513 bFound = true;
514 break;
515 }
516 }
517 if(!bFound)
518 {
519 CAG_State* U = new CAG_State(EpsilonClosureRes, ++m_nNextStateID);
520 unmarkedStates.push_back(U);
521 m_DFATable.push_back(U);
522
523 // Add transition from processingDFAState to new state on the current character
524 processingDFAState->AddTransition(*iter, U);
525 }
526 else
527 {
528 // This state already exists so add transition from
529 // processingState to already processed state
530 processingDFAState->AddTransition(*iter, s);
531 }
532 }
533 }
534}
535
536void CAG_RegEx::ReduceDFA()
537{
538 // Get the set of all dead end states in DFA
539 set<CAG_State*> DeadEndSet;
540 for(int i=0; i<m_DFATable.size(); ++i)
541 if(m_DFATable[i]->IsDeadEnd())
542 DeadEndSet.insert(m_DFATable[i]);
543
544 // If there are no dead ends then there is nothing to reduce
545 if(DeadEndSet.empty())
546 return;
547
548 // Remove all transitions to these states
549 set<CAG_State*>::iterator iter;
550 for(iter=DeadEndSet.begin(); iter!=DeadEndSet.end(); ++iter)
551 {
552 // Remove all transitions to this state
553 for(i=0; i<m_DFATable.size(); ++i)
554 m_DFATable[i]->RemoveTransition(*iter);
555
556 // Remove this state from the DFA Table
557 deque<CAG_State*>::iterator pos;
558 for(pos=m_DFATable.begin(); pos!=m_DFATable.end(); ++pos)
559 if(*pos == *iter)
560 break;
561 // Erase element from the table
562 m_DFATable.erase(pos);
563
564 // Now free the memory used by the element
565 delete *iter;
566 }
567}