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