lib-src/rewrite/burs_gn2.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/rewrite/burs_gn2.h>  // BURS generator
  26
  27 //////////////////////////////////////////////////////////////////////////////
  28 //
  29 // The class New_BURS_Gen improves upon the class BURS_Gen
  30 // by compressing the index maps using a sparse DFA compression
  31 // algorithm.
  32 //
  33 //////////////////////////////////////////////////////////////////////////////
  34
  35 //////////////////////////////////////////////////////////////////////////////
  36 //  Constructors and destructor
  37 //////////////////////////////////////////////////////////////////////////////
  38 New_BURS_Gen:: New_BURS_Gen( Mem& m) : BURS_Gen(m) {}
  39 New_BURS_Gen:: New_BURS_Gen( Mem& m, TreeGrammar& g) : BURS_Gen(m,g) {}
  40 New_BURS_Gen::~New_BURS_Gen() {}
  41
  42 //////////////////////////////////////////////////////////////////////////////
  43 //  Compilation and table emission methods.
  44 //////////////////////////////////////////////////////////////////////////////
  45 void New_BURS_Gen::compile (TreeGrammar& g)
  46 {
  47    ///////////////////////////////////////////////////////////////////////////
  48    //  Generate the tree automaton tables.
  49    ///////////////////////////////////////////////////////////////////////////
  50    Super::compile(g);
  51
  52    ///////////////////////////////////////////////////////////////////////////
  53    //  Compress the index maps.
  54    ///////////////////////////////////////////////////////////////////////////
  55    int index = 1;
  56    mu_index = (int**)mem.c_alloc(sizeof(int) * (g.functors()+1));
  57
  58    ///////////////////////////////////////////////////////////////////////////
  59    //  Temporary buffers
  60    ///////////////////////////////////////////////////////////////////////////
  61    SparseDFA::State * delta =
  62       (SparseDFA::State *)mem.c_alloc
  63          (sizeof(SparseDFA::State) * number_of_states());
  64    SparseDFA::Symbol * symbols =
  65       (SparseDFA::Symbol *)mem.c_alloc
  66          (sizeof(SparseDFA::Symbol) * number_of_states());
  67
  68    ///////////////////////////////////////////////////////////////////////////
  69    //  Start the compression process
  70    ///////////////////////////////////////////////////////////////////////////
  71    dfa_compiler.create_tables(64,8,0,number_of_states()-1);
  72    dfa_compiler.start();
  73
  74    ///////////////////////////////////////////////////////////////////////////
  75    //  Compress all index maps.
  76    ///////////////////////////////////////////////////////////////////////////
  77    total_index_entries = 0;
  78    for (Functor f = g.min_functor(); f <= g.max_functor(); f++) {
  79       mu_index[f] = (int*)mem.c_alloc(sizeof(int) * g.arity(f));
  80       for (int i = 0; i < g.arity(f); i++) {
  81          int fan_out = 0;
  82          for (int s = number_of_states() - 1; s >= 0; s--) {
  83             if (index_map(f,i,s) != 0) {
  84                symbols[fan_out] = s;
  85                delta  [fan_out] = index_map(f,i,s);
  86                fan_out++;
  87             }
  88          }
  89          dfa_compiler.add_state(index, fan_out, symbols, delta);
  90          mu_index[f][i] = index++;
  91          total_index_entries += number_of_states();
  92       }
  93    }
  94    ///////////////////////////////////////////////////////////////////////////
  95    //  Finish the compression.
  96    ///////////////////////////////////////////////////////////////////////////
  97    dfa_compiler.finish();
  98    non_error_index_entries = dfa_compiler.size();
  99 }
 100
 101 void New_BURS_Gen::clear () { Super::clear(); }
 102
 103 //////////////////////////////////////////////////////////////////////////////
 104 //  Check for completeness.
 105 //////////////////////////////////////////////////////////////////////////////
 106 Bool New_BURS_Gen::is_complete() const { return Super::is_complete(); }
 107
 108 //////////////////////////////////////////////////////////////////////////////
 109 //  Method to compute the compression rate.
 110 //  The compressed form in the base/check/next format.
 111 //////////////////////////////////////////////////////////////////////////////
 112 double New_BURS_Gen::compression_rate() const
 113 {
 114    double original = total_index_entries;
 115    double now      = dfa_compiler.size() * 2 + dfa_compiler.states();
 116
 117    return (original - now) / now;
 118 }
 119
 120 //////////////////////////////////////////////////////////////////////////////
 121 //  Methods for code generation and report generation.
 122 //////////////////////////////////////////////////////////////////////////////
 123 std::ostream& New_BURS_Gen::print_report (std::ostream& f) const
 124 {  Super::print_report(f);
 125
 126    // Print other statistics
 127    f << "Index compression statistics:\n"
 128      << "   Uncompressed index entries = " << total_index_entries     << '\n'
 129      << "   Non-empty index entries    = " << non_error_index_entries << '\n'
 130      << "   Compressed table entries   = "
 131         << (dfa_compiler.size() * 2 + dfa_compiler.states()) << '\n'
 132      << "   Compression rate           = "
 133         << int(compression_rate() * 100.0 + .5) << "%\n"
 134      ;
 135
 136    return f;
 137 }
 138
 139 std::ostream& New_BURS_Gen::gen_compressed_index
 140    (std::ostream& out, const char name[]) const
 141 {  return dfa_compiler.gen_code(out, name); }