00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef FSM_HPP
00034 #define FSM_HPP
00035
00036 #include "Types.hpp"
00037 #include "MemStreamer.hpp"
00038
00039
00040
00041
00042
00043
00044
00045 #define EDGETYPE_LABEL 0 // A normal label edge
00046
00047
00048 #define EDGETYPE_NEGLABELLIST 1 // An edge that captures everything minus certain labels
00049 #define EDGETYPE_EMPTY 2 // An empty edge. This is only used for
00050
00051
00052 class MemStreamer;
00053 class Input;
00054
00055
00056 extern MemStreamer *fsmtmpmem;
00057
00058 extern MemStreamer *fsmmem;
00059
00060
00061 struct FSMLabel
00062
00063
00064 {
00065 TLabelID labelid;
00066 FSMLabel *next;
00067
00068 FSMLabel(TLabelID mylabelid,FSMLabel *mynext=NULL)
00069 {
00070 labelid=mylabelid;
00071 next=mynext;
00072 }
00073
00074 void *operator new(size_t size, MemStreamer *mem);
00075 #ifdef SPECIAL_DELETE
00076 void operator delete(void *ptr,MemStreamer *mem) {}
00077 #endif
00078 void operator delete(void *ptr) {}
00079 };
00080
00081
00082
00083
00084 struct FSMStateSetItem;
00085 class FSMEdge;
00086 class FSM;
00087
00088 class FSMState
00089
00090 {
00091 friend FSM;
00092 friend FSMEdge;
00093 unsigned isfinal:1;
00094 unsigned isaccepting:1;
00095
00096
00097
00098 unsigned isoutcomplete:1;
00099
00100 unsigned haspoundsahead:1;
00101
00102 unsigned stateid:10;
00103 FSMEdge *outedges;
00104 FSMState *next;
00105
00106
00107 union
00108 {
00109 FSMStateSetItem *origstateset;
00110
00111
00112 void *data;
00113 long tmpval;
00114 };
00115
00116 char PruneRedundantStatesRecurs();
00117
00118
00119 char FindAcceptingStatesRecurs();
00120 char HasPoundsAheadRecurs();
00121
00122
00123 void EliminateRedundantPoundEdges();
00124
00125
00126
00127 void ComputeOutCompleteness();
00128
00129
00130 public:
00131
00132 FSMState() {}
00133 FSMState(unsigned mystateid,char myisfinal=0);
00134 FSMState(unsigned mystateid,FSMStateSetItem *myorigdataset);
00135
00136 void *operator new(size_t size, MemStreamer *mem) { return mem->GetByteBlock(size);}
00137 void operator delete(void *ptr) {}
00138 void *operator new[](size_t size, MemStreamer *mem) { return mem->GetByteBlock(size);}
00139 void operator delete[](void *ptr) {}
00140 #ifdef SPECIAL_DELETE
00141 void operator delete(void *ptr,MemStreamer *mem) {}
00142 void operator delete[](void *ptr,MemStreamer *mem) {}
00143 #endif
00144
00145 FSMEdge *GetOutEdges() { return outedges; }
00146 FSMStateSetItem *GetOrigStateSet() { return origstateset; }
00147
00148 void SetFinal(char myisfinal=1) { isfinal=myisfinal; }
00149 char IsFinal() { return isfinal; }
00150 char IsOutComplete() { return isoutcomplete; }
00151 char IsAccepting() { return isaccepting; }
00152 char HasPoundsAhead() { return haspoundsahead; }
00153 int GetStateID() { return stateid; }
00154 FSMState *GetNextStateInList() { return next; }
00155
00156 FSMEdge *FindNegEdge();
00157
00158
00159 FSMState *GetNextState(TLabelID labelid,char *overpoundedge=NULL);
00160
00161
00162
00163 #ifdef FSM_PRINT
00164 void Print();
00165 #endif
00166 #ifdef FSM_STORE
00167 void Store(MemStreamer *mem);
00168
00169
00170 void Load(unsigned char * &ptr,FSMState *statearray,MemStreamer *fsmmem);
00171
00172 #endif
00173 };
00174
00175
00176
00177 class FSMEdge
00178
00179 {
00180 friend FSMState;
00181 friend FSM;
00182
00183 unsigned type;
00184 FSMState *nextstate;
00185
00186
00187 union{
00188 FSMLabel *labellist;
00189 TLabelID labelid;
00190 };
00191
00192 public:
00193 FSMEdge *next;
00194
00195 void *operator new(size_t size, MemStreamer *mem);
00196 void operator delete(void *ptr) {}
00197 #ifdef SPECIAL_DELETE
00198 void operator delete(void *ptr,MemStreamer *mem) {}
00199 #endif
00200
00201 FSMEdge() {}
00202
00203 FSMEdge(FSMState *tostate,TLabelID mylabel);
00204 FSMEdge(FSMState *tostate);
00205 FSMEdge(FSMState *tostate,FSMLabel *mylabels);
00206
00207 unsigned GetType() { return type; }
00208 FSMState *GetNextState() { return nextstate; }
00209 FSMLabel *GetLabelList() { return labellist; }
00210 FSMLabel **GetLabelListRef() { return &labellist; }
00211 TLabelID GetLabelID() { return labelid; }
00212
00213 char DoesMatchLabel(TLabelID labelid);
00214
00215
00216 #ifdef FSM_PRINT
00217 void PrintLabelList();
00218 void Print();
00219 #endif
00220 #ifdef FSM_STORE
00221 void Store(MemStreamer *mem);
00222 void Load(unsigned char * &ptr,FSMState *statearray,MemStreamer *fsmmem);
00223
00224 #endif
00225 };
00226
00227
00228
00229
00230 struct StateEqualPair;
00231 struct StateEqualPairListItem;
00232
00233 class FSM
00234
00235 {
00236 FSMState *statelist,
00237 **laststatelistref;
00238 FSMState *startstate;
00239 unsigned long isdeterministic:1;
00240 unsigned curidx:30;
00241
00242
00243 void PruneRedundantStates();
00244
00245
00246
00247 #ifdef FSM_NEGATE
00248
00249 void CompleteDetState(FSMState *state,FSMState *deadstate);
00250
00251
00252
00253 void CompleteDetFSM();
00254
00255 #endif
00256
00257 public:
00258
00259 inline void *operator new(size_t size, MemStreamer *mem)
00260 {
00261 return mem->GetByteBlock(size);
00262 }
00263
00264 inline void operator delete(void *ptr) {}
00265 #ifdef SPECIAL_DELETE
00266 inline void operator delete(void *ptr,MemStreamer *mem) {}
00267 #endif
00268
00269 FSM()
00270 {
00271 isdeterministic=0;
00272 curidx=0;
00273 statelist=NULL;
00274 laststatelistref=&statelist;
00275 }
00276
00277 unsigned GetStateCount() { return curidx; }
00278
00279 FSMState *CreateState(char isfinal=0);
00280 FSMState *CreateState(FSMStateSetItem *list);
00281
00282
00283 FSMEdge *CreateLabelEdge(FSMState *fromstate,FSMState *tostate,TLabelID labelid);
00284
00285 FSMEdge *CreateNegEdge(FSMState *fromstate,FSMState *tostate,FSMLabel *labellist=NULL);
00286
00287 FSMEdge *CreateEmptyEdge(FSMState *fromstate,FSMState *tostate);
00288
00289
00290 void SetStartState(FSMState *mystartstate) { startstate=mystartstate; }
00291 FSMState *GetStartState() { return startstate; }
00292 FSMState *GetStateList() { return statelist; }
00293
00294 FSM *MakeDeterministic();
00295 FSM *Minimize();
00296
00297 void AddFSM(FSMState *fromstate,FSMState *tostate,FSM *fsm);
00298
00299
00300 void EliminateRedundantPoundEdges();
00301
00302
00303
00304 void ComputeOutCompleteness();
00305
00306
00307
00308 void FindAcceptingStates();
00309
00310
00311
00312
00313 void ComputeStatesHasPoundsAhead();
00314
00315
00316 #ifdef FSM_NEGATE
00317 FSM *CreateNegateFSM();
00318 #endif
00319
00320 FSM *CreateReverseFSM();
00321
00322 #ifdef FSM_PRINT
00323 void Print();
00324 #endif
00325 #ifdef FSM_STORE
00326 void Store(MemStreamer *mem);
00327 void Load(unsigned char * &ptr,MemStreamer *fsmmem);
00328 #endif
00329
00330
00331
00332
00333
00334 };
00335
00336 extern TLabelID elementpoundlabelid;
00337 extern TLabelID attribpoundlabelid;
00338
00339 #endif