lib-src/rewrite/b_rules.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 welcomed 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(read crave for)
  19 // any suggestions and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #define TreeGrammar_Iterators
  26 #include <iostream.h>
  27 #include <string.h>
  28 #include <AD/automata/treegram.ph>
  29 #include <assert.h>
  30 #include <AD/rewrite/b_rules.h>
  31 #include <AD/hash/dchash.h>
  32
  33 //////////////////////////////////////////////////////////////////////////////
  34 //
  35 //  Make hidden types visible for use.
  36 //
  37 //////////////////////////////////////////////////////////////////////////////
  38 typedef TreeGrammar::Functor        Functor;
  39 typedef TreeGrammar::NonTerminal    NonTerminal;
  40 typedef TreeGrammar::Rule           Rule;
  41 typedef TreeGrammar::Cost           Cost;
  42 typedef BURS_RuleSet::LeafReduction LeafReduction;
  43 typedef BURS_RuleSet::Reduction     Reduction;
  44 typedef BURS_RuleSet::ChainRule     ChainRule;
  45
  46 //////////////////////////////////////////////////////////////////////////////
  47 //
  48 //  Hash functions and equality functions for leaf reductions.
  49 //
  50 //////////////////////////////////////////////////////////////////////////////
  51 inline Bool equal (const LeafReduction * a, const LeafReduction * b)
  52 {  return a->f == b->f && a->cost == b->cost && a->rule == b->rule;
  53 }
  54 inline unsigned hash (const LeafReduction * a)
  55 {  return a->f + a->cost + a->rule; }
  56
  57 //////////////////////////////////////////////////////////////////////////////
  58 //
  59 //  Hash functions and equality functions for non-leaf reductions.
  60 //
  61 //////////////////////////////////////////////////////////////////////////////
  62 inline Bool equal (const Reduction * a, const Reduction * b)
  63 {  if (a->f != b->f || a->cost != b->cost ||
  64        a->rule != b->rule || a->n != b->n) return false;
  65    for (int i = a->n - 1; i >= 0; i--)
  66       if (a->rhs[i] != b->rhs[i]) return false;
  67    return true;
  68 }
  69 inline unsigned hash (const Reduction * a)
  70 {  unsigned h = a->f + a->cost + a->rule + a->n;
  71    for (int i = a->n - 1; i >= 0; i--) h += a->rhs[i];
  72    return h;
  73 }
  74
  75 //////////////////////////////////////////////////////////////////////////////
  76 //
  77 //  Hash functions and equality functions for chain reductions.
  78 //
  79 //////////////////////////////////////////////////////////////////////////////
  80 inline Bool equal (const ChainRule * a, const ChainRule * b)
  81 {  return a->rhs == b->rhs && a->cost == b->cost && a->rule == b->rule;
  82 }
  83 inline unsigned hash (const ChainRule * a)
  84 {  return a->rhs + a->cost + a->rule; }
  85
  86 //////////////////////////////////////////////////////////////////////////////
  87 //
  88 // Internal implementation
  89 //
  90 //////////////////////////////////////////////////////////////////////////////
  91 class BURS_RuleSet_Impl {
  92    BURS_RuleSet_Impl(const BURS_RuleSet_Impl&);
  93    void operator = (const BURS_RuleSet_Impl&);
  94 public:
  95    DCHashTable <LeafReduction *, int> leaf_map;
  96    DCHashTable <Reduction *,     int> non_leaf_map;
  97    DCHashTable <ChainRule *,     int> chain_rule_map;
  98    inline  BURS_RuleSet_Impl() {}
  99    inline ~BURS_RuleSet_Impl() {}
 100 };
 101
 102 //////////////////////////////////////////////////////////////////////////////
 103 //
 104 //  Constructor and destructor
 105 //
 106 //////////////////////////////////////////////////////////////////////////////
 107 BURS_RuleSet:: BURS_RuleSet( Mem& mem, const TreeGrammar& g) : G(g)
 108 {
 109     ///////////////////////////////////////////////////////////////////////////
 110     // Create a new set of hash tables.
 111     ///////////////////////////////////////////////////////////////////////////
 112     impl = new BURS_RuleSet_Impl;
 113
 114     ///////////////////////////////////////////////////////////////////////////
 115     //  Count the number of rules of each kind.
 116     ///////////////////////////////////////////////////////////////////////////
 117     leaf_reduction_count = 0;         // e.g.  A -> c
 118     reduction_count      = 0;         // e.g.  A -> f (A_1, A_2, ..., A_n)
 119     chain_rule_count     = G.size();  // e.g.  A -> B
 120     has_wild_card        = false; // assume we don't have wildcard in grammar
 121
 122     {  foreach_production (i, g) count_rules(g[i].term); }
 123
 124     ///////////////////////////////////////////////////////////////////////////
 125     //  Allocate the tables.
 126     ///////////////////////////////////////////////////////////////////////////
 127     leaf_reduction_table  = new LeafReduction [ leaf_reduction_count ];
 128     reduction_table       = new Reduction *   [ reduction_count ];
 129     chain_rule_table      = new ChainRule     [ chain_rule_count ];
 130     int non_term_count = g.max_variable() + 1 + leaf_reduction_count +
 131                             reduction_count + chain_rule_count;
 132     non_term_to_tree      = new TreeTerm [non_term_count];
 133     Bool * var_used = (Bool*)mem.c_alloc(sizeof(Bool) * (g.max_variable()+1));
 134     {  for (int i = 0; i < non_term_count; i++)
 135           non_term_to_tree[i] = wild_term;
 136     }
 137
 138     ///////////////////////////////////////////////////////////////////////////
 139     //  Now normalise the patterns into canonical form.
 140     ///////////////////////////////////////////////////////////////////////////
 141     reduction_count      = 0;
 142     leaf_reduction_count = 0;
 143     chain_rule_count     = 0;
 144     non_terminal_count   = g.max_variable() + 1;
 145
 146     ///////////////////////////////////////////////////////////////////////////
 147     // Compute the reduction rules
 148     ///////////////////////////////////////////////////////////////////////////
 149     {  foreach_production (i, g)
 150        {  NonTerminal v = g[i].var;
 151           NonTerminal rhs = add_reduction(mem, i, g[i].term, g[i].cost);
 152           if (v > 0)
 153           {  chain_rule_table[ chain_rule_count ].rhs   = rhs;
 154              chain_rule_table[ chain_rule_count ].cost  = 0;
 155              chain_rule_table[ chain_rule_count ].rule  = i;
 156              chain_rule_table[ chain_rule_count++ ].lhs = g[i].var;
 157              var_used[v] = true;
 158           }
 159        }
 160     }
 161     ///////////////////////////////////////////////////////////////////////////
 162     //  Compute the chain rules
 163     ///////////////////////////////////////////////////////////////////////////
 164     {  for (NonTerminal v = g.min_variable(); v <= g.max_variable(); v++)
 165        {  if (var_used[v])
 166           {  chain_rule_table[ chain_rule_count ].lhs  = 0;
 167              chain_rule_table[ chain_rule_count ].rhs  = v;
 168              chain_rule_table[ chain_rule_count ].cost = 0;
 169              chain_rule_table[ chain_rule_count ].rule = -1;
 170              chain_rule_count++;
 171           }
 172        }
 173     }
 174
 175     assert(non_terminal_count <= non_term_count);
 176
 177     ///////////////////////////////////////////////////////////////////////////
 178     //  Finally compute the list of non-unit reductions partitioned by
 179     //  the functors.
 180     ///////////////////////////////////////////////////////////////////////////
 181     reductions = new ReductionList * [ g.max_functor() + 1 ];
 182     {  foreach_functor (f,g) reductions[f] = 0; }
 183     {  for (int i = 0; i < reduction_count; i++) {
 184           Functor f = reduction_table[i]->f;
 185           reductions[f] =
 186              new (mem, reduction_table[i], reductions[f]) ReductionList;
 187        }
 188     }
 189
 190     ///////////////////////////////////////////////////////////////////////////
 191     // Clean up
 192     ///////////////////////////////////////////////////////////////////////////
 193     delete impl;
 194 }
 195
 196 //////////////////////////////////////////////////////////////////////////////
 197 //
 198 //  Destructor
 199 //
 200 //////////////////////////////////////////////////////////////////////////////
 201 BURS_RuleSet::~BURS_RuleSet()
 202 {  delete [] reduction_table;
 203    delete [] chain_rule_table;
 204    delete [] leaf_reduction_table;
 205    delete [] reductions;
 206 }
 207
 208 //////////////////////////////////////////////////////////////////////////////
 209 //
 210 // Method to count the number of canonical rules.
 211 //
 212 //////////////////////////////////////////////////////////////////////////////
 213 void BURS_RuleSet::count_rules(TreeTerm t)
 214 {  match (t) {
 215       case wild_term:           has_wild_card = true; chain_rule_count++;
 216       case var_term(v):         chain_rule_count++;
 217       case tree_term(_,0,_):    leaf_reduction_count++;
 218       case tree_term(_,n,subterms):
 219          for (int i = n - 1; i >= 0; i--) count_rules(subterms[i]);
 220          reduction_count++;
 221       case _:    assert("Error in BURS_RuleSet::count_rules");
 222    }
 223 }
 224
 225 //////////////////////////////////////////////////////////////////////////////
 226 //
 227 //  Method to add an reduction rule into the table
 228 //
 229 //////////////////////////////////////////////////////////////////////////////
 230 NonTerminal BURS_RuleSet::add_reduction
 231    (Mem& mem, Rule r, TreeTerm t, Cost cost)
 232 {  match (t) {
 233       case tree_term(F,0,_):
 234          leaf_reduction_table[ leaf_reduction_count ].f    = F;
 235          leaf_reduction_table[ leaf_reduction_count ].cost = cost;
 236          leaf_reduction_table[ leaf_reduction_count ].rule = r;
 237          Ix i = impl->leaf_map.lookup(leaf_reduction_table + leaf_reduction_count);
 238          if (i) {
 239             return impl->leaf_map.key(i)->lhs;
 240          } else {
 241             impl->leaf_map.insert(leaf_reduction_table + leaf_reduction_count,0);
 242             NonTerminal T = non_terminal_count++;
 243             non_term_to_tree[T] = t;
 244             // cerr << "Non-term " << T << " = "; G.print(cerr,t) << '\n';
 245             return leaf_reduction_table[ leaf_reduction_count++ ].lhs = T;
 246          }
 247       case tree_term(F,N,S):
 248          {  Reduction * red = new (mem, N) Reduction;
 249             red->f    = F;
 250             red->n    = N;
 251             red->cost = cost;
 252             red->rule = r;
 253             {  for (int i = 0; i < N; i++) {
 254                   match (S[i]) {
 255                      case wild_term: red->rhs[i] = 0;
 256                      case _: red->rhs[i] = add_reduction(mem, -1, S[i], 0);
 257                   }
 258                }
 259             }
 260             Ix i = impl->non_leaf_map.lookup(red);
 261             if (i) {
 262                return impl->non_leaf_map.key(i)->lhs;
 263             } else {
 264                reduction_table[ reduction_count++ ] = red;
 265                impl->non_leaf_map.insert(red,0);
 266                NonTerminal T = non_terminal_count++;
 267                non_term_to_tree[T] = t;
 268                // cerr << "Non-term " << T << " = "; G.print(cerr,t) << '\n';
 269                return red->lhs = T;
 270             }
 271          }
 272       case wild_term:   return 0;
 273       case var_term(v): return v;
 274       case _:   assert("Error in BURS_RuleSet::add_reduction\n");
 275                 return 0;
 276    }
 277 }
 278
 279
 280 //////////////////////////////////////////////////////////////////////////////
 281 //
 282 //  Printing methods
 283 //
 284 //////////////////////////////////////////////////////////////////////////////
 285
 286 //////////////////////////////////////////////////////////////////////////////
 287 //
 288 // Print a leaf reduction rule
 289 //
 290 //////////////////////////////////////////////////////////////////////////////
 291 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::LeafReduction& r) const
 292 {  G.print_variable(f, r.lhs);
 293    f << "\t -> ";
 294    G.print_functor (f, r.f);
 295    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 296    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 297    return f;
 298 }
 299
 300 //////////////////////////////////////////////////////////////////////////////
 301 //
 302 // Print a reduction rule
 303 //
 304 //////////////////////////////////////////////////////////////////////////////
 305 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::Reduction& r) const
 306 {  G.print_variable(f, r.lhs);
 307    f << "\t -> ";
 308    const char * f_name = G.functor_name(r.f);
 309    if (f_name[0] == '#')
 310    {  char begin_s = f_name[1];
 311       char end_s   = f_name[strlen(f_name)-1];
 312       f << '#' << begin_s;
 313       for (int i = 0; i < r.n; i++) {
 314          print (f, r.rhs[i]);
 315          if (i < r.n - 1) f << " ... ";
 316       }
 317       f << end_s;
 318    } else
 319    {  G.print_functor (f, r.f);
 320       f << '(';
 321       for (int i = 0; i < r.n; i++) {
 322          print (f, r.rhs[i]);
 323          if (i < r.n - 1) f << ',';
 324       }
 325       f << ')';
 326    }
 327    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 328    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 329    return f;
 330 }
 331
 332 //////////////////////////////////////////////////////////////////////////////
 333 //
 334 //  Print a chain rule
 335 //
 336 //////////////////////////////////////////////////////////////////////////////
 337 ostream& BURS_RuleSet::print (ostream& f, const BURS_RuleSet::ChainRule& r) const
 338 {  G.print_variable(f,r.lhs);
 339    f << "\t -> ";
 340    G.print_variable(f,r.rhs);
 341    if (r.cost > 0) f << "\t(cost " << r.cost << ')';
 342    if (r.rule >= 0) f << "\t[rule " << r.rule << ']';
 343    return f;
 344 }
 345
 346 //////////////////////////////////////////////////////////////////////////////
 347 //
 348 //  Print a rule set
 349 //
 350 //////////////////////////////////////////////////////////////////////////////
 351 ostream& operator <<(ostream& f, const BURS_RuleSet& r)
 352 {  int i;
 353    if (r.number_of_leaf_reductions() > 0) f << "Leaf reductions:\n";
 354    for (i = 0; i < r.number_of_leaf_reductions(); i++)
 355       r.print(f,r.leaf(i)) << '\n';
 356    if (r.number_of_reductions() > 0) f << "Non-leaf reductions:\n";
 357    for (i = 0; i < r.number_of_reductions(); i++)
 358       r.print(f,r.reduction(i)) << '\n';
 359    if (r.number_of_chain_rules() > 0) f << "Chain rules:\n";
 360    for (i = 0; i < r.number_of_chain_rules(); i++)
 361       r.print(f,r.chain_rule(i)) << '\n';
 362    return f;
 363 }
 364
 365 //////////////////////////////////////////////////////////////////////////////
 366 //
 367 //  Print a non-terminal
 368 //
 369 //////////////////////////////////////////////////////////////////////////////
 370 ostream& BURS_RuleSet::print (ostream& f, NonTerminal n) const
 371 {  TreeTerm t = non_term_to_tree[n];
 372    if (t != wild_term || n == 0)
 373    {  G.print(f,t);
 374    } else
 375    {  G.print_variable(f,n);
 376    }
 377    return f;
 378 }