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