include/AD/automata/treegrm.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 regular_tree_grammar_h
  26 #define regular_tree_grammar_h
  27
  28 #include <iostream>
  29 #include <new>
  30 #include <AD/generic/generic.h>
  31 #include <AD/automata/treetab.h>
  32 #include <AD/memory/mem.h>
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //  Tree grammar
  36 //////////////////////////////////////////////////////////////////////////////
  37 class TreeGrammar : public TreeTables {
  38
  39    TreeGrammar(const TreeGrammar&);       // no copy constructor
  40    void operator = (const TreeGrammar&);  // no assignment
  41
  42 public:
  43
  44    ///////////////////////////////////////////////////////////////////////////
  45    //  Inport inherited types
  46    ///////////////////////////////////////////////////////////////////////////
  47    typedef TreeTables     Super;
  48    typedef Super::Functor Functor;
  49    typedef Super::Functor Variable;
  50    typedef Super::Arity   Arity;
  51    typedef Super::State   State;
  52
  53    const int Max_arity = 256;
  54
  55    ///////////////////////////////////////////////////////////////////////////
  56    //  Definition of a tree term
  57    ///////////////////////////////////////////////////////////////////////////
  58    class TreeTerm {
  59    public:
  60       ////////////////////////////////////////////////////////////////////////
  61       //  Internal representation
  62       ////////////////////////////////////////////////////////////////////////
  63       enum { Var, Or, And, Not, Term, Set } tag;
  64       union {
  65          struct TERM { Functor f; Arity n; TreeTerm * subterms[1]; } term;
  66          Variable var;
  67          struct AND { TreeTerm * x; TreeTerm * y; } and;
  68          struct OR  { TreeTerm * x; TreeTerm * y; } or;
  69          TreeTerm     * not;
  70          class BitSet * set;
  71       };
  72
  73       ////////////////////////////////////////////////////////////////////////
  74       //  Memory management
  75       ////////////////////////////////////////////////////////////////////////
  76       inline void * operator new(size_t s, Mem& m) { return m.m_alloc(s); }
  77       inline void * operator new(size_t s, Mem& m, Variable v)
  78          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s);
  79             t->tag = Var; t->var = v; return t;
  80          }
  81       inline void * operator new(size_t s, Mem& m, TreeTerm * x, TreeTerm * y)
  82          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s);
  83             t->tag = And; t->and.x = x; t->and.y = y; return t;
  84          }
  85       inline void * operator new(size_t s, Mem& m, TreeTerm * x, TreeTerm * y, int)
  86          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s);
  87             t->tag = Or; t->or.x = x; t->or.y = y; return t;
  88          }
  89       inline void * operator new(size_t s, Mem& m, TreeTerm * x)
  90          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s);
  91             t->tag = Or; t->not = x; return t;
  92          }
  93       inline void * operator new(size_t s, Mem& m, class BitSet * set)
  94          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s);
  95             t->tag = Set; t->set = set; return t;
  96          }
  97       inline void * operator new(size_t s, Mem& m, Functor f, Arity n, TreeTerm * subterms[])
  98          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s + (n-1) * sizeof(TreeTerm*));
  99             t->tag = Term; t->term.f = f; t->term.n = n;
 100             for (int i = n - 1; i >= 0; i--) t->term.subterms[i] = subterms[i];
 101             return t;
 102          }
 103       inline void * operator new(size_t s, Mem& m, Functor f, Arity n)
 104          {  TreeTerm * t = (TreeTerm *)m.m_alloc(s + (n-1) * sizeof(TreeTerm*));
 105             t->tag = Term; t->term.f = f; t->term.n = n; return t;
 106          }
 107       inline void   operator delete(void *)        { }
 108
 109       ////////////////////////////////////////////////////////////////////////
 110       //  Equality and hashing
 111       ////////////////////////////////////////////////////////////////////////
 112       friend Bool equal(const TreeTerm *, const TreeTerm *);
 113       friend unsigned int hash(const TreeTerm *);
 114    };
 115
 116    ///////////////////////////////////////////////////////////////////////////
 117    //  Definition of a tree production
 118    ///////////////////////////////////////////////////////////////////////////
 119    struct TreeProduction {
 120       Variable   var;
 121       TreeTerm * term;
 122       TreeProduction() {}
 123       TreeProduction(Variable v, TreeTerm * t) : var(v), term(t) {}
 124    };
 125
 126 protected:
 127
 128    ///////////////////////////////////////////////////////////////////////////
 129    //  Internals
 130    ///////////////////////////////////////////////////////////////////////////
 131    Arity          * arities;                // mapping from functors to arity
 132    TreeProduction * productions;
 133    int              number_of_productions;
 134    int              number_of_functors;
 135    int              number_of_variables;
 136    Functor          maximum_functor;
 137    Functor          minimum_functor;
 138    Variable         minimum_variable;
 139    Variable         maximum_variable;
 140    int              maximum_arity;
 141
 142    void tabulate(const TreeTerm *);
 143    void tabulate_arity(const TreeTerm *);
 144
 145 private:
 146
 147    void init();  // method to initialize the class
 148
 149 public:
 150
 151    ///////////////////////////////////////////////////////////////////////////
 152    //  Constructor and destructor
 153    ///////////////////////////////////////////////////////////////////////////
 154             TreeGrammar();
 155             TreeGrammar(int n, TreeProduction []);
 156    virtual ~TreeGrammar();
 157
 158    ///////////////////////////////////////////////////////////////////////////
 159    //  Compile a set of tree productions
 160    ///////////////////////////////////////////////////////////////////////////
 161    void compile (int n, TreeProduction []);
 162
 163    ///////////////////////////////////////////////////////////////////////////
 164    //  Selectors
 165    ///////////////////////////////////////////////////////////////////////////
 166    inline TreeProduction& operator [] (int i)  { return productions[i]; }
 167    inline const TreeProduction& operator [] (int i) const { return productions[i]; }
 168    inline void     update(int i, TreeTerm * t) { productions[i].term = t; }
 169
 170    inline int      size()           const { return number_of_productions; }
 171    inline Arity    arity(Functor f) const { return arities[f]; }
 172    inline Functor  min_functor()    const { return minimum_functor; }
 173    inline Functor  max_functor()    const { return maximum_functor; }
 174    inline Variable min_variable()   const { return minimum_variable; }
 175    inline Variable max_variable()   const { return maximum_variable; }
 176    inline int      max_arity()      const { return maximum_arity; }
 177    inline int      functors()       const { return number_of_functors; }
 178    inline int      variables()      const { return number_of_variables; }
 179
 180    ///////////////////////////////////////////////////////////////////////////
 181    //  Printing
 182    ///////////////////////////////////////////////////////////////////////////
 183    std::ostream& print( std::ostream& out,
 184                    const TreeTerm * term,
 185                    const char * functor_names[],
 186                    const char * variable_names[] ) const;
 187 };
 188
 189 #endif