lib-src/automata/compdfa.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 <string.h>
  26 #include <AD/automata/compdfa.h>
  27 #include <AD/automata/gentable.h>
  28
  29 //////////////////////////////////////////////////////////////////////////
  30 // Make hidden types visible
  31 //////////////////////////////////////////////////////////////////////////
  32 typedef CompressedDFA::Symbol Symbol;
  33 typedef CompressedDFA::State  State;
  34
  35 //////////////////////////////////////////////////////////////////////////
  36 //  Constructor and destructor
  37 //////////////////////////////////////////////////////////////////////////
  38 CompressedDFA::CompressedDFA() : base(0), check(0), next(0) {}
  39 CompressedDFA::~CompressedDFA()
  40 {  delete [] base; delete [] check; delete [] next; }
  41
  42 //////////////////////////////////////////////////////////////////////////
  43 // Create an initial compressed dfa table
  44 //////////////////////////////////////////////////////////////////////////
  45 void CompressedDFA::create_tables(int size, int states, Symbol min, Symbol max)
  46 {  min_symbol = min;
  47    max_symbol = max;
  48    table_size = size;
  49    number_of_states = states;
  50    max_check = 0;
  51    max_state = 0;
  52    base  = new Offset [ number_of_states ];
  53    check = new State  [ table_size ];
  54    next  = new State  [ table_size ];
  55
  56    int i;
  57    for (i = table_size - 1; i >= 0; i--)
  58       check[i] = next[i] = error_state;
  59    for (i = number_of_states - 1; i >= 0; i--)
  60       base[i] = 0;
  61 }
  62
  63 //////////////////////////////////////////////////////////////////////////
  64 // Expand the check/next tables
  65 //////////////////////////////////////////////////////////////////////////
  66 void CompressedDFA::grow_tables(int increment)
  67 {  State * new_check = new State [ table_size + increment ];
  68    State * new_next  = new State [ table_size + increment ];
  69    memcpy(new_check,check,table_size * sizeof(State));
  70    memcpy(new_next ,next ,table_size * sizeof(State));
  71    delete [] check;
  72    delete [] next;
  73    check = new_check;
  74    next  = new_next;
  75    for (register int i = table_size + increment - 1; i >= table_size; i--)
  76       check[i] = next[i] = error_state;
  77    table_size += increment;
  78 }
  79
  80 //////////////////////////////////////////////////////////////////////////
  81 // Expand the number of states
  82 //////////////////////////////////////////////////////////////////////////
  83 void CompressedDFA::grow_states(int increment)
  84 {  Offset * new_base = new Offset [ number_of_states+increment ];
  85    memcpy(new_base,base,number_of_states * sizeof(Offset));
  86    for (int i = number_of_states; i < number_of_states + increment; i++)
  87       new_base[i] = 0;
  88    delete [] base;
  89    base = new_base;
  90    number_of_states += increment;
  91 }
  92
  93
  94 ostream& CompressedDFA::gen_state_table
  95     ( ostream& out, const char name[], const char table[],
  96       const State s[], int size, const char * mytype) const
  97 {  TablePrinter pr;
  98    if (mytype == 0) mytype = "static const DFATables::State ";
  99    pr.print(out, (const char *)s, size, sizeof(State),
 100             mytype, name, table, true);
 101    return out;
 102 }
 103
 104 ostream& CompressedDFA::gen_offset_table
 105     ( ostream& out, const char name[], const char table[],
 106       const Offset s[], int size) const
 107 {  TablePrinter pr;
 108    pr.print(out, (const char *)s, size, sizeof(Offset),
 109             "static const DFATables::Offset ", name, table);
 110    return out;
 111 }
 112
 113 ostream& CompressedDFA::gen_check_next_tables
 114    (ostream& out, const char name[], const char * mytype) const
 115 {
 116    gen_state_table(out,name,"check",check,max_check + 1,mytype);
 117    gen_state_table(out,name,"next",next,max_check + 1,mytype);
 118    return out;
 119 }
 120
 121 ostream& CompressedDFA::gen_code (ostream& out, const char name[]) const
 122 {
 123    gen_offset_table(out,name,"base",base, max_state + 1);
 124    CompressedDFA::gen_check_next_tables(out, name);
 125    return out;
 126 }