include/AD/rewrite/burs_gn2.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 improved_bottom_up_rewrite_system_generator_h
  26 #define improved_bottom_up_rewrite_system_generator_h
  27
  28 #include <AD/rewrite/burs_gen.h>  // BURS generator
  29 #include <AD/automata/sparsdfa.h> // sparse DFA compression
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //
  33 // The class New_BURS_Gen improves upon the class BURS_Gen
  34 // by compressing the index maps using a sparse DFA compression
  35 // algorithm.
  36 //
  37 //////////////////////////////////////////////////////////////////////////////
  38 class New_BURS_Gen : public BURS_Gen {
  39
  40    New_BURS_Gen(const New_BURS_Gen&);        // no copy constructor
  41    void operator = (const New_BURS_Gen&);    // no assignment
  42
  43 public:
  44
  45    ///////////////////////////////////////////////////////////////////////////
  46    // Inherit some types from superclass and make them visible.
  47    ///////////////////////////////////////////////////////////////////////////
  48    typedef BURS_Gen           Super;
  49    typedef Super::Functor     Functor;     // functor
  50    typedef Super::Variable    Variable;    // pattern variable
  51    typedef Super::NonTerminal NonTerminal; // non-terminal in automata
  52    typedef Super::Arity       Arity;       // arity of functor
  53    typedef Super::State       State;       // state in tree automata
  54    typedef Super::Cost        Cost;        // reduction cost
  55    typedef Super::Rule        Rule;        // reduction rule number
  56
  57 protected:
  58
  59    ///////////////////////////////////////////////////////////////////////////
  60    //  Internal members
  61    ///////////////////////////////////////////////////////////////////////////
  62    SparseDFA dfa_compiler;  // dfa table compression object
  63    int **    mu_index;      // mapping from functor x arity -> compressed index
  64    int       total_index_entries;     // size of all index maps together
  65    int       non_error_index_entries; // size of all non-empty index maps
  66
  67 public:
  68
  69    ///////////////////////////////////////////////////////////////////////////
  70    //  Constructors and destructor
  71    ///////////////////////////////////////////////////////////////////////////
  72             New_BURS_Gen( Mem& );
  73             New_BURS_Gen( Mem&, TreeGrammar& );
  74    virtual ~New_BURS_Gen();
  75
  76    ///////////////////////////////////////////////////////////////////////////
  77    //  Compilation and table emission methods.
  78    ///////////////////////////////////////////////////////////////////////////
  79    virtual void compile (TreeGrammar&);
  80    virtual void clear   ();
  81
  82    ///////////////////////////////////////////////////////////////////////////
  83    //  Compute the compressed index
  84    ///////////////////////////////////////////////////////////////////////////
  85    inline int    compressed_index (Functor f, Arity i) const
  86       { return mu_index[f][i]; }
  87    inline Offset compressed_offset(Functor f, Arity i) const
  88       { return dfa_compiler.state_offset(mu_index[f][i]); }
  89    virtual double compression_rate () const;
  90
  91    ///////////////////////////////////////////////////////////////////////////
  92    //  Check for completeness.
  93    ///////////////////////////////////////////////////////////////////////////
  94    virtual Bool   is_complete() const;
  95
  96    ///////////////////////////////////////////////////////////////////////////
  97    //  Methods for code generation and report generation.
  98    ///////////////////////////////////////////////////////////////////////////
  99    virtual ostream& print_report (ostream& out) const;
 100    virtual ostream& gen_compressed_index (ostream& out, const char name[]) const;
 101 };
 102
 103 #endif