85 int n_pos(
void)
const;
87 template<
class Char,
class Traits>
88 std::basic_ostream<Char,Traits>&
89 print(std::basic_ostream<Char,Traits>& os)
const;
91 static void*
operator new(size_t);
92 static void operator delete(
void*);
105 REG::Exp::operator
new(
size_t s) {
109 REG::Exp::operator
delete(
void*) {
114 REG::Exp::dispose(
void) {
117 while (!todo.empty()) {
140 if ((
this != NULL) && (--use_cnt == 0))
147 return (
this != NULL) ? _n_pos : 0;
192 for (
int i=n;
i--; ) {
200 for (
int m=n; m>1; ) {
213 for (
int i=0;
i<m;
i++) {
259 if (e == NULL)
return r2;
260 if (r2.e == NULL)
return *
this;
305 if ((n>m) || (m == 0))
318 unsigned int i = m-
n;
355 namespace MiniModel {
398 for (
const PosSet* ps =
this; ps != NULL; ps = ps->
next)
401 }
else if (ps->pos < p) {
409 while ((ps1 != NULL) && (ps2 != NULL)) {
427 while ((ps1 != NULL) && (ps2 != NULL)) {
432 *p =
n; p = &n->
next;
433 if (ps1->
pos == ps2->
pos) {
436 }
else if (ps1->
pos > ps2->
pos) {
442 *p = (ps1 != NULL) ? ps1 : ps2;
476 : nullable(n), firstpos(fp), lastpos(lp) {}
480 :
exp(e), open(true) {}
497 todo.
push(ExpInfo(
this));
500 if (todo.
top().exp == NULL) {
502 done.
push(NodeInfo(
true,NULL,NULL));
504 switch (todo.
top().exp->type) {
508 PosSet* ps =
new (psm) PosSet(p++);
509 done.
push(NodeInfo(
false,ps,ps));
513 if (todo.
top().open) {
515 todo.
top().open =
false;
516 todo.
push(todo.
top().exp->data.kids[0]);
519 NodeInfo ni = done.
pop();
520 for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
522 PosSet::cup(psm,pi[ps->pos].
followpos,ni.firstpos);
523 done.
push(NodeInfo(
true,ni.firstpos,ni.lastpos));
527 if (todo.
top().open) {
529 todo.
top().open =
false;
535 NodeInfo ni1 = done.
pop();
536 NodeInfo ni0 = done.
pop();
537 for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
539 PosSet::cup(psm,pi[ps->pos].
followpos,ni1.firstpos);
540 done.
push(NodeInfo(ni0.nullable & ni1.nullable,
542 PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
544 PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
548 if (todo.
top().open) {
550 todo.
top().open =
false;
556 NodeInfo ni1 = done.
pop();
557 NodeInfo ni0 = done.
pop();
558 done.
push(NodeInfo(ni0.nullable | ni1.nullable,
559 PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
560 PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
566 }
while (!todo.
empty());
567 return done.
top().firstpos;
571 namespace MiniModel {
605 bool empty(
void)
const;
623 StatePool::pop(
void) {
632 StatePool::empty(
void)
const {
642 switch (PosSet::cmp(ps,n->
pos)) {
652 n->
state = n_states++;
672 Support::quicksort<int,SymbolsInc>(s,
n,o);
687 void add(
int,
int,
int);
693 TransitionBag::TransitionBag(
void) :
t(
heap),
n(0) {}
697 t[n].i_state = i_state;
698 t[n].symbol = symbol;
699 t[n].o_state = o_state;
767 int n_pos = r.e->
n_pos();
769 PosInfo* pi =
heap.
alloc<PosInfo>(n_pos);
770 for (
int i=n_pos;
i--; )
771 pi[
i].followpos = NULL;
773 PosSet* firstpos = r.e->
followpos(psm,&pi[0]);
777 for (
int i=n_pos;
i--; )
778 symbols[
i] = pi[
i].symbol;
782 for (
int i = 1;
i<n_pos-1;
i++)
783 if (symbols[
i-1] != symbols[
i])
784 symbols[n_symbols++] = symbols[
i];
788 StatePool sp(firstpos);
789 while (!sp.empty()) {
790 StateNode* sn = sp.pop();
791 for (
int i = n_symbols; i--; ) {
793 for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
794 if (pi[ps->pos].symbol == symbols[i])
795 u = PosSet::cup(psm,u,pi[ps->pos].followpos);
797 tb.add(sn->state,symbols[i],sp.state(spm,u));
804 for (StateNode*
n = sp.all;
n != NULL;
n =
n->next)
805 if (
n->pos->in(n_pos-1))
811 return DFA(0,tb.transitions(),fb.finals(),
true);