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
00034
00035
00036
00037
00038 #include <gecode/minimodel.hh>
00039
00040 namespace Gecode {
00041
00042 namespace MiniModel {
00043
00044 class PosSet;
00048 typedef Support::BlockAllocator<PosSet,Heap> PosSetAllocator;
00049
00050 class NodeInfo;
00051 class PosInfo;
00052
00053 }
00054
00056 class REG::Exp {
00057 public:
00059 unsigned int use_cnt;
00061 int _n_pos;
00065 enum ExpType {
00066 ET_SYMBOL,
00067 ET_CONC,
00068 ET_OR,
00069 ET_STAR
00070 };
00072 ExpType type;
00074 union {
00076 int symbol;
00078 Exp* kids[2];
00079 } data;
00080
00082 MiniModel::PosSet*
00083 followpos(MiniModel::PosSetAllocator&,MiniModel::PosInfo*);
00085 static void inc(Exp* e);
00087 static void dec(Exp* e);
00089 static int n_pos(Exp* e);
00091 void toString(std::ostringstream& os) const;
00093 std::string toString(void) const;
00094
00095 static void* operator new(size_t);
00096 static void operator delete(void*);
00097 private:
00099 void dispose(void);
00100 };
00101
00102
00103
00104
00105
00106
00107
00108
00109 forceinline void*
00110 REG::Exp::operator new(size_t s) {
00111 return heap.ralloc(s);
00112 }
00113 forceinline void
00114 REG::Exp::operator delete(void*) {
00115
00116 }
00117
00118 void
00119 REG::Exp::dispose(void) {
00120 Support::DynamicStack<Exp*,Heap> todo(heap);
00121 todo.push(this);
00122 while (!todo.empty()) {
00123 Exp* e = todo.pop();
00124 switch (e->type) {
00125 case ET_OR:
00126 case ET_CONC:
00127 if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
00128 todo.push(e->data.kids[1]);
00129 case ET_STAR:
00130 if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
00131 todo.push(e->data.kids[0]);
00132 default: ;
00133 }
00134 heap.rfree(e);
00135 }
00136 }
00137
00138 forceinline void
00139 REG::Exp::inc(Exp* e) {
00140 if (e != NULL)
00141 e->use_cnt++;
00142 }
00143 forceinline void
00144 REG::Exp::dec(Exp* e) {
00145 if ((e != NULL) && (--e->use_cnt == 0))
00146 e->dispose();
00147 }
00148
00149
00150 forceinline int
00151 REG::Exp::n_pos(Exp* e) {
00152 return (e != NULL) ? e->_n_pos : 0;
00153 }
00154
00155 void
00156 REG::Exp::toString(std::ostringstream& os) const {
00157 switch (type) {
00158 case ET_SYMBOL:
00159 os << "[" << data.symbol << "]";
00160 return;
00161 case ET_STAR:
00162 {
00163 bool par = ((data.kids[0] != NULL) &&
00164 ((data.kids[0]->type == ET_CONC) ||
00165 (data.kids[0]->type == ET_OR)));
00166 os << (par ? "*(" : "*");
00167 if (data.kids[0]==NULL) {
00168 os << "[]";
00169 } else {
00170 data.kids[0]->toString(os);
00171 }
00172 os << (par ? ")" : "");
00173 return;
00174 }
00175 case ET_CONC:
00176 {
00177 bool par0 = ((data.kids[0] != NULL) &&
00178 (data.kids[0]->type == ET_OR));
00179 os << (par0 ? "(" : "");
00180 if (data.kids[0]==NULL) {
00181 os << "[]";
00182 } else {
00183 data.kids[0]->toString(os);
00184 }
00185 os << (par0 ? ")+" : "+");
00186 bool par1 = ((data.kids[1] != NULL) &&
00187 (data.kids[1]->type == ET_OR));
00188 os << (par1 ? "(" : "");
00189 if (data.kids[1]==NULL) {
00190 os << "[]";
00191 } else {
00192 data.kids[1]->toString(os);
00193 }
00194 os << (par1 ? ")" : "");
00195 return;
00196 }
00197 case ET_OR:
00198 if (data.kids[0]==NULL) {
00199 os << "[]";
00200 } else {
00201 data.kids[0]->toString(os);
00202 }
00203 os << "|";
00204 if (data.kids[1]==NULL) {
00205 os << "[]";
00206 } else {
00207 data.kids[1]->toString(os);
00208 }
00209 return;
00210 default: GECODE_NEVER;
00211 }
00212 GECODE_NEVER;
00213 return;
00214 }
00215
00216 std::string
00217 REG::Exp::toString(void) const {
00218 std::ostringstream os;
00219 toString(os);
00220 return os.str();
00221 }
00222
00223
00224
00225
00226
00227
00228
00229 forceinline
00230 REG::REG(Exp* f) : e(f) {}
00231
00232 REG::REG(void) : e(NULL) {}
00233
00234 REG::REG(const REG& r) : e(r.e) {
00235 REG::Exp::inc(e);
00236 }
00237
00238 const REG&
00239 REG::operator =(const REG& r) {
00240 if (&r != this) {
00241 REG::Exp::inc(r.e);
00242 REG::Exp::dec(e);
00243 e = r.e;
00244 }
00245 return *this;
00246 }
00247
00248 REG::~REG(void) {
00249 REG::Exp::dec(e);
00250 }
00251
00252 REG::REG(int s) : e(new Exp) {
00253 e->use_cnt = 1;
00254 e->_n_pos = 1;
00255 e->type = REG::Exp::ET_SYMBOL;
00256 e->data.symbol = s;
00257 }
00258
00259 REG::REG(const IntArgs& x) {
00260 int n = x.size();
00261 if (n < 1)
00262 throw MiniModel::TooFewArguments("REG");
00263 Exp** a = heap.alloc<Exp*>(n);
00264
00265 for (int i=n; i--; ) {
00266 a[i] = new Exp();
00267 a[i]->use_cnt = 1;
00268 a[i]->_n_pos = 1;
00269 a[i]->type = REG::Exp::ET_SYMBOL;
00270 a[i]->data.symbol = x[i];
00271 }
00272
00273 for (int m=n; m>1; ) {
00274 if (m & 1) {
00275 m -= 1;
00276 Exp* e1 = a[m];
00277 Exp* e2 = a[0];
00278 a[0] = new Exp;
00279 a[0]->use_cnt = 1;
00280 a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
00281 a[0]->type = REG::Exp::ET_OR;
00282 a[0]->data.kids[0] = e1;
00283 a[0]->data.kids[1] = e2;
00284 } else {
00285 m >>= 1;
00286 for (int i=0; i<m; i++) {
00287 Exp* e1 = a[2*i];
00288 Exp* e2 = a[2*i+1];
00289 a[i] = new Exp;
00290 a[i]->use_cnt = 1;
00291 a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
00292 a[i]->type = REG::Exp::ET_OR;
00293 a[i]->data.kids[0] = e1;
00294 a[i]->data.kids[1] = e2;
00295 }
00296 }
00297 }
00298 e = a[0];
00299 heap.free<Exp*>(a,n);
00300 }
00301
00302 REG
00303 REG::operator |(const REG& r2) {
00304 if (e == r2.e)
00305 return *this;
00306 Exp* f = new Exp();
00307 f->use_cnt = 1;
00308 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00309 f->type = REG::Exp::ET_OR;
00310 f->data.kids[0] = e; REG::Exp::inc(e);
00311 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00312 REG r(f);
00313 return r;
00314 }
00315
00316 REG&
00317 REG::operator |=(const REG& r2) {
00318 if (e == r2.e)
00319 return *this;
00320 Exp* f = new Exp();
00321 f->use_cnt = 1;
00322 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00323 f->type = REG::Exp::ET_OR;
00324 f->data.kids[0] = e;
00325 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00326 e=f;
00327 return *this;
00328 }
00329
00330 REG
00331 REG::operator +(const REG& r2) {
00332 if (e == NULL) return r2;
00333 if (r2.e == NULL) return *this;
00334 Exp* f = new Exp();
00335 f->use_cnt = 1;
00336 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00337 f->type = REG::Exp::ET_CONC;
00338 f->data.kids[0] = e; REG::Exp::inc(e);
00339 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00340 REG r(f);
00341 return r;
00342 }
00343
00344 REG&
00345 REG::operator +=(const REG& r2) {
00346 if (r2.e == NULL)
00347 return *this;
00348 if (e == NULL) {
00349 e=r2.e; REG::Exp::inc(e);
00350 } else {
00351 Exp* f = new Exp();
00352 f->use_cnt = 1;
00353 f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
00354 f->type = REG::Exp::ET_CONC;
00355 f->data.kids[0] = e;
00356 f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
00357 e=f;
00358 }
00359 return *this;
00360 }
00361
00362 REG
00363 REG::operator *(void) {
00364 if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
00365 return *this;
00366 Exp* f = new Exp();
00367 f->use_cnt = 1;
00368 f->_n_pos = REG::Exp::n_pos(e);
00369 f->type = REG::Exp::ET_STAR;
00370 f->data.kids[0] = e; REG::Exp::inc(e);
00371 REG r(f);
00372 return r;
00373 }
00374
00375 REG
00376 REG::operator ()(unsigned int n, unsigned int m) {
00377 REG r;
00378 if ((n>m) || (m == 0))
00379 return r;
00380 if (n>0) {
00381 unsigned int i = n;
00382 REG r0 = *this;
00383 while (i>0)
00384 if (i & 1) {
00385 r = r0+r; i--;
00386 } else {
00387 r0 = r0+r0; i >>= 1;
00388 }
00389 }
00390 if (m > n) {
00391 unsigned int i = m-n;
00392 REG s0;
00393 s0 = s0 | *this;
00394 REG s;
00395 while (i>0)
00396 if (i & 1) {
00397 s = s0+s; i--;
00398 } else {
00399 s0 = s0+s0; i >>= 1;
00400 }
00401 r = r + s;
00402 }
00403 return r;
00404 }
00405
00406 REG
00407 REG::operator ()(unsigned int n) {
00408 REG r;
00409 if (n > 0) {
00410 REG r0 = *this;
00411 unsigned int i = n;
00412 while (i>0)
00413 if (i & 1) {
00414 r = r0+r; i--;
00415 } else {
00416 r0 = r0+r0; i >>= 1;
00417 }
00418 }
00419 return r+**this;
00420 }
00421
00422 REG
00423 REG::operator +(void) {
00424 return this->operator ()(1);
00425 }
00426
00427 std::string
00428 REG::toString(void) const {
00429 if (e==NULL) {
00430 return "[]";
00431 }
00432 return e->toString();
00433 }
00434
00435 namespace MiniModel {
00436
00437
00438
00439
00440
00441
00445 enum PosSetCmp {
00446 PSC_LE,
00447 PSC_EQ,
00448 PSC_GR
00449 };
00450
00454 class PosSet : public Support::BlockClient<PosSet,Heap> {
00455
00456
00457
00458 public:
00459 int pos; PosSet* next;
00460
00461 PosSet(void);
00462 PosSet(int);
00463
00464 bool in(int) const;
00465 static PosSetCmp cmp(PosSet*,PosSet*);
00466 static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
00467 };
00468
00469
00470 forceinline
00471 PosSet::PosSet(void) {}
00472 forceinline
00473 PosSet::PosSet(int p) : pos(p), next(NULL) {}
00474
00475
00476 forceinline bool
00477 PosSet::in(int p) const {
00478 for (const PosSet* ps = this; ps != NULL; ps = ps->next)
00479 if (ps->pos == p) {
00480 return true;
00481 } else if (ps->pos < p) {
00482 return false;
00483 }
00484 return false;
00485 }
00486
00487 forceinline PosSetCmp
00488 PosSet::cmp(PosSet* ps1, PosSet* ps2) {
00489 while ((ps1 != NULL) && (ps2 != NULL)) {
00490 if (ps1 == ps2)
00491 return PSC_EQ;
00492 if (ps1->pos < ps2->pos)
00493 return PSC_LE;
00494 if (ps1->pos > ps2->pos)
00495 return PSC_GR;
00496 ps1 = ps1->next; ps2 = ps2->next;
00497 }
00498 if (ps1 == ps2)
00499 return PSC_EQ;
00500 return ps1 == NULL ? PSC_LE : PSC_GR;
00501 }
00502
00503 PosSet*
00504 PosSet::cup(PosSetAllocator& psm, PosSet* ps1, PosSet* ps2) {
00505 PosSet* ps;
00506 PosSet** p = &ps;
00507 while ((ps1 != NULL) && (ps2 != NULL)) {
00508 if (ps1 == ps2) {
00509 *p = ps1; return ps;
00510 }
00511 PosSet* n = new (psm) PosSet;
00512 *p = n; p = &n->next;
00513 if (ps1->pos == ps2->pos) {
00514 n->pos = ps1->pos;
00515 ps1 = ps1->next; ps2 = ps2->next;
00516 } else if (ps1->pos > ps2->pos) {
00517 n->pos = ps1->pos; ps1 = ps1->next;
00518 } else {
00519 n->pos = ps2->pos; ps2 = ps2->next;
00520 }
00521 }
00522 *p = (ps1 != NULL) ? ps1 : ps2;
00523 return ps;
00524 }
00525
00526
00528 class NodeInfo {
00529 public:
00530 bool nullable;
00531 PosSet* firstpos;
00532 PosSet* lastpos;
00533 NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
00534 };
00535
00537 class ExpInfo {
00538 public:
00539 REG::Exp* exp;
00540 bool open;
00541 ExpInfo(REG::Exp* e=NULL);
00542 };
00543
00548 class PosInfo {
00549 public:
00550 int symbol;
00551 PosSet* followpos;
00552 };
00553
00554 forceinline
00555 NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
00556 : nullable(n), firstpos(fp), lastpos(lp) {}
00557
00558 forceinline
00559 ExpInfo::ExpInfo(REG::Exp* e)
00560 : exp(e), open(true) {}
00561
00562 }
00563
00564 forceinline MiniModel::PosSet*
00565 REG::Exp::followpos(MiniModel::PosSetAllocator& psm,
00566 MiniModel::PosInfo* pi) {
00567 int p=0;
00568
00569 using MiniModel::PosSet;
00570 using MiniModel::NodeInfo;
00571 using MiniModel::ExpInfo;
00572
00573 Support::DynamicStack<ExpInfo,Heap> todo(heap);
00574 Support::DynamicStack<NodeInfo,Heap> done(heap);
00575
00576
00577 todo.push(ExpInfo(this));
00578
00579 do {
00580 if (todo.top().exp == NULL) {
00581 todo.pop();
00582 done.push(NodeInfo(true,NULL,NULL));
00583 } else {
00584 switch (todo.top().exp->type) {
00585 case ET_SYMBOL:
00586 {
00587 pi[p].symbol = todo.pop().exp->data.symbol;
00588 PosSet* ps = new (psm) PosSet(p++);
00589 done.push(NodeInfo(false,ps,ps));
00590 }
00591 break;
00592 case ET_STAR:
00593 if (todo.top().open) {
00594
00595 todo.top().open = false;
00596 todo.push(todo.top().exp->data.kids[0]);
00597 } else {
00598 todo.pop();
00599 NodeInfo ni = done.pop();
00600 for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
00601 pi[ps->pos].followpos =
00602 PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
00603 done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
00604 }
00605 break;
00606 case ET_CONC:
00607 if (todo.top().open) {
00608
00609 todo.top().open = false;
00610 REG::Exp* e = todo.top().exp;
00611 todo.push(e->data.kids[1]);
00612 todo.push(e->data.kids[0]);
00613 } else {
00614 todo.pop();
00615 NodeInfo ni1 = done.pop();
00616 NodeInfo ni0 = done.pop();
00617 for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
00618 pi[ps->pos].followpos =
00619 PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
00620 done.push(NodeInfo(ni0.nullable & ni1.nullable,
00621 ni0.nullable ?
00622 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
00623 ni1.nullable ?
00624 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
00625 }
00626 break;
00627 case ET_OR:
00628 if (todo.top().open) {
00629
00630 todo.top().open = false;
00631 REG::Exp* e = todo.top().exp;
00632 todo.push(e->data.kids[1]);
00633 todo.push(e->data.kids[0]);
00634 } else {
00635 todo.pop();
00636 NodeInfo ni1 = done.pop();
00637 NodeInfo ni0 = done.pop();
00638 done.push(NodeInfo(ni0.nullable | ni1.nullable,
00639 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
00640 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
00641 }
00642 break;
00643 default: GECODE_NEVER;
00644 }
00645 }
00646 } while (!todo.empty());
00647 return done.top().firstpos;
00648 }
00649
00650
00651 namespace MiniModel {
00652
00653 class StateNode;
00654
00658 typedef Support::BlockAllocator<StateNode,Heap> StatePoolAllocator;
00659
00663 class StateNode : public Support::BlockClient<StateNode,Heap> {
00664 public:
00665 PosSet* pos;
00666 int state;
00667 StateNode* next;
00668 StateNode* left;
00669 StateNode* right;
00670 };
00671
00675 class StatePool {
00676 public:
00677 int n_states;
00678 StateNode root;
00679 StateNode* next;
00680 StateNode* all;
00681
00682 StatePool(PosSet*);
00683
00684 StateNode* pop(void);
00685 bool empty(void) const;
00686
00687 int state(StatePoolAllocator&, PosSet*);
00688 };
00689
00690 forceinline
00691 StatePool::StatePool(PosSet* ps) {
00692 next = &root;
00693 all = NULL;
00694 n_states = 1;
00695 root.pos = ps;
00696 root.state = 0;
00697 root.next = NULL;
00698 root.left = NULL;
00699 root.right = NULL;
00700 }
00701
00702 forceinline StateNode*
00703 StatePool::pop(void) {
00704 StateNode* n = next;
00705 next = n->next;
00706 n->next = all;
00707 all = n;
00708 return n;
00709 }
00710
00711 forceinline bool
00712 StatePool::empty(void) const {
00713 return next == NULL;
00714 }
00715
00716 forceinline int
00717 StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
00718 int d = 0;
00719 StateNode** p = NULL;
00720 StateNode* n = &root;
00721 do {
00722 switch (PosSet::cmp(ps,n->pos)) {
00723 case PSC_EQ: return n->state;
00724 case PSC_LE: p = &n->left; n = *p; break;
00725 case PSC_GR: p = &n->right; n = *p; break;
00726 default: GECODE_NEVER;
00727 }
00728 d++;
00729 } while (n != NULL);
00730 n = new (spm) StateNode; *p = n;
00731 n->pos = ps;
00732 n->state = n_states++;
00733 n->next = next;
00734 n->left = NULL;
00735 n->right = NULL;
00736 next = n;
00737 return n->state;
00738 }
00739
00743 class SymbolsInc {
00744 public:
00745 forceinline bool
00746 operator ()(int x, int y) {
00747 return x < y;
00748 }
00749 forceinline static void
00750 sort(int s[], int n) {
00751 SymbolsInc o;
00752 Support::quicksort<int,SymbolsInc>(s,n,o);
00753 }
00754 };
00755
00756
00761 class TransitionBag {
00762 private:
00763 Support::DynamicArray<DFA::Transition,Heap> t;
00764 int n;
00765 public:
00766 TransitionBag(void);
00767 void add(int,int,int);
00768 void finish(void);
00769 DFA::Transition* transitions(void);
00770 };
00771
00772 forceinline
00773 TransitionBag::TransitionBag(void) : t(heap), n(0) {}
00774
00775 forceinline void
00776 TransitionBag::add(int i_state, int symbol, int o_state) {
00777 t[n].i_state = i_state;
00778 t[n].symbol = symbol;
00779 t[n].o_state = o_state;
00780 n++;
00781 }
00782
00783 forceinline void
00784 TransitionBag::finish(void) {
00785 t[n].i_state = -1;
00786 }
00787
00788 forceinline DFA::Transition*
00789 TransitionBag::transitions(void) {
00790 return &t[0];
00791 }
00792
00793
00798 class FinalBag {
00799 private:
00800 Support::DynamicArray<int,Heap> f;
00801 int n;
00802 public:
00803 FinalBag(void);
00804 void add(int);
00805 void finish(void);
00806 int* finals(void);
00807 };
00808
00809 forceinline
00810 FinalBag::FinalBag(void) : f(heap), n(0) {}
00811
00812 forceinline void
00813 FinalBag::add(int state) {
00814 f[n++] = state;
00815 }
00816
00817 forceinline void
00818 FinalBag::finish(void) {
00819 f[n] = -1;
00820 }
00821
00822 forceinline int*
00823 FinalBag::finals(void) {
00824 return &f[0];
00825 }
00826
00827 }
00828
00829 REG::operator DFA(void) {
00830 using MiniModel::PosSetAllocator;
00831 using MiniModel::StatePoolAllocator;
00832 using MiniModel::PosInfo;
00833 using MiniModel::PosSet;
00834 using MiniModel::NodeInfo;
00835
00836 using MiniModel::StatePool;
00837 using MiniModel::StateNode;
00838
00839 using MiniModel::TransitionBag;
00840 using MiniModel::FinalBag;
00841
00842 using MiniModel::SymbolsInc;
00843
00844 PosSetAllocator psm(heap);
00845 StatePoolAllocator spm(heap);
00846 REG r = *this + REG(Int::Limits::max+1);
00847 int n_pos = REG::Exp::n_pos(r.e);
00848
00849 PosInfo* pi = heap.alloc<PosInfo>(n_pos);
00850 for (int i=n_pos; i--; )
00851 pi[i].followpos = NULL;
00852
00853 PosSet* firstpos = r.e->followpos(psm,&pi[0]);
00854
00855
00856 int* symbols = heap.alloc<int>(n_pos);
00857 for (int i=n_pos; i--; )
00858 symbols[i] = pi[i].symbol;
00859
00860 SymbolsInc::sort(&symbols[0],n_pos-1);
00861 int n_symbols = 1;
00862 for (int i = 1; i<n_pos-1; i++)
00863 if (symbols[i-1] != symbols[i])
00864 symbols[n_symbols++] = symbols[i];
00865
00866
00867 TransitionBag tb;
00868 StatePool sp(firstpos);
00869 while (!sp.empty()) {
00870 StateNode* sn = sp.pop();
00871 for (int i = n_symbols; i--; ) {
00872 PosSet* u = NULL;
00873 for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
00874 if (pi[ps->pos].symbol == symbols[i])
00875 u = PosSet::cup(psm,u,pi[ps->pos].followpos);
00876 if (u != NULL)
00877 tb.add(sn->state,symbols[i],sp.state(spm,u));
00878 }
00879 }
00880 tb.finish();
00881
00882
00883 FinalBag fb;
00884 for (StateNode* n = sp.all; n != NULL; n = n->next)
00885 if (n->pos->in(n_pos-1))
00886 fb.add(n->state);
00887 fb.finish();
00888
00889 heap.free<PosInfo>(pi,n_pos);
00890 heap.free<int>(symbols,n_pos);
00891 return DFA(0,tb.transitions(),fb.finals(),true);
00892 }
00893
00894 }
00895
00896
00897