1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 // FSM.cc
4 // ------
5 // Dragon final state machine implementation module
6 //
7 // Design and Implementation by Bjoern Lemke
8 //
9 // (C)opyright 2007 by Bjoern Lemke
10 //
11 // This program is free software; you can redistribute it and/or modify
12 // it under the terms of the GNU General Public License as published by
13 // the Free Software Foundation; either version 2, or (at your option)
14 // any later version.
15 //
16 // This program is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU General Public License
22 // along with this program; see the file COPYING. If not, write to
23 // the Free Software Foundation, 59 Temple Place - Suite 330,
24 // Boston, MA 02111-1307, USA.
25 //
26 // IMPLEMENTATION MODULE
27 //
28 // Class: FSM
29 //
30 // Description: implementation of a final state machine for lexical analysis
31 //
32 ///////////////////////////////////////////////////////////////////////////////
33
34 // DRAGON INCLUDES
35
36 #include "FSM.h"
37
38 /////////////////////////////////
39 // FSM Class Implementation //
40 /////////////////////////////////
41
EpsilonClosureMap()42 FSM::EpsilonClosureMap::EpsilonClosureMap()
43 {
44 }
45
EpsilonClosureMap(unsigned long state)46 FSM::EpsilonClosureMap::EpsilonClosureMap(unsigned long state)
47 {
48 _state = state;
49 }
50
EpsilonClosureMap(unsigned long state,SetT<unsigned long> & closure)51 FSM::EpsilonClosureMap::EpsilonClosureMap(unsigned long state, SetT<unsigned long>& closure)
52 {
53 _state = state;
54 _closure = closure;
55
56 }
57
operator =(const FSM::EpsilonClosureMap & m)58 FSM::EpsilonClosureMap FSM::EpsilonClosureMap::operator = (const FSM::EpsilonClosureMap& m)
59 {
60 _state = m._state;
61 _closure = m._closure;
62 return(*this);
63 }
64
operator ==(FSM::EpsilonClosureMap m)65 bool FSM::EpsilonClosureMap::operator == (FSM::EpsilonClosureMap m)
66 {
67 if (_state == m._state)
68 return true;
69 return false;
70 }
71
operator <(FSM::EpsilonClosureMap m)72 bool FSM::EpsilonClosureMap::operator < (FSM::EpsilonClosureMap m)
73 {
74 if (_state < m._state)
75 return true;
76 return false;
77 }
78
operator >(FSM::EpsilonClosureMap m)79 bool FSM::EpsilonClosureMap::operator > (FSM::EpsilonClosureMap m)
80 {
81 if (_state > m._state)
82 return true;
83 return false;
84 }
85
getState()86 long FSM::EpsilonClosureMap::getState()
87 {
88 return _state;
89 }
90
getClosure()91 SetT<unsigned long>& FSM::EpsilonClosureMap::getClosure()
92 {
93 return _closure;
94 }
95
FSM(TreeT<FSMState> * pStateTable,TreeT<FSMTransition> * pTransitionTable)96 FSM::FSM(TreeT<FSMState> * pStateTable, TreeT<FSMTransition> *pTransitionTable)
97 {
98 _pStateTable = pStateTable;
99 _pTransitionTable = pTransitionTable;
100 }
101
~FSM()102 FSM::~FSM()
103 {
104 }
105
epsilonFree()106 void FSM::epsilonFree()
107 {
108
109 TreeT<EpsilonClosureMap> map;
110 SetT<unsigned long> closureSet;
111
112 unsigned long startState;
113
114 TreeT<FSMTransition> tmpTransitionTable;
115
116 FSMState *pState = _pStateTable->First();
117 while (pState)
118 {
119 if (pState->Type() == START)
120 startState = pState->Num();
121
122 SetT<unsigned long> closureSet;
123 buildEpsilonClosure(pState->Num(), closureSet);
124 EpsilonClosureMap c(pState->Num(), closureSet);
125 map.Insert(c);
126 pState = _pStateTable->Next();
127 }
128
129 FSMTransition *pTrans = _pTransitionTable->First();
130
131 while (pTrans)
132 {
133 FSMState *pState = _pStateTable->First();
134 while (pState)
135 {
136 EpsilonClosureMap *pMap = map.Find(EpsilonClosureMap(pState->Num()));
137
138 if (pMap)
139 {
140
141 if (pMap->getClosure().Find(pTrans->Source()) && pTrans->Sign() != EPSILON )
142 {
143 tmpTransitionTable.Insert(FSMTransition(pState->Num(),
144 pTrans->Target(),
145 pTrans->Sign()));
146 }
147 }
148 pState = _pStateTable->Next();
149 }
150 pTrans = _pTransitionTable->Next();
151
152 }
153
154
155 TreeT<FSMState> newStateTable;
156 TreeT<FSMTransition> newTransTable;
157
158 // build up new state table
159
160
161 EpsilonClosureMap *pMap = map.First();
162 while (pMap)
163 {
164
165 SetT<unsigned long> c = pMap->getClosure();
166
167 StateType stateType = NONE;
168 Chain token;
169
170 // find out new state type
171
172 unsigned long *pCS = c.First();
173 while (pCS)
174 {
175 FSMState *pState = _pStateTable->First();
176 while (pState)
177 {
178 if ( pState->Num() == *pCS )
179 {
180
181 if (pMap->getState() == startState)
182 {
183 switch (pState->Type())
184 {
185 case START:
186 if (stateType == NONE)
187 stateType = START;
188 else if (stateType == FINAL)
189 stateType = ANY;
190 break;
191 case FINAL:
192 if (stateType == NONE)
193 stateType = FINAL;
194 else if (stateType == START)
195 stateType = ANY;
196 // token=Chain(pState->Token());
197 break;
198 case ANY:
199 stateType = ANY;
200 // token=Chain(pState->Token());
201 break;
202 case NONE:
203 break;
204 }
205 }
206 else
207 {
208 switch (pState->Type())
209 {
210 case FINAL:
211 stateType = FINAL;
212 // token=Chain(pState->Token());
213 break;
214 case ANY:
215 stateType = FINAL;
216 // token=Chain(pState->Token());
217 break;
218 case NONE:
219 break;
220 case START:
221 break;
222 }
223 }
224 }
225
226 pState = _pStateTable->Next();
227 }
228
229 // insert new state
230
231 pCS = c.Next();
232 }
233
234
235 newStateTable.Insert(FSMState(pMap->getState(), stateType, token));
236
237 pMap = map.Next();
238 }
239
240
241 // build up new trans table
242
243 SetT<unsigned long> todoStateSet;
244
245 pState = _pStateTable->First();
246 while (pState)
247 {
248 if (pState->Type() == START || pState->Type() == ANY)
249 {
250 todoStateSet.Insert(pState->Num());
251
252 }
253 pState = _pStateTable->Next();
254 }
255
256
257 SetT<unsigned long> doneStateSet;
258
259 while ( ! todoStateSet.isEmpty())
260 {
261
262 unsigned long *pS = todoStateSet.First();
263 if (pS)
264 {
265 FSMTransition *pTrans = tmpTransitionTable.First();
266 while (pTrans)
267 {
268 if (*pS == pTrans->Source())
269 {
270 newTransTable.Insert(FSMTransition(pTrans->Source(),
271 pTrans->Target(),
272 pTrans->Sign()));
273
274 if (doneStateSet.Find(pTrans->Target()) == 0)
275 todoStateSet.Insert(pTrans->Target());
276 }
277 pTrans = tmpTransitionTable.Next();
278
279 }
280 }
281
282 doneStateSet.Insert(*pS);
283 todoStateSet.Remove(*pS);
284
285 }
286
287 _pStateTable->Empty();
288 _pTransitionTable->Empty();
289
290 // copy new tables
291
292 // native copy of transitions
293
294 pTrans = newTransTable.First();
295 while (pTrans)
296 {
297 _pTransitionTable->Insert(*pTrans);
298 pTrans = newTransTable.Next();
299 }
300
301 // check out reachable states during state table copy
302
303 pState = newStateTable.First();
304 while (pState)
305 {
306 pTrans = _pTransitionTable->First();
307 bool notFound = true;
308 while (pTrans && notFound)
309 {
310 if (pTrans->Source() == pState->Num()
311 || pTrans->Target() == pState->Num())
312 {
313 _pStateTable->Insert(*pState);
314 notFound = false;
315 }
316 pTrans = _pTransitionTable->Next();
317 }
318 pState = newStateTable.Next();
319 }
320
321 }
322
buildEpsilonClosure(unsigned long state,SetT<unsigned long> & closureSet)323 void FSM::buildEpsilonClosure(unsigned long state, SetT<unsigned long>& closureSet )
324 {
325
326 closureSet.Insert(state);
327
328 FSMTransition *pTrans = _pTransitionTable->First();
329 while (pTrans)
330 {
331 void* treePointer = _pTransitionTable->getTreePointer();
332
333 if (pTrans->Source() == state && pTrans->Sign() == EPSILON)
334 {
335 closureSet.Insert(pTrans->Target());
336 SetT<unsigned long> tmpClosureSet;
337
338 buildEpsilonClosure(pTrans->Target(), tmpClosureSet);
339 closureSet = closureSet + tmpClosureSet;
340 }
341 _pTransitionTable->setTreePointer(treePointer);
342 pTrans = _pTransitionTable->Next();
343 }
344 }
345
346
invert()347 void FSM::invert()
348 {
349
350 FSMState* pState = _pStateTable->First();
351 while (pState)
352 {
353
354 if (pState->Type() == START)
355 {
356 pState->setType(FINAL);
357 }
358 else if (pState->Type() == FINAL)
359 {
360 pState->setType(START);
361 }
362
363
364
365 pState = _pStateTable->Next();
366 }
367
368 FSMTransition* pTrans = _pTransitionTable->First();
369 while (pTrans)
370 {
371 unsigned long swpNum = pTrans->Source();
372
373 pTrans->setSource(pTrans->Target());
374 pTrans->setTarget(swpNum);
375
376 pTrans = _pTransitionTable->Next();
377 }
378
379 }
380
determinate()381 void FSM::determinate()
382 {
383
384 TreeT<char> signSet;
385 FSMTransition* pTrans = _pTransitionTable->First();
386 while (pTrans)
387 {
388
389 signSet.Insert(pTrans->Sign());
390
391 pTrans = _pTransitionTable->Next();
392 }
393
394 TreeT<FSMState> startStateSet;
395
396 FSMState *pState = _pStateTable->First();
397 while (pState)
398 {
399 if (pState->Type() == START || pState->Type() == ANY)
400 {
401 startStateSet.Insert(*pState);
402 }
403 pState = _pStateTable->Next();
404 }
405
406 TreeT<PowerState> powerStateSet;
407 TreeT<PowerTransition> powerTransTable;
408
409 TreeT< TreeT<FSMState> > todoSet;
410 TreeT< TreeT<FSMState> > doneSet;
411 todoSet.Insert(startStateSet);
412
413 while ( ! todoSet.isEmpty() )
414 {
415
416 TreeT<FSMState>* pSourceStateSet = todoSet.First();
417
418 char* pSign = signSet.First();
419
420 while (pSign)
421 {
422
423 TreeT<FSMState> targetStateSet;
424
425 FSMState* pState = pSourceStateSet->First();
426 while (pState)
427 {
428
429 FSMTransition *pTrans = _pTransitionTable->First();
430 while (pTrans)
431 {
432 if (pTrans->Source() == pState->Num()
433 && pTrans->Sign() == *pSign)
434
435 {
436 FSMState *pTarget = _pStateTable->Find(FSMState(pTrans->Target()));
437 if (pTarget)
438 {
439 targetStateSet.Insert(*pTarget);
440 }
441 }
442 pTrans = _pTransitionTable->Next();
443 }
444 pState = pSourceStateSet->Next();
445 }
446
447 // insert new transition
448
449 if (! targetStateSet.isEmpty())
450 {
451 PowerTransition p( *pSourceStateSet, targetStateSet, *pSign);
452
453
454 powerTransTable.Insert(p);
455
456 if (! doneSet.Find(targetStateSet))
457 {
458 todoSet.Insert(targetStateSet);
459 }
460
461 }
462 pSign = signSet.Next();
463 }
464 doneSet.Insert(*pSourceStateSet);
465 todoSet.Remove(*pSourceStateSet);
466 }
467
468
469 unsigned long nextId=0;
470 PowerTransition *pPT = powerTransTable.First();
471 while (pPT)
472 {
473 PowerState s(pPT->getSource(), nextId, NONE);
474
475 if ( powerStateSet.Insert(s) )
476 nextId++;
477
478 PowerState t(pPT->getTarget(), nextId, NONE);
479
480 if ( powerStateSet.Insert(t) )
481 nextId++;
482
483 pPT = powerTransTable.Next();
484 }
485
486 PowerState *pPS = powerStateSet.First();
487
488 while (pPS)
489 {
490
491 StateType stateType = NONE;
492 Chain token;
493
494 if ( startStateSet == (TreeT<FSMState>)pPS->getStateSet() )
495 {
496 FSMState *pState = pPS->getStateSet().First();
497 while (pState)
498 {
499 switch (pState->Type())
500 {
501 case ANY:
502 stateType = ANY;
503 token = pState->Token();
504 break;
505 case START:
506 if (stateType == NONE)
507 stateType = START;
508 else if (stateType == FINAL)
509 stateType = ANY;
510 break;
511 case FINAL:
512 if (stateType == NONE)
513 stateType = FINAL;
514 else if (stateType == START)
515 stateType = ANY;
516 token = pState->Token();
517 break;
518 default:
519 break;
520 }
521 pState = pPS->getStateSet().Next();
522 }
523 }
524 else
525 {
526 FSMState *pState = pPS->getStateSet().First();
527 while (pState)
528 {
529 switch (pState->Type())
530 {
531 case FINAL:
532 stateType = FINAL;
533 token = pState->Token();
534 break;
535 case ANY:
536 stateType = FINAL;
537 token = pState->Token();
538 break;
539 default:
540 break;
541 }
542 pState = pPS->getStateSet().Next();
543 }
544 }
545
546 pPS->setType(stateType);
547 pPS->setToken(token);
548
549 pPS = powerStateSet.Next();
550 }
551
552 // build up origin tables
553
554 _pStateTable->Empty();
555 _pTransitionTable->Empty();
556
557 pPS = powerStateSet.First();
558 while (pPS)
559 {
560 FSMState s(pPS->getId(), pPS->getType(), pPS->getToken());
561 _pStateTable->Insert(s);
562 pPS = powerStateSet.Next();
563 }
564
565
566 pPT = powerTransTable.First();
567 while (pPT)
568 {
569 PowerState *pS = powerStateSet.Find(PowerState(pPT->getSource()));
570 PowerState *pT = powerStateSet.Find(PowerState(pPT->getTarget()));
571 if (pS && pT)
572 {
573 _pTransitionTable->Insert(FSMTransition(pS->getId(),
574 pT->getId(),
575 pPT->getSign()));
576 }
577 pPT = powerTransTable.Next();
578 }
579 }
580
States()581 unsigned long FSM::States()
582 {
583 return _pStateTable->Size();
584 }
585
Transitions()586 unsigned long FSM::Transitions()
587 {
588 return _pTransitionTable->Size();
589 }
590
printFsm()591 void FSM::printFsm()
592 {
593
594 cout << "StateTable:" << endl;
595 cout << "-----------" << endl;
596 cout << "Num Type" << endl;
597
598 FSMState* pState = _pStateTable->First();
599 while (pState)
600 {
601 cout.width(3);
602 cout << pState->Num() << " ";
603 cout.width(5);
604 switch (pState->Type())
605 {
606 case START:
607 cout << "START" << " ";
608 break;
609 case FINAL:
610 cout << "FINAL" << "(" << pState->Token() << ")";
611 break;
612 case ANY:
613 cout << "ANY" << "(" << pState->Token() << ")";
614 break;
615 case NONE:
616 cout << "NONE" << " ";
617 break;
618 }
619 cout << endl;
620 pState = _pStateTable->Next();
621 }
622
623
624 cout << "TransitionTable:" << endl;
625 cout << "----------------" << endl;
626 cout << "Source Target Sign" << endl;
627
628 FSMTransition* pTransition = _pTransitionTable->First();
629 while (pTransition) {
630 cout.width(6);
631 cout << pTransition->Source() << " ";
632 cout.width(6);
633 cout << pTransition->Target() << " ";
634 cout.width(4);
635 if (pTransition->Sign() == EPSILON)
636 cout << "EPL" << " ";
637 else
638 cout << pTransition->Sign() << " ";
639 cout << endl;
640
641 pTransition = _pTransitionTable->Next();
642 }
643
644 }
645
646
647
648 /////////////////////////////
649 // PowerState Methods //
650 ////////////////////////////
651
PowerState()652 FSM::PowerState::PowerState()
653 {
654 }
655
~PowerState()656 FSM::PowerState::~PowerState()
657 {
658 }
659
PowerState(const TreeT<FSMState> & stateSet)660 FSM::PowerState::PowerState(const TreeT<FSMState> &stateSet)
661 {
662 _stateSet = stateSet;
663 }
664
PowerState(const TreeT<FSMState> & stateSet,unsigned long id,StateType type)665 FSM::PowerState::PowerState(const TreeT<FSMState> &stateSet, unsigned long id, StateType type)
666 {
667 _stateSet = stateSet;
668 _id = id;
669 _type = type;
670 }
671
PowerState(const FSM::PowerState & p)672 FSM::PowerState::PowerState(const FSM::PowerState& p)
673 {
674 _stateSet = p._stateSet;
675 _id = p._id;
676 _type = p._type;
677 }
678
679
operator =(const FSM::PowerState & p)680 FSM::PowerState& FSM::PowerState::operator = (const FSM::PowerState& p)
681 {
682 _stateSet = p._stateSet;
683 _id = p._id;
684 _type = p._type;
685 return (*this);
686 }
687
operator ==(FSM::PowerState p)688 bool FSM::PowerState::operator == (FSM::PowerState p)
689 {
690 if ( _stateSet == p._stateSet )
691 {
692 return true;
693 }
694 return false;
695 }
696
697
operator <(FSM::PowerState p)698 bool FSM::PowerState::operator < (FSM::PowerState p)
699 {
700 if ( _stateSet < p._stateSet )
701 {
702 return true;
703 }
704 return false;
705 }
706
operator >(FSM::PowerState p)707 bool FSM::PowerState::operator > (FSM::PowerState p)
708 {
709 if ( _stateSet > p._stateSet )
710 {
711 return true;
712 }
713 return false;
714 }
715
setType(StateType type)716 void FSM::PowerState::setType(StateType type)
717 {
718 _type = type;
719 }
720
setToken(const Chain & token)721 void FSM::PowerState::setToken(const Chain& token)
722 {
723 _token = token;
724 }
725
getStateSet()726 TreeT<FSMState>& FSM::PowerState::getStateSet()
727 {
728 return _stateSet;
729 }
730
getId()731 unsigned long FSM::PowerState::getId()
732 {
733 return _id;
734 }
735
getType()736 StateType FSM::PowerState::getType()
737 {
738 return _type;
739 }
740
getToken()741 const Chain& FSM::PowerState::getToken()
742 {
743 return _token;
744 }
745
746
747 /////////////////////////////
748 // PowerTransition Methods //
749 ////////////////////////////
750
PowerTransition()751 FSM::PowerTransition::PowerTransition()
752 {
753 }
754
~PowerTransition()755 FSM::PowerTransition::~PowerTransition()
756 {
757 }
758
PowerTransition(const TreeT<FSMState> & source,const TreeT<FSMState> & target,char sign)759 FSM::PowerTransition::PowerTransition(const TreeT<FSMState> &source, const TreeT<FSMState>& target, char sign)
760 {
761 _source = source;
762 _target = target;
763 _sign = sign;
764 }
765
PowerTransition(const FSM::PowerTransition & x)766 FSM::PowerTransition::PowerTransition(const FSM::PowerTransition& x)
767 {
768 _source = x._source;
769 _target = x._target;
770 _sign = x._sign;
771 }
772
773
operator =(const FSM::PowerTransition & x)774 FSM::PowerTransition& FSM::PowerTransition::operator = (const FSM::PowerTransition& x)
775 {
776 _source = x._source;
777 _target = x._target;
778 _sign = x._sign;
779 return (*this);
780 }
781
operator ==(FSM::PowerTransition x)782 bool FSM::PowerTransition::operator == (FSM::PowerTransition x)
783 {
784 if ( _source == x._source && _target == x._target && _sign == x._sign)
785 {
786 return true;
787 }
788 return false;
789 }
790
operator >(FSM::PowerTransition x)791 bool FSM::PowerTransition::operator > (FSM::PowerTransition x)
792 {
793 if ( _source > x._source )
794 {
795 return true;
796 } else if ( _source == x._source )
797 {
798 if ( _target > x._target )
799 {
800 return true;
801 } else if ( _target == x._target )
802 {
803 if ( _sign > x._sign )
804 {
805 return true;
806 }
807 }
808 }
809
810 return false;
811 }
812
operator <(FSM::PowerTransition x)813 bool FSM::PowerTransition::operator < (FSM::PowerTransition x)
814 {
815 if ( _source < x._source )
816 {
817 return true;
818 } else if ( _source == x._source )
819 {
820 if ( _target < x._target )
821 {
822 return true;
823 } else if ( _target == x._target )
824 {
825 if ( _sign < x._sign )
826 {
827 return true;
828 }
829 }
830 }
831
832 return false;
833 }
834
835
getSource()836 TreeT<FSMState>& FSM::PowerTransition::getSource()
837 {
838 return _source;
839 }
840
getTarget()841 TreeT<FSMState>& FSM::PowerTransition::getTarget()
842 {
843 return _target;
844 }
845
getSign()846 char FSM::PowerTransition::getSign()
847 {
848 return _sign;
849 }
850
851
852
853
854
855