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