lib-src/automata/nfa_node.old.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <AD/automata/nfa_node.h>
  26 #include <AD/memory/mempool.h>
  27 #include <AD/contain/bitset.h>
  28
  29 //////////////////////////////////////////////////////////////////////////////
  30 //  Import some type definitions
  31 //////////////////////////////////////////////////////////////////////////////
  32 typedef DFATables::State  State;
  33 typedef DFATables::Rule   Rule;
  34 typedef DFATables::Symbol Symbol;
  35
  36 //////////////////////////////////////////////////////////////////////////////
  37 //  Memory allocation routine
  38 //////////////////////////////////////////////////////////////////////////////
  39 //inline void * NFA_Node::operator new(size_t n, MemPool& mem) { return mem[n]; }
  40
  41 //////////////////////////////////////////////////////////////////////////////
  42 //  Constructors and destructors
  43 //////////////////////////////////////////////////////////////////////////////
  44 inline NFA_Node   :: NFA_Node() : closure_set(0) {}
  45 inline NFA_Delta  :: NFA_Delta() : delta_bit(NoDeltaBit) {}
  46 inline NFA_Accept :: NFA_Accept() {}
  47 inline NFA_Or     :: NFA_Or() {}
  48 inline NFA_Epsilon:: NFA_Epsilon() {}
  49 NFA_Node   ::~NFA_Node() {}
  50 NFA_Accept ::~NFA_Accept() {}
  51 NFA_Or     ::~NFA_Or() {}
  52 NFA_Delta  ::~NFA_Delta() {}
  53 NFA_Epsilon::~NFA_Epsilon() {}
  54
  55 //////////////////////////////////////////////////////////////////////////////
  56 //  Functions to construct NFA nodes
  57 //  (Note: Placement new does not work with constructor with arguments
  58 //   in g++ 2.5.8)
  59 //////////////////////////////////////////////////////////////////////////////
  60 NFA_Accept * mkaccept(MemPool& mem, State s)
  61    {  NFA_Accept * n = new (mem) NFA_Accept;
  62       n->state = s;
  63       return n;
  64    }
  65 NFA_Or * mkor(MemPool& mem, NFA_Node * x, NFA_Node * y)
  66    {  NFA_Or * n = new (mem) NFA_Or;
  67       n->out2 = x;
  68       n->out  = y;
  69       return n;
  70    }
  71 NFA_Delta * mkdelta(MemPool& mem, State s, Symbol c, NFA_Node * out)
  72    {  NFA_Delta * n = new (mem) NFA_Delta;
  73       n->state = s;
  74       n->c     = c;
  75       n->out   = out;
  76       return n;
  77    }
  78 NFA_Epsilon * mkepsilon(MemPool& mem, NFA_Node * out)
  79    {  NFA_Epsilon * n = new (mem) NFA_Epsilon;
  80       n->out = out;
  81       return n;
  82    }
  83
  84 //////////////////////////////////////////////////////////////////////////////
  85 //  Compute the epsilon closure from one state
  86 //  Returns the state if the closure is guaranteed to be just a singleton.
  87 //////////////////////////////////////////////////////////////////////////////
  88 int NFA_Accept ::closure(BitSet * set) { set->add(state); return state; }
  89 int NFA_Delta  ::closure(BitSet * set) { set->add(state); return state; }
  90 int NFA_Epsilon::closure(BitSet * set) { out->closure(set); return NoDeltaBit; }
  91 int NFA_Or::closure(BitSet * set)
  92    { out->closure(set); out2->closure(set); return NoDeltaBit; }
  93
  94 //////////////////////////////////////////////////////////////////////////////
  95 //  Compute the epsilon closure for all states
  96 //////////////////////////////////////////////////////////////////////////////
  97 BitSet * NFA_Accept::epsilon_closure
  98    (MemPool& mem, size_t N, size_t rules, NFA_Delta * A[])
  99 {  if (closure_set) return closure_set;
 100    closure_set = new(mem,N) BitSet;
 101    closure_set->add(state);            // add accept state
 102    return closure_set;
 103 }
 104
 105 BitSet * NFA_Epsilon::epsilon_closure
 106    (MemPool& mem, size_t N, size_t rules, NFA_Delta * A[])
 107 {  if (closure_set) return closure_set;
 108    return closure_set = out->epsilon_closure(mem,N,rules,A);
 109 }
 110
 111 BitSet * NFA_Delta::epsilon_closure
 112    (MemPool& mem, size_t N, size_t rules, NFA_Delta * A[])
 113 {  if (closure_set) return closure_set;
 114    A[state] = this;
 115    closure_set = new(mem,N) BitSet;
 116    closure_set->add(state);
 117    delta_bit = out->closure(delta_set = new(mem,N) BitSet);
 118    out->epsilon_closure(mem, N, rules, A);
 119    return closure_set;
 120 }
 121
 122 BitSet * NFA_Or::epsilon_closure
 123    (MemPool& mem, size_t N, size_t rules, NFA_Delta * A[])
 124 {  if (closure_set) return closure_set;
 125
 126    closure_set = new(mem,N) BitSet;
 127    out->closure(closure_set);
 128    out2->closure(closure_set);
 129
 130    accept_thinning(closure_set,rules);
 131
 132    out->epsilon_closure(mem, N, rules, A);
 133    out2->epsilon_closure(mem, N, rules, A);
 134
 135    return closure_set;
 136 }