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 #include <stdio.h>
00034
00035 #include "LabelDict.hpp"
00036 #include "FSM.hpp"
00037 #include "Load.hpp"
00038
00039
00040
00041
00042 TLabelID elementpoundlabelid=LABEL_UNDEFINED;
00043 TLabelID attribpoundlabelid=LABEL_UNDEFINED;
00044
00045 void FSMInit()
00046
00047 {
00048 elementpoundlabelid=globallabeldict.CreateLabelOrAttrib("#",1,0);
00049 attribpoundlabelid=globallabeldict.CreateLabelOrAttrib("#",1,1);
00050 }
00051
00052 MemStreamer *fsmtmpmem,*fsmmem;
00053
00054 inline void *FSMLabel::operator new(size_t size, MemStreamer *mem)
00055 {
00056 return mem->GetByteBlock(size);
00057 }
00058
00059 inline void *FSMEdge::operator new(size_t size, MemStreamer *mem)
00060 {
00061 return mem->GetByteBlock(size);
00062 }
00063
00064
00065
00066 inline char IsInLabelList(FSMLabel *labellist,TLabelID labelid)
00067
00068 {
00069 FSMLabel *curitem=labellist;
00070 while(curitem!=NULL)
00071 {
00072 if(curitem->labelid==labelid)
00073 return 1;
00074 curitem=curitem->next;
00075 }
00076 return 0;
00077 }
00078
00079 inline void RemoveFromLabelList(FSMLabel **listref,int labelid)
00080
00081 {
00082 while(*listref!=NULL)
00083 {
00084 if((*listref)->labelid==labelid)
00085 {
00086 *listref=(*listref)->next;
00087 return;
00088 }
00089 listref=&((*listref)->next);
00090 }
00091 }
00092
00093 inline void DupLabelList(FSMLabel *labellist,FSMLabel **newlabellist)
00094
00095 {
00096 while(labellist!=NULL)
00097 {
00098 *newlabellist=new(fsmmem) FSMLabel(labellist->labelid);
00099 newlabellist=&((*newlabellist)->next);
00100 labellist=labellist->next;
00101 }
00102 }
00103
00104
00105
00106 inline FSMEdge::FSMEdge(FSMState *tostate)
00107 {
00108 type=EDGETYPE_EMPTY;
00109 nextstate=tostate;
00110 }
00111
00112 inline FSMEdge::FSMEdge(FSMState *tostate,TLabelID mylabelid)
00113 {
00114 type=EDGETYPE_LABEL;
00115 nextstate=tostate;
00116 labelid=mylabelid;
00117 }
00118
00119 inline FSMEdge::FSMEdge(FSMState *tostate,FSMLabel *mylabels)
00120 {
00121 type=EDGETYPE_NEGLABELLIST;
00122 nextstate=tostate;
00123 labellist=mylabels;
00124 }
00125
00126 inline char FSMEdge::DoesMatchLabel(TLabelID mylabelid)
00127
00128 {
00129 if(labelid==LABEL_UNDEFINED)
00130 return type==EDGETYPE_NEGLABELLIST;
00131
00132 switch(type)
00133 {
00134 case EDGETYPE_LABEL: return labelid==mylabelid;
00135 case EDGETYPE_NEGLABELLIST:return !IsInLabelList(labellist,mylabelid);
00136 case EDGETYPE_EMPTY: return 0;
00137 }
00138 return 0;
00139 }
00140
00141
00142
00143 inline FSMState::FSMState(unsigned mystateid,char myisfinal)
00144 {
00145 stateid=mystateid;
00146 isfinal=myisfinal;
00147 outedges=NULL;
00148 next=NULL;
00149 origstateset=NULL;
00150 }
00151
00152 inline FSMEdge *FSMState::FindNegEdge()
00153
00154
00155 {
00156 FSMEdge *edge=outedges;
00157
00158 while(edge!=NULL)
00159 {
00160 if(edge->GetType()==EDGETYPE_NEGLABELLIST)
00161 return edge;
00162 edge=edge->next;
00163 }
00164 return NULL;
00165 }
00166
00167 FSMState *FSMState::GetNextState(TLabelID labelid,char *overpoundedge)
00168
00169
00170
00171
00172 {
00173 FSMEdge *edge=outedges;
00174 FSMEdge *defaultedge=NULL;
00175 char isattrib=ISATTRIB(labelid);
00176
00177 if(overpoundedge!=NULL)
00178 *overpoundedge=0;
00179
00180 while(edge!=NULL)
00181 {
00182 switch(edge->GetType())
00183 {
00184 case EDGETYPE_LABEL:
00185
00186 if(edge->labelid==labelid)
00187 return edge->GetNextState();
00188
00189
00190
00191 if((((edge->labelid==elementpoundlabelid)&&(isattrib==0))||
00192 ((edge->labelid==attribpoundlabelid)&&(isattrib==1)))&&
00193 (defaultedge==NULL))
00194 {
00195 defaultedge=edge;
00196 if(overpoundedge!=NULL)
00197 *overpoundedge=1;
00198 }
00199 break;
00200
00201 case EDGETYPE_NEGLABELLIST:
00202 {
00203
00204
00205
00206
00207 if(!IsInLabelList(edge->labellist,labelid))
00208
00209 {
00210 defaultedge=edge;
00211 if(overpoundedge!=NULL)
00212 *overpoundedge=0;
00213 }
00214 break;
00215 }
00216
00217
00218 }
00219 edge=edge->next;
00220 }
00221
00222
00223 if(defaultedge!=NULL)
00224 return defaultedge->GetNextState();
00225 else
00226 return NULL;
00227 }
00228
00229
00230
00231
00232 FSMEdge *FSM::CreateLabelEdge(FSMState *fromstate,FSMState *tostate,TLabelID labelid)
00233
00234 {
00235 FSMEdge *edge=new(fsmmem) FSMEdge(tostate,labelid);
00236
00237 edge->next=fromstate->outedges;
00238 fromstate->outedges=edge;
00239 return edge;
00240 }
00241
00242 FSMEdge *FSM::CreateNegEdge(FSMState *fromstate,FSMState *tostate,FSMLabel *labellist)
00243
00244 {
00245 FSMEdge *edge=new(fsmmem) FSMEdge(tostate,labellist);
00246
00247 edge->next=fromstate->outedges;
00248 fromstate->outedges=edge;
00249 return edge;
00250 }
00251
00252 FSMEdge *FSM::CreateEmptyEdge(FSMState *fromstate,FSMState *tostate)
00253
00254 {
00255 FSMEdge *edge=new(fsmmem) FSMEdge(tostate);
00256
00257 edge->next=fromstate->outedges;
00258 fromstate->outedges=edge;
00259 return edge;
00260 }
00261
00262 FSMState *FSM::CreateState(char isfinal)
00263 {
00264 FSMState *newstate=new(fsmmem) FSMState(curidx,isfinal);
00265
00266 curidx++;
00267
00268 *laststatelistref=newstate;
00269 laststatelistref=&((*laststatelistref)->next);
00270 return newstate;
00271 }
00272
00273
00274
00275
00276
00277
00278
00279
00280 struct FSMStateSetItem
00281
00282 {
00283 FSMStateSetItem *next;
00284 FSMState *state;
00285
00286 FSMStateSetItem(FSMState *mystate,FSMStateSetItem *mynext)
00287 {
00288 state=mystate;
00289 next=mynext;
00290 }
00291
00292 void *operator new(size_t size) { return fsmtmpmem->GetByteBlock(size); }
00293 void operator delete(void *ptr) {}
00294 void *operator new[] (size_t size) { return fsmtmpmem->GetByteBlock(size); }
00295 void operator delete[] (void *ptr) {}
00296 };
00297
00298 inline FSMState::FSMState(unsigned mystateid,FSMStateSetItem *origset)
00299
00300
00301 {
00302 outedges =NULL;
00303 origstateset=origset;
00304 stateid =mystateid;
00305 next =NULL;
00306 isfinal =0;
00307
00308 while(origset!=NULL)
00309 {
00310 if(origset->state->IsFinal())
00311 {
00312 isfinal=1;
00313 break;
00314 }
00315 origset=origset->next;
00316 }
00317 }
00318
00319 inline FSMState *FSM::CreateState(FSMStateSetItem *list)
00320
00321 {
00322 FSMState *newstate=new(fsmmem) FSMState(curidx,list);
00323
00324 curidx++;
00325 *laststatelistref=newstate;
00326 laststatelistref=&((*laststatelistref)->next);
00327
00328 return newstate;
00329 }
00330
00331 inline char IsInStateSet(FSMStateSetItem *set,FSMState *state)
00332
00333 {
00334 FSMStateSetItem *curitem=set;
00335
00336
00337 while(curitem!=NULL)
00338 {
00339 if(curitem->state==state)
00340 return 1;
00341 curitem=curitem->next;
00342 }
00343 return 0;
00344 }
00345
00346 inline FSMStateSetItem *AddToStateSet(FSMStateSetItem *set,FSMState *state)
00347
00348
00349
00350
00351
00352
00353 {
00354
00355
00356 if(IsInStateSet(set,state))
00357 return set;
00358
00359 set=new FSMStateSetItem(state,set);
00360
00361
00362
00363 FSMEdge *outedges=state->GetOutEdges();
00364 while(outedges!=NULL)
00365 {
00366 if(outedges->GetType()==EDGETYPE_EMPTY)
00367 set=AddToStateSet(set,outedges->GetNextState());
00368 outedges=outedges->next;
00369 }
00370 return set;
00371 }
00372
00373 inline void CreateStateSet(FSMStateSetItem *fromstateset,int labelid,FSMStateSetItem **newset)
00374
00375
00376
00377
00378 {
00379 FSMEdge *curedge;
00380
00381 *newset=NULL;
00382
00383 while(fromstateset!=NULL)
00384 {
00385 curedge=fromstateset->state->GetOutEdges();
00386
00387 while(curedge!=NULL)
00388 {
00389 if(curedge->DoesMatchLabel(labelid))
00390 *newset=AddToStateSet(*newset,curedge->GetNextState());
00391
00392 curedge=curedge->next;
00393 }
00394 fromstateset=fromstateset->next;
00395 }
00396 }
00397
00398 inline char CompareStateSets(FSMStateSetItem *set1,FSMStateSetItem *set2)
00399
00400
00401 {
00402 int count1=0;
00403 FSMStateSetItem *curitem=set2;
00404
00405
00406
00407
00408
00409 while(set1!=NULL)
00410 {
00411 if(!IsInStateSet(set2,set1->state))
00412 return 0;
00413
00414 count1++;
00415 set1=set1->next;
00416 }
00417
00418
00419 curitem=set2;
00420 while(curitem!=NULL)
00421 {
00422 count1--;
00423 if(count1<0)
00424 return 0;
00425 curitem=curitem->next;
00426 }
00427 return 1;
00428 }
00429
00430 inline void FindAllOutgoingLabels(FSMState *state,FSMLabel **dest)
00431
00432
00433
00434
00435 {
00436 FSMLabel *curlabel;
00437 FSMEdge *outedge;
00438
00439 outedge=state->GetOutEdges();
00440 while(outedge!=NULL)
00441 {
00442 switch(outedge->GetType())
00443 {
00444 case EDGETYPE_LABEL:
00445 if(!IsInLabelList(*dest,outedge->GetLabelID()))
00446
00447 *dest=new(fsmtmpmem) FSMLabel(outedge->GetLabelID(),*dest);
00448
00449 break;
00450
00451 case EDGETYPE_NEGLABELLIST:
00452 curlabel=outedge->GetLabelList();
00453 while(curlabel!=NULL)
00454 {
00455 if(!IsInLabelList(*dest,curlabel->labelid))
00456
00457 *dest=new(fsmtmpmem) FSMLabel(curlabel->labelid,*dest);
00458
00459 curlabel=curlabel->next;
00460 }
00461 }
00462 outedge=outedge->next;
00463 }
00464 }
00465
00466 inline void FindAllOutgoingLabels(FSMStateSetItem *set,FSMLabel **dest)
00467
00468
00469 {
00470
00471 while(set!=NULL)
00472 {
00473
00474 FindAllOutgoingLabels(set->state,dest);
00475
00476 set=set->next;
00477 }
00478 }
00479
00480 inline char ConsiderNegEdgeAtState(FSM *newfsm,FSMState *curstate,FSMLabel *mylabellist,FSMState *curstatelist,FSMState **newstate)
00481
00482
00483
00484
00485 {
00486 FSMStateSetItem *nextstateset;
00487
00488
00489 CreateStateSet(curstate->GetOrigStateSet(),LABEL_UNDEFINED,&nextstateset);
00490
00491
00492 if(nextstateset==NULL)
00493 return 0;
00494
00495
00496 while(curstatelist!=NULL)
00497 {
00498 if(CompareStateSets(nextstateset,curstatelist->GetOrigStateSet()))
00499
00500 {
00501 newfsm->CreateNegEdge(curstate,curstatelist,mylabellist);
00502
00503 *newstate=curstatelist;
00504 return 0;
00505 }
00506 curstatelist=curstatelist->GetNextStateInList();
00507 }
00508
00509
00510
00511
00512 *newstate=newfsm->CreateState(nextstateset);
00513 newfsm->CreateNegEdge(curstate,*newstate,mylabellist);
00514
00515 return 1;
00516 }
00517
00518 inline char ConsiderLabelIDAtState(FSM *newfsm,FSMState *curstate,int labelid,FSMState *curstatelist,FSMState **newstate)
00519
00520
00521
00522
00523 {
00524 FSMStateSetItem *nextstateset;
00525 FSMEdge *edge;
00526
00527
00528 CreateStateSet(curstate->GetOrigStateSet(),labelid,&nextstateset);
00529
00530
00531 if(nextstateset==NULL)
00532 return 0;
00533
00534
00535 while(curstatelist!=NULL)
00536 {
00537 if(CompareStateSets(nextstateset,curstatelist->GetOrigStateSet()))
00538
00539 {
00540 *newstate=curstatelist;
00541
00542
00543
00544 edge=curstate->FindNegEdge();
00545 if((edge!=NULL)&&(edge->GetNextState()==curstatelist))
00546
00547 RemoveFromLabelList(edge->GetLabelListRef(),labelid);
00548 else
00549 newfsm->CreateLabelEdge(curstate,curstatelist,labelid);
00550
00551 return 0;
00552 }
00553 curstatelist=curstatelist->GetNextStateInList();
00554 }
00555
00556
00557
00558
00559 *newstate=newfsm->CreateState(nextstateset);
00560
00561 newfsm->CreateLabelEdge(curstate,*newstate,labelid);
00562 return 1;
00563 }
00564
00565 FSM *FSM::MakeDeterministic()
00566
00567 {
00568 FSMStateSetItem *todolist=NULL,**todoref=&todolist;
00569
00570
00571 FSMLabel *tmplabellist,*curlabel;
00572 FSMState *curstate,*newnextstate;
00573 FSM *newfsm=new(fsmmem) FSM();
00574
00575 FSMStateSetItem *startstateset=NULL;
00576
00577
00578 startstateset=AddToStateSet(startstateset,startstate);
00579
00580
00581 curstate=newfsm->CreateState(startstateset);
00582
00583 newfsm->SetStartState(curstate);
00584
00585
00586 do
00587 {
00588
00589 tmplabellist=NULL;
00590 FindAllOutgoingLabels(curstate->GetOrigStateSet(),&tmplabellist);
00591
00592
00593
00594 if(ConsiderNegEdgeAtState(newfsm,curstate,tmplabellist,newfsm->GetStateList(),&newnextstate)==1)
00595
00596
00597 todolist=new FSMStateSetItem(newnextstate,todolist);
00598
00599
00600
00601 curlabel=tmplabellist;
00602 while(curlabel!=NULL)
00603 {
00604 if(ConsiderLabelIDAtState(newfsm,curstate,curlabel->labelid,newfsm->GetStateList(),&newnextstate)==1)
00605
00606
00607 todolist=new FSMStateSetItem(newnextstate,todolist);
00608
00609 curlabel=curlabel->next;
00610 }
00611
00612 if(todolist==NULL)
00613 break;
00614
00615
00616 curstate=todolist->state;
00617 todolist=todolist->next;
00618 }
00619 while(1);
00620
00621 return newfsm;
00622 }
00623
00624
00625
00626
00627
00628
00629 struct StateEqualPairListItem
00630
00631 {
00632 StateEqualPair *statepair;
00633 StateEqualPairListItem *next;
00634
00635 StateEqualPairListItem(StateEqualPair *mystatepair,StateEqualPairListItem *mynext)
00636 {
00637 statepair=mystatepair;
00638 next=mynext;
00639 }
00640
00641 void *operator new(size_t size) { return fsmtmpmem->GetByteBlock(size); }
00642 void operator delete(void *ptr) {}
00643 };
00644
00645 struct StateEqualPair
00646
00647
00648
00649 {
00650 unsigned long isnotequal:1;
00651 FSMState *state1,*state2;
00652 StateEqualPairListItem *dependlist;
00653
00654
00655 void *operator new[] (size_t size) { return fsmtmpmem->GetByteBlock(size); }
00656 void operator delete[] (void *ptr) {}
00657 };
00658
00659 inline char CheckEqual(FSMState *nextstate1,FSMState *nextstate2,StateEqualPair **array)
00660
00661
00662
00663 {
00664 if(nextstate1!=NULL)
00665 {
00666 if(nextstate2==NULL)
00667
00668 return 0;
00669
00670 unsigned sid1=nextstate1->GetStateID();
00671 unsigned sid2=nextstate2->GetStateID();
00672 if(sid1==sid2)
00673 return 1;
00674
00675 if(sid2<sid1)
00676 return !(array[sid1][sid2].isnotequal);
00677 else
00678 return !(array[sid2][sid1].isnotequal);
00679 }
00680 else
00681 return nextstate2==NULL;
00682 }
00683
00684 inline void AddDependency(FSMState *nextstate1,FSMState *nextstate2,StateEqualPair *curpair,StateEqualPair **array)
00685
00686 {
00687 StateEqualPair *nextpair;
00688
00689 if((nextstate1==NULL)||(nextstate2==NULL))
00690 return;
00691
00692 unsigned sid1=nextstate1->GetStateID();
00693 unsigned sid2=nextstate2->GetStateID();
00694 if(sid1==sid2)
00695 return;
00696
00697 nextpair= (sid2<sid1) ? (array[sid1]+sid2) : (array[sid2]+sid1);
00698
00699 if((nextpair->dependlist==NULL)||
00700 (nextpair->dependlist->statepair!=curpair))
00701
00702 nextpair->dependlist=new StateEqualPairListItem(curpair,nextpair->dependlist);
00703 }
00704
00705 void MarkDependentNotEqual(StateEqualPairListItem *dependlist)
00706
00707
00708 {
00709 while(dependlist!=NULL)
00710 {
00711 if(dependlist->statepair->isnotequal==0)
00712 {
00713 dependlist->statepair->isnotequal=1;
00714 if(dependlist->statepair->dependlist!=NULL)
00715 MarkDependentNotEqual(dependlist->statepair->dependlist);
00716 }
00717 dependlist=dependlist->next;
00718 }
00719 }
00720
00721
00722
00723 FSM *FSM::Minimize()
00724 {
00725 int statenum,i,j;
00726 FSMState *curstate1,*curstate2;
00727 StateEqualPair *pairptr;
00728 FSMLabel *tmplabellist,*curlabel;
00729
00730
00731 PruneRedundantStates();
00732
00733
00734
00735
00736
00737 statenum=GetStateCount();
00738
00739 StateEqualPair **array=(StateEqualPair **)fsmtmpmem->GetByteBlock(statenum*sizeof(StateEqualPair *));
00740
00741 curstate1=statelist;
00742
00743
00744
00745
00746 for(i=0;i<statenum;i++)
00747 {
00748 array[i]=new StateEqualPair[i];
00749
00750 pairptr=array[i];
00751
00752 curstate2=statelist;
00753
00754 for(j=0;j<i;j++)
00755 {
00756 pairptr->state1 =curstate1;
00757 pairptr->state2 =curstate2;
00758 pairptr->dependlist =NULL;
00759 pairptr->isnotequal =(curstate1->IsFinal() != curstate2->IsFinal());
00760
00761 pairptr++;
00762 curstate2=curstate2->next;
00763 }
00764 curstate1=curstate1->next;
00765 }
00766
00767 curstate1=statelist;
00768
00769
00770
00771 for(i=0;i<statenum;i++)
00772 {
00773 pairptr=array[i];
00774
00775 curstate2=statelist;
00776
00777 for(j=0;j<i;j++)
00778 {
00779
00780
00781 tmplabellist=NULL;
00782 FindAllOutgoingLabels(curstate1,&tmplabellist);
00783 FindAllOutgoingLabels(curstate2,&tmplabellist);
00784
00785
00786
00787
00788 curlabel=tmplabellist;
00789 while(curlabel!=NULL)
00790 {
00791 if(CheckEqual( curstate1->GetNextState(curlabel->labelid),
00792 curstate2->GetNextState(curlabel->labelid),array)==0)
00793 break;
00794 curlabel=curlabel->next;
00795 }
00796
00797
00798 if(curlabel==NULL)
00799
00800 {
00801 if(CheckEqual( curstate1->GetNextState(LABEL_UNDEFINED),
00802 curstate2->GetNextState(LABEL_UNDEFINED),array)==0)
00803 curlabel=(FSMLabel *)1;
00804 }
00805
00806 if(curlabel!=NULL)
00807
00808 {
00809
00810 pairptr->isnotequal=1;
00811
00812 if(pairptr->dependlist!=NULL)
00813 MarkDependentNotEqual(pairptr->dependlist);
00814 }
00815 else
00816
00817
00818 {
00819 curlabel=tmplabellist;
00820 while(curlabel!=NULL)
00821 {
00822 AddDependency( curstate1->GetNextState(curlabel->labelid),
00823 curstate2->GetNextState(curlabel->labelid),
00824 pairptr,
00825 array);
00826
00827 curlabel=curlabel->next;
00828 }
00829 AddDependency( curstate1->GetNextState(LABEL_UNDEFINED),
00830 curstate2->GetNextState(LABEL_UNDEFINED),
00831 pairptr,
00832 array);
00833 }
00834 pairptr++;
00835 curstate2=curstate2->next;
00836 }
00837 curstate1=curstate1->next;
00838 }
00839
00840
00841
00842 FSM *newfsm=new(fsmmem) FSM();
00843 FSMEdge *edge,*negedge;
00844
00845
00846
00847 curstate1=statelist;
00848
00849 for(i=0;i<statenum;i++)
00850 {
00851 pairptr=array[i];
00852 curstate2=statelist;
00853
00854 for(j=0;j<i;j++)
00855 {
00856 if(pairptr->isnotequal==0)
00857
00858
00859 {
00860 curstate1->data=curstate2->data;
00861 array[i]=NULL;
00862 break;
00863 }
00864 curstate2=curstate2->next;
00865 pairptr++;
00866 }
00867
00868 if(i==j)
00869
00870 curstate1->data=newfsm->CreateState(curstate1->IsFinal());
00871
00872 curstate1=curstate1->next;
00873 }
00874
00875
00876 newfsm->SetStartState((FSMState *)startstate->data);
00877
00878
00879 curstate1=statelist;
00880 for(i=0;i<statenum;i++)
00881 {
00882 if(array[i]!=NULL)
00883 {
00884
00885
00886 edge=curstate1->FindNegEdge();
00887 if(edge!=NULL)
00888 {
00889 tmplabellist=NULL;
00890 DupLabelList(edge->GetLabelList(),&tmplabellist);
00891
00892 negedge=newfsm->CreateNegEdge((FSMState *)curstate1->data,
00893 (FSMState *)edge->GetNextState()->data,
00894 tmplabellist);
00895 }
00896 else
00897 negedge=NULL;
00898
00899
00900 edge=curstate1->GetOutEdges();
00901 while(edge!=NULL)
00902 {
00903 if(edge->GetType()==EDGETYPE_LABEL)
00904 {
00905 if((negedge!=NULL)&&
00906 (negedge->GetNextState()==(FSMState *)edge->nextstate->data))
00907
00908
00909 RemoveFromLabelList(&(negedge->labellist),edge->labelid);
00910 else
00911 newfsm->CreateLabelEdge((FSMState *)curstate1->data,
00912 (FSMState *)edge->GetNextState()->data,
00913 edge->labelid);
00914 }
00915 edge=edge->next;
00916 }
00917 }
00918 curstate1=curstate1->next;
00919 }
00920 return newfsm;
00921 }
00922
00923
00924
00925
00926 char FSMState::PruneRedundantStatesRecurs()
00927
00928
00929
00930
00931
00932 {
00933 char reachesfinalstate=0;
00934
00935
00936
00937
00938
00939
00940
00941 if(isfinal)
00942 tmpval=3;
00943 else
00944 tmpval=1;
00945
00946 FSMEdge *outedge=outedges;
00947
00948 while(outedge!=NULL)
00949 {
00950 if((outedge->GetNextState()->tmpval&1)==0)
00951
00952 {
00953 if(outedge->GetNextState()->PruneRedundantStatesRecurs())
00954 tmpval=3;
00955 }
00956 else
00957 {
00958 if(outedge->GetNextState()->tmpval==3)
00959 tmpval=3;
00960 }
00961 outedge=outedge->next;
00962 }
00963 return (tmpval==3);
00964 }
00965
00966 void FSM::PruneRedundantStates()
00967
00968
00969 {
00970 FSMState *curstate=statelist;
00971 FSMEdge **outedgeref;
00972
00973
00974 while(curstate!=NULL)
00975 {
00976 curstate->tmpval=0;
00977 curstate=curstate->next;
00978 }
00979 startstate->PruneRedundantStatesRecurs();
00980
00981 FSMState **curstateref=&statelist;
00982
00983 curidx=0;
00984
00985 while(*curstateref!=NULL)
00986 {
00987 if((*curstateref)->tmpval!=3)
00988
00989
00990 {
00991 *curstateref=(*curstateref)->next;
00992 }
00993 else
00994 {
00995 (*curstateref)->stateid=curidx;
00996
00997 outedgeref=&((*curstateref)->outedges);
00998 while(*outedgeref!=NULL)
00999 {
01000 if((*outedgeref)->GetNextState()->tmpval!=3)
01001
01002 *outedgeref=(*outedgeref)->next;
01003 else
01004 outedgeref=&((*outedgeref)->next);
01005 }
01006 curidx++;
01007 curstateref=&((*curstateref)->next);
01008 }
01009 }
01010 *curstateref=NULL;
01011 }
01012
01013
01014
01015
01016 void FSMState::EliminateRedundantPoundEdges()
01017
01018
01019
01020 {
01021 FSMEdge *outedge=GetOutEdges();
01022 FSMLabel *curlabel;
01023
01024 FSMEdge *elementpoundedge=NULL;
01025 FSMEdge *attribpoundedge=NULL;
01026 FSMEdge *negedge=NULL;
01027
01028
01029
01030
01031
01032
01033 outedge=GetOutEdges();
01034
01035 while(outedge!=NULL)
01036 {
01037 switch(outedge->GetType())
01038 {
01039 case EDGETYPE_LABEL:
01040 if(outedge->GetLabelID()==elementpoundlabelid)
01041 elementpoundedge=outedge;
01042 else
01043 {
01044 if(outedge->GetLabelID()==attribpoundlabelid)
01045 attribpoundedge=outedge;
01046 }
01047 break;
01048
01049 case EDGETYPE_NEGLABELLIST:
01050 negedge=outedge;
01051 break;
01052 }
01053 outedge=outedge->next;
01054 }
01055
01056
01057 if(negedge==NULL)
01058 return;
01059
01060
01061 if((attribpoundedge==NULL)&&
01062 (elementpoundedge==NULL))
01063 return;
01064
01065
01066
01067
01068
01069 curlabel=negedge->labellist;
01070 while(curlabel==NULL)
01071 {
01072 outedge=GetOutEdges();
01073 while(outedge!=NULL)
01074 {
01075 if(outedge->GetType()==EDGETYPE_LABEL)
01076 {
01077 if(outedge->GetLabelID()==curlabel->labelid)
01078 break;
01079 }
01080 outedge=outedge->next;
01081 }
01082 if(outedge==NULL)
01083 {
01084 if(ISATTRIB(curlabel->labelid))
01085
01086
01087 attribpoundedge=NULL;
01088 else
01089 elementpoundedge=NULL;
01090 }
01091 curlabel=curlabel->next;
01092 }
01093
01094
01095
01096 if((attribpoundedge==NULL)&&
01097 (elementpoundedge==NULL))
01098 return;
01099
01100 FSMEdge **edgeref=&outedges;
01101
01102 while(*edgeref!=NULL)
01103 {
01104 if((*edgeref==attribpoundedge)||
01105 (*edgeref==elementpoundedge))
01106 *edgeref=(*edgeref)->next;
01107 else
01108 edgeref=&((*edgeref)->next);
01109 }
01110 }
01111
01112 void FSM::EliminateRedundantPoundEdges()
01113
01114
01115
01116 {
01117 FSMState *state=statelist;
01118 while(state!=NULL)
01119 {
01120 state->EliminateRedundantPoundEdges();
01121 state=state->next;
01122 }
01123 }
01124
01125
01126
01127 void FSMState::ComputeOutCompleteness()
01128
01129
01130 {
01131 FSMEdge *outedge=GetOutEdges();
01132 FSMLabel *curlabel;
01133 FSMEdge *elementpoundedge=NULL,
01134 *attribpoundedge=NULL,
01135 *negedge=NULL;
01136
01137 while(outedge!=NULL)
01138 {
01139 switch(outedge->GetType())
01140 {
01141 case EDGETYPE_LABEL:
01142 if(outedge->GetLabelID()==elementpoundlabelid)
01143 {
01144 if(attribpoundedge!=NULL)
01145
01146 {
01147 isoutcomplete=1;
01148 return;
01149 }
01150 elementpoundedge=outedge;
01151 }
01152 else
01153 {
01154 if(outedge->GetLabelID()==attribpoundlabelid)
01155 {
01156 if(elementpoundedge!=NULL)
01157
01158 {
01159 isoutcomplete=1;
01160 return;
01161 }
01162 attribpoundedge=outedge;
01163 }
01164 }
01165 break;
01166
01167 case EDGETYPE_NEGLABELLIST:
01168 negedge=outedge;
01169 break;
01170 }
01171 outedge=outedge->next;
01172 }
01173
01174 if(negedge==NULL)
01175
01176 {
01177 isoutcomplete=0;
01178 return;
01179 }
01180
01181
01182 curlabel=negedge->GetLabelList();
01183 while(curlabel!=NULL)
01184 {
01185 outedge=GetOutEdges();
01186 while(outedge!=NULL)
01187 {
01188 if(outedge->GetType()==EDGETYPE_LABEL)
01189 {
01190 if(outedge->GetLabelID()==curlabel->labelid)
01191 break;
01192 }
01193 outedge=outedge->next;
01194 }
01195 if(outedge==NULL)
01196
01197
01198 {
01199
01200 if((ISATTRIB(curlabel->labelid)&&(attribpoundedge==NULL))||
01201 ((!ISATTRIB(curlabel->labelid))&&(elementpoundedge==NULL)))
01202 {
01203 isoutcomplete=0;
01204 return;
01205 }
01206 }
01207 curlabel=curlabel->next;
01208 }
01209
01210
01211
01212
01213 isoutcomplete=1;
01214 }
01215
01216 void FSM::ComputeOutCompleteness()
01217
01218
01219 {
01220 FSMState *curstate=statelist;
01221
01222 while(curstate!=NULL)
01223 {
01224 curstate->ComputeOutCompleteness();
01225 curstate=curstate->next;
01226 }
01227 }
01228
01229 char FSMState::FindAcceptingStatesRecurs()
01230
01231
01232 {
01233 tmpval=1;
01234
01235 isaccepting=(isfinal && IsOutComplete());
01236
01237
01238
01239
01240 FSMEdge *outedge=outedges;
01241
01242 while(outedge!=NULL)
01243 {
01244 if((outedge->GetNextState()->tmpval&1)==0)
01245
01246 {
01247 if(outedge->GetNextState()->FindAcceptingStatesRecurs()==0)
01248
01249 isaccepting=0;
01250 }
01251 else
01252 {
01253 if(outedge->GetNextState()->isaccepting==0)
01254
01255 isaccepting=0;
01256 }
01257 outedge=outedge->next;
01258 }
01259
01260
01261 return isaccepting;
01262 }
01263
01264 void FSM::FindAcceptingStates()
01265
01266
01267
01268 {
01269 FSMState *curstate=statelist;
01270
01271
01272
01273 ComputeOutCompleteness();
01274
01275
01276 while(curstate!=NULL)
01277 {
01278 curstate->tmpval=0;
01279 curstate=curstate->next;
01280 }
01281
01282 startstate->FindAcceptingStatesRecurs();
01283 }
01284
01285
01286
01287
01288 char FSMState::HasPoundsAheadRecurs()
01289
01290
01291 {
01292 tmpval=1;
01293
01294 haspoundsahead=0;
01295
01296 FSMEdge *outedge=outedges;
01297
01298 while(outedge!=NULL)
01299 {
01300 if((outedge->GetNextState()->tmpval&1)==0)
01301
01302 {
01303 if(outedge->GetNextState()->HasPoundsAheadRecurs()!=0)
01304
01305 haspoundsahead=1;
01306 }
01307 else
01308 {
01309 if(outedge->GetNextState()->haspoundsahead)
01310
01311 haspoundsahead=1;
01312 }
01313
01314 if(outedge->GetType()==EDGETYPE_LABEL)
01315 {
01316 if((outedge->GetLabelID()==elementpoundlabelid)||
01317 (outedge->GetLabelID()==attribpoundlabelid))
01318
01319 haspoundsahead=1;
01320 }
01321 outedge=outedge->next;
01322 }
01323
01324
01325 return haspoundsahead;
01326 }
01327
01328 void FSM::ComputeStatesHasPoundsAhead()
01329 {
01330 FSMState *curstate=statelist;
01331
01332
01333 while(curstate!=NULL)
01334 {
01335 curstate->tmpval=0;
01336 curstate=curstate->next;
01337 }
01338
01339 startstate->HasPoundsAheadRecurs();
01340 }
01341
01342
01343
01344
01345 #ifdef FSM_NEGATE
01346
01347 void FSM::CompleteDetState(FSMState *state,FSMState *deadstate)
01348
01349
01350 {
01351 FSMEdge *outedge=state->GetOutEdges();
01352 FSMLabel *labellist=NULL,**ref;
01353 FSMLabel *curlabel;
01354 char isneglist=0,deleted;
01355
01356 while(outedge!=NULL)
01357 {
01358 switch(outedge->GetType())
01359 {
01360 case EDGETYPE_LABEL:
01361 if(isneglist==0)
01362 {
01363 if(!IsInLabelList(labellist,outedge->labelid))
01364
01365 labellist=new(fsmtmpmem) FSMLabel(outedge->labelid,labellist);
01366 }
01367 else
01368 {
01369
01370
01371 deleted=0;
01372
01373 ref=&labellist;
01374 while(*ref!=NULL)
01375 {
01376 if((*ref)->labelid==outedge->labelid)
01377 {
01378 *ref=(*ref)->next;
01379 deleted=1;
01380 break;
01381 }
01382 ref=&((*ref)->next);
01383 }
01384 if(deleted==0)
01385
01386 {
01387 Error("Fatal error in FSM::CompleteDetState()");
01388 Exit();
01389 }
01390 }
01391 break;
01392
01393 case EDGETYPE_NEGLABELLIST:
01394 if(isneglist)
01395
01396 {
01397 Error("Fatal error in FSM::CompleteDetState()");
01398 Exit();
01399 }
01400 isneglist=1;
01401
01402 curlabel=outedge->GetLabelList();
01403 while(curlabel!=NULL)
01404 {
01405 deleted=0;
01406
01407 ref=&labellist;
01408 while(*ref!=NULL)
01409 {
01410 if((*ref)->labelid==curlabel->labelid)
01411 {
01412 *ref=(*ref)->next;
01413 deleted=1;
01414 break;
01415 }
01416 ref=&((*ref)->next);
01417 }
01418 if(deleted==0)
01419
01420 labellist=new (fsmtmpmem) FSMLabel(curlabel->labelid,labellist);
01421
01422 curlabel=curlabel->next;
01423 }
01424 }
01425 outedge=outedge->next;
01426 }
01427
01428 if(isneglist==1)
01429
01430 {
01431 ref=&labellist;
01432 while(*ref!=NULL)
01433 {
01434 CreateLabelEdge(state,deadstate,(*ref)->labelid);
01435 ref=&((*ref)->next);
01436 }
01437 }
01438 else
01439 CreateNegEdge(state,deadstate,labellist);
01440 }
01441
01442 void FSM::CompleteDetFSM()
01443
01444
01445
01446 {
01447
01448 FSMState *deadstate,*curstate;
01449 FSMEdge *loopedge;
01450
01451 deadstate=CreateState((char)0);
01452
01453
01454
01455 loopedge=CreateNegEdge(deadstate,deadstate,NULL);
01456
01457
01458
01459
01460 curstate=statelist;
01461
01462 while(curstate!=NULL)
01463 {
01464
01465 CompleteDetState(curstate,deadstate);
01466 curstate=curstate->next;
01467 }
01468 }
01469
01470 FSM *FSM::CreateNegateFSM()
01471
01472
01473
01474 {
01475 FSM *detfsm;
01476 FSMState *curstate;
01477
01478
01479 detfsm=MakeDeterministic();
01480
01481
01482 detfsm->CompleteDetFSM();
01483
01484
01485
01486 curstate=detfsm->GetStateList();
01487
01488 while(curstate!=NULL)
01489 {
01490 if(curstate->IsFinal())
01491 curstate->isfinal=0;
01492 else
01493 curstate->isfinal=1;
01494
01495 curstate=curstate->next;
01496 }
01497
01498 detfsm=detfsm->Minimize();
01499
01500 return detfsm;
01501 }
01502
01503 #endif
01504
01505
01506
01507
01508 void FSM::AddFSM(FSMState *fromstate,FSMState *tostate,FSM *fsm)
01509
01510 {
01511 FSMState *curstate=fsm->GetStateList(),*newstate;
01512
01513
01514
01515 while(curstate!=NULL)
01516 {
01517
01518 if(curstate==fsm->GetStartState())
01519 curstate=fromstate;
01520 else
01521 {
01522 newstate=CreateState((char)0);
01523 curstate->data=newstate;
01524 }
01525 if(curstate->IsFinal())
01526
01527 CreateEmptyEdge((FSMState *)(curstate->data),tostate);
01528
01529 curstate=curstate->next;
01530 }
01531
01532
01533 curstate=fsm->GetStateList();
01534
01535 FSMEdge *outedge;
01536
01537
01538
01539 while(curstate!=NULL)
01540 {
01541 outedge=curstate->GetOutEdges();
01542 while(outedge!=NULL)
01543 {
01544 switch(outedge->GetType())
01545 {
01546 case EDGETYPE_LABEL:
01547 CreateLabelEdge((FSMState *)(curstate->data),
01548 (FSMState *)(outedge->GetNextState()->data),
01549 outedge->labelid);
01550 break;
01551
01552 case EDGETYPE_NEGLABELLIST:
01553 {
01554 FSMLabel *newlabellist=NULL;
01555
01556 DupLabelList(outedge->labellist,&newlabellist);
01557
01558 CreateNegEdge((FSMState *)(curstate->data),
01559 (FSMState *)(outedge->GetNextState()->data),
01560 newlabellist);
01561 break;
01562 }
01563
01564 case EDGETYPE_EMPTY:
01565 CreateEmptyEdge((FSMState *)(curstate->data),
01566 (FSMState *)(outedge->GetNextState()->data));
01567 break;
01568 }
01569
01570 outedge=outedge->next;
01571 }
01572 curstate=curstate->next;
01573 }
01574 }
01575
01576
01577
01578
01579
01580 FSM *FSM::CreateReverseFSM()
01581
01582
01583 {
01584 FSMState *newstate;
01585 FSMEdge *edge;
01586
01587 FSM *newfsm=new(fsmmem) FSM();
01588
01589
01590
01591
01592 FSMState *newstartstate=newfsm->CreateState();
01593
01594 newfsm->SetStartState(newstartstate);
01595
01596 FSMState *curstate=statelist;
01597
01598
01599
01600
01601
01602
01603 while(curstate!=NULL)
01604 {
01605 newstate=newfsm->CreateState(curstate==startstate);
01606
01607 if(curstate->IsFinal())
01608 newfsm->CreateEmptyEdge(newstartstate,newstate);
01609
01610 curstate->data=newstate;
01611 curstate=curstate->next;
01612 }
01613
01614
01615 curstate=statelist;
01616
01617 while(curstate!=NULL)
01618 {
01619 edge=curstate->GetOutEdges();
01620 while(edge!=NULL)
01621 {
01622 switch(edge->GetType())
01623 {
01624 case EDGETYPE_LABEL:
01625 newfsm->CreateLabelEdge((FSMState *)(edge->GetNextState()->data),
01626 (FSMState *)(curstate->data),
01627 edge->GetLabelID());
01628 break;
01629
01630 case EDGETYPE_NEGLABELLIST:
01631 {
01632 FSMLabel *newlabellist=NULL;
01633
01634 DupLabelList(edge->GetLabelList(),&newlabellist);
01635
01636 newfsm->CreateNegEdge( (FSMState *)(edge->GetNextState()->data),
01637 (FSMState *)(curstate->data),
01638 newlabellist);
01639 break;
01640 }
01641 case EDGETYPE_EMPTY:
01642 newfsm->CreateEmptyEdge((FSMState *)(edge->GetNextState()->data),
01643 (FSMState *)(curstate->data));
01644 break;
01645 }
01646 edge=edge->next;
01647 }
01648 curstate=curstate->next;
01649 }
01650 return newfsm;
01651 }
01652
01653
01654
01655
01656
01657
01658 #ifdef FSM_PRINT
01659
01660 void FSMState::Print()
01661
01662 {
01663 printf("%lu",stateid);
01664 if(isfinal)
01665 printf(":F");
01666
01667 if(isoutcomplete)
01668 printf(":C");
01669
01670 if(isaccepting)
01671 printf(":A");
01672
01673 if(haspoundsahead)
01674 printf(":P");
01675
01676
01677
01678
01679
01680
01681
01682
01683
01684
01685
01686
01687
01688
01689
01690
01691
01692 }
01693
01694 void FSMEdge::PrintLabelList()
01695
01696 {
01697 FSMLabel *curlabel=labellist;
01698
01699 while(curlabel!=NULL)
01700 {
01701 globallabeldict.PrintLabel(curlabel->labelid);
01702
01703 curlabel=curlabel->next;
01704 if(curlabel!=NULL)
01705 printf("|");
01706 }
01707 }
01708
01709 void FSMEdge::Print()
01710
01711 {
01712 switch(type)
01713 {
01714 case EDGETYPE_LABEL:
01715 globallabeldict.PrintLabel(labelid);
01716 break;
01717
01718 case EDGETYPE_NEGLABELLIST:
01719 printf("ALL BUT ");
01720 PrintLabelList();
01721 break;
01722
01723 case EDGETYPE_EMPTY:
01724 break;
01725 }
01726 }
01727
01728
01729
01730
01731 void FSM::Print()
01732
01733 {
01734 FSMState *curstate=statelist;
01735 FSMEdge *edge;
01736
01737 while(curstate!=NULL)
01738 {
01739 edge=curstate->GetOutEdges();
01740
01741 while(edge!=NULL)
01742 {
01743 curstate->Print();
01744 printf(" -- ");
01745 edge->Print();
01746 printf(" --> ");
01747 edge->GetNextState()->Print();
01748 printf("\n");
01749
01750 edge=edge->next;
01751 }
01752 curstate=curstate->next;
01753 }
01754 }
01755
01756 #endif // FSM_PRINT
01757
01758
01759
01760
01761
01762 #ifdef FSM_STORE
01763
01764 void FSMEdge::Store(MemStreamer *mem)
01765
01766 {
01767
01768
01769
01770 mem->StoreUInt32(type);
01771 mem->StoreUInt32(nextstate->GetStateID());
01772
01773 switch(type)
01774 {
01775 case EDGETYPE_LABEL:
01776 mem->StoreUInt32(labelid);
01777 break;
01778
01779 case EDGETYPE_NEGLABELLIST:
01780 {
01781 FSMLabel *curlabel=labellist;
01782 int labelcount=0;
01783
01784
01785
01786 while(curlabel!=NULL)
01787 {
01788 labelcount++;
01789 curlabel=curlabel->next;
01790 }
01791
01792
01793 mem->StoreUInt32(labelcount);
01794
01795
01796 curlabel=labellist;
01797
01798 while(curlabel!=NULL)
01799 {
01800 mem->StoreUInt32(curlabel->labelid);
01801 curlabel=curlabel->next;
01802 }
01803 }
01804 }
01805 }
01806
01807 void FSMEdge::Load(unsigned char * &ptr,FSMState *statearray,MemStreamer *fsmmem)
01808 {
01809 type=LoadUInt32(ptr);
01810
01811 nextstate=statearray+LoadUInt32(ptr);
01812
01813 switch(type)
01814 {
01815 case EDGETYPE_LABEL:
01816 labelid=(unsigned short)LoadUInt32(ptr);;
01817 break;
01818
01819 case EDGETYPE_NEGLABELLIST:
01820 {
01821 FSMLabel **labelref=&labellist;
01822 unsigned long labelcount;
01823
01824 labelcount=LoadUInt32(ptr);
01825
01826 while(labelcount--)
01827 {
01828 *labelref=new(fsmmem) FSMLabel((unsigned short)LoadUInt32(ptr));
01829 labelref=&((*labelref)->next);
01830 }
01831 *labelref=NULL;
01832 }
01833 }
01834 }
01835
01836
01837
01838
01839 void FSMState::Store(MemStreamer *mem)
01840 {
01841
01842 mem->StoreUInt32(isfinal);
01843
01844
01845
01846 FSMEdge *curedge=outedges;
01847 unsigned long edgecount=0;
01848
01849 while(curedge!=NULL)
01850 {
01851 edgecount++;
01852 curedge=curedge->next;
01853 }
01854
01855
01856 mem->StoreUInt32(edgecount);
01857
01858
01859 curedge=outedges;
01860 while(curedge!=NULL)
01861 {
01862 curedge->Store(mem);
01863 curedge=curedge->next;
01864 }
01865 }
01866
01867 void FSMState::Load(unsigned char * &ptr,FSMState *statearray,MemStreamer *fsmmem)
01868 {
01869 unsigned long edgecount;
01870
01871
01872 isfinal=LoadUInt32(ptr);
01873
01874 FSMEdge **edgeref =&outedges;
01875
01876
01877
01878 edgecount=LoadUInt32(ptr);
01879
01880
01881 while(edgecount--)
01882 {
01883 *edgeref=new(fsmmem) FSMEdge();
01884
01885 (*edgeref)->Load(ptr,statearray,fsmmem);
01886 edgeref=&((*edgeref)->next);
01887 }
01888 *edgeref=NULL;
01889 }
01890
01891
01892
01893
01894 void FSM::Store(MemStreamer *mem)
01895
01896 {
01897 mem->StoreUInt32(curidx);
01898
01899
01900 mem->StoreUInt32(startstate->GetStateID());
01901
01902 FSMState *curstate=statelist;
01903
01904
01905 while(curstate!=NULL)
01906 {
01907 curstate->Store(mem);
01908 curstate=curstate->next;
01909 }
01910 }
01911
01912 void FSM::Load(unsigned char * &ptr,MemStreamer *fsmmem)
01913 {
01914
01915 curidx=LoadUInt32(ptr);
01916
01917 unsigned long startstateidx;
01918
01919 startstateidx=LoadUInt32(ptr);
01920
01921 FSMState **stateref=&statelist;
01922 FSMState *statearray=new(fsmmem) FSMState[curidx];
01923
01924 for(unsigned i=0;i<curidx;i++)
01925 {
01926 *stateref=statearray+i;
01927 (*stateref)->stateid=i;
01928 (*stateref)->next=NULL;
01929 (*stateref)->origstateset=NULL;
01930
01931 (*stateref)->Load(ptr,statearray,fsmmem);
01932
01933 stateref=&((*stateref)->next);
01934 }
01935 *stateref=NULL;
01936
01937 startstate=statearray+startstateidx;
01938 }
01939
01940 #endif // FSM_STORE
01941
01942
01943
01944
01945
01946
01947
01948
01949
01950
01951
01952
01953
01954
01955
01956
01957
01958
01959
01960
01961
01962
01963
01964
01965
01966
01967
01968
01969
01970
01971
01972
01973
01974
01975
01976
01977
01978
01979
01980
01981
01982
01983
01984
01985
01986
01987
01988
01989
01990
01991
01992
01993
01994
01995
01996
01997
01998
01999
02000
02001
02002
02003
02004
02005
02006
02007
02008
02009
02010
02011
02012
02013
02014
02015
02016
02017
02018
02019
02020
02021
02022
02023
02024
02025
02026
02027
02028
02029
02030
02031
02032
02033
02034
02035
02036
02037
02038
02039
02040
02041
02042
02043
02044
02045
02046