include/AD/automata/nfa_node.old.h

   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 #ifndef nondeterministic_finite_automata_nodes_h
  26 #define nondeterministic_finite_automata_nodes_h
  27
  28 #include <stdlib.h>
  29 #include <AD/automata/dfatable.h>  // DFA tables internals
  30 #include <AD/contain/bitset.h>
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  Opaque definitions
  34 //////////////////////////////////////////////////////////////////////////////
  35 class MemPool;
  36 class NFA_Delta;
  37
  38 //////////////////////////////////////////////////////////////////////////////
  39 //  Base class for an NFA node
  40 //////////////////////////////////////////////////////////////////////////////
  41 class NFA_Node {
  42    NFA_Node(const NFA_Node&);          // no copy constructor
  43    void operator = (const NFA_Node&);  // no assignment
  44 public:
  45    typedef DFATables::Symbol Symbol;
  46    typedef DFATables::State  State;
  47    typedef DFATables::Rule   Rule;
  48 protected:
  49    enum { NoDeltaBit = -1 };
  50    BitSet   * closure_set;  // epsilon_closure
  51    NFA_Node * out;          // out transition
  52    NFA_Node();
  53    virtual ~NFA_Node();
  54 public:
  55    inline void set_out(NFA_Node * n) { out = n; }
  56
  57    virtual int closure (BitSet *) = 0;
  58    virtual BitSet * epsilon_closure
  59      (MemPool&    mem_pool,
  60       size_t      number_of_states,
  61       size_t      number_of_rules,
  62       NFA_Delta * state_table[]
  63      ) = 0;
  64
  65    ///////////////////////////////////////////////////////////////////////////
  66    //  Thin the accept states.  I.e. select the first accept state
  67    //  and eliminate the rest
  68    ///////////////////////////////////////////////////////////////////////////
  69    inline static Rule accept_thinning
  70       (register BitSet * set, register size_t rules)
  71    {  for (register int i = 0; i < rules; i++)
  72       {  if ((*set)[i]) {
  73             //for (register int j = i+1; j < rules; j++) set->remove(j);
  74             return i+1;
  75          }
  76       }
  77       return 0;
  78    }
  79 };
  80
  81 //////////////////////////////////////////////////////////////////////////////
  82 //  Base class for an accept NFA node
  83 //////////////////////////////////////////////////////////////////////////////
  84 class NFA_Accept : public NFA_Node {
  85    NFA_Accept(const NFA_Accept&);        // no copy constructor
  86    void operator = (const NFA_Accept&);  // no assignment
  87 protected:
  88    State state;  // nfa state
  89    virtual int closure (BitSet *);
  90    NFA_Accept();
  91   ~NFA_Accept();
  92 public:
  93    virtual BitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
  94    friend NFA_Accept * mkaccept(MemPool&, State);
  95 };
  96
  97 //////////////////////////////////////////////////////////////////////////////
  98 // Epsilon node
  99 //////////////////////////////////////////////////////////////////////////////
 100 class NFA_Epsilon : public NFA_Node {
 101    NFA_Epsilon(const NFA_Epsilon&);       // no copy constructor
 102    void operator = (const NFA_Epsilon&);  // no assignment
 103 private:
 104    virtual int closure (BitSet *);
 105    NFA_Epsilon();
 106   ~NFA_Epsilon();
 107 public:
 108    virtual BitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 109    friend NFA_Epsilon * mkepsilon(MemPool&, NFA_Node *);
 110 };
 111
 112 //////////////////////////////////////////////////////////////////////////////
 113 //  Disjunction
 114 //////////////////////////////////////////////////////////////////////////////
 115 class NFA_Or : public NFA_Node {
 116    NFA_Or(const NFA_Or&);            // no copy constructor
 117    void operator = (const NFA_Or&);  // no assignment
 118 private:
 119    NFA_Node * out2;  // the second out transition
 120    virtual int closure (BitSet *);
 121    NFA_Or();
 122   ~NFA_Or();
 123 public:
 124    inline void set_out2(NFA_Node * n) { out2 = n; }
 125    virtual BitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 126    friend NFA_Or * mkor(MemPool&, NFA_Node *, NFA_Node *);
 127 };
 128
 129 //////////////////////////////////////////////////////////////////////////////
 130 //  Delta NFA node
 131 //////////////////////////////////////////////////////////////////////////////
 132 class NFA_Delta : public NFA_Accept {
 133    NFA_Delta(const NFA_Delta&);         // no copy constructor
 134    void operator = (const NFA_Delta&);  // no assignment
 135 private:
 136    Symbol     c;         // out transition character
 137    int        delta_bit; // state bit of delta_set if delta_set is
 138                          // a singleton or empty.
 139    BitSet   * delta_set; // set of out transition states(after closure)
 140    virtual int closure (BitSet *);
 141    NFA_Delta();
 142   ~NFA_Delta();
 143 public:
 144    virtual BitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 145    inline BitSet * delta  () const { return delta_set; }
 146    inline void     add_delta (BitSet * set) const
 147       { if (delta_bit >= 0) set->add(delta_bit);
 148         else set->Union(*delta_set);
 149       }
 150    inline Symbol   symbol () const { return c; }
 151    friend NFA_Delta * mkdelta(MemPool&, State, Symbol, NFA_Node *);
 152 };
 153
 154 #endif