include/AD/automata/nfa_node.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/fbitset.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    FastBitSet * 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 void closure (FastBitSet *) = 0;
  58    virtual FastBitSet * 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 FastBitSet * set, register size_t rules)
  71    {  int first_bit = set->first_bit();
  72       return first_bit < (int)rules ? first_bit + 1 : 0;
  73    }
  74 };
  75
  76 //////////////////////////////////////////////////////////////////////////////
  77 //  Base class for an accept NFA node
  78 //////////////////////////////////////////////////////////////////////////////
  79 class NFA_Accept : public NFA_Node {
  80    NFA_Accept(const NFA_Accept&);        // no copy constructor
  81    void operator = (const NFA_Accept&);  // no assignment
  82 protected:
  83    State state;  // nfa state
  84    virtual void closure (FastBitSet *);
  85    NFA_Accept();
  86   ~NFA_Accept();
  87 public:
  88    virtual FastBitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
  89    friend NFA_Accept * mkaccept(MemPool&, State);
  90 };
  91
  92 //////////////////////////////////////////////////////////////////////////////
  93 // Epsilon node
  94 //////////////////////////////////////////////////////////////////////////////
  95 class NFA_Epsilon : public NFA_Node {
  96    NFA_Epsilon(const NFA_Epsilon&);       // no copy constructor
  97    void operator = (const NFA_Epsilon&);  // no assignment
  98 private:
  99    virtual void closure (FastBitSet *);
 100    NFA_Epsilon();
 101   ~NFA_Epsilon();
 102 public:
 103    virtual FastBitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 104    friend NFA_Epsilon * mkepsilon(MemPool&, NFA_Node *);
 105 };
 106
 107 //////////////////////////////////////////////////////////////////////////////
 108 //  Disjunction
 109 //////////////////////////////////////////////////////////////////////////////
 110 class NFA_Or : public NFA_Node {
 111    NFA_Or(const NFA_Or&);            // no copy constructor
 112    void operator = (const NFA_Or&);  // no assignment
 113 private:
 114    NFA_Node * out2;  // the second out transition
 115    virtual void closure (FastBitSet *);
 116    NFA_Or();
 117   ~NFA_Or();
 118 public:
 119    inline void set_out2(NFA_Node * n) { out2 = n; }
 120    virtual FastBitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 121    friend NFA_Or * mkor(MemPool&, NFA_Node *, NFA_Node *);
 122 };
 123
 124 //////////////////////////////////////////////////////////////////////////////
 125 //  Delta NFA node
 126 //////////////////////////////////////////////////////////////////////////////
 127 class NFA_Delta : public NFA_Accept {
 128    NFA_Delta(const NFA_Delta&);         // no copy constructor
 129    void operator = (const NFA_Delta&);  // no assignment
 130 private:
 131    Symbol       c;         // out transition character
 132    FastBitSet * delta_set; // set of out transition states(after closure)
 133    virtual void closure (FastBitSet *);
 134    NFA_Delta();
 135   ~NFA_Delta();
 136 public:
 137    virtual FastBitSet * epsilon_closure (MemPool&, size_t, size_t, NFA_Delta * []);
 138    inline const FastBitSet * delta  () const { return delta_set; }
 139    inline void  add_delta (FastBitSet * set) const
 140       { set->Union(*delta_set); }
 141    inline Symbol   symbol () const { return c; }
 142    friend NFA_Delta * mkdelta(MemPool&, State, Symbol, NFA_Node *);
 143 };
 144
 145 #endif