lib-src/automata/treegram.pcc

   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 <assert.h>
  27 #include <AD/automata/treegram.ph>
  28 #include <AD/contain/bitset.h>
  29
  30 //////////////////////////////////////////////////////////////////////////////
  31 //  Make hidden types visible
  32 //////////////////////////////////////////////////////////////////////////////
  33 typedef TreeGrammar::TreeProduction TreeProduction;
  34 typedef TreeGrammar::Functor        Functor;
  35 typedef TreeGrammar::Arity          Arity;
  36
  37 //////////////////////////////////////////////////////////////////////////////
  38 //  Function to allocate a new term
  39 //////////////////////////////////////////////////////////////////////////////
  40 TreeTerm new_term(Mem& mem, short int f, unsigned char n, TreeTerm * subterms)
  41 {  TreeTerm * S = n > 0 ? (TreeTerm*)mem.c_alloc(sizeof(TreeTerm) * n) : 0;
  42    if (subterms) for (int i = n - 1; i >= 0; i--) S[i] = subterms[i];
  43    return tree_term'(mem)(f,n,S);
  44 }
  45
  46 //////////////////////////////////////////////////////////////////////////////
  47 //  Method to initialize an instance
  48 //////////////////////////////////////////////////////////////////////////////
  49 void TreeGrammar::init()
  50    {  productions           = 0;
  51       arities               = 0;
  52       minimum_functor       = maximum_functor =
  53       minimum_variable      = maximum_variable = 0;
  54       maximum_arity         = 0;
  55       number_of_productions = 0;
  56       number_of_variables   = 0;
  57       number_of_functors    = 0;
  58       functor_names         = 0;
  59       variable_names        = 0;
  60    }
  61
  62 //////////////////////////////////////////////////////////////////////////////
  63 //  Constructors and destructor
  64 //////////////////////////////////////////////////////////////////////////////
  65 TreeGrammar::TreeGrammar() { init(); }
  66 TreeGrammar::TreeGrammar(int n, TreeProduction P[], const char * f[], const char * v[])
  67    { init(); compile(n,P,f,v); }
  68 TreeGrammar::~TreeGrammar()
  69 {  delete [] productions;
  70    delete [] arities;
  71 }
  72
  73 //////////////////////////////////////////////////////////////////////////////
  74 // Method to compile a set of tree productions
  75 //////////////////////////////////////////////////////////////////////////////
  76 void TreeGrammar::compile
  77    ( int                  n,       // number of productions
  78      TreeProduction       P[],     // an array of tree productions
  79      const char *         f_names[], // names of functors
  80      const char *         v_names[], // names of variables(non-terminals)
  81      Functor              min_f,   // user supplied minimal functor encoding
  82      Functor              max_f,   // user supplied maximal functor encoding
  83      Variable             min_v,   // user supplied minimal variable encoding
  84      Variable             max_v    // user supplied maximal variable encoding
  85    )
  86 {
  87    ///////////////////////////////////////////////////////////////////////////
  88    //  (1)  Allocate the productions array and initialize various members.
  89    ///////////////////////////////////////////////////////////////////////////
  90    productions           = new TreeProduction [n];
  91    minimum_functor       = min_f;
  92    maximum_functor       = max_f;
  93    minimum_variable      = min_v;
  94    maximum_variable      = max_v;
  95    maximum_arity         = 0;
  96    number_of_productions = n;
  97    functor_names         = f_names;
  98    variable_names        = v_names;
  99    memcpy(productions,P,n * sizeof(TreeProduction));
 100
 101    ///////////////////////////////////////////////////////////////////////////
 102    //  (2) Compute the ranges of non-terminals and functors.
 103    ///////////////////////////////////////////////////////////////////////////
 104    int i;
 105    for (i = 0; i < n; i++) {
 106       Variable v = P[i].var;
 107       if (v < minimum_variable) minimum_variable = v;
 108       if (v > maximum_variable) maximum_variable = v;
 109       tabulate(P[i].term);
 110    }
 111    if (minimum_functor  > maximum_functor ) minimum_functor  = maximum_functor = 0;
 112    if (minimum_variable > maximum_variable) minimum_variable = maximum_variable = 0;
 113    number_of_variables = maximum_variable - minimum_variable + 1;
 114    number_of_functors  = maximum_functor - minimum_functor + 1;
 115
 116    ///////////////////////////////////////////////////////////////////////////
 117    //  (3) Compute the mapping from functors to their rank.
 118    ///////////////////////////////////////////////////////////////////////////
 119    arities = new Arity [number_of_functors];
 120    memset(arities, 0, number_of_functors * sizeof(Arity));
 121    for (i = 0; i < n; i++) tabulate_arity(P[i].term);
 122
 123    assert(minimum_variable >= 0);
 124    assert(minimum_functor >= 0);
 125 }
 126
 127 //////////////////////////////////////////////////////////////////////////////
 128 //  Auxiliary method to compute the ranges of non-terminals and functors.
 129 //////////////////////////////////////////////////////////////////////////////
 130 void TreeGrammar::tabulate(const TreeTerm t)
 131 {  match (t) {
 132       case wild_term:   // do nothing
 133       case var_term(v): if (v < minimum_variable) minimum_variable = v;
 134                         if (v > maximum_variable) maximum_variable = v;
 135       case and_term(x,y): tabulate(x); tabulate(y);
 136       case or_term(x,y):  tabulate(x); tabulate(y);
 137       case not_term(n):   tabulate(n);
 138       case tree_term(f,n,subterms):
 139          if (f < minimum_functor) minimum_functor = f;
 140          if (f > maximum_functor) maximum_functor = f;
 141          for (int i = n - 1; i >= 0; i--) tabulate(subterms[i]);
 142       case set_term _:  // do nothing
 143    }
 144 }
 145
 146 //////////////////////////////////////////////////////////////////////////////
 147 //  Auxiliary method to compute the arity of functors.
 148 //////////////////////////////////////////////////////////////////////////////
 149 void TreeGrammar::tabulate_arity(const TreeTerm t)
 150 {  match (t) {
 151       case and_term(x,y): tabulate_arity(x); tabulate_arity(y);
 152       case or_term(x,y):  tabulate_arity(x); tabulate_arity(y);
 153       case not_term(n):   tabulate_arity(n);
 154       case tree_term(f,n,subterms):
 155          arities[f] = n;
 156          for (int i = n - 1; i >= 0; i--)
 157             tabulate_arity(subterms[i]);
 158          if (n > maximum_arity) maximum_arity = n;
 159      case _:          // do nothing
 160    }
 161 }
 162
 163 ///////////////////////////////////////////////////////////////////////////
 164 //  Equality for terms.   Shallow comparison only
 165 ///////////////////////////////////////////////////////////////////////////
 166 Bool equal(const TreeTerm a, const TreeTerm b)
 167 {  match (a) and (b) {
 168       case (wild_term,        wild_term):        return true;
 169       case (var_term u,       var_term v):       return u == v;
 170       case (or_term(a,b),     or_term(c,d)):     return a == c && b == d;
 171       case (and_term(a,b),    and_term(c,d)):    return a == c && b == d;
 172       case (set_term a,       set_term b):       return a == b;
 173       case (tree_term(f,n,s), tree_term(g,m,t)):
 174          if (f != g || n != m) return false;
 175          for (int i = n - 1; i >= 0; i--)
 176             if (s[i] != t[i]) return false;
 177          return true;
 178       case _:                                    return false;
 179    }
 180 }
 181
 182 ///////////////////////////////////////////////////////////////////////////
 183 //  Hash function for terms
 184 ///////////////////////////////////////////////////////////////////////////
 185 unsigned int hash(const TreeTerm a)
 186 {  match (a) {
 187       case wild_term:      return 73;
 188       case var_term v:     return v;
 189       case or_term(x,y):   return 493 + (unsigned int)x + (unsigned int)y;
 190       case and_term(x,y):  return 245 + (unsigned int)x + (unsigned int)y;
 191       case not_term(n):    return 127 + (unsigned int)n;
 192       case tree_term(f,n,subterms):
 193          unsigned int h = f;
 194          for (int i = n - 1; i >= 0; i--) h += h + (unsigned int)subterms[i];
 195          return h;
 196       case set_term s:     return (unsigned int)s;
 197    }
 198 }
 199
 200 ///////////////////////////////////////////////////////////////////////////
 201 //  Printing methods.
 202 ///////////////////////////////////////////////////////////////////////////
 203
 204 const char * TreeGrammar::functor_name(Functor f) const
 205 {  if (functor_names && f >= min_functor() && f <= max_functor())
 206       return functor_names[f];
 207    else
 208       return "F";
 209 }
 210
 211 const char * TreeGrammar::variable_name(Variable v) const
 212 {  if (variable_names && v >= min_variable() && v <= max_variable() &&
 213        variable_names[v] != 0)
 214       return variable_names[v];
 215    else
 216       return "V";
 217 }
 218
 219 ///////////////////////////////////////////////////////////////////////////
 220 //  Method to print a functor name.
 221 ///////////////////////////////////////////////////////////////////////////
 222 std::ostream& TreeGrammar::print_functor(std::ostream& out, Functor f) const
 223 {  if (functor_names && f >= min_functor() && f <= max_functor())
 224       return out << functor_names[f];
 225    else
 226       return out << 'F' << f;
 227 }
 228
 229 ///////////////////////////////////////////////////////////////////////////
 230 //  Method to print a variable name.
 231 ///////////////////////////////////////////////////////////////////////////
 232 std::ostream& TreeGrammar::print_variable(std::ostream& out, Variable v) const
 233 {  if (variable_names && v >= min_variable() && v <= max_variable() &&
 234        variable_names[v] != 0)
 235       return out << '<' << variable_names[v] << '>';
 236    else
 237       return out << v;
 238 }
 239
 240 ///////////////////////////////////////////////////////////////////////////
 241 //  Method to print a tree term.
 242 ///////////////////////////////////////////////////////////////////////////
 243 std::ostream& TreeGrammar::print(std::ostream& S, const TreeTerm term) const
 244 {  match (term) {
 245       case wild_term:     S << '_';
 246       case var_term v:    print_variable(S, v);
 247       case or_term(x,y):  S << '('; print(S,x); S << " or: "; print(S,y); S << ')';
 248       case and_term(x,y): S << '('; print(S,x); S << " and: "; print(S,y); S << ')';
 249       case not_term n:    S << "not: "; print(S,n);
 250       case set_term s:    S << *s;
 251       case tree_term(f,n,subterms):
 252       {  const char * f_name = functor_name(f);
 253          Bool first = true;
 254          TreeTerm t = term;
 255          if (f_name[0] == '#')
 256          {  char begin_ch = f_name[1];
 257             char end_ch   = f_name[strlen(f_name)-1];
 258             S << '#' << begin_ch;
 259             match while (t)
 260             {  tree_term(f,2,subterms):
 261                {  if (! first) S << ", "; print(S,subterms[0]); first = false;
 262                   t = subterms[1];
 263                }
 264             |  tree_term(f,0,subterms) | (functor_name(f))[0] == '#':
 265                {  return S << end_ch; }
 266             |  _:
 267                {  if (! first) S << " ... "; print(S,t); return S << end_ch; }
 268             }
 269          } else if (f_name[0] != '\0' && f_name[1] == '|')
 270          {  S << f_name[0] << "| ";
 271             for (int i = 0; i < n; i++) {
 272                 print(S,subterms[i]); if (i < n - 1) S << ", ";
 273             }
 274             S << ' ' << (f_name + 5);
 275          } else
 276          {  print_functor(S,f);
 277             if (n > 0) {
 278                S << '(';
 279                for (int i = 0; i < n; i++) {
 280                    print(S,subterms[i]); if (i < n - 1) S << ", ";
 281                }
 282                S << ')';
 283             }
 284          }
 285       }
 286    }
 287    return S;
 288 }
 289
 290 ///////////////////////////////////////////////////////////////////////////
 291 //  Method to print a tree production.
 292 ///////////////////////////////////////////////////////////////////////////
 293 std::ostream& TreeGrammar::print(std::ostream& out, const TreeProduction& P) const
 294 {   print_variable(out, P.var);
 295     out << " : ";
 296     print(out, P.term);
 297     return out;
 298 }
 299
 300 ///////////////////////////////////////////////////////////////////////////
 301 //  Method to print a tree grammar.
 302 ///////////////////////////////////////////////////////////////////////////
 303 std::ostream& operator << (std::ostream& out, const TreeGrammar& G)
 304 {   for (int i = 0; i < G.size(); i++) {
 305        out << '[' << i << ']' << '\t';
 306        G.print(out,G[i]) << '\n';
 307     }
 308     return out;
 309 }