1 #ifndef _FSM_H_INCLUDED_ 2 #define _FSM_H_INCLUDED_ 3 /////////////////////////////////////////////////////////////////////////////// 4 // 5 // FSM.h 6 // ----- 7 // Dragon final state machine interface definition 8 // 9 // Design and Implementation by Bjoern Lemke 10 // 11 // (C)opyright 2007 by Bjoern Lemke 12 // 13 // This program is free software; you can redistribute it and/or modify 14 // it under the terms of the GNU General Public License as published by 15 // the Free Software Foundation; either version 2, or (at your option) 16 // any later version. 17 // 18 // This program is distributed in the hope that it will be useful, 19 // but WITHOUT ANY WARRANTY; without even the implied warranty of 20 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 // GNU General Public License for more details. 22 // 23 // You should have received a copy of the GNU General Public License 24 // along with this program; see the file COPYING. If not, write to 25 // the Free Software Foundation, 59 Temple Place - Suite 330, 26 // Boston, MA 02111-1307, USA. 27 // 28 // INTERFACE MODULE 29 // 30 // Class: FSM 31 // 32 // Description: implementation of a final state machine for lexical analysis 33 // 34 ////////////////////////////////////////////////////////////////////////////// 35 36 // BASE INCLUDES 37 #include <lfcbase/Chain.h> 38 #include <lfcbase/TreeT.h> 39 #include <lfcbase/SetT.h> 40 41 // DRAGON INCLUDES 42 #include "FSMState.h" 43 #include "FSMTransition.h" 44 45 class FSM { 46 47 public: 48 49 FSM(TreeT<FSMState>* pStateTable, TreeT<FSMTransition>* pTransitionTable); 50 ~FSM(); 51 52 void epsilonFree(); 53 void determinate(); 54 void invert(); 55 56 unsigned long States(); 57 unsigned long Transitions(); 58 void printFsm(); 59 60 private: 61 62 63 class PowerState; 64 class PowerTransition; 65 66 TreeT<FSMState> *_pStateTable; 67 TreeT<FSMTransition> *_pTransitionTable; 68 69 void buildEpsilonClosure(unsigned long state, SetT<unsigned long>& closureSet); 70 71 class EpsilonClosureMap { 72 73 public: 74 75 EpsilonClosureMap(); 76 EpsilonClosureMap(unsigned long state); 77 EpsilonClosureMap(unsigned long state, SetT<unsigned long>& closure); 78 79 EpsilonClosureMap operator = (const EpsilonClosureMap& m); 80 81 bool operator == (EpsilonClosureMap m); 82 83 bool operator < (EpsilonClosureMap m); 84 bool operator > (EpsilonClosureMap m); 85 86 87 long getState(); 88 SetT<unsigned long>& getClosure(); 89 90 private: 91 92 unsigned long _state; 93 SetT<unsigned long> _closure; 94 95 }; 96 97 class PowerState { 98 99 public: 100 101 PowerState(); 102 PowerState(const TreeT<FSMState>& stateSet); 103 PowerState(const TreeT<FSMState>& stateSet, unsigned long id, StateType type); 104 ~PowerState(); 105 106 PowerState(const PowerState& p); 107 PowerState& operator = (const PowerState& p); 108 bool operator == (PowerState p); 109 110 bool operator < (PowerState p); 111 bool operator > (PowerState p); 112 113 114 void setType(StateType type); 115 void setToken(const Chain& token); 116 117 TreeT<FSMState>& getStateSet(); 118 unsigned long getId(); 119 StateType getType(); 120 const Chain& getToken(); 121 122 private: 123 124 TreeT<FSMState> _stateSet; 125 unsigned long _id; 126 StateType _type; 127 Chain _token; 128 }; 129 130 131 132 class PowerTransition { 133 134 public: 135 136 PowerTransition(); 137 PowerTransition(const TreeT<FSMState>& source, const TreeT<FSMState>& target, char sign); 138 ~PowerTransition(); 139 140 PowerTransition(const PowerTransition& x); 141 PowerTransition& operator = (const PowerTransition& x); 142 bool operator == (PowerTransition x); 143 144 bool operator > (PowerTransition x); 145 bool operator < (PowerTransition x); 146 147 TreeT<FSMState>& getSource(); 148 TreeT<FSMState>& getTarget(); 149 char getSign(); 150 151 private: 152 153 TreeT<FSMState> _source; 154 TreeT<FSMState> _target; 155 char _sign; 156 157 }; 158 159 160 161 }; 162 163 164 #endif 165 166