include/AD/automata/treegram.ph

   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 tree_grammar_h
  26 #define tree_grammar_h
  27
  28 #include <iostream>
  29 #include <new.h>
  30 #include <AD/generic/generic.h>   // generic definitions
  31 #include <AD/automata/treetab.h>  // tree grammar tables
  32 #include <AD/memory/mem.h>        // memory managers
  33 #include <AD/contain/bitset.h>    // bit sets
  34
  35 ////////////////////////////////////////////////////////////////////////////////
  36 //  Definition of a tree term.
  37 ////////////////////////////////////////////////////////////////////////////////
  38    datatype TreeTerm =
  39       wild_term                                  // wild card
  40    |  tree_term ( TreeTables::Functor,
  41                   int         = 0,
  42                   TreeTerm [] = 0)               // functor with subterms
  43    |  var_term  (TreeTables::Variable)           // a variable
  44    |  and_term  (TreeTerm, TreeTerm)             // conjunctive pattern
  45    |  or_term   (TreeTerm, TreeTerm)             // disjunction pattern
  46    |  not_term  (TreeTerm)                       // pattern complement
  47    |  set_term  (BitSet *)                       // represent a set of patterns
  48    public: {
  49
  50       //////////////////////////////////////////////////////////////////////////
  51       //  The memory management routines of redefined to take advantage of
  52       //  placement.
  53       //////////////////////////////////////////////////////////////////////////
  54       inline void * operator new (size_t n) { return new char [n]; }
  55       inline void * operator new (size_t n, Mem& mem) { return mem.m_alloc(n); }
  56       inline void   operator delete (void *) {}
  57
  58       //////////////////////////////////////////////////////////////////////////
  59       //  Function to allocate a new term.
  60       //////////////////////////////////////////////////////////////////////////
  61       friend TreeTerm new_term(Mem& mem, short int f, unsigned char n=0, TreeTerm * subterms=0);
  62
  63       //////////////////////////////////////////////////////////////////////////
  64       // Equality and hashing of tree terms
  65       //////////////////////////////////////////////////////////////////////////
  66       friend Bool equal(const TreeTerm, const TreeTerm);
  67       friend unsigned int hash(const TreeTerm);
  68    };
  69
  70 //////////////////////////////////////////////////////////////////////////////
  71 //  Tree grammar
  72 //////////////////////////////////////////////////////////////////////////////
  73 class TreeGrammar : public TreeTables {
  74
  75    TreeGrammar(const TreeGrammar&);       // no copy constructor
  76    void operator = (const TreeGrammar&);  // no assignment
  77
  78 public:
  79
  80    ///////////////////////////////////////////////////////////////////////////
  81    //  Inport inherited types
  82    ///////////////////////////////////////////////////////////////////////////
  83    typedef TreeTables         Super;
  84    typedef Super::Functor     Functor;
  85    typedef Super::Variable    Variable;
  86    typedef Super::NonTerminal NonTerminal;
  87    typedef Super::Arity       Arity;
  88    typedef Super::State       State;
  89    typedef Super::Cost        Cost;
  90
  91    enum TreeGrammar_constants { Max_arity = 256 };
  92
  93    ///////////////////////////////////////////////////////////////////////////
  94    //  Definition of a tree production
  95    ///////////////////////////////////////////////////////////////////////////
  96    struct TreeProduction {
  97       Variable var;
  98       TreeTerm term;
  99       Cost     cost;
 100       TreeProduction() {}
 101       TreeProduction(Variable v, TreeTerm t, Cost c = 0)
 102         : var(v), term(t), cost(c) {}
 103    };
 104
 105 protected:
 106
 107    ///////////////////////////////////////////////////////////////////////////
 108    //  Internals
 109    ///////////////////////////////////////////////////////////////////////////
 110    Arity          * arities;                // mapping from functors to arity
 111    TreeProduction * productions;            // tree productions
 112    int              number_of_productions;  // production count
 113    int              number_of_functors;     // total number of functors
 114    int              number_of_variables;    // total number of non-terminals
 115    Functor          maximum_functor;        // range of functors
 116    Functor          minimum_functor;
 117    Variable         minimum_variable;       // range of non-terminals
 118    Variable         maximum_variable;
 119    int              maximum_arity;          // maximum arity of all functors
 120    const char **    functor_names;          // names of functors
 121    const char **    variable_names;         // names of non-terminals
 122
 123 private:
 124
 125    void tabulate       (const TreeTerm);  // method to tabulate the ranges
 126    void tabulate_arity (const TreeTerm);  // method to tabulate the arities
 127    void init();                           // method to initialize the class
 128
 129 public:
 130
 131    ///////////////////////////////////////////////////////////////////////////
 132    //  Constructors and destructor
 133    ///////////////////////////////////////////////////////////////////////////
 134             TreeGrammar();
 135             TreeGrammar(int n, TreeProduction [], const char *[], const char *[] = 0);
 136    virtual ~TreeGrammar();
 137
 138    ///////////////////////////////////////////////////////////////////////////
 139    //  Compile a set of tree productions
 140    ///////////////////////////////////////////////////////////////////////////
 141    void compile (int n, TreeProduction [],
 142                  const char * functor_names[] = 0,
 143                  const char * variable_names[] = 0,
 144                  Functor min_f = 32767, Functor max_f = 0,
 145                  Variable min_v = 32767, Variable max_v = 0
 146                 );
 147
 148    ///////////////////////////////////////////////////////////////////////////
 149    //  Indexing
 150    ///////////////////////////////////////////////////////////////////////////
 151    inline const TreeProduction& operator [] (int i) const { return productions[i]; }
 152    inline       TreeProduction& operator [] (int i)       { return productions[i]; }
 153
 154    ///////////////////////////////////////////////////////////////////////////
 155    //  Mutators
 156    ///////////////////////////////////////////////////////////////////////////
 157    inline void  update(int i, TreeTerm t) { productions[i].term = t; }
 158    void         normalise();
 159
 160    ///////////////////////////////////////////////////////////////////////////
 161    //  Selectors
 162    ///////////////////////////////////////////////////////////////////////////
 163    inline int      size()           const { return number_of_productions; }
 164    inline Arity    arity(Functor f) const { return arities[f]; }
 165    inline Functor  min_functor()    const { return minimum_functor; }
 166    inline Functor  max_functor()    const { return maximum_functor; }
 167    inline Variable min_variable()   const { return minimum_variable; }
 168    inline Variable max_variable()   const { return maximum_variable; }
 169    inline int      max_arity()      const { return maximum_arity; }
 170    inline int      functors()       const { return number_of_functors; }
 171    inline int      variables()      const { return number_of_variables; }
 172
 173    ///////////////////////////////////////////////////////////////////////////
 174    //  Printing methods
 175    ///////////////////////////////////////////////////////////////////////////
 176    const char * functor_name  (Functor)  const;
 177    const char * variable_name (Variable) const;
 178    std::ostream& print_functor  (std::ostream&, Functor)               const;
 179    std::ostream& print_variable (std::ostream&, Variable)              const;
 180    std::ostream& print          (std::ostream&, const TreeTerm)        const;
 181    std::ostream& print          (std::ostream&, const TreeProduction&) const;
 182    std::ostream& print          (std::ostream&, const TreeGrammar&)    const;
 183    friend std::ostream& operator << (std::ostream&, const TreeGrammar&);
 184
 185    ///////////////////////////////////////////////////////////////////////////
 186    //  Iterator macros
 187    //  These can be used for to make code more readable.
 188    ///////////////////////////////////////////////////////////////////////////
 189 #ifdef TreeGrammar_Iterators
 190 #  define foreach_functor(f,G) \
 191       for(TreeGrammar::Functor f = (G).min_functor(); f <= (G).max_functor(); f++)
 192 #  define foreach_unit_functor(f,G) \
 193       foreach_functor(f,G) if ((G).arity(f) == 0)
 194 #  define foreach_non_unit_functor(f,G) \
 195       foreach_functor(f,G) if ((G).arity(f) > 0)
 196 #  define foreach_arity(i,f,G) \
 197       for(int i = (G).arity(f); i >= 0; i--)
 198 #  define foreach_variable(v,G) \
 199       for(TreeGrammar::Variable v = (G).min_variable(); v <= (G).max_variable(); v++)
 200 #  define foreach_production(i,G) \
 201       for(int i = 0; i < (G).size(); i++)
 202 #endif
 203 };
 204
 205 #endif