lib-src/automata/sparsdfa.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/sparsdfa.h>
  26 #include <AD/contain/varstack.h>
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 // Since optimal compression of the sparse table is equivalent to the
  30 // problem of prune trie space minimization and is
  31 // NP-complete(\cite{NP}, page 226), we'll use a simple first-fit
  32 // strategy instead.
  33 //
  34 // The first-fit compression algorithm treats singleton states
  35 // (i.e. states with only one out transition) specially.  Singleton states
  36 // transitions are saved on the stack |singletons| and are processed at
  37 // the end of the run to fill up the remaining gaps.
  38 //////////////////////////////////////////////////////////////////////////////
  39
  40 ////////////////////////////////////////////////////////////////////////
  41 //  Make hidden types visible
  42 ////////////////////////////////////////////////////////////////////////
  43 typedef SparseDFA::Symbol Symbol;
  44 typedef SparseDFA::State  State;
  45
  46 //////////////////////////////////////////////////////////////////////////
  47 //  Internally, class SparseDFA contains a stack of states with
  48 //  single non-error transition.  These types of states are treated
  49 //  as a special case to during table compression.
  50 //////////////////////////////////////////////////////////////////////////
  51 struct SingleTrans {
  52    State state; Symbol c; State dest;
  53    SingleTrans() {}
  54    SingleTrans(State s, Symbol a, State d) : state(s), c(a), dest(d) {}
  55 };
  56
  57 //////////////////////////////////////////////////////////////////////////
  58 // Stack of states with only 1 out transition
  59 //////////////////////////////////////////////////////////////////////////
  60 struct SparseDFA_Impl {
  61    VarStack <SingleTrans> singletons;
  62 };
  63
  64 ////////////////////////////////////////////////////////////////////////
  65 //  Constructor and destructor
  66 ////////////////////////////////////////////////////////////////////////
  67 SparseDFA:: SparseDFA () : impl(0) {}
  68 SparseDFA::~SparseDFA () { delete impl; }
  69
  70 ////////////////////////////////////////////////////////////////////////
  71 //  Start generating tables; just clear the stack that memorize
  72 //  singleton transitions
  73 ////////////////////////////////////////////////////////////////////////
  74 void SparseDFA::start()
  75 { delete impl; impl = new SparseDFA_Impl; impl->singletons.clear();
  76   offset_base = 0;
  77 }
  78
  79 ////////////////////////////////////////////////////////////////////////
  80 //  Finish generating tables.  We'll go thru the singletons transitions
  81 //  emit them at this point
  82 ////////////////////////////////////////////////////////////////////////
  83 void SparseDFA::finish()
  84 {  //
  85    // Fit all singleton transitions into the gaps.  O(n) complexity.
  86    //
  87    register int offset, limit;
  88    VarStack <SingleTrans>& singletons = impl->singletons;
  89    for (offset = - min_symbol; ! singletons.is_empty(); ) {
  90       SingleTrans& t = singletons.pop();
  91       for (;;) {
  92          for (limit = table_size - max_symbol - 1; offset < limit; offset++) {
  93             if (check[offset + t.c] == error_state) {
  94                base[t.state]       = offset;
  95                check[offset + t.c] = t.state;
  96                next[offset + t.c]  = t.dest;
  97                if (offset + max_symbol > max_check)
  98                   max_check = offset + max_symbol;
  99                goto next_symbol;
 100             }
 101          }
 102          //
 103          // All available gaps are filled.  We'll have to increase
 104          // the table size to fit in the rest.  We'll have a perfect fit.
 105          //
 106          grow_tables( singletons.size() + max_symbol - min_symbol + 1);
 107          limit = table_size;
 108          max_check = table_size - 1;
 109       }
 110    next_symbol: ;
 111    }
 112
 113    /////////////////////////////////////////////////////////////////////
 114    // Clean up
 115    /////////////////////////////////////////////////////////////////////
 116    delete impl; impl = 0;
 117 }
 118
 119 ////////////////////////////////////////////////////////////////////////
 120 //  Add a new state to the automaton
 121 ////////////////////////////////////////////////////////////////////////
 122 void SparseDFA::add_state
 123    ( State s, int fan_out, const Symbol symbols[], const State delta[] )
 124 {  register int i, offset;
 125
 126    //
 127    // Increase the size of the state to base offset table if necessary.
 128    //
 129    if (s > max_state) max_state = s;
 130    if (s - error_state + 1 > number_of_states)
 131    {  grow_states(states() * 3 / 2 + 8);
 132    }
 133
 134    //
 135    // Singletons are saved onto a stack and processed at the end of the run.
 136    //
 137    if (fan_out == 0) return;
 138    if (fan_out == 1) {
 139       impl->singletons.push(SingleTrans(s,symbols[0],delta[0]));
 140       return;
 141    }
 142
 143    //
 144    // Now fit in the rest using a simple first fit strategy.  Worst case
 145    // complexity is O(n^2).  However, since the transitions are sparse
 146    // we expect the average complexity to be better.
 147    //
 148    {  register int i, limit;
 149       for (i = offset_base, limit = table_size; i < limit; i++)
 150       {  if (check[i] == error_state) break;  }
 151       offset_base = i;
 152    }
 153
 154    for (offset = - min_symbol + offset_base;; ) {
 155       register int limit = table_size - max_symbol - 1;
 156       if (limit <= offset) grow_tables(table_size * 3 / 2 + offset - limit);
 157
 158       //
 159       // Use linear search on the tables
 160       //
 161
 162       for ( ; offset < limit; offset++) {
 163          for (i = fan_out - 1; i >= 0; i--)
 164             if (check[offset + symbols[i]] != error_state) goto try_again;
 165          //
 166          // Found the right spot
 167          //
 168          for (i = fan_out - 1; i >= 0; i--) {
 169             check[offset + symbols[i]] = s;
 170             next[offset + symbols[i]]  = delta[i];
 171          }
 172          base[s] = offset;
 173          if (offset + max_symbol > max_check)
 174             max_check = offset + max_symbol;
 175          return;
 176       try_again: ;
 177       }
 178    }
 179 }